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