Примеры логических функций.

Логических функций одной переменной четыре; они приведены в таблице 2.

Таблица 2.

Здесь функции и - константы 0 и 1 соответственно, значения которых не зависят от значения переменной, и, следовательно, переменная для них несущественна. Значения функции совпадают со значениями переменной . Наконец, функция , значения которой противоположны значениям переменной, есть ни что иное, как отрицание (функция НЕ). Различные способы обозначения этой функции: .

Логических функций двух переменных – шестнадцать; они приведены в таблице 3.

Таблица 3.

Функции и , как и в предыдущем случае являются константами, то есть функциями с двумя несущественными переменными. Отметим, что формально эти функции отличаются от функций и из предыдущего примера, поскольку являются бинарными операциями на множестве . Однако ранее было принято функции, отличающиеся только несущественными переменными, считать равными.

Среди представленных в таблице 3 функций отметим те, которые уже знакомы нам в качестве логических операций, изученных в ходе предыдущей лекции.

Функция является конъюнкцией переменных и (функцией И). Она равна 1 тогда и только тогда, когда обе переменные равны 1. Обозначается: , . Её также называют логическим умножением, поскольку таблица её действительно совпадает с таблицей обычного умножения для чисел 0 и 1. Поэтому, кстати, по аналогии с обычным умножением, знак операции между переменными часто опускают: .

Операцию будем называть умножением по модулю 2 (см. ниже). Она реализует произведение остатков от деления чисел 0 и 1 на число 2.

Функция называется дизъюнкцией переменных и (функцией ИЛИ). Она равна 1, если значения или равны 1. Союз “или” понимается здесь в неразделительном смысле “хотя бы один из двух”. Обозначается: .

Функция называется неравнозначностью переменных и . Она равна 1, когда значения аргументов различны, и равна 0, когда значения аргументов одинаковы. Обозначается: .

Привести пример такой функции более сложно. Для этого введём следующее понятие, широко используемое в теории чисел.

Два целых числа и называются сравнимыми по модулю , если при делении на это число они дают одинаковые остатки.

Обозначается: . Например, , . Так вот, функцию можно рассматривать, как сложение по модулю 2. Действительно, сумма остатков от деления чисел 0 и 1 на число 2 равна 1, а сумма остатков от деления чисел 0 и 0, либо 1 и 1 на 2 равна 0.

Функция называется импликацией или логическим следованием. Обозначается: .

Функция называется эквивалентностью или равнозначностью. Она равна 1, если значения переменных одинаковы и 0, если они различны. Обозначается: .

Есть ещё две функции двух переменных, имеющие специальные названия. Функция называется стрелкой Пирса и обозначается . Функция называется штрихом Шеффера и обозначается . Остальные функции специальных названий не имеют и, как можно показать, легко выражаются через перечисленные выше функции.

В функциях и переменная фиктивна. Из таблицы 3 видно, что , а . Аналогично, в функциях и переменная фиктивна: , а .

Доказано, что с ростом числа переменных доля функций, имеющих фиктивные переменные, убывает и стремится к нулю.