Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Б) сопоставить полученную КНФ с перечисленными признаками СвКНФ;
|
|
в) если в како-либо конъюнкте отсутствует переменная (формула), наличествующая в исходной формуле, то следует дизънктивно присоединить к данному конъюнкту противоречие (Х & Ø Х), а затем применить закон дистрибутивности дизъюнкции относительно конъюнкции.
С помощью СвКНФ решают задачу нахождения всех логических следствий данных формул.
Приведем примеры.
1) Имеем формулы Ø В и А É В. Найдем все логические следствия этих формул.
Прежде всего, конъюнктивно объединим данные формулы:
Ø B & (A É B).
Приведем полученную формулу к ее СвКНФ. Сначала получим ее КНФ:
Ø B & (A É B)
Ø B & (Ø A Ú B).
Сопоставим теперь полученную КНФ с признаками СвКНФ. Оказывается, в первом конъюнкте отсутсвует формула А, наличествующая в исходной формуле. Присоединим дизъюнктивно к первому конъюнкту противоречие (А & Ø A) и применим закон дистрибутивности дизъюнкции относительно конъюнкции:
(Ø B Ú (A & Ø A)) & (Ø A Ú B)
(Ø B Ú A) & (Ø B Ú Ø A) & (Ø A Ú B).
Таким образом, мы получили СвКНФ, которая позволяет обозреть все логические следствия исходных формул. Такими следствиями являются:
1. (Ø B Ú А);
2. (Ø В Ú Ø А);
3. (Ø А Ú В);
4. (Ø В Ú А) & (Ø B Ú Ø A);
5. (Ø B Ú A) & (Ø A Ú B);
6. (Ø B Ú Ø A) & (Ø A Ú B);
7. (Ø B Ú A) & (Ø B Ú Ø A) & (Ø A Ú B).
2) Возьмем теперь формулы В Ú С, В É Ø А, В É С и найдем их логические следствия:
1. (B Ú C) & (B É Ø A) & (B É C)
2. (B Ú C) & (Ø B Ú Ø A) & (Ø B Ú C)
3. [(B Ú C) Ú (A & Ø A)] & [(Ø B Ú Ø A) Ú (C & Ø C)] & [(Ø B Ú C) Ú (Ø A & A)]
4. (B Ú C Ú A) & (B Ú C Ú Ø A) & (Ø B Ú Ø A Ú C) & (Ø B Ú Ø A Ú Ø C) &
& (Ø B Ú C Ú A) & (B Ú C Ú Ø A)
Данная СвКНФ представляет все возможные логические следствия исходных формул.
В) Сокращенная конъюнктивная нормальная форма (СкКНФ).
СкКНФ имеет следующие признаки:
Ни один конъюнкт не содержит двух одинаковых формул;
В СкКНФ отсутствуют два или более одинаковых конъюнкта;
В СкКНФ отсутствуют конъюнкты, содержащие некоторую формулу и ее отрицание.
Чтобы привести формулу к ее СкКНФ, необходимо выполнить следующие действия:
Получить из исходной формулы ее КНФ;
Сопоставить полученную КНФ с признаками СкКНФ;
|
|