Построить таблицу истинности для заданной формулы:
(¬A&C∨A&B∨¬A&¬B&¬C)& (¬A&¬B∨B&¬(A&C))
Формула содержит три атома А, В, С. Для такой формулы существует 8 интерпретаций.
Таблица истинности принимает вид:
|
A |
B |
C |
(¬A&C∨A&B∨¬A&¬B&¬C) |
(¬A&¬B∨B&¬(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 |
Упростить выражение (левую часть):
(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
Представить в ДНФ и в КНФ следующие формулы:
¬(¬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)
Формализовать представленные рассуждения в виде формул алгебры логики.
Или Валя и Борис одного возраста, или Валя старше Бориса. Если Валя и Борис одного возраста, то Наташа и Борис не одного возраста. Если Валя старше Бориса, то Борис старше Сергея. Следовательно, или Наташа и Борис не одного возраста, или Борис старше Сергея.
Введем следующие обозначения:
A – Валя и Борис одного возраста
B – Валя старше Бориса
C–Наташа и Борис одного возраста
D – Борис старше Сергея
Формализация рассуждения:
A∨B, A→¬C, B→D├ ¬C∨D
Для формализованного в задаче 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=И
Соответственно, логическое следствие доказано.