Нормальные формы в логике высказываний
.pdf
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Совершенные дизъюнктивные нормальные формы
Определение
ÄÍÔ G(X1; : : : ; Xn) называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ), если выполняются следующие условия:
1Любая элементарная конъюнкция в G для каждой
переменной Xi, i = 1; : : : ; n содержит либо Xi, ëèáî åå отрицание :Xi.
2Формула G не содержит одинаковых элементарных конъюнкций (с точностью до перестановки сомножителей)
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Совершенные дизъюнктивные нормальные формы
Определение
ÄÍÔ G(X1; : : : ; Xn) называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ), если выполняются следующие условия:
1Любая элементарная конъюнкция в G для каждой
переменной Xi, i = 1; : : : ; n содержит либо Xi, ëèáî åå отрицание :Xi.
2Формула G не содержит одинаковых элементарных конъюнкций (с точностью до перестановки сомножителей)
(X ^:Y ) _(X ^Y ) _(:X ^:Y ) |
является СДНФ |
X является СДНФ 
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Совершенные дизъюнктивные нормальные формы
Определение
ÄÍÔ G(X1; : : : ; Xn) называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ), если выполняются следующие условия:
1Любая элементарная конъюнкция в G для каждой
переменной Xi, i = 1; : : : ; n содержит либо Xi, ëèáî åå отрицание :Xi.
2Формула G не содержит одинаковых элементарных конъюнкций (с точностью до перестановки сомножителей)
(X ^:Y ) _(X ^Y ) _(:X ^:Y ) |
является СДНФ |
X является СДНФ 
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
1 :(X ^Y )
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
1 :(X ^Y ) (ýòî äàæå íå ÄÍÔ)
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
1 :(X ^Y ) (ýòî äàæå íå ÄÍÔ)
2 (X ^Y ^Z) _(:X ^Z)
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
1 :(X ^Y ) (ýòî äàæå íå ÄÍÔ)
2(X ^Y ^Z) _(:X ^Z)
(вторая конъюнкция не содержит ни Y íè :Y )
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
1 :(X ^Y ) (ýòî äàæå íå ÄÍÔ)
2(X ^Y ^Z) _(:X ^Z)
(вторая конъюнкция не содержит ни Y íè :Y )
3 (X ^Y ) _(:X ^Y ) _(Y ^X)
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Примеры не СДНФ
СДНФ не являются
1 :(X ^Y ) (ýòî äàæå íå ÄÍÔ)
2(X ^Y ^Z) _(:X ^Z)
(вторая конъюнкция не содержит ни Y íè :Y )
3(X ^Y ) _(:X ^Y ) _(Y ^X)
(содержит две одинаковые элементарные конъюнкции)
Нормальные формы в логике высказываний