Тема 1.6. Составление формулы по заданной таблице истинности. Пример

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

Выбираем строки, где и выписываем конъюнкции всех переменных, при чем, если переменная в этом наборе равна 1, то записываем ее саму, а если переменная = 0, то ее отрицание.

Для данного примера

коньюнкция этих дизъюнкций и будет искомой формулой:

Определение: Конъюнкция называется элементарной, если все переменные, входящие в нее, различны. Количество букв, входящих в элементарную конъюнкцию или элементарную дизъюнкцию, называется рангом.

Число 1 считается элементарной конъюнкцией ранга 0. Переменная считается элементарной конъюнкцией или элементарной дизъюнкцией ранга 1. Число 0 считается элементарной дизъюнкцией ранга 0. Любую конъюнкцию переменных, не являющуюся тождественно ложной, можно привести к виду элементарной, а любую дизъюнкцию букв, не являющуюся тождественно истинной, также можно привести к виду элементарной. Для этого надо применить свойства коммутативности, идемпотентности и ассоциативности конъюнкции и дизъюнкции.

Строго доказано, что любую формулу булевой алгебры можно выразить с помощью операций , &, . Интуитивно этот факт очевиден, вспомним алгоритм составления формулы по таблице истинности. При этом мы используем только эти операции. Такая форма записи называется дизъюнктивной нормальной формой (ДНФ). Это своеобразный механизм нормализации формул алгебры логики.

Определение: ДНФ – это дизъюнкция различных элементарных конъюнкций (т.е. каждая конъюнкция состоит из элементарных высказываний или их отрицаний).

Аналогично определяется КНФ – коньюктивная нормальная форма.

Определение: Если в ДНФ все элементарные конъюнкции имеют один и тот же ранг, равный числу переменных, от которых зависит ДНФ, то она называется совершенной (СДНФ).

Теорема. Для любой функции, не являющейся тождественно ложной, существует и притом единственная СДНФ.

Следствие. Любую булеву функцию, не являющуюся тождественно ложной можно представить в виде суперпозиции &,,, причем отрицание относится только к переменным.

Определение: Система логических операций называется функционально полной, если с помощью этих операций и констант этой системы можно представить любую функцию булевой алгебры.

Системы {&,,}; {,}; {&,},{/} – являются функционально полными

{&,} – функционально неполная.

Мы примем эти факты без доказательства, и решая задачи, будем стараться любую формулу представить с помощью {&,,}. Позже мы более подробно обсудим вопрос функциональной полноты и неполноты системы операций.