Алгоритм приведения к СДНФ1-3 шаги взяты из ДНФ. 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) по закону дистрибутивности. 4. Если элементарная конъюнкция С не содержит атомарной формулы X i, ни ее отрицания для некоторого i =1.. n, то заменим С на две элементарные конъюнкции (C Xi) (C Xi) 5. Если элементарная конъюнкция С содержит два вхождения одного литерала, то один из них вычеркиваем. Если С содержит X i и X i для некоторого i =1,.., n то вычеркиваем всю элементарную конъюнкцию. 6. Если формула содержитодинаковые элементарные конъюнкции, то вычеркиваем одну из них. Пример: F = (X↔Y) X 1-3 шаг: F 3=(X Y Шаг 5: F 4=(X Y) - СДНФ относительно X и Y
|