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

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

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

Определение

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

Например, X ^:Y ^Z элементарная конъюнкция

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

Таким образом, X è :X элементарные конъюнкции

Формула X ^Y ^1 элементарной конъюнкцией не является, так как содержит константу 1 (хотя легко приводится к равносильной элементарной конъюнкции)

Формула :(X ^Y ) не является элементарной конъюнкцией, так как отрицание применяется не к переменной

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

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

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

Определение

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

Например, X ^:Y ^Z элементарная конъюнкция

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

Таким образом, X è :X элементарные конъюнкции

Формула X ^Y ^1 элементарной конъюнкцией не является, так как содержит константу 1 (хотя легко приводится к равносильной элементарной конъюнкции)

Формула :(X ^Y ) не является элементарной конъюнкцией, так как отрицание применяется не к переменной

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение

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

(ñîêð. ÄÍÔ),

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

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

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

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

Определение

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

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

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

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

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

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

Определение

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

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

(X ^:Y ) _(Y ^:Z) _(:X ^Z) является ДНФ

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

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

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

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

Определение

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

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

(X ^:Y ) _(Y ^:Z) _(:X ^Z) является ДНФ

X _(:Y ^Z) является ДНФ

(по поводу этой формулы напомним: X является элементарной конъюнкцией)

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