43) Алгебра логики. Дизюнктивная нормальная форма.

Алгебра логики— раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть истинными, ложными или содержащими истину и ложь в разных соотношениях.

Дизъюнкти́вная норма́льная фо́рма(ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции нескольких конъюнкций. Булева формула – формула логики высказываний. Например, следующие формулы записаны в ДНФ:;;;

Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем, т.е. для доказательства, реализованного программно.

Любая булева формула может быть приведена к ДНФ. Впрочем, при этом размер булевой формулы может возрасти экспоненциально. Так, например, 2ⁿконъюнктов потребуется, чтобы записать следующую формулу:

Формальная грамматика, описывающая ДНФ: Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:<ДНФ> → <конъюнкт>; <ДНФ> → <ДНФ> ∨<конъюнкт>;<конъюнкт> → <литерал>;<конъюнкт> → (<конъюнкт>∧<литерал>); <литерал> → <терм>;<литерал> → ¬<терм>, где <терм> обозначает произвольную булеву переменную, <литерал> - константу.

44)Алгебра логики. Коньюнкивная нормальная форма

Алгебра логики – раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть истинными, ложными или содержащими истину и ложь в разных соотношениях.

Конъюнктивной нормальной формой (КНФ) формулыАназывается равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.Совершенной конъюнктивной нормальнойформулыА(СКНФА) называется КНФА, удовлетворяющая следующим условиям:

1.      все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные;

2.      все элементарные дизъюнкции, входящие в КНФ А, различны;

3.      каждая элементарная дизъюнкция, входящая в КНФ А, содержит переменную один раз;

4.      ни одна элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

Конъюнктивная нормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций. Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило:выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.