Файл: Интеллектуальные информационные системы. Решение.docx

ВУЗ: Не указан

Категория: Решение задач

Дисциплина: Логика

Добавлен: 18.10.2018

Просмотров: 2326

Скачиваний: 25

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Задание 1

Построить таблицу истинности для заданной формулы:

A&CA&B¬A&¬B&¬C)& (¬A&¬BB&¬(A&C))

Формула содержит три атома А, В, С. Для такой формулы существует 8 интерпретаций.

Таблица истинности принимает вид:

A

B

C

A&CA&B¬A&¬B&¬C)

(¬A&¬BB&¬(A&C))

F

0

0

0

1

1

1

0

0

1

1

1

1

0

1

0

0

1

0

0

1

1

1

1

1

1

0

0

0

0

0

1

0

1

0

0

0

1

1

0

1

1

1

1

1

1

1

0

0





Задание 2

Упростить выражение (левую часть):

(A&B¬ (A&B)&CA&¬C)&(AC&¬AB&¬(AC))=AC

Cогласно правилу Де-Моргана раскроем скобку ¬ (AC))= ¬AC

Тогда: B&¬ (AC)=B&¬A&¬C

Тогда выражение в правой скобке можно упростить:

AC&¬AB&¬ (AC)=A(B&¬A&¬C)∨(C&¬A)=

= (A∨C)∨(B&¬A&¬C) =(A∨C∨B)&(A∨C∨¬A)&(A∨C∨¬C)=

= ACB


Подобные преобразования выполняем и с левой скобкой:

(A&B)¬ (A&B)&C∨(A&¬C)=

=(A&B)∨C∨(A&¬C)=

= A&BCA=CA=AC


Общеевыражение принимает вид:(AC)&(ACB)

Применяя формулу поглощения получаем: AC






Задание 3

Представить в ДНФ и в КНФ следующие формулы:

¬(¬AA&B&¬C)¬(¬BC)&(¬AB)

Получим ДНФ:

¬(¬AA&B&¬C)¬(¬BC)&(¬AB)=

=¬((¬AA)&(¬AB)&(¬A¬C)(B&¬C)&(¬AB)=

=¬((¬AB)&( ¬A¬C)(B&¬C)&(¬AB)=

=¬((¬A&(B¬C))(B&¬C&B) (¬A&¬C&B)=

=¬((¬A&(B¬C))(B&¬C)(¬A&¬C&B)=

=¬((¬A&(B¬C))(B¬C)&(¬A)=

=A∨(¬B&C)(B&¬A)∨(¬C&¬A)=

=A∨(B&¬C)

Получим КНФ:

¬(¬AA&B&¬C)¬(¬BC)&(¬AB)=A∨(B&¬C)=

=(AB)&(A¬C)





Задача 4

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

Или Валя и Борис одного возраста, или Валя старше Бориса. Если Валя и Борис одного возраста, то Наташа и Борис не одного возраста. Если Валя старше Бориса, то Борис старше Сергея. Следовательно, или Наташа и Борис не одного возраста, или Борис старше Сергея.

Введем следующие обозначения:

A – Валя и Борис одного возраста

B – Валя старше Бориса

C–Наташа и Борис одного возраста

D – Борис старше Сергея

Формализация рассуждения:

AB, A→¬C, B→D├ ¬CD





Задание 5

Для формализованного в задаче 4 рассуждения доказать логическое следствие заключения из посылок: AB, A→¬C, B→D├ ¬CD

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

AB

A→¬C

B→D

_______

¬CD

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

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

(AB)&(A→¬C)&(B→D) → (¬CD)

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

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

¬((AB)&(¬A¬C)&( ¬BD))(¬CD)

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

¬(AB)¬ (¬A¬C)¬ (¬BD)(¬CD)=

=(¬A&¬B)(A&C)(B&¬D)¬CD

Перегруппируем слагаемые и применим тождества для упрощения:

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

=(¬A&¬B)A¬CB¬D=

BA¬CB¬D

Выделенные элементы в формуле дают ИСТИНУ, значит:

A¬CИ¬D


Соответственно, логическое следствие доказано.