2.2.2. Элементарные булевы функции. Представление булевых функций пропозиционными формулами
Помимо таблицы истинности булевы функции можно задавать пропозиционными формулами, т. е. формулами, в которых переменные 
(понимаемые как элементарные высказывания), а также, возможно, числа 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 |
;
;
.
| < Предыдущая | Следующая > |
|---|
