Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л
Задача 10.
Если Х и Y логически истинны,
а Z - логически ложно, что можно
сказать о высказывании
?
Ответ: логически истинно.
Задача 11. Пусть Х означает: «Я сдам экзамен»; а Y: «Я буду регулярно выполнять домашние задания». Запишите в символической форме следующие высказывания:
(а) « Я сдам этот экзамен только в том случае, если буду регулярно выполнять домашние задания».
(б) «Регулярное выполнение домашних заданий является необходимым условием для того, что я сдам этот экзамен».
(в) «Сдача этого экзамена является достаточным условием того, что я регулярно выполнял домашние задания».
(г) «Я сдам этот экзамен в том и только в том случае, если я буду регулярно выполнять домашние задания».
(д) «Регулярное выполнение домашних заданий есть необходимое и достаточное условие того, чтобы я сдал экзамен».
Выясните,
какому из перечисленных высказываний
соответствуют следующие символические
формы:
.
Задача 12.
Докажите равносильность
с помощью формул алгебры высказываний.
Решение.
Используя формулу
,
запишем:
,
тогда
по
закону де Моргана, т.е.
,
т.к. по закону двойного отрицания
,
что и требовалось доказать.
Полученная формула дает правило
построения отрицания для импликации,
часто применяемое в математических
рассуждениях:
.
Задача 13. Проверьте, будут ли эквивалентны следующие формулы:
а)
и
б)
и
.
Решение. Составим таблицы истинности:
Таблица 19.
X |
У |
Z |
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
Формулы не эквивалентны.
Таблица 20.
X |
У |
Z |
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Формулы эквивалентны.
Задача 14. Постройте таблицы истинности для высказываний:
а)
;
б)
.
Какие другие составные высказывания имеют те же таблицы истинности? Покажите, что любая таблица истинности может быть реализована посредством составного высказывания, в котором используется единственная связка: стрелка Пирса.
Задача 15. Докажите, что импликация
эквивалентна
.
Решение. Доказательство проведем с помощью таблицы истинности.
Таблица 21.
-
X
У
1
0
0
1
0
0
1
1
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
1
1
1
0
1
1
Одинаковость третьего и седьмого столбцов и является доказательством в задаче.