Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ОТВЕТЫ И РЕШЕНИЯ

Ответы и решения к главе 1

Задача 1.11. Все подмножества составляют булеан:

В(М) = {0, {а}, {Ь}, {с}, {сі}, {е}, {а, Ь}, {а, с}, {а, с!}, {а, е},

{Ь, с}, {Ь, с!}, {Ь, е}, {с, с1}, {с, е}, {сі, е}, {а, Ь, с}, {а, Ь, е},

{а, Ь, с!}, {а, с, (1}, {а, с, е}, {а, сі, е}, {Ь, с, сі), {Ь, с, е}, {Ь, сі, е},

{с, сі, е}, {а, Ь, с, сі}, {а, Ь, с, е}, {а, Ь, сі, е}, {а, с, сі, е}, {Ь, с, сі, е}, {а, Ь, с, сі, е}}.

Задача 1.2. Собственное подмножество не должно совпадать с самим множеством, таких подмножеств 31:

{0, {а}, {Ь}, {с}, {сі}, М, {а, Ь), {а, с), {а, сі}, {а, е}, {Ь, с}, {Ь, сі},

{Ь, е}, {с, сі}, {с, е}, {сі, е}, {а, Ь, с}, {а, Ь, е}, {а, Ь, сі}, {а, с, сі},

{а, с, е}, {а, сі, е}, {Ь, с, сі}, {Ь, с, е}, {Ь, сі, е}, {с, сі, е}, {а, Ь, с, сі}, {а, Ь, с, е}, {а, Ь, сі, е}, {а, с, сі, е}, {Ь, с, сі, е}}.

Задача 1.3. Мощность булеана равна 32, сам булеан

В(М) = {0, {а}, {Ь}, {с}, {сі}, {е}, {а, Ь}, {а, с}, {а, сі}, {а, е}, {Ь, с}, {Ь, сі}, {Ь, е}, {с, сі}, {с, е}, {сі, е}, {а, Ь, с}, {а, Ь, е}, {а, Ь, сі},

{а, с, с!}, {а, с, е}, {а, сі, е}, {Ь, с, сі}, {Ь, с, е}, {Ь, сі, е}, {с, сі, е},

{а, Ь, с, сі}, {а, Ь, с, е}, {а, Ь, сі, е}, {а, с, сі, е}, {Ь, с, сі, е},

{а, Ь, с, сі, е}}.

Задача 1.4. Любое множество, мощность которого равна 5, например УУ= {1, 2, 3, 4, 5}.

Задача 1.5

М={2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

М={х/хе Nих<2 и шос1(л:, 2) = 0};

М= {х/ іот I := 1 1:о 10 бол: := 2 * /'}.

Задача 1.6. Множества натуральных чисел счетно-бесконечно, его мощность — алеф-нуль.

Задача 1.7. Мощность множества натуральных чисел на отрезке [1, 1024] равна натуральному числу 1024.

Задача 1.8. Множество рациональных чисел счетно-бесконечно, его мощность — алеф-нуль.

Задача 1.9. Множество вещественных чисел на отрезке [0, 1] несчетно, его мощность — алеф.

Задача 1.10. Множество точек на плоскости несчетно, его мощность — алеф.

Задача 1.14

О {с, с};

  • 2) {я, Ь, с,
  • 3) {с}; 4) {с}.

Задача 1.15. Данная задача имеет более одного правильного решения. Приведем несколько:

  • а) А п В пС, В / С / А, В / (С иА) = В п (А и С);
  • б) (А п В) / С, / С) п В, (В / С) п А, А п В п С;
  • в) С / {А и В),С / А / С, С п~Ап~В, (4ий)пС;
  • г) (й/4)пСи(й/С)пС,= (4пй)/Си(4пС)/5.

Задача 1.16. Круги Эйлера—Венна (рис. 7.1.1).

Решение задачи 1.16

Рис. 7.1.1. Решение задачи 1.16

Задача 1.17

  • 1) {2,3,4,5,6,7,8,91;
  • 2) {7};
  • 3) {4, 7};
  • 4) {1,2,3,5,6,9}.

Задача 1.18

  • 1) универсум/;
  • 2) {Ц;
  • 3) {1,3,5};
  • 4) 0.

Задача 1.19. Первый элемент а, второй элемент представляет собой множество {Ь, с). Все подмножества образуют булеан

В{Х) = {0, {а}, {Ь, с}, {а, {

Задача 1.20. Первый элемент а, второй элемент представляет собой множество {а, Ь). Собственных подмножеств всего три: 0, {а},

{а, Ь).

Задача 1.21. Исходное множество содержит два элемента. Первый элемент — пустое множество 0, второй элемент представляет собой множество с одним элементом {0}. Подмножеств всего три: 0, {0}, {0, {0}}.

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

  • РЬЬ — свойство иметь темные волосы;
  • РЬе — свойство иметь темные глаза;
  • РЬИе — свойство иметь темные волосы и темные глаза.

Тогда число темноволосых и светлоглазых людей по теореме включения-исключения равно

Х= п(РЬИ) - п(РЬИе) = 7-5 = 2.

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

  • РЬк — свойство иметь темные волосы;
  • РЬе — свойство иметь темные глаза;
  • РЬЬе — свойство иметь темные волосы и темные глаза.

Число светловолосых и темноглазых людей равно

Х= п(РЬе) - п(РЬЬе) = 8-5 = 3.

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

  • РЬИ — свойство иметь темные волосы;
  • РЬе — свойство иметь темные глаза;
  • РЬИе — свойство иметь темные волосы и темные глаза.

Число светловолосых и светлоглазых людей по формуле включения-исключения равно

Х= п - п(РЬЬ) - п(РЬе) + п(РЬИе) =15-8-7 + 5 = 5.

Задача 1.30. На множестве натуральных чисел только сложение и умножение дают в результате операции натуральное число.

Задача 1.31. На множестве четных натуральных чисел только сложение и умножение дают в результате операции четное натуральное число.

Задача 1.32. На множестве натуральных чисел операции возведение в степень, сложения и умножения дают в результате натуральное число, т.е. а), б), г).

Задача 1.33. На множестве натуральных чисел только сумма квадратов и нахождение наибольшего общего делителя дают в результате натуральное число, т.е. б) и в).

Задача 1.34. На множестве рациональных чисел сложение, вычитание и умножение дают в результате рациональное число, так как рациональное число представимо как дробь а/Ь или сД/ и по правилу арифметических действий:

ad + be а с

_• _

bd '~b~~d

Ъ d

ad - be a c a ? c • __

bd ’~b 'd~ ~b~d'

где awe — целые числа; bwd— натуральные числа. To есть б), в) и г).

Задача 1.35. На множестве рациональных чисел все указанные случаи (деление, сумма квадратов, нахождение наибольшего общего делителя, остаток от деления, отрицательный целый коэффициент при сумме квадратов) дают в результате рациональное число, так как рациональное число представимо как дробь а/Ь или сД/ и по правилу арифметических действий:

а с _ ad I а ~Ъ ~d~ ~bc

+

/СЛ2

a2d2 + b2c

у

а j

b2d2

;-2

  • ( 2 а с
  • —Г + -
  • 2 Л

V

d2)

где а и с — целые числа, bwd — натуральные числа. То есть а), б), в), г) и д).

Задача 1.36. На множестве целых чисел в результате операций только деление может дать дробное число, т.е. б), в), г) и д).

Задача 1.37. На множестве действительных чисел только возведение в степень может дать иррациональное число, т.е. б), в) и г).

Задача 1.38. На множестве действительных чисел все указанные операции дают либо действительное число, либо натуральное. Натуральные числа как подмножество входят в действительные числа. То есть а), б), в), г) и д).

Задача 1.47. Рефлексивность, несимметричность, нетранзитив-ность.

Задача 1.48. Рефлексивность, симметричность, транзитивность.

Задача 1.49. Рефлексивность, несимметричность, нетранзитив-ность.

Задача 1.50. Т~М) = {(я, а), (Ь, я), (.Ъ, Ь), , Ъ), (с, с), (cl, с), (е, */)}. Обратите внимание: все рефлексивные пары, заданные в прямом бинарном отношении, входят также и в обратное отношение!

Задача 1.51. Т(М) = {(я, с), (я, d), (я, с), (b, я), (6, <У), (Z), с), (с, А), (с, с), (с, я), (б/, d), (d, с), (d, b), (flf, я), (с, А), (е, с), (е, с), (с, */))}.

Задача 1.52. R(M) = {(1,1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (1, 2), (1, 3), (1,4), (1, 5), (1,6), (1, 7), (1, 8), (2, 4), (2, 6), (2, 8), (3, 6), (4, 8)}. Рефлексивное, антисимметричное, транзитивное.

Задача 1.53. R(M) = {(2, 1), (З, 1), (4, 1), (5, 1), (6, 1), (7, 1), (8, 1), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (5, 6), (6, 7), (7, 8)}. Иррефлек-сивное, антисимметричное, нетранзитивное.

Задача 1.54. R(M) = {(1, 1), (2, 1), (З, 1), (4, 1), (5, 1), (6, 1), (7, 1), (8, 1), (1,2), (3, 2), (5, 2), (7, 2), (2, 3), (5, 3), (8, 3), (3, 4), (7, 4), (4, 5), (5, 6), (6, 7), (7, 8)}. Нерефлексивное, несимметричное, нетранзитивное.

Задача 1.55. Нерефлексивное, несимметричное, нетранзитивное.

Задача 1.56. Иррефлексивное, антисимметричное, интранзитив-ное.

Задача 1.57. Рефлексивное, несимметричное, нетранзитивное.

Задача 1.61. Рефлексивность, несимметричность, нетранзитив-ность.

Задача 1.62. Рефлексивность, антисимметричность, транзитивность.

Задача 1.63. Иррефлексивность, антисимметричность, транзитивность.

Задача 1.64. Решений больше чем одно. Все решения должны обладать свойствами рефлексивности и симметричности. При этом на паре (я, Ь) отношение не должно быть задано, а на паре (я, с) — задано. Например, R = {(я, я), (b, b), (с, с), (d, tf), (е, е), (Ь, я), (с, е), (е,У), (/; я)}.

Задача 1.65. Решений больше чем одно. Все решения должны обладать свойствами рефлексивности, симметричности, транзитивности. При этом элемент b не должен вступать в отношения ни с каким другим элементом, кроме себя самого, либо я и b должны принадлежать разным классам эквивалентности, я и с должны принадлежать одному классу эквивалентности. Например, R = {(а, а), (b, b), (с, с), (d, d), (е, е), (/;/), (я, с), (с, a), (a, d),(d, а), (с, d), (d, с), (b, е), (е, b), (А,/), (/, А), (в,У), (/, е)}.

Задача 1.66. Решений больше чем одно. Все решения должны обладать свойствами рефлексивности, антисимметричности, транзитивности. При этом элементы а и b не должны быть сравнимы между собой, а элементы а и с — сравнимы. Например, R = {(а, а), (b, b), (с, с), (d, d), (е, е), (/,/), (Л я), (я, с), (/; с), (/; Zj), (b, d), (f, d)}.

Задача 1.67. Решений больше чем одно. Все решения должны обладать свойствами иррефлексивности, антисимметричности, транзитивности. При этом элементы а и b не должны быть сравнимы между собой, а элементы а и с — сравнимы. Например, /? = {/, я), (я, с),if, с), (f, Ъ), (b, d), (f, d)}.

Задача 1.68. R является отношением частичной упорядоченности тогда и только тогда, когда оно рефлексивно, антисимметрично и транзитивно. Отношение делимости нацело рефлексивно, так как гез(я, я) = 0; антисимметрично, так как если геБ(я, Ь) = 0, то res(b, я) = = Ь транзитивно, так как если ге5(я, Ь) = 0 и res(b, с) = 0, то ге5(я, с) = 0. Следовательно, R — отношение частично упорядоченное.

Задача 1.69. R является отношением частичной упорядоченности тогда и только тогда, когда оно иррефлексивно, антисимметрично и транзитивно. Отношение, определяющее наличие наибольшего общего делителя, равного к, является нерефлексивным, так как при а— к пара (я, я) принадлежит R, в других случаях — не принадлежит. Следовательно, R не является отношением строгой упорядоченности.

Задача 1.77. 24. Задача 1.78. 24. Задача 1.79. 60.

Задача 1.80. 60.

Задача 1.81. 35.

Задача 1.82. 35.

Задача 1.83. 21.

Задача 1.84. 21.

Задача 1.85. 120.

Задача 1.86. 20.

Задача 1.87. ЗО.

Задача 1.88. 60.

Задача 1.96. Опыт состоит только из одного события, событие А несовместимо с событием В. Следовательно, неверными будут утверждения:

  • • событие А невозможно;
  • • событие В невозможно;
  • • события Л и В равновероятны.

Задача 1.97. Опыт состоит только из одного события, событие А несовместимо с событием В. Следовательно, неверными будут утверждения:

  • • событие А невозможно;
  • • событие В невозможно;
  • • события Л и В равновероятны.

Задача 1.98. Опыт состоит только из одного события, событие А несовместимо с событием В, оба события равновероятны. Следовательно, неверными будут утверждения:

  • • событие А невозможно;
  • • событие В невозможно.

Задача 1.99. Опыт состоит только из одного события, событие А несовместимо с событием В, оба события равновероятны. Следовательно, неверными будут утверждения:

  • • событие А невозможно;
  • • событие В невозможно.

Задача 1.100. По правилу суммы 4+1=5.

Задача 1.101. По правилу суммы 6 + 9 = 15.

Задача 1.102. По правилу суммы 3 + 2 = 5.

Задача 1.103. По правилу суммы 4+11 = 15.

Задача 1.104. В данном случае мы выбираем четверку <х, у, г, и>> с повторениями. При этом должны обязательно выполняться следующие условия:

  • • последний элемент уг — либо 0, либо 5 по правилу делимости;
  • • первый элемент* не может быть 0, иначе число не четырехзначное.

По правилу произведения получаем 9 • 10 • 10-2= 1800.

Задача 1.105. Рассмотрим первый случай, когда три одинаковые книги стоят рядом на первой полке (рис. 7.1.2).

Рис. 7.1.2. Решение задачи 1.105 (а)

Все остальные восемь книг можно переставлять как угодно, т.е. Р| = 3 • 8!

Рассмотрим второй случай, когда три одинаковые книги стоят рядом на первой полке (рис. 7.1.3).

Рис. 7.1.3. Решение задачи 1.105 (б)

Все остальные восемь книг можно переставлять как угодно, т.е. Р2 = 4 - 8!

По правилу суммы получаем

р= р1 + р2 = 3 • 8! + 4 • 8! = 7 • 8! = 282240.

Задача 1.106. Построим решение от противного. Количество способов расставить книги по двум полкам равно числу размещений на двух полках:

о 11'

А?, = _ = !б5 • 8!

11 3!

Количество способов расставить книги на первой полке так, чтобы они стояли все три рядом, равно 3 • 8!

Тогда количество способов расставить книги так, чтобы одинаковые книги не стояли все три рядом на первой полке, равно

165 8! - 3 8! = 162 - 8! = 6531 840.

Задача 1.107. На одной полке стоит 5 книг, на второй — 6. Известно, что 3 книги одинаковые. Сколькими способами можно рас-ставить книги так, чтобы три одинаковые книги стояли на второй полке?

Три одинаковые книги на второй полке можно расставить , 6'

СІ --= 20 способами.

6 З!-З!

При этом остальные 8 книг можно переставлять как угодно, т.е. Р8 = 8! способами.

По правилу произведения получаем 20 • 8! = 806400.

Задача 1.108. Построим решение от противного. Количество способов расставить книги по двум полкам равно числу размещений на двух полках:

Л,9, = - = 165-8!

11 3!

Количество способов расставить три одинаковые книги на первой

, 5'

полке равно С5 = ——— = 10, при этом все остальные 8 книг переставляем как угодно т.е. Р% = 8! способами. По правилу произведения получаем 10-81 = 403 200.

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

С1 =-:— = 20 способами. При этом остальные 8 книг можно пе-

реставлять как угодно, т.е. Я8 = 8! способами. По правилу произведения получаем 20 • 8! = 806400.

Три книги могут стоять либо на первой полке, либо на второй полке. По правилу суммы получаем, что количество способов расставить книги так, чтобы три одинаковые стояли на одной из полок, равно 30 • 8! = 1 209600.

Тогда количество способов расставить книги так, чтобы три одинаковые книги не стояли ни на одной из полок, равно

  • 165 -8! -30 -8! = 135 -8! = 5443200.
  • 5 X

Задача 1.113. ах = -; ап+1 = —ап.

2 2

Задача 1.114. я, = Ь{ + с,; ап+] = Ьп+] + сп+1

с, = -3.

Задача 1.115. ах

х -1

~т~

X2 + 2 п + 2

Задача 1.116. а. = 1; а2 ---; а =--хя .

3 /7 + 1

 
<<   СОДЕРЖАНИЕ   >>