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

формула может быть записана различным образом. Например, функция F(A,B) может быть записана следующими эквивалентными выражениями:

Эквивалентность этих формул легко проверить по таблицам истинности или выполнив необходимые преобразования.

таблицу истинности достаточно сложно, так как приходится перебирать большое количество вариантов. В таких случаях формулы удобно привести к нормальной форме.
Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного отрицания, при этом знаки отрицания находятся только при логических переменных.
В алгебре высказываний используют две нормальные формы: дизъюнктивную (ДНФ) и конъюнктивную нормальные формы (КНФ).

≡ A.

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

ДНФ

Определение. Высказывательная форма, состоящая из переменных или отрицаний переменных, с применением только одной операции конъюнкции, называется элементарной конъюнкцией (или конъюнктом).
Например,

≡ А

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

КНФ

Определение. Высказывательная форма, состоящая из переменных или отрицания переменных, с применением только одной операции дизъюнкции, называется элементарной дизъюнкцией (или дизъюнктом).
Например,

логики и правила логических преобразований по следующему алгоритму:
Устранить «↔» и «→».
Применив законы де Моргана отнести отрицания к переменным.
Избавиться от двойных отрицаний.
Применив закон дистрибутивности, добиться того, чтобы все конъюнкции встречались раньше дизъюнкций.

логики и правила логических преобразований по следующему алгоритму:
Устранить «↔» и «→».
Применив законы де Моргана отнести отрицания к переменным.
Избавиться от двойных отрицаний.
Применив закон дистрибутивности, добиться того, чтобы все дизъюнкции встречались раньше конъюнкций.