Элементарные булевы функции. Представление булевых функций пропозиционными формулами.
Помимо таблицы истинности булевы функции можно задавать пропозиционными
формулами, т.е. формулами, в которых переменные 
(понимаемые как элементарные высказывания), а
также, возможно, числа 1 и 0 ("истина", "ложь") связаны
логическими операциями. При этом могут использоваться также скобки для указания
порядка выполнения операций.
Булевы функции, соответствующие отдельным логическим операциям, называют элементарными. Перечислим некоторые из них:
1. 
(нуль – функция);
2. 
(один функция);
3. 
(отрицание 
; 
означает ù
x);
4. 
(конъюнкция или произведение; 
);
5. 
(дизъюнкция);
6. 
(импликация);
7. 
(эквиваленция);
8. 
(сумма по модулю 2; таблица истинности этой функции приведена
в 1.).
С помощью операции композиции функций из элементарных функций
можно получать другие более сложные булевы функции. Заметим, в частности,
что и сами элементарные функции представляются через другие элементарные.
Например, 
, т. е. 
.
Теорема 2. Всякая булева функция является композицией элементарных функций: отрицания, конъюнкции и дизъюнкции.
Доказательство. Действительно, нуль–функция представляется
следующим образом: 
. Поэтому
пусть далее функция 
не тождественно равна 0. Рассмотрим ее область истинности:
все такие наборы 
, что 
. Для каждого такого набора построим конъюнкцию 
,
где 
, а 
. Соединим все полученные конъюнкции знаком дизъюнкции,
т. е. рассмотрим : 
(*)
Поскольку 
только, если 
(проверьте), то и 
только тогда, когда 
. Таким образом, полученная формула (*) принимает значение
1 в точности на тех наборах значений переменных, что и функция . Значит,
,
что и требовалось доказать.
Замечание. Из теоремы следует, что всякая булева функция
представляется с помощью некоторой пропозиционной формулы, например в форме
(*), которая называется совершенной дизъюнктивной нормальной формой (СДНФ)
функции 
. Конъюнкция нескольких
переменных (возможно с отрицаниями) называется элементарной конъюнкцией. Дизъюнкция
нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой
(ДНФ).
На следующем примере по таблице истинности получены представления
в виде СДНФ элементарных функций: 
, 
и 
.
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
0 |
;
;
.