Задачи по дискретной математике: учебное пособие

Выходные данные

Борзунов, С. В. Задачи по дискретной математике / С. В. Борзунов, С. Д. Кургалин. — СПб.: БХВ-Петербург, 2016. — 528 с.: ил. — (Учебная литература для вузов). ISBN 978-5-9775-3672-1

В учебном пособии даны задачи и упражнения вузовского курса дискретной математики, включая разделы, связанные со спецификой информационно-коммуникационных технологий. В каждой главе приводятся теоретические сведения, необходимые для решения задач разного уровня сложности, ответы и во многих случаях подробные пояснения к решениям. Для студентов и преподавателей профильных вузов.

УДК 519.1(075.8) ББК 22.176я73

Рецензенты:
А.Г. Буховец — д-р техн. наук, проф. кафедры прикладной математики и математических методов в экономике Воронежского государственного аграрного университета им. императора Петра I
В.Г. Курбатов — д-р физ.-мат. наук, проф. кафедры гуманитарных и естественно-научных дисциплин Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации (Липецкий филиал)

Оглавление

• Предисловие — 6
• Глава 1. Основы математической логики — 11
• Глава 2. Теория множеств — 78
• Глава 3. Отношения и функции — 121
• Глава 4. Комбинаторика — 163
• Глава 5. Графы — 194
• Глава 6. Булева алгебра — 236
• Глава 7. Комплексные числа — 276
• Глава 8. Рекуррентные соотношения — 307
• Глава 9. Понятие алгоритма. Корректность алгоритмов — 349
• Глава 10. Машина Тьюринга — 360
• Глава 11. Асимптотический анализ — 374
• Глава 12. Базовые алгоритмы — 392
• Глава 13. Параллельные алгоритмы — 443
• Справочные материалы — 493

Глава 1. Основы математической логики

Математическая логика — наука, изучающая математические доказательства. Предметами математической логики являются математические доказательства, методы и средства их построения.

Самый простой раздел математической логики — логика высказываний. Высказыванием называется утверждение, имеющее значение истинности, т. е. оно может быть истинным или ложным. Соответствующие значения истинности будем обозначать как И и Л.

Составное высказывание может быть построено из простых высказываний с помощью логических операций и скобок. Наиболее часто используемыми логическими операциями являются: и (конъюнкция или логическое умножение), или (дизъюнкция или логическое сложение), если… то (логическое следствие или импликация, эта операция обозначается также «⇒»), не (отрицание). Конъюнкцию, дизъюнкцию и импликацию относят к бинарным операциям, так как в них используются два операнда, отрицание — унарная операция, для нее нужен один операнд.

Два составных высказывания называются логически эквивалентными, если они принимают одинаковые значения истинности при любом наборе значений составных частей. Составное высказывание, принимающее истинные значения при любых значениях своих компонент, называется тавтологией. Высказывание (не Q) ⇒ (не P) называется противоположным или контрапозитивным к высказыванию P ⇒ Q.

Запись P ⇒ Q читается следующим образом: «P влечет Q», или «из P следует Q», или «Q необходимо для P», или «P достаточно для Q».

Для обоснования логической эквивалентности высказываний используют таблицу истинности, в которой перечислены истинностные значения логических выражений для всех возможных наборов истинностных значений компонент (табл. 1.1). Эквивалентность двух высказываний можно установить посредством сравнения их таблиц истинности. У логически эквивалентных высказываний они совпадают.

Таблица 1.1. Таблица истинности

P	Q	не P	P и Q	P или Q	P ⇒ Q
И	И	Л	И	И	И
И	Л	Л	Л	И	Л
Л	И	И	Л	И	И
Л	Л	И	Л	Л	И

Если высказывания A и B эквивалентны, то пишут A ⇔ B. Последнее высказывание может быть записано через операции конъюнкции и импликации как (A ⇒ B) и (B ⇒ A).

Основные законы алгебры логики перечислены в табл. 1.2. Справедливость перечисленных законов легко доказать построением соответствующих таблиц истинности. Некоторые законы алгебры логики имеют непосредственные аналоги в алгебре вещественных чисел, к ним относятся законы коммутативности, ассоциативности и дистрибутивности. Однако есть и такие законы, как, например, законы де Моргана, которые таких аналогов не имеют.

Таблица 1.2. Законы алгебры логики

Название	Законы
Законы идемпотентности	A или A ⇔ A; A и A ⇔ A
Свойства констант «И» и «Л»	A или Л ⇔ A; A или И ⇔ И; A и И ⇔ A; A и Л ⇔ Л
Свойства дополнения	A или (не A) ⇔ И; A и (не A) ⇔ Л; не (не A) ⇔ A
Законы коммутативности	A или B ⇔ B или A; A и B ⇔ B и A
Законы ассоциативности	A или (B или C) ⇔ (A или B) или C; A и (B и C) ⇔ (A и B) и C
Законы дистрибутивности	A или (B и C) ⇔ (A или B) и (A или C); A и (B или C) ⇔ (A и B) или (A и C)
Законы поглощения	A или (A и B) ⇔ A; A и (A или B) ⇔ A
Законы де Моргана	не (A или B) ⇔ (не A) и (не B); не (A и B) ⇔ (не A) или (не B)

Утверждения о свойствах переменной x называют предикатами и обозначают: P(x), Q(x), … Областью истинности предиката называется совокупность всех x, при которых данный предикат становится истинным высказыванием. Свойства предикатов изучает логика предикатов.

Для построения сложных логических выражений используются кванторы: ∀ (для всех) — квантор всеобщности и ∃ (существует) — квантор существования. Квантор — это логическая операция, которая по предикату P(x) строит высказывание, характеризующее область истинности P(x).

Логическое выражение ∀x (P(x)) (читается «для всех x верно P(x)») означает, что для всех возможных значений x высказывание P(x) принимает истинное значение. Выражение ∃x (P(x)) (читается «существует x такое, что верно P(x)») означает, что для некоторого значения x P(x) принимает истинное значение.

Для отрицаний логических выражений с кванторами известны следующие логические эквивалентности:
не ∀x (P(x)) ⇔ ∃x (не P(x));
не ∃x (P(x)) ⇔ ∀x (не P(x)).

Существует несколько основных методов доказательства истинности высказывания вида P ⇒ Q:
1) прямое рассуждение: предполагается истинность P и выводится истинность Q;
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.

Высказывание 1 обычно называют базой индукции, высказывание 2 — шагом индукции.

Пример 1.1

Докажем, что для всех натуральных n выполняется равенство: 1² + 3² + 5² + … + (2n − 1)² = n(4n² − 1) / 3.

Доказательство:
База индукции: для n = 1 равенство 1² = 1(4*1² − 1) / 3 верно.
Шаг индукции: предполагаем P(k) истинно. Доказываем P(k+1). После алгебраических преобразований левой части получаем выражение, тождественное правой части для k+1. Утверждение доказано.

Пример 1.2. Неравенство Бернулли

(1 + a)ⁿ ≥ 1 + na для n = 1, 2, … и a > −1.
Доказательство:
База индукции: для n = 1 (1+a) ≥ 1+a — верно.
Шаг индукции: умножаем обе части предположения (1+a)ᵏ ≥ 1+ka на (1+a). Получаем (1+a)ᵏ⁺¹ ≥ 1 + (k+1)a + ka². Так как ka² ≥ 0, неравенство выполняется.

Задачи к главе «Основы математической логики»

1.1. Установите, какие из следующих предложений являются высказываниями:
1) Язык Pascal относится к высокоуровневым языкам программирования.
2) Пейте морковный сок!
3) Есть ли жизнь на Марсе?
4) Первые компьютеры появились в XVIII веке.

1.2. Установите, какие из следующих предложений являются высказываниями:
1) Любое квадратное уравнение имеет вещественные корни.
2) Треугольник ABC подобен треугольнику A’B’C’.
3) Неверно, что на Луне нет воды.
4) Да здравствуют Олимпийские игры!

1.3. На листе бумаги записано предложение: «Это предложение ложно». Является ли оно высказыванием?

1.4. Покажите, что выполняются законы де Моргана: 1) не (A и B) ⇔ (не A) или (не B); 2) не (A или B) ⇔ (не A) и (не B).

1.5. Обобщите логические эквивалентности из упражнения 1.4 на случай произвольного числа простых высказываний A1, A2, …, An.

1.6. Покажите, что высказывание A ⇒ (B ⇒ C) логически эквивалентно высказыванию (A и B) ⇒ C.

1.7. Покажите, что высказывание A ⇒ (B ⇒ C) логически эквивалентно высказыванию (не C) ⇒ ((не A) или (не B)).

1.8. Покажите, что высказывание A или (B и C) логически эквивалентно высказыванию (A или B) и (A или C).

1.9. Покажите, что высказывание A и (B или C) логически эквивалентно высказыванию (A и B) или (A и C).

1.10. Докажите, что высказывание ((A или B) и (не (A и B))) ⇔ ((A и (не B)) или ((не A) и B)) является тавтологией.

1.11. Является ли высказывание (A ⇒ (B ⇒ C)) ⇒ ((A и B) ⇒ C) тавтологией?

1.12. Являются ли высказывания 1) (A и (B или C)) ⇒ (A или (B и C)), 2) (A и (B ⇒ C)) и (B или (B ⇒ C)) тавтологиями?

1.13. Являются ли высказывания 1) (A ⇒ (B или C)) ⇒ ((не B) ⇒ A), 2) ((A и B) ⇒ C) ⇒ ((не C) ⇒ A) тавтологиями?

1.14. Обозначим через A: «я голоден», B: «сейчас три часа», C: «пора обедать». Запишите:
1) Если сейчас три часа или я голоден, то пора обедать.
2) Если не пора обедать, то я не голоден.
3) Если я голоден, то пора обедать. Но я не голоден. Значит, или сейчас не три часа, или не пора обедать.

1.15. Обозначим через A: «светит солнце», B: «на улице жарко», C: «идет снег». Запишите:
1) Если идет снег, то, если светит солнце, на улице не жарко.
2) Если светит солнце, то на улице либо жарко, либо идет снег (но не одновременно).

1.16. Сформулируйте контрапозитивное высказывание: «Если гвардейцы кардинала поблизости, то д’Артаньян готов к бою».

1.17. Сформулируйте контрапозитивное высказывание: «Если Арамис станет епископом и Портос получит баронский титул, то д’Артаньяну вручат маршальский жезл».

1.18. Сформулируйте контрапозитивное высказывание: «Если Атос перехватит письмо и Портос уйдет от погони, то Арамис раскроет замысел кардинала».