Различные формы представления высказываний
Литерой называется элемент высказывания x или её отрицание.
Элементарной дизъюнкцией называется выражение следующего вида:
, (2.2)
где
литера.
Элементарной конъюнкцией называется выражение следующего вида:
, (2.3)
Дизъюнктивной нормальной формой (ДНФ) формулы называется выражение вида:
, (2.4)
где
элементарная конъюнкция.
Конъюнктивной нормальной формой (КНФ) формулы называется выражение вида:
, (2.5)
где
элементарная дизъюнкция.
Любую формулу можно представить в виде ДНФ или КНФ.
ПРИМЕР
Пусть дана формула
Требуется получить ДНФ и КНФ данной формулы.
Применяя формулы равносильности, получаем КНФ :
Применяя формулы равносильности, получаем ДНФ :
Совершенной дизъюнктивной нормальной формой (СДНФ) формулы называется такая ДНФ, для которой выполняются следующие условия:
Все элементарные конъюнкции, входящие в ДНФ , различны.
Все элементарные конъюнкции, входящие в ДНФ , содержат литеры, соответствующие всем переменным.
Каждая элементарная конъюнкция, входящая в ДНФ , не содержит двух одинаковых литер.
Каждая элементарная конъюнкция, входящая в ДНФ , не содержит переменную и ее отрицание.
СДНФ можно получить двумя способами:
по таблице истинности;
с помощью равносильных преобразований.
Первый способ получения СДНФ рассмотрен выше. Рассмотрим второй способ, который состоит в следующем:
С помощью равносильных преобразований формулы получают ДНФ . При этом в полученной ДНФ возможны следующие ситуации:
Элементарная конъюнкция ДНФ не содержит переменную
,
тогда используются следующие равносильные
преобразования:
Если в ДНФ входят две одинаковые элементарные конъюнкции, то используя следующее равносильное преобразование:
,
одну элементарную конъюнкцию можно отбросить.
Если элементарная конъюнкция ДНФ содержит одновременно переменную и ее отрицание, то используя следующие равносильные преобразования:
,
эту элементарную конъюнкцию можно отбросить
Если элементарная конъюнкция ДНФ содержит дважды переменную , то используя следующее равносильное преобразование:
,
одну переменную можно отбросить
СДНФ формулы существует в единственном виде.
ПРИМЕР
Получить
СДНФ формулы
С помощью равносильных преобразований получаем СДНФ :
С помощью таблицы истинности получаем СДНФ :
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
СДНФ
Очевидно, что в результат двух способов совпадает.
Совершенной конъюнктивной нормальной формой (СКНФ) формулы называется такая КНФ, для которой выполняются следующие условия:
Все элементарные дизъюнкции, входящие в КНФ , различны.
Все элементарные дизъюнкции, входящие в КНФ , содержат литеры, соответствующие всем переменным.
Каждая элементарная дизъюнкция, входящая в КНФ , не содержит двух одинаковых литер.
Каждая элементарная дизъюнкция, входящая в КНФ , не содержит переменную и ее отрицание.
СКНФ можно получить двумя способами:
по таблице истинности;
с помощью равносильных преобразований.
По
первому способу по таблице истинности
получаем СДНФ
,
а СКНФ
можно получить, следуя следующему
правилу
С помощью равносильных преобразований формулы получают КНФ . При этом в полученной КНФ возможны следующие ситуации:
Элементарная дизъюнкция КНФ не содержит переменную , тогда используются следующие равносильные преобразования:
Если в КНФ входят две одинаковые элементарные дизъюнкции, то используя следующее равносильное преобразование:
,
одну элементарную дизъюнкцию можно отбросить.
Если элементарная дизъюнкция КНФ содержит одновременно переменную и ее отрицание, то используя следующие равносильные преобразования:
,
эту элементарную дизъюнкцию можно отбросить.
Если элементарная дизъюнкция КНФ содержит дважды переменную , то используя следующее равносильное преобразование:
,
одну переменную можно отбросить.
СКНФ формулы существует в единственном виде.
ПРИМЕР
Получить СКНФ формулы
С помощью равносильных преобразований получаем СКНФ :
С помощью таблицы истинности получаем СДНФ :
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
СДНФ
Очевидно, что в результат двух способов совпадает.
СДНФ формулы можно получить из СКНФ , используя следующее правило:
