С. Д. Кургалин, С. В. Борзунов, С. Н. Синицина
ЗАДАЧИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Учебное пособие для вузов
Издательско-полиграфический центр
Воронежского государственного университета
2011
Утверждено научно-методическим советом факультета компьютерных
наук 15 июня 2011 г., протокол № 5
Рецензент канд. физ.-мат. наук, доцент Л. А. Минин
Учебное пособие подготовлено на кафедре цифровых технологий факультета компьютерных наук Воронежского государственного университета
Рекомендуется для студентов факультета компьютерных наук 1-го курса
дневного отделения
Для направлений 230400 «Информационные системы и технологии»;
010200 «Математика и компьютерные науки»
Содержание
Введение
4
1 Логика и доказательство
5
2 Задачи к главе «Логика и доказательство»
6
3 Теория множеств
13
4 Задачи к главе «Теория множеств»
16
5 Система с базой знаний
22
6 Задачи к главе «Система с базой знаний»
23
7 Отношения
26
8 Задачи к главе «Отношения»
28
9 Функции
40
10 Задачи к главе «Функции»
41
11 Комбинаторика
49
12 Задачи к главе «Комбинаторика»
50
13 Графы
62
14 Задачи к главе «Графы»
64
3
Введение
Настоящее учебное пособие предназначено для практических, лабораторных занятий и самостоятельной работы по курсам «Дискретная
математика» и «Дискретная математика, математическая логика и их
приложения в математике и компьютерных науках» для студентов факультета компьютерных наук Воронежского государственного университета. <...> Учебное пособие содержит базовые теоретические представления и
методы решения основных типов задач по курсам «Дискретная математика» и «Дискретная математика, математическая логика и их приложения в математике и компьютерных науках». <...> Каждый раздел начинается с основных теоретических положений и
формул, знание которых необходимо при решении задач, и содержит указания по их практическому использованию. <...> Составное высказывание может быть построено из простых высказываний с помощью логических операций. <...> Два составных высказывания <...>
Задачи_по_дискретной_математике.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
С. Д. Кургалин, С. В. Борзунов, С. Н. Синицина
ЗАДАЧИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Учебное пособие для вузов
Издательско-полиграфический центр
Воронежского государственного университета
2011
Стр.1
Содержание
Введение
1 Логика и доказательство
2 Задачи к главе «Логика и доказательство»
3 Теория множеств
4 Задачи к главе «Теория множеств»
5 Система с базой знаний
6 Задачи к главе «Система с базой знаний»
7 Отношения
8 Задачи к главе «Отношения»
9 Функции
10 Задачи к главе «Функции»
11 Комбинаторика
12 Задачи к главе «Комбинаторика»
13 Графы
14 Задачи к главе «Графы»
4
5
6
13
16
22
23
26
28
40
41
49
50
62
64
3
Стр.3
2. Обратное рассуждение: прямым рассуждением доказывается истинность
высказывания (не Q) ⇒ (не P) как логически эквивалентного
(P ⇒Q).
3. Метод «от противного»: предполагается истинность P и ложность
Q и на основе аргументированных рассуждений получается противоречие.
Принцип
математической индукции.
Пусть P(n) — предикат, определённый для всех натуральных чисел
n.
Предположим, что
1. P(1) истинно и
2. ∀k 1 импликация (P(k)⇒P(k +1)) верна.
Тогда P(n) истинно при любом натуральном n.
2 Задачи к главе «Логика и доказательство»
1. Покажите, что высказывание A⇒(B ⇒C) логически эквивалентно
высказыванию (A и B)⇒C.
Решение:
Составим таблицу истинности приведённых высказываний.
A B C A и B B ⇒C A⇒(B ⇒C) (A и B)⇒C
И И И
И И Л
И Л И
И Л Л
Л И И
Л И Л
Л Л И
Л Л Л
И
И
Л
Л
Л
Л
Л
Л
И
Л
И
И
И
Л
И
И
И
Л
И
И
И
И
И
И
И
Л
И
И
И
И
И
И
Два последних столбца совпадают, поэтому соответствующие выражения
логически эквивалентны.
6
Стр.6
2. Покажите, что высказывание A⇒(B ⇒C) логически эквивалентно
высказыванию не C ⇒((не A) или (не B)).
Решение:
Обозначим: P1 = A⇒(B ⇒C), P2 = не C ⇒((не A) или (не B)).
A B C B ⇒C (не A) или (не B)
И И И
И И Л
И Л И
И Л Л
Л И И
Л И Л
Л Л И
Л Л Л
лентность P1 и P2.
3. Покажите, что высказывание A или (B и C) логически эквивалентно
высказыванию (A или B) и (A или C).
Решение:
Задача решается составлением таблицы истинности для высказываний
P1 = A или (B и C), P2 = (A или B) и (A или C).
A B C A или B A или C B и C
И И И
И И Л
И Л И
И Л Л
Л И И
Л И Л
Л Л И
Л Л Л
И
И
И
И
И
И
Л
Л
И
И
И
И
И
Л
И
Л
7
И
Л
Л
Л
И
Л
Л
Л
P1
И
И
И
И
И
Л
Л
Л
P2
И
И
И
И
И
Л
Л
Л
И
Л
И
И
И
Л
И
И
Л
Л
И
И
И
И
И
И
P1
И
Л
И
И
И
И
И
И
P2
И
Л
И
И
И
И
И
И
Из сравнения двух последних столбцов следует логическая эквива
Стр.7
4. Покажите, что высказывание A и (B или C) логически эквивалентно
высказыванию (A и B) или (A и C).
Решение:
Задача решается составлением таблицы истинности для высказываний
P1 = A и (B или C), P2 = (A и B) или (A и C).
A B C
A и B
И И И
И И Л
И Л И
И Л Л
Л И И
Л И Л
Л Л И
Л Л Л
И
И
Л
Л
Л
Л
Л
Л
И
Л
И
Л
Л
Л
Л
Л
И
И
И
Л
И
И
И
Л
A и C B или C P1
И
И
И
Л
Л
Л
Л
Л
P2
И
И
И
Л
Л
Л
Л
Л
5. Является ли высказывание (A⇒(B ⇒C))⇒((A и B)⇒C) тавтологией?
Ответ:
Приведенное высказывание является тавтологией.
6. Является ли высказывание (A и (B или C))⇒(A или (B и C))
тавтологией?
Ответ: Не является.
7. Является ли высказывание (A⇒B или C) ⇒ (не B ⇒A) тавтологией?
Ответ:
Не является.
8. Является ли высказывание (A и B ⇒C)⇒(не C ⇒A) тавтологией?
Ответ:
Не является.
9. Докажите методом математической индукции высказывание: 1 +
3 +5+. . .+(2n−1) = n2 для всех натуральных чисел n.
8
Стр.8