Условие:
Приведите алгоритм построения нормальных форм: ДНФ, КНФ для
формул логики высказываний.
Решение:
Ниже приводится пошаговый алгоритм получения дизъюнктивной нормальной формы (ДНФ) и конъюнктивной нормальной формы (КНФ) для формул логики высказываний.
-
Первоначальная подготовка формулы. а) Удалите из формулы операторы импликации (→) и эквиваленции (↔) с помощью следующих эквивалентностей: • A → B эквивалентно ¬A ∨ B. • A ↔ B эквивалентно (A ∧ B) ∨ (¬A ∧ ¬B). б) Цель – получить формулу, в которой используются только логические операции ¬ (НЕ), ∧ (И) и ∨ (ИЛИ).
-
Приведение к отрицательной нормальной форме (ННФ). а) Примените законы де Моргана, чтобы перенести отрицания в...