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

Пример 8.4:

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-10-28