4) Нормальные формы.
Элементарной дизъюнкцией(конъюнкцией) назовем дизъюнкцию(конъюнкцию) переменных и их отрицаний.
ДНФ. Дизъюнктивной нормальной формой данной логической формулы назовем равносильную ей дизъюнкцию элементарных конъюнкций.
КНФ. Конъюнктивной нормальной формой данной логической формулы назовем равносильную ей конъюнкцию элементарных дизъюнкций.
В любой логической формуле существуют КНФ и ДНФ.
Теорему докажем предъявлением алгоритма приведения формулы к нормальному виду:
Освободиться от импликации и эквиваленции
Пользуясь законами де Моргана, перейти к формуле с тесными отрицаниями
Пользуясь дистрибутивными законами, сделать дизъюнкцию (конъюнкцию для КНФ) внешней операцией
5)Алгоритмы построения днф и кнф.
Порядок приведения к нормальному виду. 1)Перейти к булевым операциям2) Опустим отрицание на простые высказывания, снимем двойное отрицание. 3)раскрыть скобки. 4) Повторяющиеся выражения взять по 1 разу 5)Применим дистрибутивные законы и формулы поглащения.
6)Сднф и скнф.
Элементарную конъюнкцию назовем правильной если она содержит каждую переменную ровно 1 раз включая ее вхождение под знаком отрицания.
Элементарную конъюнкцию назовем полной для данной формулы если она содержит все входящие формулы переменной.
СДНФ. Совершенной дизъюнктивной нормальной формой для данной формулы называется такая ее ДНФ у которой все элементарные конъюнкции правильные и полные, так же она не содержит элементарных конъюнкций.
СКНФ. Совершенной конъюнктивной нормальной формой для данной формулы называется такая ее КНФ у которой все элементарные дизъюнкции правильные и полные, так же она не содержит элементарных дизъюнкций.
Алгоритм приведения
1)Перейти к булевым операциям2) Опустим отрицание на простые высказывания, снимем двойное отрицание. 3)раскрыть скобки. 4) Повторяющиеся слагаемые взять по 1 разу 5)Опустить тождественно ложные слагаемые 6) пополнить оставшиеся слагаемые недостающими переменными 7) повторить пункт 4
7)Основные проблемы алгебры высказываний.
В алгебре высказываний выделяют 3 основные проблемы: разрешения, равносильности, представимости.
Разрешения.
Существует ли алгоритм, позволяющий с помощью равносильных преобразований для произвольной формулы алгебры высказываний выяснить, является ли она тождественно истинной, тождественно ложной или нетривиально выполнимой?
Равносильности
Существует ли алгоритм, позволяющий с помощью равносильных преобразований для произвольных формул выяснить, равносильны ли они?
Представления
Можно
ли двузначную 0-1 функцию n
двузначных переменных f(x1,x2…xn)
реализовать формулой алгебры высказываний
F(x1,x2…xn)
так что f(x1,x2..xn)=
(x1,x2….xn)
Ответ положителен. Причем для двух последних проблем его можно получить, применяя теорию СДНФ - СКНФ, что касается первой проблемы, для неё проще обойтись ДНФ и КНФ.
2. Теорема (Критерий тождественной истинности формул). Для того, чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы в равносильной ей КНФ были тождественно истинны все элементарные дизъюнкции.
Теорема (Критерий тождественной истинности элементарной дизъюнкции). Для того, чтобы элементарная дизъюнкция была тождественно истинна, необходимо и достаточно, чтобы в ней существовала хотя бы для одной переменной пара-переменная и её отрицание.
3. Теорема (Критерий тождественной ложности формул). Для того, чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы в равносильной ей ДНФ все ЭК были тождественно ложны.
Теорема (Критерий тождественной ложности ЭК). Для того, чтобы ЭК была тождественно ложно