Элементарные булевы функции. Равносильности

Булевых (или логических) функций от одной переменной . Они приведены в следующей таблице:

	0		отрицание	1
0	0	0	1	1
1	0	1	0	1

Основные элементарные булевы функции от двух переменных приведены в следующей таблице:

		конъюнк- ция	дизъюнк- ция	имплика- ция	эквивален-тность	сложение по модулю два	стрелка Пирса	штрих Шеффера
0	0	0	0	1	1	0	1	1
0	1	0	1	1	0	1	0	1
1	0	0	1	0	0	1	0	1
1	1	1	1	1	1	0	0	0

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

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

Кроме таблицы истинности, булевы функции могут быть заданы аналитически с помощью формул. Например, .

Если формула a реализует булеву функцию F, которая тождественно равна единице, то она называется тождественно истинной. Если формула a реализует булеву функцию F, которая тождественно равна нулю, то она называется тождественно ложной.

Если формулы a и b зависят от одних и тех же переменных и реализуют одну и ту же булеву функцию F, то формулы a и b называются равносильными.