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

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

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

Конъюнктивные нормальные форма (КНФ)

Определение

Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию логических переменных и их отрицаний

1Элементарная дизъюнкция принимает значение 0 тогда и

только, когда все составляющие ее высказывания принимают значения 0

2Если элементарная дизъюнкция содержит переменную и ее отрицание, то она равна 1 (поскольку X _:X eq 1)

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

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

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

Конъюнктивные нормальные форма (КНФ)

Определение

Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию логических переменных и их отрицаний

1Элементарная дизъюнкция принимает значение 0 тогда и

только, когда все составляющие ее высказывания принимают значения 0

2Если элементарная дизъюнкция содержит переменную и ее отрицание, то она равна 1 (поскольку X _:X eq 1)

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

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

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

Конъюнктивная нормальная форма (КНФ)

Определение

Формула имеет конъюнктивную нормальную форму

(ñîêð. ÊÍÔ),

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

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

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

Конъюнктивная нормальная форма (КНФ)

Определение

Формула имеет конъюнктивную нормальную форму

(сокр. КНФ), если она является конъюнкцией элементарных дизъюнкций

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

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

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

Конъюнктивная нормальная форма (КНФ)

Определение

Формула имеет конъюнктивную нормальную форму

(сокр. КНФ), если она является конъюнкцией элементарных дизъюнкций

Теорема 5.1

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

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

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

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

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

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

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

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

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

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

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

Разница лишь в том, что на шаге 3 нужно использовать закон дистрибутивности 3.

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

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

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

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

Определение

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

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

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

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

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

Определение

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

1Любая элементарная дизъюнкция в G для каждой переменной Xi, i = 1; : : : ; n

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

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

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

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

Определение

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

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

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

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