Логика. Радько О.Ю. - 32 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Среди всех этих ДНФ есть одна, которая отличаете однородностью и «совершенством» своей формы. Mы
имеем в виду формулу .BCACABABC ∨∨ Она так и называется: «совершенная дизъюнктивно-нормальная
форма» (СДНФ).
Дадим точное определение:
СДНФ – это такая ДНФ, которая удовлетворяет следующим условиям:
1. Все элементарные конъюнкции различны.
2. Нет нулевых конъюнкций.
3. Ни одна из элементарных конъюнкций не содержит одинаковых членов.
4. Каждая элементарная конъюнкция содержит все переменные.
Чтобы получить СДНФ, надо сначала найти минимальную ДНФ. Тогда будут выполнены условия 1, 2, 3.
Посли этого надо преобразовать эту минимальную ДНФ таким образом, чтобы было выполнено условие 4. Это
делается следующим образом:
.
)()(1*1*
BCACBACBACABABC
BCAAACBCCABBCACBABBCACBAB
∨∨∨∨=
=∨∨∨∨=∨∨=∨∨
Приведение формул алгебры высказываний к КНФ виду.
Элементарной дизъюнкцией называется дизъюнкция, состоящая только из переменных или их отрица-
ний. Например: DCBA ∨∨∨ .
Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Напри-
мер:
))()()(( CBCACCBABAA ∨∨∨∨∨∨∨
. Если воспользоваться равносильностью
A
A
A
=∨
, то
B
A
A
∨∨
можно заменить через
B
A
∨
. Кроме того, известно, что, 1=∨ CC . А если один член дизъюнкции равен 1, то и
вся дизъюнкция равна 1. Значит 1=∨∨∨ CCBA . Но
A
A
=
1* . Значит единичный член конъюнкции можно
просто опустить. Таким образом, первоначальная КНФ сводится к более простой форме:
))()(( CBCABA ∨∨∨
.
Но эта формула не является ещё минимальной. Для КНФ тоже существуют правила поглощения, основан-
ные на соображениях симметрии. Эти правила можно получить по закону двойственности из аналогичных пра-
вил, установленных для ДНФ.
Мы знаем, например, что CBCACBCABA ∨=∨∨ (симметрия нарушена по переменной С. Поглоти-
лось выражение, не содержащее эту переменную). Запишем теперь двойственную равносильность:
))(())()(( CBCACBCABA ∨∨=∨∨∨
. В левой части стоит ранее полученная КНФ. Значит эту КНФ действи-
тельно можно свести к более простой форме.
В то же время мы установили новое правило поглощения:
Если КНФ зависит от трёх переменных и представляет собой конъюнкцию трёх элементарных
дизъюнкций и если симметрия нарушена только по одной из переменных, то поглощается та элементар-
ная дизъюнкция, которая эту переменную не содержит.
Аналогичным образом можно получить и второе правило поглощения, основанное на соображениях сим-
метрии. Мы уже знаем, что CBAACCBBA ∨=∨∨ .
Запишем двойственную равносильность:
=∨∨∨ ))()(( CBCABA
))(( CBCA ∨∨=
.
Сформулируем соответствующее правило поглощения:
Если КНФ зависит от трёх переменных и представляет собой конъюнкцию трёх элементарных
дизъюнкций и если симметрия нарушена по двум из этих переменных, то данная КНФ равносильна
конъюнкции, одним из членов которой является переменная, по которой симметрия не нарушена, а вто-
рым членом является тот член первоначальной КНФ, который эту переменную не содержит.
Чтобы найти минимальную КНФ, равносильную данной формуле, надо эту формулу сначала при-
вести к виду ДНФ, затем надо разложить её на «множители» и применить законы поглощения.
Рассмотрим конкретный пример.
.))(())()((
))()()((
)())((
CBBACBCABA
CBBBCABACBABACCBAB
CBACCBABCBACCBBA
∨∨=∨∨∨=
=∨∨∨∨=∨=∨∨=
=∨∨∨=∨∨∨∨∨
Можно поступить и по-другому. Новый подход начнётся с того момента, когда была получена формула
ACCBAB ∨∨
. В этой формуле симметрия нарушена только по одной переменной B. Мы применяли соответ-
ствующий закон поглощения. А сейчас мы этого делать не будем. Вместо этого мы добавим к нашей формуле
нулевую конъюнкцию, составленную из той переменной, по которой была нарушена симметрия, т.е. добавим
B
B
и произведём группировку:
))(()()( CBBACBBCBABBACCBAB ∨∨=∨∨∨=∨∨∨
.

Страницы