Цель: изучить булевские (“логические”) операции на примере вычисления индикаторов множеств на плоскости, соответствие булевских и теоретико-множественных операций.
Критерии полноты
Скобка Айверсона — обозначение с помощью заключения логического утверждения в квадратные скобки численного значения этого утверждения (0 для лжи, 1 для истины). Например, sgn(x) = [x > 0] – [x < 0].
Индикатор множества S или характеристическая функция множества S — это функция вида 1S: X → B, где X — некое надмножество множества S (т. е. S ⊆ X), а B = {0, 1}, такая, что 1S(x) = [x ∈ S].
Индикатор обладает рядом интересных свойств. Пусть A ⊆ X и B ⊆ X, тогда следующие утверждения верны для любого x ∈ X.
В C++ встроен тип bool, множество значений которого состоит из логических констант true (“истина”, численно равна 1) и false (“ложь”, численно равна 0). Пример реализации булевской функции “и-не”:
bool nand(bool a, bool b)
{
return !(a && b); // не (a и b)
}
| Отношение | C++ |
|---|---|
| = “равно” | == |
| ≠ | != |
| < | < |
| > | > |
| ≤ | <= |
| ≥ | >= |
| Множества | Логика | Логика — C++ |
|---|---|---|
| пространство | 1 | true |
| ∅ | 0 | false |
| дополнение | ¬ | ! |
| ∩ | ∧ | && |
| ∪ | ∨ | || |
| \ | ∧¬ | &&! |
| ∆ | ⊕ | != |
| ⊂ | < | < |
| ⊆ | ≤, → | <= |
Проверка на равенство логических величин совпадает с операцией “эквиваленция”, на неравенство — с операцией “исключающее или”. В C++ нет таких встроенных логических операций, поэтому может использоваться простое сравнение на равенство == или неравенство != при соблюдении важного условия: их операнды должны быть результатами вычисления логических выражений либо логическими константами true и false.
Сравнения вида что-то == true и что-то == false избыточны.
Почему условие выше названо важным? Дело в том, что bool — фактически целочисленный тип с размером представления не меньше одного байта (а может и больше), в то время как для значений 0 и 1 достаточно одного бита. Допускается приведение к bool целочисленных значений, при этом ноль трактуется как ложь, а все прочие значения как истина. Но переданное в булевскую функцию число может и дальше неявно интерпретироваться как число (особенно, если включены оптимизации, применяемые компилятором).
bool bad_xor(bool a, bool b)
{
return a != b; // хм?
}
int main()
{
cout << bad_xor(1, 2); // может быть как 1, так и 0
cout << bad_xor(true, true); // обязательно 0
}Для исправления ситуации удобно использовать оператор отрицания, для которого гарантируется, что его результат равен либо 0, либо 1. Та же гарантия предоставляется для всех встроенных операторов, возвращающих булевское значение (“и”, “или”, сравнения).
bool logic_xor(bool a, bool b)
{
// Выглядит странно, но работает правильно.
return !a != !b;
}Данная формула короче логических аналогов (a && !b) || (!a && b) и (a || b) && !(a && b).
У изучающих язык C нередко возникает вопрос, почему в нём нет логического оператора xor ^^ в то время как есть поразрядный оператор ^. Короткий ответ: потому что он не может быть вычислен по “короткой схеме” как “и” и “или”. См. также развёрнутый ответ Д.Ричи.
Уравнение прямой на плоскости имеет вид ax + by + c = 0, где (x, y) ∈ ℝ2 – координаты некоторой точки на плоскости, (a, b, c) ∈ (ℝ2 \ 0) × ℝ — коэффициенты уравнения. Если интерпретировать запись уравнения как логическое выражение, вычисляющее [ax + by + c = 0], то получим определение индикатора прямой.
Неравенство полуплоскости легко получить из уравнения прямой, заменив знак равенства на тот или иной знак неравенства. Если точки прямой, ограничивающей полуплоскость, включаются в полуплоскость, то неравенство нестрогое, в противном случае — строгое. Неравенство полуплоскости позволяет легко задать индикатор полуплоскости.
Упражнение. Попробуйте изобразить четыре полуплоскости, заданные неравенствами:
Фигура на изображении является пересечением полуплоскости (x ≥ –4) и объединения следующих фигур:
Удобно определить отдельные функции-индикаторы для множеств “круг с заданными радиусом и координатами центра” и “прямоугольник со сторонами, параллельными осям координат, и заданными координатами углов”.
// Проверить попадание в круг.
bool in_circle(float x, float y, // координаты точки
float cx, float cy, float r) // координаты центра круга и его радиус
{
// Константы -- после инициализации значения не изменяются.
const float dx = x - cx,
dy = y - cy;
return dx * dx + dy * dy <= r * r;
}
// Проверить попадание в прямоугольник.
bool in_rectangle(float x, float y,
float left, float right, float bottom, float top)
// координаты левой, правой, нижней и верхней граней
{
return left <= x && x <= right // && -- "и"
&& bottom <= y && y <= top;
}Теперь не составит труда написать индикаторную функцию заданной фигуры.
// Проверить попадание в заданную фигуру.
bool in_figure(float x, float y)
{
// фигура может быть представлена как пересечение полуплоскости и
// объединения трёх фигур: двух прямоугольников и сегмента круга
return (in_rectangle(x, y, 2.0, 4.0, -5.0, 5.0)
|| in_rectangle(x, y, -4.0, -2.0, -5.0, 5.0) // || -- "или"
|| in_circle(x, y, -2.0, 0.0, 5.0)) && x >= -4.0;
}Функция main итоговой программы, удовлетворяющей критериям полноты, выглядит следующим образом:
int main()
{
cout << "Enter a sequence of coordinates x, y: ";
// Цикл ввода пар значений x, y до первой ошибки ввода.
for (double x = 0, y = 0; cin >> x >> y;)
{
cout << "(x, y) within the figure == " << in_figure(x, y) << endl;
}
return 0;
}Для выполнения данного задания можно взять исходный код примера и заменить в нём функцию-индикатор фигуры-примера на свою функцию-индикатор.
Этот же пример с визуализацией функции-индикатора с помощью OpenGL/GLSL.
Кувшинов Д.Р. © 2015