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