Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. — М. : Мир, 1984. — 454 с. (Гл. 4). [30] Столл Р. Множества. Логика. Аксиоматические теории / Р. Столл. — М. : Просвещение, 1968. — 232 с. (Гл. 1, 2, 6). [31] Фридман А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. — М. : Мир, 1978. — 580 с. (Гл. 6). [32] Фудзисава Т. Математика для радиоинженеров: Теория дискретных струк- тур / Т. Фудзисава, Т. Касами. — М. : Радио и связь, 1984. — 240 с. (Гл. 1, 2, 4–6). [33] Харари Ф. Теория графов / Ф. Харари. — М. : Едиториал УРСС, 2003. — 300 с. (Гл. 4). [34] Холл М. Комбинаторика / М. Холл. — М. : Мир, 1970. — 424 с. (Гл. 5). [35] Чень Ч. Математическая логика и автоматическое доказательство теорем / Ч. Чень, Р. Ли. — М. : Наука, 1983. — 360 с. (Гл. 6). [36] Шенфилд Дж. Математическая логика / Дж. Шенфилд. — М. : Наука, 1975. — 528 с. (Гл. 1, 2, 6). [37] Яблонский С. В. Введение в дискретную матаматику / С. В. Яблонский. — М. : Наука, 1986. — 384 с. (Гл. 4, 6). П р и л о ж е н и е Варианты типового расчета Условия задач 1. Докажите тождества, используя только определения операций над мно- жествами. 2. Докажите методом математической индукции. 3. Докажите утверждение. 4. Пусть A = {a, b, c}, B = {1, 2, 3, 4}, P 1 ⊆ A × B, P 2 ⊆ B 2 . Изобра- зите отношения P 1 и P 2 графически. Найдите [(P 1 ◦ P 2 ) −1 ]. Проверьте с помощью матрицы [P 2 ], является ли отношение P 2 рефлексивным, симметричным, антисимметричным, транзитивным? 5. Найдите область определения, область значений отношения P . Явля- ется ли отношение P рефлексивным, симметричным, антисимметрич- ным, транзитивным? 6. Является ли алгеброй следующий набор B = hB; Σi? 7. Постройте подсистему B(X), если... 8. Используя многомодульную арифметику с вектором оснований β, вычислить a + b, a − b, 3 · a, 17 −1 (mod β), 2/13 − 5/19. Каков знак числа x в симметричной системе относительно β? 9. Даны графы G 1 и G 2 . Найдите G 1 ∪ G 2 , G 1 ∩ G 2 , G 1 ⊕ G 2 , G 1 × G 2 . Для графа G 1 ∪ G 2 найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1. 10. Найдите матрицы фундаментальных циклов, фундаментальных разре- зов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным? 11. Составьте таблицы истинности формул. ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 239 12. Проверьте двумя способами, будут ли эквивалентны следующие фор- мулы... а) составлением таблиц истинности; б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований. 13. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина. 14. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f (x, y, z) двумя способами: а) методом Квайна; б) с помощью карт Карно. Каким классам Поста принадлежит эта функция? 15. С помощью карт Карно найдите сокращенную, все тупиковые и мини- мальные ДНФ, КНФ булевой функции f (x 1 , x 2 , x 3 , x 4 ), заданной век- тором своих значений. 16. Является ли полной система функций J? Образует ли она базис? 17. С помощью алгебры логики проверьте истинность соотношения для любых множеств A, B, C. Если соотношение неверно, постройте контр- пример. 18. С помощью алгебры логики докажите первое тождество из задания 1. 240 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 1 1. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A × (B ∪ C) = (A × B) ∪ (A × C). 2. 7 n − 1 кратно 6 для всех n > 1. 3. |A| > ω, |B| < ω ⇒ |A \ B| = |A|. 4. P 1 = {ha, 1i, ha, 2i, hb, 3i, hc, 2i, hc, 3i, hc, 4i}, P 2 = {h1, 1i, h2, 1i, h2, 2i, h2, 3i, h2, 4i, h3, 3i, h4, 4i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x 2 + y 2 = 1. 6. hω; +, 0i. 7. B = hZ; +, −i, X = {−5, 4}. 8. β = [5, 7, 11, 2], a = 34, b = 58, x = [2, 5, 1, 1]. 9. G 1 : • • • • - - ¡ ¡ ¡ µ h h 1 2 4 3 G 2 : A A A • • • h h 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ • • • • • • • • 11. x ∨ y ↔ y ↓ x, x | y → (z ⊕ xy). 12. x → (y ⊕ z) и x → y ⊕ x → z. 13. x ∨ y → (z ⊕ x). 14. f (0, 1, 0) = f (1, 0, 0) = f (1, 0, 1) = 0. 15. (1101 1101 0011 0011). 16. J = {x ∨ y, x ⊕ y}. 17. (A ∪ B) \ (C ∩ A) = (B \ C) \ (A ∪ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 241 Вариант 2 1. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), (A ∪ B) × C = (A × C) ∪ (B × C). 2. n 3 + 11n кратно 6 для всех n ∈ ω. 3. ω + ω = ω. 4. P 1 = {ha, 1i, ha, 2i, ha, 3i, ha, 4i, hb, 3i, hc, 2i}, P 2 = {h1, 1i, h1, 4i, h2, 2i, h2, 3i, h3, 3i, h3, 2i, h4, 1i, h4, 4i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x · y > 1. 6. hQ \ Z; +, ·, :i. 7. B = hZ; +, ·i, X = {−5}. 8. β = [3, 7, 11, 2], a = 32, b = 74, x = [1, 4, 7, 0]. 9. G 1 : • • • • - ¾ ¡ ¡ ¡ @ @ @ h 1 2 4 3 G 2 : • • • A A AU ¢ ¢ ¢® h 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ©© ©© ©©@ @ @ • • • • • • • • 11. (x ↔ y) ∨ y ↓ x, ((x → y) | z) ⊕ xy. 12. x | (y → z) и x | y → x | z. 13. x ∨ y → (z ⊕ x). 14. f (0, 1, 1) = f (1, 0, 0) = f (1, 1, 0) = 0. 15. (1111 1100 1011 1011). 16. J = {x → y, x ∧ y}. 17. (A ∪ B) \ (C ∩ B) = (A \ C) ∪ (A \ B). 242 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 3 1. A ∩ B = A ∪ B, A × (B \ C) = (A × B) \ (A × C). 2. 1 · 4 + 2 · 7 + 3 · 10 + . . . + n(3n + 1) = n(n + 1) 2 3. [0, 1] ∪ [2, 3] ∼ [0, 1]. 4. P 1 = {ha, 1i, ha, 2i, ha, 4i, hc, 3i, hc, 2i, hc, 4i}, P 2 = {h2, 1i, h3, 1i, h3, 2i, h4, 1i, h4, 3i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ y = |x|. 6. hR; ·, :, −1i. 7. B = hZ; +, −i, X = {−3, 4}. 8. β = [7, 11, 5, 2], a = 24, b = 67, x = [5, 2, 1, 1]. 9. G 1 : • • • • 6 - ¡ ¡ ¡ ª h 1 2 4 3 G 2 : • • • ¾ ¢ ¢ ¢¸ A A AK h 3 2 1 10. G: @ @ @©© ©© ©© ¡ ¡ ¡ ¡ ¡ ¡ • • • • • • • • 11. x ∨ y ↔ y ↓ x, x | y → z ⊕ xy. 12. x ∧ (y ⊕ z) и x ∧ y ⊕ x ∧ z. 13. x ∨ y → z ⊕ x. 14. f (0, 0, 0) = f (0, 0, 1) = f (1, 0, 1) = f (1, 1, 1) = 1. 15. (1110 0101 0011 0101). 16. J = {x ↔ y, x | y}. 17. (A ∪ C) \ (B ∩ A) = (A \ B) \ (A ∩ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 243 Вариант 4 1. A \ (B ∪ C) = (A \ B) ∩ (A \ C), A × (B ∩ C) = (A × B) ∩ (A × C). 2. 10 n − 1 кратно 9 для всех n ∈ ω. 3. 2 ω + 2 ω = 2 ω 4. P 1 = {ha, 1i, ha, 2i, hb, 2i, hb, 4i, hc, 3i, hc, 2i}, P 2 = {h1, 1i, h1, 2i, h2, 2i, h3, 3i, h4, 3i, h4, 4i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x 2 + x = y 2 + y. 6. hR; p , −i. 7. B = hZ; +, −i, X = {4, 10}. 8. β = [7, 11, 3, 2], a = 46, b = 38, x = [4, 5, 2, 0]. 9. G 1 : h h • • • • ¡ ¡ ¡ @ @ @ 1 2 4 3 G 2 : • • • - A A AU ¢ ¢ ¢® h 3 2 1 10. G: @ @ @ @ @ @ ©© ©© ©© ©© ©© ©© ¡ ¡ ¡ ¡ ¡ ¡ • • • • • • • • 11. (x ↔ y) ∨ y ↓ x, (x → y) | z ⊕ xy. 12. x ∨ (y ⊕ z) и (x ∨ y) ⊕ (x ∨ z). 13. (x ∨ y) → (z ↔ x). 14. f (0, 0, 1) = f (1, 1, 1) = f (1, 1, 0) = 0. 15. (1101 0011 1101 0011). 16. J = {x ⊕ y, x ∨ y}. 17. (A ∩ B) ∪ (A \ C) = A \ (B ∪ C). 244 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 5 1. (A ∪ B) \ C = (A \ C) ∪ (B \ C), (A ∩ B) × C = (A × C) ∩ (B × C). 2. 1 · 2 + 2 · 3 + 3 · 4 + . . . + n(n + 1) = n(n + 1)(n + 2) 3 3. [a, b] ∼ R. 4. P 1 = {ha, 1i, ha, 4i, hb, 2i, hb, 3i, hc, 1i, hc, 4i}, P 2 = {h1, 1i, h1, 4i, h2, 1i, h3, 4i, h4, 3i, h4, 1i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x − y ∈ Z. 6. hQ; p , :i. 7. B = hω; +, ·, 3i, X = {2, 5}. 8. β = [11, 7, 3, 2], a = 67, b = 79, x = [6, 5, 1, 0]. 9. G 1 : • • • • h h h h 6 @ @ @ I ¡ ¡ ¡ ª 1 2 4 3 G 2 : • • • ¢ ¢ ¢¸ - h h 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ @ • • • • • • • • 11. x ∨ y → (y ⊕ x), ((x ↔ y) | z) ↓ xy. 12. x ∧ (y → z) и x ∧ y → x ∧ z. 13. x ∨ y → (z ↔ x). 14. f (0, 0, 0) = f (1, 1, 1) = f (1, 1, 0) = 0. 15. (1100 1011 1111 1011). 16. J = {x → y, x ∧ y}. 17. (A \ B) ∪ (A \ C) = A \ (B ∪ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 245 Вариант 6 1. A ∪ B = A ∩ B, (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D). 2. 1 1 · 2 + 1 2 · 3 + 1 3 · 4 + . . . + 1 n(n + 1) = n n + 1 3. |Z × Q| = ω. 4. P 1 = {ha, 1i, ha, 2i, ha, 4i, hb, 1i, hb, 4i, hc, 3i}, P 2 = {h1, 1i, h2, 4i, h2, 1i, h3, 3i, h4, 2i, h4, 1i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x + y = −2. 6. hZ; +, −, −2i. 7. B = hR \ {0}; :, 1i, X = {2}. 8. β = [11, 5, 7, 2], a = 58, b = 37, x = [7, 2, 1, 0]. 9. G 1 : • • • • 6 - ? ¾ h 1 2 4 3 G 2 : • • • -A A AK ¢ ¢ ¢® h 3 2 1 10. G: @ @ @ @ @ @ ¡ ¡ ¡ HH HH HH • • • • • • • • 11. x ⊕ y ↔ y | x, (x ↓ y ↔ z) ∨ xy. 12. x ∧ (y ↔ z) и x ∧ y ↔ x ∧ z. 13. x | y ⊕ z → x. 14. f (0, 0, 1) = f (0, 1, 1) = f (1, 1, 0) = f (1, 1, 1) = 1. 15. (0101 0101 1110 0011). 16. J = {x ↔ y, x | y}. 17. (A \ B) ∩ (A \ C) = A \ (B ∩ C). 246 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 7 1. A \ (B ∩ C) = (A \ B) ∪ (A \ C), (A \ B) × C = (A × C) \ (B × C). 2. µ 1 − 1 4 ¶ µ 1 − 1 9 ¶ µ 1 − 1 16 ¶ . . . µ 1 − 1 n 2 ¶ = n + 1 2n для n > 2. 3. [0, 1] ∼ [0, 1). 4. P 1 = {ha, 1i, hb, 3i, hb, 1i, hb, 4i, hc, 3i, hc, 2i}, P 2 = {h1, 3i, h1, 4i, h2, 2i, h3, 3i, h4, 3i, h4, 4i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x 2 + y 2 = 4. 6. hω; :, −1i. 7. B = hR 2 ; +, −i, X = {h1, 2i, h0, 1i}. 8. β = [5, 3, 11, 2], a = 44, b = 59, x = [3, 2, 7, 1]. 9. G 1 : • • • • ¡ ¡ ¡ h 1 2 4 3 G 2 : • • • ¢ ¢ ¢® - h h 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ©© ©© ©© ©© ©© ©© • • • • • • • • 11. (x ∨ y) ↓ (y → x), x | y ↔ z ⊕ xy. 12. x ∧ y | z и x ∧ y | (x ∧ z). 13. z → x ↔ y | x. 14. f (0, 0, 0) = f (1, 0, 1) = f (1, 1, 1) = 0. 15. (0011 0011 1101 1101). 16. J = {x ⊕ y, x ∨ y}. 17. (A ⊕ B) \ (A ⊕ C) = A \ (B ⊕ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 247 Вариант 8 1. A ∪ B = A ∩ B, C ⊆ D ⇒ A × C ⊆ B × D. 2. 1 2 + 2 2 + 3 2 + . . . + n 2 = n(n + 1)(2n + 1) 6 3. [0, 1] ∼ (0, 1]. 4. P 1 = {ha, 1i, hb, 3i, hc, 1i, hc, 4i, hc, 3i, hc, 2i}, P 2 = {h1, 1i, h1, 2i, h1, 4i, h2, 1i, h2, 2i, h2, 3i h3, 3i, h3, 2i, h3, 4i, h4, 3i, h4, 4i, h4, 1i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ y < x − 1. 6. hR \ Z; +, ·i. 7. B = hQ; ·, 1 2 i, X = {3}. 8. β = [3, 11, 7, 2], a = 21, b = 77, x = [2, 8, 3, 1]. 9. G 1 : • • • • h h 1 2 4 3 G 2 : • • • ¢ ¢ ¢® A A AU - h h 3 2 1 10. G: ¡ ¡ ¡ @ @ @ • • • • • • • • 11. (x ⊕ y) → y ↓ x, x | y ∨ z ↔ xy. 12. |