Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Совершенные конъюнктивные нормальные формы

Определение

ÊÍÔ G(X1; : : : ; Xn) называется совершенной конъюнктивной нормальной формой (сокращенно СКНФ), если выполняются следующие условия:

1Любая элементарная дизъюнкция в G для каждой

переменной Xi, i = 1; : : : ; n содержит либо Xi, ëèáî åå отрицание :Xi.

2Формула G не содержит одинаковых элементарных дизъюнкций (с точностью до перестановки сомножителей)

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Приведение формулы к СКНФ

Определение

Формула F(X1; : : : ; Xn) называется тождественно-истинной,

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Приведение формулы к СКНФ

Определение

Формула F(X1; : : : ; Xn) называется тождественно-истинной, если она принимает значение 1 на каждом наборе переменных

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Приведение формулы к СКНФ

Определение

Формула F(X1; : : : ; Xn) называется тождественно-истинной, если она принимает значение 1 на каждом наборе переменных

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Приведение формулы к СКНФ

Определение

Формула F(X1; : : : ; Xn) называется тождественно-истинной, если она принимает значение 1 на каждом наборе переменных

Замечание 4

Любая элементарная дизъюнкция, которая содержит вместе с переменной Xi ее отрицание :Xi не является тождественно-истинной.

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Приведение формулы к СКНФ

Теорема 5.2

Любая формула, не являющаяся тождественно-истинной может быть приведена к совершенной дизъюнктивной нормальной форме.

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Приведение формулы к СКНФ

Теорема 5.2

Любая формула, не являющаяся тождественно-истинной может быть приведена к совершенной дизъюнктивной нормальной форме.

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к CКНФ

Алгоритм вполне аналогичен алгоритму приведения к СДНФ

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к CКНФ

Алгоритм вполне аналогичен алгоритму приведения к СДНФ Различия в шаге 5.

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к CКНФ

Алгоритм вполне аналогичен алгоритму приведения к СДНФ Различия в шаге 5.

Если дизъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj,

Нормальные формы в логике высказываний