Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
Когда приехали гости, оказалось, что из этих трех сообщений истинным было только одно. Кто приехал навестить Мишу? ЗАДАЧИ И УПРАЖНЕНИЯ 231 27. В коробке лежат шары: большие и маленькие, красные и зеленые, светлые и темные. Из коробки нужно достать шар, удовлетворяющий следующим условиям: • если шар светлый, то он может быть маленьким тогда и только тогда, когда он красный; • шар может быть большим и светлым, если он зеленый; • если шар большой, то, для того чтобы он был зеленым, достаточно, чтобы он был темным. Свести эти высказывания к двум простейшим. 28. Студенты узнали, что к ним в группу должен прийти новичок, приехавший из другого города. Обсуждая эту новость, они высказали ряд предположе- ний: • для того, чтобы новичок был добрым, достаточно, чтобы он был умным и сильным; • если новичок сильный, то он либо глупый, либо злой; • если новичок умный, то для того чтобы он был добрым, необходимо, чтобы он был сильным. Когда эти высказывания были сведены к двум простейшим, оказалось, что из этих условий выполнено только одно. После этого было высказано еще одно суждение: “Необходимое условие доброты — это ум. Значит, новичок умный, но слабый”. Каким был новичок? 29. Сотрудники фирмы обсуждали вопрос о предстоящей командировке. Были высказаны следующие суждения: • если поедут Иванов и Петров, то надо послать и Сидорова; • Сидоров поедет только при условии, что поедет Иванов; значит, Петрова послать нельзя; • надо послать Иванова или Петрова. Директор сказал, что можно выполнить лишь одно из этих предложений. Кого хотели послать в командировку сотрудники и кого решил послать ди- ректор? Библиографический список [1] Акритас А. Основы компьютерной алгебры с приложениями / А. Акритас. — М. : Мир, 1994. — 544 с. (Гл. 3) 1 [2] Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати. — М. : Наука, 1974. — 368 с. (Гл. 4). [3] Белов В. В. Теория графов / В. В. Белов, Е. М. Воробьев, В. Е. Шаталов. — М. : Высш. школа, 1976. — 392 с. (Гл. 4). [4] Гаврилов Г. П. Задачи и упражнения по дискретной математике / Г. П. Гав- рилов, А. А. Сапоженко. — М. : ФИЗМАТЛИТ, 2005. — 416 с. (Гл. 4–6). [5] Гиндикин С. Г. Алгебра логики в задачах / С. Г. Гиндикин. — М. : Наука, 1972. — 288 с. (Гл. 6). [6] Горбатов В. А. Фундаментальные основы дискретной математики / В. А. Гор- батов. — М. : ФИЗМАТЛИТ, 2000. — 544 с. (Гл. 1, 2, 4, 6). [7] Деньдобренко Б. Н. Автоматизация конструирования РЭА / Б. Н. Деньдоб- ренко, А. С. Малика. — М. : Высш. школа, 1980. — 384 с. (Гл. 4). [8] Ершов Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин. — М. : ФИЗМАТЛИТ, 2011. — 356 с. (Гл. 1, 2, 6). [9] Кнут Д. Искусство программирования для ЭВМ. Т. 1 / Д. Кнут. — М. : Вильямс, 2011. — 712 с. (Гл. 4). [10] Кнут Д. Искусство программирования для ЭВМ. Т. 2 / Д. Кнут. — М. : Вильямс, 2007. — 828 с. (Гл. 4). [11] Кнут Д. Искусство программирования для ЭВМ. Т. 3 / Д. Кнут. — М. : Вильямс, 2007. — 822 с. (Гл. 4). [12] Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофи- дес. — М. : Мир, 1978. — 432 с. (Гл. 4). 1 В скобках указаны номера глав настоящего учебника, при работе над которыми эта литература может оказаться полезной. БИБЛИОГРАФИЧЕСКИЙ СПИСОК 233 [13] Кузнецов О. П. Дискретная математика для инженера / О. П. Кузнецов. — СПб. : Лань, 2009. – 400 с. (Гл. 1, 2, 4, 6). [14] Кук Д. Компьютерная математика / Д. Кук, Г. Бейз. — М. : Наука, 1990. — 384 с. (Гл. 1–4). [15] Курейчик В. М. Математическое обеспечение конструкторского и техноло- гического проектирования с применением САПР / В. М. Курейчик. — М. : Радио и связь, 1990. — 352 с. (Гл. 4). [16] Лавров И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров, Л. Л. Максимова. — М. : ФИЗМАТЛИТ, 2006. — 256 с. (Гл. 1, 2, 6). [17] Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М. : Наука, 1990. — 384 с. (Гл. 4). [18] Липский В. Комбинаторика для программистов / В. Липский. — М. : Мир, 1988. — 213 с. (Гл. 4, 5). [19] Логический подход к искусственному интеллекту: От классической логики к логическому программированию / А. Тейз и др. — М. : Мир, 1990. — 429 с. (Гл. 4). [20] Мадер В.В. Школьнику об алгебре логики / В. В. Мадер. — М. : Просвещение, 1993. — 128 с. (Гл. 6) [21] Мендельсон Э. Введение в математическую логику / Э. Мендельсон. — М. : Наука, 1984. — 320 с. (Гл. 1, 2). [22] Нефедов В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипо- ва. — М. : Изд-во МАИ, 1992. — 264 с. (Гл. 1, 2, 4–6). [23] Новиков Ф. А. Дискретная математика для программистов / Ф. А. Нови- ков. — СПб : Питер, 2013. — 432 с. (Гл. 1, 2, 4–6). [24] Общая алгебра / О. В. Мельников и др.; Под ред. Л. А. Скорнякова. — М. : Наука, 1990. — Т. 1. — 592 с. (Гл. 1, 2). [25] Общая алгебра / В. А. Артамонов и др.; Под ред. Л. А. Скорнякова. — М. : Наука, 1990. — Т. 2 — 479 с. (Гл. 1, 2). [26] Оре О. Теория графов / О. Оре. — М. : УРСС, 2009. — 354 с. (Гл. 4). 234 БИБЛИОГРАФИЧЕСКИЙ СПИСОК [27] Рейнгольд Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. — М. : Мир, 1980. — 476 с. (Гл. 4, 5). [28] Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. — М. : Мир, 1984. — 454 с. (Гл. 4). [29] Столл Р. Множества. Логика. Аксиоматические теории / Р. Столл. — М. : Просвещение, 1968. — 232 с. (Гл. 1, 2, 6). [30] Фридман А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. — М. : Мир, 1978. — 580 с. (Гл. 6). [31] Фудзисава Т. Математика для радиоинженеров: Теория дискретных струк- тур / Т. Фудзисава, Т. Касами. — М. : Радио и связь, 2012. — 242 с. (Гл. 1, 2, 4–6). [32] Харари Ф. Теория графов / Ф. Харари. — М. : УРСС, 2015. — 304 с. (Гл. 4). [33] Холл М. Комбинаторика / М. Холл. — М. : Мир, 1970. — 424 с. (Гл. 5). [34] Чень Ч. Математическая логика и автоматическое доказательство теорем / Ч. Чень, Р. Ли. — М. : Наука, 1983. — 360 с. (Гл. 6). [35] Шенфилд Дж. Математическая логика / Дж. Шенфилд. — М. : Наука, 1975. — 528 с. (Гл. 1, 2, 6). [36] Яблонский С. В. Введение в дискретную математику / С. В. Яблонский. — М. : Высшая школа, 2010. — 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. Составьте таблицы истинности формул. 236 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 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. ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 237 Вариант 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). 238 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 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). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 239 Вариант 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). 240 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 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). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 241 Вариант 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: ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ @ • • |