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

© 2011-2024 Контрольные работы по математике и другим предметам!