Задание 1

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

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

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

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

Задание 2

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

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

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

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

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

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

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

= A∨C∨B

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

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

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

= A&B∨C∨A=C∨A=A∨C

Общеевыражение принимает вид:(A∨C)&(A∨C∨B)

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

Задание 3

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

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

Получим ДНФ:

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

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

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

=¬((¬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)

Получим КНФ:

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

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

Задача 4

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

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

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

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

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

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

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

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

A∨B, A→¬C, B→D├ ¬C∨D

Задание 5

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

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

A∨B

A→¬C

B→D

_______

¬C∨D

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

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

(A∨B)&(A→¬C)&(B→D) → (¬C∨D)

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

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

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

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

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

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

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

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

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

=¬B∨A∨¬C∨B∨¬D

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

A∨¬C∨И∨¬D=И

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