Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
Скачать 1.36 Mb.
|
а){→, ¬}; б) {↔, ⊕}; в) {↓}; г) {∧, →, Какие из указанных систем образуют базис? После изучения главы 4 выполняются задачи 10–16 контрольной работы. Задача 10 решается аналогично примеру 4.1.1, задача 11 — аналогично примерами, задача 12 — аналогично примерами, задача 13 — аналогично примерами, задача 14 — аналогично примеру 4.7.3, задача 15 — аналогично примеру 4.9.3, а задачи 16 и 17 — аналогично примеру 4.11.1. Варианты контрольной работы Условия задач. Докажите тождества, используя только определения операций надмножествами. Докажите методом математической индукции. Докажите утверждение. A = {a, b, c}, B = {1, 2, 3, 4}, P 1 ⊆ A × B, P 2 ⊆ B 2 . Изобразите, графически. Найдите [(P 1 ◦ P 2 ) −1 ]. Проверьте с помощью матрицы [P 2 ], является ли отношение рефлексивным, симметричным, антисимметричным, транзитивным. Найдите область определения, область значений отношения P Является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным. Является ли алгеброй следующий набор B = B; Σ ? 7. Постройте подсистему B(X), если. Даны графы и G 2 . Найдите G 1 ∪ G 2 , G 1 ∩ G 2 , G 1 ⊕ G 2 , G 1 × Для графа найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины, исходящие из вершины 1. 9. Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным. Составьте таблицы истинности формул. Проверьте двумя способами, будут ли эквивалентны следующие формулы... а) составлением таблиц истинности; б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина. ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f (x, y, z) двумя способами: а) методом Квайна; б) с помощью карт Карно. Каким классам Поста принадлежит эта функция. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ, КНФ булевой функции f (x 1 , x 2 , x 3 , x 4 ), заданной вектором своих значений. Является ли полной система функций Образует ли она базис. С помощью алгебры логики проверьте истинность соотношения для любых множеств A, B, C. Если соотношение неверно, постройте контрпример. С помощью алгебры логики докажите первое тождество из задания ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 119 Вариант 1 1. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A × (B ∪ C) = (A × B) ∪ (A × C). 2. n 7 − n кратно 7 для всех n > 0. 3. |Q 2 | = ω. 4. P 1 = { a, 3 , a, 2 , a, 4 , b, 1 , c, 2 , c, 4 , c, 3 }, P 2 = { 1, 1 , 2, 2 , 2, 1 , 3, 3 , 4, 4 , 4, 3 , 1, 4 , 2, 4 , 3, 2 , 3, 4 }. 5. P ⊆ (Z + ) 2 , x, y ∈ P ⇔ x 2 = где Z + = {x ∈ Z | x > 0}. 6. Z; +, ·, 1 − ı . 7. B = C; · , X = {e ı π 4 }. 8. G 1 : • • • • E E h h 1 2 4 3 G 2 : e e e • • • h h 3 2 1 9. G: d d d d d d • • • • • • • • 10. (x ∧ y) ↔ (y ↓ x), (x → y)|(z ⊕ x ∨ y). 11. x ↔ (y ⊕ z) и (x ↔ y) ⊕ (x ↔ z). 12. (x ∨ y) → (z ↔ x). 13. f (0, 0, 1) = f (0, 1, 1) = f (1, 1, 0) = 0. 14. (0011 0011 0101 1100). 15. J = {x → y, x ∧ y}. 16. (A \ B) \ (A ∩ C) = A \ (B ∪ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 2 1. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), (A ∪ B) × C = (A × C) ∪ (B × C). 2. 7 n − 1 кратно 6 для всех n 1. 3. A B∪C ∼ A B × A C , если B ∩ C = ∅. 4. P 1 = { b, 2 , a, 3 , b, 1 , b, 4 , c, 1 , c, 2 , c, 4 }, P 2 = { 1, 1 , 1, 2 , 1, 4 , 2, 2 , 2, 4 , 3, 3 , 3, 2 , 3, 4 , 4, 4 }. 5. P ⊆ (Z + ) 2 , x, y ∈ P ⇔ x 2 = где Z + = {x ∈ Z | x > 0}. 6. C \ {0}; +, · . 7. B = C; +, · , X = {2 ı}. 8. G 1 : • • • • E ' d d d h 1 2 4 3 G 2 : • • • e e e ¡ ¡ ¡ h 3 2 1 9. G: ¨¨ ¨¨ ¨¨d d d • • • • • • • • 10. (x ↓ (y ⊕ (y → x)), x ∨ (y|z ⊕ xy). 11. x → (y ↓ z) и (x → y) ↓ (x → z). 12. ((x ↔ y)|z) ⊕ y. 13. f (0, 0, 0) = f (0, 0, 1) = f (1, 0, 0) = f (1, 1, 0) = 0. 14. (1110 1001 0111 0001). 15. J = {x ↓ y, x ↔ y}. 16. (A ⊕ B) ∩ (A ⊕ C) = A \ (B ∩ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 121 Вариант 3 1. A ∩ B = A ∪ B, A × (B \ C) = (A × B) \ (A × C). 2. n 3 + 11n кратно 6 для всех n ∈ ω. 3. |A| ω, |B| < ω ⇒ |A \ B| = |A|. 4. P 1 = { a, 2 , a, 3 , a, 4 , b, 3 , c, 1 , c, 4 }, P 2 = { 1, 1 , 2, 3 , 2, 2 , 3, 4 , 1, 4 , 2, 4 , 4, 2 }. 5. P ⊆ (Z + ) 2 , x, y ∈ P ⇔ x 2 > где Z + = {x ∈ Z | x > 0}. 6. C \ R; +, −, , 2 − ı . 7. B = C; · , X = {3 ı}. 8. G 1 : • • • • T E © h 1 2 4 3 G 2 : • • • ' ¡ ¡ ¡! e e eu h 3 2 1 9. G: d d d¨¨ ¨¨ ¨¨ • • • • • • • • 10. x|(y ⊕ (y ∨ x)), x → (y ↓ (z ↔ xy)). 11. x ↓ (y|z) и (x ↓ y)|(x ↓ z). 12. ((x ↓ y) → (z ↔ y). 13. f (0, 1, 1) = f (1, 0, 0) = f (1, 0, 1) = 1. 14. (0001 0011 1100 1110). 15. J = {x ⊕ y, x ∨ y}. 16. (A ∪ B) ⊕ (A ∩ C) = A ⊕ (B \ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 4 1. A \ (B ∪ C) = (A \ B) ∩ (A \ C), A × (B ∩ C) = (A × B) ∩ (A × C). 2. 1 · 4 + 2 · 7 + 3 · 10 + · · · + n(3n + 1) = n(n + 1) 2 3. ω + ω = ω. 4. P 1 = { a, 1 , a, 2 , b, 3 , c, 2 , c, 3 , c, 4 }, P 2 = { 1, 1 , 2, 1 , 2, 2 , 2, 3 , 2, 4 , 3, 3 , 4, 4 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x 2 + y 2 = 1. 6. C \ R; +, ·, : . 7. B = C; +, ı , X = R. 8. G 1 : h h • • • • d d d 1 2 4 3 G 2 : • • • E e e e ¡ ¡ ¡ h 3 2 1 9. G: d d d d d d ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ • • • • • • • • 10. x ⊕ (y → (y ↔ x)), x ↓ (y|(z ∨ xy)). 11. x ↔ (y|z) и (x ↔ y)|(x ↔ z). 12. ((x ↓ y) → z) ↔ y. 13. f (0, 0, 1) = f (1, 0, 0) = f (1, 1, 0) = 1. 14. (0011 1100 0011 0101). 15. J = {x ∧ y, x → y}. 16. (A ∪ B) \ (B ∩ C) = (A \ B) ∪ (A \ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 123 Вариант 5 1. (A ∪ B) \ C = (A \ C) ∪ (B \ C), (A ∩ B) × C = (A × C) ∩ (B × C). 2. 10 n − 1 кратно 9 для всех n ∈ ω. 3. [0, 1] ∪ [2, 3] ∼ [0, 1]. 4. P 1 = { a, 1 , a, 2 , a, 3 , a, 4 , b, 3 , c, 2 }, P 2 = { 1, 1 , 1, 4 , 2, 2 , 2, 3 , 3, 3 , 3, 2 , 4, 1 , 4, 4 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x · y > 1. 6. ω; +, 0 . 7. B = Z; +, − , X = {−5, 4}. 8. G 1 : • • • • h h h h T d d d s © 1 2 4 3 G 2 : • • • ¡ ¡ ¡! E h h 3 2 1 9. G: d d d d d d d d d • • • • • • • • 10. (x ∨ y) → (y ⊕ x), x ↓ (y ↔ (z ↓ xy)). 11. x → (y ↔ z) и (x → y) ↔ (x → z). 12. x ∨ y → (z ↔ y). 13. f (0, 1, 1) = f (0, 1, 0) = f (1, 0, 0) = f (1, 0, 1) = 0. 14. (1010 0010 1101 0111). 15. J = {x ↓ y, x ↔ y}. 16. (A \ B) ∪ (C \ B) = (B ∪ C) \ A. ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 6 1. A ∪ B = A ∩ B, (A ∩ (B) × (C ∩ D) = (A × C) ∩ (B × D). 2. 1 · 2 + 2 · 3 + 3 · 4 + . . . + n(n + 1) = n(n+1)(n+2) 3 3. 2 ω + 2 ω = 2 ω 4. P 1 = { a, 1 , a, 2 , a, 4 , c, 3 , c, 2 , c, 4 }, P 2 = { 2, 1 , 3, 1 , 3, 2 , 4, 1 , 4, 3 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ y = |x|. 6. Q \ Z; +, ·, : . 7. B = Z; +, · , X = {−5}. 8. G 1 : • • • • T E c ' h 1 2 4 3 G 2 : • • • Ee e eu ¡ ¡ ¡ h 3 2 1 9. G: d d d d d d rr rr rr • • • • • • • • 10. x ↔ (y ∧ (y → x)), x ∨ (y ⊕ (z ↓ x|y)). 11. x → (y ↓ z) и (x → y) ↓ (x → z). 12. ((x ↔ y) → z)|y. 13. f (0, 1, 1) = f (0, 1, 0) = f (1, 0, 1) = f (1, 1, 1) = 1. 14. (0011 1101 0010 1100). 15. J = {x ∨ y, x ↔ y}. 16. A \ (B \ C) = (A \ B) \ C. ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 125 Вариант 7 1. A \ (B ∩ C) = (A \ B) ∪ (A \ C), (A \ B) × C = (A × C) \ (B × C). 2. 1 1·2 + 1 2·3 + 1 3·4 + . . . + 1 n(n+1) = n n+1 3. [a, b] ∼ R. 4. P 1 = { a, 1 , a, 2 , b, 2 , b, 4 , c, 3 , c, 2 }, P 2 = { 1, 1 , 1, 2 , 2, 2 , 3, 3 , 4, 3 , 4, 4 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x 2 + x = y 2 + y. 6. R; ·, :, −1 . 7. B = Z; +, − , X = {−3, 4}. 8. G 1 : • • • • h 1 2 4 3 G 2 : • • • ¡ ¡ ¡ E h h 3 2 1 9. G: ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ • • • • • • • • 10. (x ∨ y) ↔ (y ↓ x), x|y) → (z ⊕ xy). 11. x → (y ⊕ z) и (x → y) ⊕ (x → z). 12. (x ∨ y) → (z ⊕ x). 13. f (0, 1, 0) = f (1, 0, 0) = f (1, 0, 1) = 0. 14. (1101 1101 0011 0011). 15. J = {x ∨ y, x ⊕ y}. 16. (A ∪ B) \ (C ∩ A) = (B \ C) \ (A ∪ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 8 1. A ∪ B = A ∩ B, C ⊆ D ⇒ A × C ⊆ B × D. 2. (1 − 1 4 )(1 − 1 9 )(1 − 1 16 ) . . . (1 − 1 n 2 ) = n+1 2n для n 2. 3. |Z × Q| = ω. 4. P 1 = { a, 1 , a, 4 , b, 2 , b, 3 , c, 1 , c, 4 }, P 2 = { 1, 1 , 1, 4 , 2, 1 , 3, 4 , 4, 3 , 4, 1 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x − y ∈ Z. 6. R; , − . 7. B = Z; +, − , X = {4, 10}. 8. G 1 : • • • • h h 1 2 4 3 G 2 : • • • ¡ ¡ ¡ e e e E h h 3 2 1 9. G: d d d • • • • • • • • 10. (x ↔ y) ∨ (y ↓ x), ((x → y)|z) ⊕ xy. 11. x|(y → z) и (x|y) → (x|z). 12. (x ∨ y) → (z ⊕ x). 13. f (0, 1, 1) = f (1, 0, 0) = f (1, 1, 0) = 0. 14. (1111 1100 1011 1011). 15. J = {x → y, x ∧ y}. 16. (A ∪ B) \ (C ∩ B) = (A \ C) ∪ (A \ B). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 127 Вариант 9 1. (A ∩ B) \ C = (A \ C) ∩ (B \ C), (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 = { a, 1 , a, 2 , a, 4 , b, 1 , b, 4 , c, 3 }, P 2 = { 1, 1 , 2, 4 , 2, 1 , 3, 3 , 4, 2 , 4, 1 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x + y = −2. 6. Q; , : . 7. B = ω; +, ·, 3 , X = {2, 5}. 8. G 1 : • • • • d d d h 1 2 4 3 G 2 : • • • e e e ¡ ¡ ¡' h 3 2 1 9. G: d d d • • • • • • • • 10. (x ∨ y) ↔ (y ↓ x), ((x|y) → z) ⊕ xy. 11. x ∧ (y ⊕ z) и (x ∧ y) ⊕ (x ∧ z). 12. (x ∨ y) → (z ⊕ x). 13. f (0, 0, 0) = f (0, 0, 1) = f (1, 0, 1) = f (1, 1, 1) = 1. 14. (1110 0101 0011 0101). 15. J = {x ↔ y, x|y}. 16. (A ∪ C) \ (B ∩ A) = (A \ B) \ (A ∩ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 10 1. A ∪ (A ∩ B) = A ∩ (A ∪ B) = A, (A ∪ B) × (C ∪ D) = (A × C) ∪ (B × C) ∪ (A × D) ∪ (B × D). 2. 1 2! + 2 3! + . . . + n−1 n! = 1 для n 2. 3. [0, 1] ∼ (0, 1]. 4. P 1 = { a, 1 , b, 3 , b, 1 , b, 4 , c, 3 , c, 2 }, P 2 = { 1, 3 , 1, 4 , 2, 2 , 3, 3 , 4, 3 , 4, 4 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x 2 + y 2 = 4. 6. Z; +, −, −2 . 7. B = R \ {0}; :, 1 , X = {2}. 8. G 1 : • • • • T E E d d d c h 1 2 4 3 G 2 : • • • ¡ ¡ ¡e e e ' h 3 2 1 9. G: ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ rr rr rr d d d • • • • • • • • 10. (x ↔ y) ∨ (y ↓ x), ((x → y)|z) ⊕ xy. 11. x ∧ (y ⊕ z) и (x ∧ y) ⊕ (x ∧ z). 12. (x ∨ y) → (z ↔ x). 13. f (0, 0, 1) = f (1, 1, 1) = f (1, 1, 0) = 0. 14. (1101 0011 1101 0011). 15. J = {x ⊕ y, x ∨ y}. 16. (A ∩ B) ∪ (A \ C) = A \ (B ∪ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 129 Вариант 11 1. (A \ B) \ C = A \ (B ∪ C), A ⊆ C, B ⊆ D ⇒ A × B = (A × D) ∩ (C × B). 2. 1 · 2 + 2 · 5 + 3 · 8 + . . . + n(3n − 1) = n 2 (n + 1). 3. ω 2 ∼ ω 3 4. P 1 = { a, 1 , b, 3 , c, 1 , c, 4 , c, 3 , c, 2 }, P 2 = { 1, 1 , 1, 2 , 1, 4 , 2, 1 , 2, 2 , 2, 3 3, 3 , 3, 2 , 3, 4 , 4, 3 , 4, 4 , 4, 1 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ y < x − 1. 6. P 1 = { a, 2 , a, 4 , b, 3 , c, 1 , c, 2 }, P 2 = { 1, 1 , 1, 3 , 2, 4 , 3, 1 , 3, 4 , 4, 3 , 4, 2 }. 7. P ⊆ Z 2 , x, y ∈ P ⇔ x 2 + y 2 = 1. 8. Q; , ·, −10 . 9. B = Z 3 ; +, − , X = { 0, 1, 1 , 0, 0, 1 }. 10. G 1 : • • • • d d d s T h 1 2 4 3 G 2 : • • • ¡ ¡ ¡! Ee e e h 3 2 1 11. G: d d d d d d • • • • • • • • 12. (x ∨ y) → (y ⊕ x), ((x ↔ y)|z) ↓ xy. 13. x ∧ (y → z) и (x ∧ y) → (x ∧ z). 14. (x ∨ y) → (z ↔ x). 15. f (0, 0, 0) = f (1, 1, 1) = f (1, 1, 0) = 0. 16. (1100 1011 1111 1011). 17. J = {x → y, x ∧ y}. 18. (A \ B) ∪ (A \ C) = A \ (B ∪ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 12 1. A \ (B \ C) = (A \ B) ∪ (A ∩ C), U 2 \ (A × B) = (A × U) ∪ (U × B). 2. n 3 + 5n кратно 6 для всех n ∈ ω. 3. ω + n = ω. 4. P 1 = { a, 1 , a, 2 , a, 4 , b, 3 , c, 1 , c, 4 }, P 2 = { 1, 3 , 1, 2 , 2, 3 , 3, 2 , 3, 4 , 4, 1 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x 2 = y. 6. R \ Z; +, · . 7. B = Q; ·, 1 2 , X = {3}. 8. G 1 : h h h h • • • • 1 2 4 3 G 2 : h h h • • • E ¡ ¡ ¡!e e e 3 2 1 9. G: d d d d d d ¨¨ ¨¨ ¨¨ • • • • • • • • 10. (x ⊕ y) ↔ (y|x), ((x ↓ y) ↔ z) ∨ xy. 11. x ∧ (y ↔ z) и (x ∧ y) ↔ (x ∧ z). 12. (x|y) ⊕ (z → x). 13. f (0, 0, 1) = f (0, 1, 1) = f (1, 1, 0) = f (1, 1, 1) = 1. 14. (0101 0101 1110 0011). 15. J = {x ↔ y, x|y}. 16. (A \ B) ∩ (A \ C) = A \ (B ∩ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 131 Вариант 13 1. A ∪ (B \ C) = (A ∪ B) \ (C \ A); A, B = ∅, (A × B) ∪ (B × A) = (C × D) ⇒ A = B = C = D. 2. 4 n − 1 кратно 3 для всех n > 0. 3. ω 2 ∼ Z. 4. P 1 = { a, 3 , a, 2 , b, 2 , b, 3 , c, 1 , c, 4 }, P 2 = { 1, 1 , 1, 2 , 2, 2 , 3, 3 , 4, 1 , 4, 4 }. 5. P ⊆ R 2 , x, y ∈ P ⇔ x 2 y. 6. Q; +, −, :, 1 3 7. B = Z; +, · , X = {−2, 16}. 8. G 1 : • • • • ' ' d d d 1 2 4 3 G 2 : • • • Ee e eu ¡ ¡ ¡ h 3 2 1 9. G: d d d • • • • • • • • 10. (x ∨ y) ↓ (y → x), ((x|y) ↔ z) ⊕ xy. 11. x ∧ (y|z) и (x ∧ y)|(x ∧ z). 12. (z → x) ↔ (y|x). 13. f (0, 0, 0) = f (1, 0, 1) = f (1, 1, 1) = 0. 14. (0011 0011 1101 1101). 15. J = {x ⊕ y, x ∨ y}. 16. (A ⊕ B) \ (A ⊕ C) = A \ (B ⊕ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 14 1. A ∩ (B \ C) = (A ∩ B) \ (A ∩ C), (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D). 2. 4 n + 15n − 1 кратно 9 для всех натуральных n. 3. ω 2 ∼ Z 2 4. P 1 = { a, 2 , a, 4 , b, 3 , c, 1 , c, 2 }, P 2 = { 1, 1 , 1, 3 , 2, 4 , 3, 1 , 3, 4 , 4, 3 , 4, 2 }. 5. P ⊆ Z 2 , x, y ∈ P ⇔ x 2 + y 2 = 1. 6. R \ {0}; +, : . 7. B = Q; +, · , X = {2, 1 2 }. 8. G 1 : h h h h • • • • 1 2 4 3 G 2 : • • • e e e h h 3 2 1 9. G: d d d • • • • • • • • 10. (x ⊕ y) → (y ↓ x), ((x|y) ∨ z) ↔ xy. 11. x ∨ (y → z) и (x ∨ y) → (x ∨ z). 12. (x|y) ⊕ (z → x). 13. f (1, 0, 1) = f (0, 1, 0) = f (1, 1, 1) = 0. 14. (1011 1011 1100 1111). 15. J = {x → y, x ∧ y}. 16. (A \ B) ⊕ (A \ C) = A ⊕ (B \ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ 133 Вариант 15 1. A ∩ B = A ∪ B, U 2 \ (C × D) = (C × U) ∪ (U × D). 2. 11 n+1 + 12 кратно 133 для всех n > 0. 3. (0, 1] ∼ [0, +∞). 4. P 1 = { b, 1 , b, 3 , c, 1 , c, 2 , c, 3 , c, 4 }, P 2 = { 1, 1 , 2, 2 , 2, 3 , 2, 4 , 3, 2 , 3, 3 , 3, 4 , 4, 2 , 4, 3 , 4, 4 }. 5. P ⊆ Z 2 , x, y ∈ P ⇔ x + y кратно 3. 6. ω; :, −1 . 7. B = R 2 ; +, − , X = { 1, 2 , 0, 1 }. 8. G 1 : • • • • © d d d h 1 2 4 3 G 2 : h • • • e e e ¡ ¡ ¡ 3 2 1 9. G: ¨¨ ¨¨ ¨¨ • • • • • • • • 10. x ↔ (y → (y ↓ x)), ((x|y) ∨ z) ⊕ xy. 11. x ∨ (y|z) и (x ∨ y)|(x ∨ z). 12. (z → x) ↔ (x|y). 13. f (1, 0, 0) = f (1, 1, 0) = f (0, 1, 1) = f (0, 1, 0) = 1. 14. (0101 0011 0101 1110). 15. J = {x ↔ y, x|y}. 16. (A ∪ B) ⊕ (A ∪ C) = A ∪ (B ⊕ C). ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ Вариант 16 1. (A ∩ B) ∪ (A ∩ B) = (A ∪ B) ∩ (A ∪ B) = A; (A ∪ B) × (C ∪ D) = (A × C) ∪ (B × C) ∪ (A × D) ∪ (B × D). 2. 9 n+1 − 8n − 9 кратно 16 для всех n 0. 3. 2 ω + ω = 2 ω 4. P 1 = { a, 1 , a, 2 , a, 4 , b, 2 , b, 4 , c, 3 }, P 2 = { 1, 1 , 2, 2 , 2, 4 , 3, 3 , 4, 4 , 4, 2 }. 5. P ⊆ Z 2 , x, y ∈ P ⇔ x − y кратно 2. 6. ω; +, ·, : . 7. B = Q; +, · , X = { 1 2 }. 8. G 1 : • • • • d d d ' © h 1 2 4 3 G 2 : h • • • ¡ ¡ ¡!e e e E 3 2 1 9. G: ¨¨ ¨¨ ¨¨d d d • • • • • • • • 10. x ↓ (y → (y|x)), x ⊕ (y ∨ z ↔ xy). 11. x ∨ (y ↔ z) и (x ∨ y) ↔ (x ∨ z). 12. (z → x) ⊕ (x|y). 13. f (0, 1, 1) = f (1, 0, 0) = f (1, 0, 1) = 0. 14. (0011 1101 0011 1100). 15. J = {x ⊕ y, x ∨ y}. 16. (A \ B) ⊕ (A \ C) = A ∩ (B ⊕ C). |