Определение. Алгебра, образованная множеством вместе со всеми возможными операциями на нём, называется алгеброй логики. Определение

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

0 0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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