Алгебра логики высказываний. Контрольная работа

КМ 1 Задание 1

Для заданной формулы алгебры логики построить таблицу истинности.

(ØAÚA&BÚB&C)&(B ÚØA&ØB&ØСÚØA&С)

Прежде, чем выполнять свой вариант, рекомендуется рассмотреть примеры решения задачи.

Примеры решения задачи.

Пример 1. Дана формула: F = A®BÚC

Формула содержит три атома A, B, C. Для такой формулы существует 8 интерпретаций. Представим их в таблице.

Последний столбец – результат. Заметим, что первоначально

выполняется BÚC, так как операция ИЛИ имеет высший приоритет по отношению к операции ИМПЛИКАЦИЯ (правая и левая части для импликации выделены цветом).

Пример 2 F = ((B&CÚA)®ØB) Ú ØA& B&ØC

Для наглядности обозначим части формулы:

F1 = ((B&CÚA)®ØB) F2 = ØA& B&ØC F = F1Ú F2

Примечание В математической логике, в отличие от схемотехники, принято использовать обозначения И (истина) и Л (ложь) для значений атомарных высказываний. При работе с высказываниями, представленными в виде формул, допустимо использовать обозначения 1 (истина) и 0 (ложь) для наглядности. Правила выполнения логических операций представлены в таблицах в лекционном материале.

КМ 1 Задача 2.

Заданную формулу привести к дизъюнктивной нормальной форме (ДНФ) и к конъюнктивной нормальной форме (КНФ). Преобразования выполнять аналитически.

Ø(ØAÚA&B&ØC)ÚØ(ØBÚC)&(ØAÚB)

Пример решения задачи

Формула логики высказываний F представлена в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда она имеет форму F = B1 & B2 & … & Bm, где каждая из Bi (i = 1, m ) есть дизъюнкция литер.

Аналогично говорят, что формула логики высказываний F представлена в

дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда она имеет форму F = A1 ÚA2 Ú… ÚAn, где каждая из Ai (i = 1, n ) есть конъюнкция литер.

Алгоритм преобразования произвольной формулы исчисления высказываний в нормальную форму состоит из следующих шагов.

Шаг 1. Избавляемся от связок эквивалентность и импликация, применяя формулы

А « В = (А ® В) & (В ® А).

А ® В = ØА Ú В.

Шаг 2. Продвигаем знаки отрицания до атомов, используя правила Де- Моргана, также снимаем двойные отрицания.

ØØА = А.

Ø(AÚB) =ØА & ØBü

Ø(A& B) =ØA ÚØBý

þзаконы Де-Моргана.

Шаг 3. Для получения КНФ применяем правило внесения в скобки А Ú (В & С) = (А Ú В) & (А Ú С) .

Для получения ДНФ многократно применяем правило раскрытия скобок

А & (В Ú С) = А & В Ú А & С .

Получим ДНФ для формулы (A ®(B ÚØC)) ®D.

В преобразованиях используем формулы Де-Моргана и тождество

X® Y = ØX Ú Y

(A ® (B Ú ØC)) ® D = (ØA Ú B Ú ØC) ®D = Ø(ØA Ú B Ú ØC) Ú D = (A&ØB & C)

Ú D = A&ØB & C Ú D (дополнительные скобки здесь не нужны, поскольку приоритет операции & выше, чем приоритет операции Ú)

Получим КНФ для формулы (A ®(B ÚØC)) ®D.

(A ® (B Ú ØC)) ® D = (ØA Ú B Ú ØC) ® D = Ø(ØA Ú B Ú ØC) Ú D = (A & ØB & C) Ú D = (A Ú D) & (ØB Ú D) & (C Ú D).

На последнем шаге используем тождество X Ú Y&Z = (X Ú Y)&(X Ú Z)

КМ 1 задания 3 - 4 - 5

Задача 3

Формализовать представленные рассуждения в виде формул алгебры логики. Выделить атомарные высказывания и связки. Определить посылки и заключение в заданном рассуждении.

Если Смит был убийцей, то Джонс лжет. Если Джонс лжет, то убийство имело место после полуночи. Джонс не встречал этой ночью Смита тогда и только тогда, когда Смит был убийцей. Если Джонс встречал этой ночью Смита, то убийство имело место после полуночи. Следовательно, убийство имело место после полуночи.

Пример решения задания 3.

Условия задачи

Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встанурано,то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен не ходить завтра на первое занятие, или не ходить на танцы.

Введем буквенные обозначения для атомарных высказываний: A: я пойду завтра на первое занятие

B: я должен буду встать рано C: я пойду вечером на танцы D: я лягу спать поздно

E: я буду вынужден довольствоваться пятью часами сна Обозначим красным цветом логические связки между атомами.

Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встанурано,то я буду вынужден довольствоваться пятью часами сна. Я просто невсостоянии обойтись пятью часами сна. Следовательно, я должен не ходить завтра на первое занятие, или не ходить на танцы.

Подставляем обозначения для атомов: Если A, то B, и если C, то D.

Если D, и B, то E.

Я не в состоянии E. (утверждение Е отрицается) Следовательно, не А, или не С.

Окончательно: Формализация рассуждения.

(A → B)& (C → D), D&B → E, ¬E ├ ¬A v ¬C

В данном рассуждении заключение ¬A v ¬C логически следует из посылок (A → B)& (C → D), D&B → E и посылки ¬E.

Форма записи приведена ниже (под чертой записываем заключение):

(1)( A → B)& ( C → D)

1. D&B → E
2. ¬E

(¬A v ¬C)

Следующее задание заключается в доказательстве того, что заключение истинно, если истинны одновременно все посылки.

Задание 4

Для формализованного в задаче 3 рассуждения доказать логическое следствие заключения из посылок.

Пример решения задания 4.

В формализованном выше рассуждении из трёх посылок следует заключение ¬A v ¬C.

( A → B)& ( C → D)

D&B → E

¬E

¬A v ¬C

Доказательство логического следования.

Построим формулу по Теореме 1 о логическом следовании: ((A → B)&( C → D)&( D&B → E)& ¬E) ®(¬A v ¬C)

Наша цель – доказать общезначимость этой формулы.

Выполним следующие преобразования. Избавляемся от импликаций:

Ø((A → B)&( C → D)&( D&B → E)& ¬E) Ú (¬A v ¬C)

Ø((ØA Ú B)&( ØC ÚD)&(Ø(D&B) Ú E)& ¬E) Ú (¬A v ¬C)

Применяем правила Де-Моргана:

Ø((ØA Ú B) &( ØC ÚD)&(ØDÚØB Ú E)& ¬E) Ú ¬A v ¬C =

Ø(ØA Ú B) ÚØ ( ØC Ú D) ÚØ (Ø DÚØ B Ú E) ÚØØE) Ú ¬A v ¬C = (A & ØB) Ú (C & ØD) Ú(D& B &ØE) Ú E Ú ¬A v ¬C

Перегруппируем для наглядности логические слагаемые и применим известное тождество (например, (A & ØB) Ú¬A заменяем на ¬AÚØB ) :

(A & ØB) Ú ¬A Ú (C & ØD) Ú ¬C Ú(D& B &ØE) Ú E =

= ¬A ÚØB ÚØC ÚØD ÚD& B ÚE

Применяем тождество повторно к подчеркнутым частям формулы:

¬A ÚØB ÚØC ÚØDÚ D& B Ú E = ¬A ÚØB ÚØC ÚØD Ú BÚ E =

= ¬A ÚØBÚ B ÚØC ÚØD Ú E = ¬A Ú И ÚØC ÚØDÚ E = И

Доказательство логического следования от противного.

Построим формулу по Теореме 2 о логическом следовании:

(A → B)&( C → D)&( D&B → E)& ¬E&¬ (¬A v ¬C)

Докажем ее противоречивость.

(A → B)&( C → D)&( D&B → E)& ¬E&¬ (¬A v ¬C) = (¬A v B)&( ¬C v D)&( ¬ D v ¬B v E)& ¬E& A &C=

= (¬A & A v B&A)&( ¬C&C v D&C)& ( ¬ D& ¬E v ¬B & ¬E v E& ¬E) =

=( B& A)&( D&C ) & (¬ D& ¬E v ¬B & ¬E)= A& B& C& D& ¬ D& ¬E v A& B& C& D&¬B & ¬E =Л v Л =Л

Произведение подчеркнутых сомножителей, например, ¬A & Aдаёт значение Л, далее (Л v B&A) заменяем просто на B & A

Мы доказали справедливость приведенного рассуждения, используя две теоремы о логическом следствии. В системах искусственного интеллекта доказательство рассуждений выполняется автоматически (автоматическое доказательство теорем) на основе метода резолюции.

Метод резолюции реализует доказательство «от противного»; требуется показать, что, добавив к посылкам отрицание заключения, мы обязательно придём к противоречию. Для этого все посылки и заключение, взятое со знаком отрицания, приводятся к конъюнктивной нормальной форме (КНФ), где каждый сомножитель содержит только атомы (с отрицаниями или без отрицаний), соединённые операциями Ú. Каждое такое выражение мы называем дизъюнктом. Процесс доказательства заключается в получении новых резольвент из пар дизъюнктов, при этом резольвента является логическим следствием этих дизъюнктов. Получение новых дизъюнктов продолжается до тех пор, пока не будет выведен тождественно ложный дизъюнкт, обозначенный □.

Задание 5

Доказать справедливость рассуждения (взять свой вариант из задания 3)

методом резолюции

Пример решения задания методом резолюции.

Условия задачи (вспомним).

Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.

Буквенные обозначения для атомарных высказываний:

A: я пойду завтра на первое занятие

B: я должен буду встать рано C: я пойду вечером на танцы D: я лягу спать поздно

E: я буду вынужден довольствоваться пятью часами сна

Формализация рассуждения дана выше.

В формализованном рассуждении из посылок следует заключение ¬A v ¬C.

(1) (A → B)&(C → D)

(2) D&B → E

(3) ¬E _

¬A v ¬C

Решение.

Доказываем логическое следствие заключения (¬A v ¬C) из посылок.

Построим отрицание заключения:

¬ (¬A v ¬C) = A & C по правилу Де-Моргана.

Доказательство методом резолюции выполняется только «от противного»: к произведению всех посылок добавляем отрицание заключения: (A → B)&( C → D)&( D&B → E)& (¬E) & ¬ (¬A v ¬C).

Приводим к КНФ: (¬A v B)&( ¬C v D)&( ¬ D v ¬B v E)& ¬E & A & C.

Строим S – множество дизъюнктов, входящих в КНФ:

S = { D₁, D₂, D₃, D₄, D₅, D₆}, где

D₁ = ¬A v B D₂ = ¬C v D

D₃ = ¬ D v ¬B v E D₄ = ¬E

D₅ = А

D₆ = С

Для доказательства противоречивости S нужно убедиться в том, что множество дизъюнктов S содержит пустой (ложный) дизъюнкт □.

Поскольку S первоначально такого дизъюнкта не содержит, надо вывести

его, используя правило порождения новых дизъюнктов из исходных. Новые дизъюнкты получаем методом резолюции и добавляем их к множеству S.

D₁ :¬A v BD₂ : ¬C v D

D₃: ¬ D v ¬B v E D₄ : ¬E

D₅: А

D₆ : С

D7 : ¬ D v ¬B (резольвента D₃, D₄) D8 : ¬C v ¬B (резольвента D₂, D₇) D9 : ¬A v ¬C (резольвента D₁, D₈) D10 : ¬C (резольвента D₁₀, D₅) D11 : □ (резольвента D₁₁, D₆)

Итак, мы вывели пустой (тождественно ложный) дизъюнкт и доказали противоречивость множества S. Для наглядности процесс вывода пустого дизъюнкта представлен в виде дерева. Каждому узлу дерева приписан дизъюнкт из S или резольвента предыдущих дизъюнктов.

¬ D v ¬B v E ØE

C

□