Дизъюнктивная нормальная форма (ДНФ)Формула G имеет дизъюнктивную нормальную форму, если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций. Например, (X Y) ( X Z). Теорема: Для всякой формулы F существует формула G, равносильная F и имеющая ДНФ. Алгоритм приведения к ДНФ 1. Исключить из исходной формулы эквиваленцию () и импликацию (). F G = F G; F G = (F G) (G F) 2. Занести отрицание к атомарным формулам с помощью следующих законов: (F G) = F G; (F G) = F G; F = F 3. Если формула содержит подформулу вида Н 1 (Н 2 Н 3), то заменить на равносильную (Н 1 Н 2) (Н 1 Н 3) по закону дистрибутивности. Нормальные формы в логике высказываний. Алгоритм преобразования формулы в конъюнктивную нормальную форму (КНФ) Литерал – атомарная формула (кроме логических 1 и 0) или ее отрицание. Элементарной дизъюнкцией (дизъюнктом) называется литерал или дизъюнкция литералов.
|