Алгоритм приведения к СДНФ
1-3 шаги взяты из ДНФ. 1. Исключить из исходной функции эквиваленцию ( F 2. Занести отрицание к атомам формул с помощью следующих законов: · · F = F – закон двойного отрицания. 3. Если формула содержит подформулу вида Н 1 4. Если элементарная конъюнкция С не содержит атомарной формулы X i, ни ее отрицания для некоторого i =1.. n, то заменим С на две элементарные конъюнкции (C 5. Если элементарная конъюнкция С содержит два вхождения одного литерала, то один из них вычеркиваем. Если С содержит X i и X i для некоторого i =1,.., n то вычеркиваем всю элементарную конъюнкцию. 6. Если формула содержитодинаковые элементарные конъюнкции, то вычеркиваем одну из них. Пример: F = (X↔Y) 1-3 шаг: F 3=(X Шаг 5: F 4=(X
|
) и импликацию (
).
F 
G; F 
(G 
G; 
G - закон де Моргана;
