Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
x ∨ (y → z) и x ∨ y → x ∨ z. 13. x | y ⊕ z → x. 14. f (1, 0, 1) = f (0, 1, 0) = f (1, 1, 1) = 0. 15. (1011 1011 1100 1111). 16. J = {x → y, x ∧ y}. 17. (A \ B) ⊕ (A \ C) = A ⊕ (B \ C). 248 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 9 1. (A ∩ B) \ C = (A \ C) ∩ (B \ C), (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D). 2. 1 2! + 2 3! + . . . + n − 1 n! = 1 − 1 n! для n > 2. 3. ω 2 ∼ ω 3 4. P 1 = {ha, 1i, ha, 2i, ha, 4i, hb, 3i, hc, 1i, hc, 4i}, P 2 = {h1, 3i, h1, 2i, h2, 3i, h3, 2i, h3, 4i, h4, 1i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x 2 = y. 6. hQ; +, −, :, 1 3 i. 7. B = hZ; +, ·i, X = {−2, 16}. 8. β = [5, 11, 7, 2], a = 53, b = 88, x = [4, 9, 3, 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. z → x ↔ x | y. 14. f (1, 0, 0) = f (1, 1, 0) = f (0, 1, 1) = f (0, 1, 0) = 1. 15. (0101 0011 0101 1110). 16. J = {x ↔ y, x | y}. 17. (A ∪ B) ⊕ (A ∪ C) = A ∪ (B ⊕ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 249 Вариант 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 · 5 + 3 · 8 + . . . + n(3n − 1) = n 2 (n + 1). 3. ω + n = ω. 4. P 1 = {ha, 3i, ha, 2i, hb, 2i, hb, 3i, hc, 1i, hc, 4i}, P 2 = {h1, 1i, h1, 2i, h2, 2i, h3, 3i, h4, 1i, h4, 4i}. 5. P ⊆ R 2 , hx, yi ∈ P ⇔ x 2 > y. 6. hR \ {0}; +, :i. 7. B = hQ; +, ·i, X = {2, 1 2 }. 8. β = [5, 11, 3, 2], a = 48, b = 35, x = [2, 5, 1, 1]. 9. G 1 : • • • • 6 - - @ @ @ R ? h 1 2 4 3 G 2 : • • • ¢ ¢ ¢A A AU ¾ 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. z → x ⊕ x | y. 14. f (0, 1, 1) = f (1, 0, 0) = f (1, 0, 1) = 0. 15. (0011 1101 0011 1100). 16. J = {x ⊕ y, x ∨ y}. 17. (A \ B) ⊕ (A \ C) = A ∩ (B ⊕ C). 250 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 11 1. (A \ B) \ C = A \ (B ∪ C), A ⊆ C, B ⊆ D ⇒ A × B = (A × D) ∩ (C × B). 2. n 3 + 5n кратно 6 для всех n ∈ ω. 3. ω 2 ∼ Z. 4. P 1 = {ha, 2i, ha, 4i, hb, 3i, hc, 1i, hc, 2i}, P 2 = {h1, 1i, h1, 3i, h2, 4i, h3, 1i, h3, 4i, h4, 3i, h4, 2i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x 2 + y 2 = 1. 6. hQ; p , ·, −10i. 7. B = hZ 3 ; +, −i, X = {h0, 1, 1i, h0, 0, 1i}. 8. β = [7, 5, 11, 2], a = 54, b = 76, x = [4, 3, 2, 0]. 9. G 1 : • • • • ¡ ¡ ¡ µ @ @ @ I 6 h 1 2 4 3 G 2 : • • • ¢ ¢ ¢¸ -A A A 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 ⊕ y. 14. f (0, 0, 1) = f (1, 0, 0) = f (1, 1, 0) = 0. 15. (1011 1111 1011 1100). 16. J = {x ∧ y, x → y}. 17. (A \ B) ∪ (A \ C) = A \ (B ⊕ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 251 Вариант 12 1. A \ (B \ C) = (A \ B) ∪ (A ∩ C), U 2 \ (A × B) = (A × U) ∪ (U × B). 2. 4 n − 1 кратно 3 для всех n > 0. 3. ω 2 ∼ Z 2 4. P 1 = {hb, 1i, hb, 3i, hc, 1i, hc, 2i, hc, 3i, hc, 4i}, P 2 = {h1, 1i, h2, 2i, h2, 3i, h2, 4i, h3, 2i, h3, 3i, h3, 4i, h4, 2i, h4, 3i, h4, 4i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x + y кратно 3. 6. hω; +, ·, :i. 7. B = hQ; +, ·i, X = { 1 2 }. 8. β = [3, 11, 5, 2], a = 61, b = 42, x = [1, 7, 2, 0]. 9. G 1 : h h h h • • • • 1 2 4 3 G 2 : h h h • • • - ¢ ¢ ¢¸A A AU 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 ⊕ y. 14. f (0, 0, 1) = f (0, 1, 1) = f (1, 1, 1) = 0. 15. (0011 1110 0101 0101). 16. J = {x | y, x ↔ y}. 17. (A \ B) ∪ (B \ C) = (A ∪ C) \ B. 252 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 13 1. A ∪ (B \ C) = (A ∪ B) \ (C \ A); A, B 6= ∅, (A × B) ∪ (B × A) = (C × D) ⇒ A = B = C = D. 2. 4 n + 15n − 1 кратно 9 для всех натуральных n. 3. (0, 1] ∼ [0, +∞). 4. P 1 = {ha, 1i, ha, 2i, ha, 4i, hb, 2i, hb, 4i, hc, 3i}, P 2 = {h1, 1i, h2, 2i, h2, 4i, h3, 3i, h4, 4i, h4, 2i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x − y кратно 2. 6. hR; −, ·, :i. 7. B = hω; +, ·i, X = {2}. 8. β = [7, 11, 3, 2], a = 73, b = 36, x = [6, 7, 1, 0]. 9. G 1 : • • • • ¾ ¾ ¡ ¡ ¡ µ @ @ @ R 1 2 4 3 G 2 : • • • -A A AK ¢ ¢ ¢® h 3 2 1 10. G: ³³ ³³ ³³ ³³³ PPP PPP PPP ¡ ¡ ¡ @ @ @ • • • • • • • • 11. x ↓ (y → y ∨ x), x | (y ↔ z ⊕ xy). 12. x ⊕ y | z и (x ⊕ y) | (x ⊕ z). 13. x ↓ y → z ⊕ y. 14. f (0, 0, 0) = f (0, 0, 1) = f (1, 1, 0) = 0. 15. (0011 0011 1100 1111). 16. J = {x ⊕ y, x ∨ y}. 17. (A ∩ B) ⊕ (B ∪ C) = (A \ B) ⊕ C. ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 253 Вариант 14 1. A ∩ (B \ C) = (A ∩ B) \ (A ∩ C), (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D). 2. 11 n+1 + 12 2n−1 кратно 133 для всех n > 0. 3. 2 ω + ω = 2 ω 4. P 1 = {ha, 2i, ha, 3i, ha, 4i, hc, 3i, hc, 1i, hc, 4i}, P 2 = {h1, 4i, h2, 3i, h2, 1i, h3, 4i, h4, 2i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ 2x = 3y. 6. hQ; +, −, √ 2i. 7. B = hR; 3 p , 2i, X = {1}. 8. β = [3, 5, 11, 2], a = 43, b = 87, x = [2, 4, 7, 1]. 9. G 1 : h h h h • • • • 1 2 4 3 G 2 : • • • A A A h h 3 2 1 10. G: ³³ ³³ ³³ ³³³ PPP PPP PPP ¡ ¡ ¡ @ @ @ • • • • • • • • 11. x ⊕ (y → (y ↔ x)), x ↓ (y ∨ z | xy). 12. x ↓ (y ↔ z) и x ↓ y ↔ x ↓ z. 13. x ↓ y → z ↔ y. 14. f (0, 0, 0) = f (0, 1, 0) = f (1, 1, 1) = 0. 15. (1100 0101 0011 0011). 16. J = {x ∧ y, x → y}. 17. (A ∪ B) \ (A ∪ C) = A \ (B ∪ C). 254 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 15 1. A ∩ B = A ∪ B, U 2 \ (C × D) = (C × U) ∪ (U × D). 2. 9 n+1 − 8n − 9 кратно 16 для всех n > 0. 3. 2 ω + n = 2 ω 4. P 1 = {ha, 1i, ha, 2i, hb, 3i, hb, 4i, hc, 3i, hc, 4i}, P 2 = {h1, 1i, h1, 4i, h2, 1i, h2, 2i, h2, 4i, h3, 3i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x + y нечетно. 6. hR + ; p , :, ·i, где R + = {x ∈ R | x > 0}. 7. B = hQ \ {0}; :i, X = { 1 2 , 1 4 }. 8. β = [5, 11, 3, 2], a = 58, b = 32, x = [3, 5, 1, 0]. 9. G 1 : • • • • ¡ ¡ ¡ ª @ @ @ R h 1 2 4 3 G 2 : h • • • A A AU ¢ ¢ ¢® 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 ↔ y. 14. f (0, 0, 0) = f (0, 0, 1) = f (1, 0, 0) = f (1, 1, 0) = 1. 15. (0010 0111 1010 1101). 16. J = {x ∨ y, x ↔ y}. 17. (A \ B) ∪ (B \ C) = (A \ B) ∪ C. ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 255 Вариант 16 1. (A ∩ B) ∪ (A ∩ B) = (A ∪ B) ∩ (A ∪ B) = A; (A ∪ B) × (C ∪ D) = (A × C) ∪ (B × C) ∪ (A × D) ∪ (B × D). 2. n(2n 2 − 3n + 1) кратно 6 для всех натуральных n. 3. |Z 2 | = ω. 4. P 1 = {ha, 2i, ha, 3i, ha, 4i, hb, 1i, hb, 2i, hb, 4i}, P 2 = {h1, 1i, h1, 3i, h1, 4i, h2, 2i, h2, 3i, h3, 2i, h3, 3i, h4, 3i, h4, 4i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x − y четно. 6. hQ + ; +, ·, −1i, где Q + = {x ∈ Q|x > 0}. 7. B = hZ; +, −i, X = {3, 4}. 8. β = [7, 11, 5, 2], a = 73, b = 48, x = [2, 8, 3, 1]. 9. G 1 : • • • • ¡ ¡ ¡ @ @ @ ¾ ¡ ¡ ¡ ª h 1 2 4 3 G 2 : h • • • ¢ ¢ ¢¸A A A - 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ ©© ©© ©©@ @ @ • • • • • • • • 11. x | y → (y ⊕ x), x ∧ y ∨ (z ↔ x ↓ y). 12. x → y | z и (x → y) | (x → z). 13. x ↓ y → z ⊕ y. 14. f (1, 0, 1) = f (0, 1, 1) = f (0, 1, 0) = 0. 15. (0011 1111 0011 1100). 16. J = {x ⊕ y, x ∨ y}. 17. (A \ B) ∪ (A ∩ C) = A \ (B ∪ C). 256 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 17 1. (A \ B) \ C = (A \ C) \ (B \ C); A ⊆ B, C ⊆ D ⇒ A × C ⊆ B × D. 2. 1 1 · 3 + 1 3 · 5 + 1 5 · 7 + . . . + 1 (2n − 1)(2n + 1) = n 2n + 1 3. ω · n = ω. 4. P 1 = {ha, 3i, hb, 4i, hb, 3i, hb, 1i, hb, 2i, hc, 2i}, P 2 = {h1, 1i, h1, 3i, h2, 4i, h3, 1i, h3, 3i, h4, 2i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ 5x = 2y. 6. hZ − ; +, −i, где Z − = {x ∈ Z | x < 0}. 7. B = hR 3 ; ×i, X = {h1, 0, 0i, h0, 0, 1i}, × — операция векторного произ- ведения. 8. β = [11, 7, 3, 2], a = 57, b = 81, x = [5, 4, 2, 0]. 9. G 1 : • • • • h 6 - ¡ ¡ ¡ ª 1 2 4 3 G 2 : • • • h ¢ ¢ ¢A A AU ¾ 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 ↔ y). 14. f (1, 0, 0) = f (0, 1, 1) = f (0, 1, 0) = 0. 15. (0101 0011 1100 0011). 16. J = {x ∧ y, x → y}. 17. (A ⊕ B) \ (B ∩ C) = A ⊕ (B \ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 257 Вариант 18 1. A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C, (A \ B) × C = (A × C) \ (B × C). 2. n 5 − n кратно 5 для всех натуральных n. 3. |A × B × C| = |C × A × B|. 4. P 1 = {ha, 3i, hb, 4i, hb, 3i, hc, 1i, hc, 2i, hc, 4i}, P 2 = {h1, 2i, h1, 3i, h1, 4i, h2, 3i, h4, 3i, h4, 2i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x = −y. 6. hZ − ; +, ·i, где Z − = {x ∈ Z | x < 0}. 7. B = hZ; +, ·i, X = {−2, 7}. 8. β = [7, 5, 11, 2], a = 48, b = 63, x = [3, 2, 6, 1]. 9. G 1 : • • • • h h ¡ ¡ ¡ @ @ @ 1 2 4 3 G 2 : • • • h ¢ ¢ ¢A A AU ¾ 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 → y. 14. f (0, 0, 1) = f (0, 1, 1) = f (1, 0, 0) = f (1, 0, 1) = 1. 15. (0111 1101 0010 1010). 16. J = {x ↓ y, x ↔ y}. 17. (A ∪ B) \ (A ∪ C) = A ⊕ (B ∪ C). 258 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 19 1. A ∩ B = (A ∪ B) ∩ A, (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D). 2. 6 2n−1 + 1 кратно 7 для всех n > 1. 3. |Z × ω| = ω. 4. P 1 = {ha, 1i, hb, 2i, hb, 3i, hc, 1i, hc, 3i, hc, 4i}, P 2 = {h1, 1i, h1, 2i, h1, 3i, h2, 2i, h2, 3i, h3, 3i, h3, 4i, h4, 1i, h4, 4i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ x + 1 = y. 6. h{A ∈ M n (Z) | det A 6= 0}; +, ·i. 7. B = hR 3 ; +i, X = {h1, 2, 3i, h−1, 0, 0i}. 8. β = [7, 3, 11, 2], a = 37, b = 74, x = [4, 1, 5, 0]. 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. x ↓ y → z ↔ x. 14. f (1, 0, 0) = f (0, 0, 1) = f (0, 1, 1) = 0. 15. (1111 1100 0011 0011). 16. J = {x ⊕ y, x ∨ y}. 17. (A ∩ B) ⊕ (A ∪ C) = A ⊕ (B ∪ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 259 Вариант 20 1. A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C), (A ∩ B) × C = (A × C) ∩ (B × C). 2. 1 3 + 2 3 + 3 3 + . . . + n 3 = n 2 (n + 1) 2 4 3. Множества точек двух окружностей эквивалентны. 4. P 1 = {ha, 2i, ha, 4i, ha, 3i, hc, 1i, hc, 2i, hc, 3i}, P 2 = {h1, 1i, h1, 4i, h2, 3i, h3, 3i, h4, 1i, h4, 3i, h4, 4i}. 5. P ⊆ Z 2 , hx, yi ∈ P ⇔ y > x − 2. 6. ¿ {A ∈ M 2 (Z) | det A 6= 0}; ·, µ 1 1 −1 −1 ¶À 7. B = hQ \ {0}; ·, :i, X = {−5}. 8. β = [5, 11, 7, 2], a = 63, b = 35, x = [3, 4, 2, 0]. 9. G 1 : • • • • h 6 - ? ¾ 1 2 4 3 G 2 : • • • h h ¢ ¢ ¢® A A AU - 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ • • • • • • • • 11. x ∧ y ↔ y ↓ x, (x → y) | (z ⊕ x ∨ y). 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) = 0. 15. (0011 0011 0101 1100). 16. J = {x → y, x ∧ y}. 17. (A \ B) \ (A ∩ C) = A \ (B ∪ C). 260 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 21 1. A ⊕ (A ⊕ B) = B, A × (B ∩ C) = (A × B) ∩ (A × C). 2. 8 n − 1 кратно 7 для всех натуральных n > 1. 3. (B × C) A ∼ B A × C A 4. P 1 = {ha, 2i, ha, 4i, hb, 1i, hb, 2i, hb, 4i, hc, 2i, hc, 4i}, P 2 = {h1, 1i, h2, 2i, h2, 4i, h3, 3i, h4, 4i, h3, 2i, h1, 3i, h4, 1i}. 5. P ⊆ (Z + ) 2 , hx, yi ∈ P ⇔ НОД(x, y) 6= 1, где Z + = {x ∈ Z | x > 0}. 6. hC \ {0}; −, +, :, p i. 7. B = hC; +, −, 1i, X = {2 . ı}. 8. β = [3, 11, 7, 2], a = 84, b = 26, x = [1, 7, 5, 1]. 9. G 1 : • • • • h h h ¡ ¡ ¡ µ 1 2 4 3 G 2 : • • • h -A A AK ¢ ¢ ¢® 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 ⊕ y. 14. f (0, 0, 0) = f (0, 0, 1) = f (1, 0, 0) = f (1, 1, 0) = 0. 15. (1110 1001 0111 0001). 16. J = {x ↓ y, x ↔ y}. 17. (A ⊕ B) ∩ (A ⊕ C) = A \ (B ∩ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 261 Вариант 22 1. A ∪ B = A ⊕ B ⊕ (A ∩ B), A × (B \ C) = (A × B) \ (A × C). 2. 1 2 + 3 2 + 5 2 + . . . + (2n − 1) 2 = n(2n − 1)(2n + 1) 3 3. (A B ) C ∼ A B×C 4. P 1 = {hb, 1i, ha, 3i, ha, 4i, hc, 2i, hc, 4i, hb, 4i}, P 2 = {h1, 1i, h2, 3i, h2, 2i, h2, 4i, h3, 3i, h3, 4i, h4, 2i, h4, 4i}. 5. P ⊆ (Z + ) 2 , hx, yi ∈ P ⇔ x 6= y. 6. hZ; +, ·, 1 − . ıi. 7. B = hC; ·i, X = {e . ı π 4 }. 8. β = [7, 11, 3, 2], a = 65, b = 89, x = [6, 7, 2, 0]. 9. G 1 : • • • • h h 1 2 4 3 G 2 : • • h - ¢ ¢ ¢A A AU 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 ↔ y). 14. f (0, 1, 1) = f (1, 0, 0) = f (1, 0, 1) = 1. 15. (0001 0011 1100 1110). 16. J = {x ⊕ y, x ∨ y}. 17. (A ∪ B) ⊕ (A ∩ C) = A ⊕ (B \ C). 262 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 23 1. A \ B = A ⊕ (A ∩ B), (A ∪ B) × C = (A × C) ∪ (B × C). 2. 4 n + 6n − 1 кратно 9 для всех натуральных n > 0. 3. Множества точек двух квадратов эквивалентны. 4. P 1 = {ha, 3i, ha, 2i, ha, 4i, hb, 1i, hc, 2i, hc, 4i, hc, 3i}, P 2 = {h1, 1i, h2, 2i, h2, 1i, h3, 3i, h4, 4i, h4, 3i, h1, 4i, h2, 4i, h3, 2i, h3, 4i}. 5. P ⊆ (Z + ) 2 , hx, yi ∈ P ⇔ x 2 = y, где Z + = {x ∈ Z | x > 0}. 6. hC \ {0}; +, ·i. 7. B = hC; +, ·i, X = {2 . ı}. 8. β = [11, 3, 5, 2], a = 43, b = 67, x = [4, 2, 3, 1]. 9. G 1 : • • • • h ? ¡ ¡ ¡ µ @ @ @ R ? 1 2 4 3 G 2 : • • • h h ¢ ¢ ¢® A A A 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 ↔ y. 14. f (0, 0, 1) = f (1, 0, 0) = f (1, 1, 0) = 1. 15. (0011 1100 0011 0101). 16. J = {x ∧ y, x → y}. 17. (A ∪ B) \ (B ∩ C) = (A \ B) ∪ (A \ C). ВАРИАНТЫ ТИПОВОГО РАСЧЕТА 263 Вариант 24 1. A ∪ B = (A ⊕ B) ∪ (A ∩ B), A × (B ∪ C) = (A × B) ∪ (A × C). 2. 1 2 − 2 2 2 + 3 2 3 − 4 2 4 + . . . + (−1) n+1 n 2 n = 1 9 µ 2 + (−1) n−1 3n + 2 2 n ¶ 3. |Q 2 | = ω. 4. P 1 = {hb, 2i, ha, 3i, hb, 1i, hb, 4i, hc, 1i, hc, 2i, hc, 4i}, P 2 = {h1, 1i, h1, 2i, h1, 4i, h2, 2i, h2, 4i, h3, 3i, h3, 2i, h3, 4i, h4, 4i}. 5. P ⊆ (Z + ) 2 , hx, yi ∈ P ⇔ x 2 6= y, где Z + = {x ∈ Z | x > 0}. 6. hC \ R; +, −, p , 2 − . ıi. 7. B = hC; ·i, X = {3 . ı}. 8. β = [7, 3, 11, 2], a = 31, b = 78, x = [6, 1, 7, 0]. 9. G 1 : • • • • h h ¡ ¡ ¡ @ @ @ 1 2 4 3 G 2 : • • • h A A AU ¢ ¢ ¢¸ 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 ↔ y). 14. f (0, 1, 1) = f (0, 1, 0) = f (1, 0, 0) = f (1, 0, 1) = 0. 15. (1010 0010 1101 0111). 16. J = {x ↓ y, x ↔ y}. 17. (A \ B) ∪ (C \ B) = (B ∪ C) \ A. 264 ВАРИАНТЫ ТИПОВОГО РАСЧЕТА Вариант 25 1. A ∪ B = A ∩ B; A ⊆ C, B ⊆ D ⇒ A × B = (A × D) ∩ (C × B). 2. n 7 − n кратно 7 для всех n > 0. 3. A B∪C ∼ A B × A C , если B ∩ C = ∅. 4. P 1 = {ha, 2i, ha, 3i, ha, 4i, hb, 3i, hc, 1i, hc, 4i}, P 2 = {h1, 1i, h2, 3i, h2, 2i, h3, 4i, h1, 4i, h2, 4i, h4, 2i}. 5. P ⊆ (Z + ) 2 , hx, yi ∈ P ⇔ x 2 > y, где Z + = {x ∈ Z | x > 0}. 6. hC \ R; +, ·, :i. 7. B = hC; +, . ıi, X = R. 8. β = [5, 7, 11, 2], a = 43, b = 74, x = [3, 2, 5, 1]. 9. G 1 : • • • • h h h ? @ @ @ R ? ¡ ¡ ¡ ª 1 2 4 3 G 2 : • • • h h h - A A A 3 2 1 10. G: ¡ ¡ ¡ ¡ ¡ ¡ ©© ©© ©© @ @ @ • • • • • • • • 11. x ↔ y ∧ (y → x), x ∨ (y ⊕ z ↓ x | y). 12. x → y ↓ z и (x → y) ↓ (x → z). 13. (x ↔ y → z) | y. 14. f (0, 1, 1) = f (0, 1, 0) = f (1, 0, 1) = f (1, 1, 1) = 1. 15. (0011 1101 0010 1100). 16. J = {x ∨ y, x ↔ y}. 17. A \ (B \ C) = (A \ B) \ C. Указатель терминов Автоморфизм, 58 Аксиома бесконечности, 47 выбора, 48 замены, 47 математической индукции, 27 множества всех подмножеств, 47 регулярности, 48 суммы, 47 существования пары, 47 пустого множества, 47 экстенсиональности, 47 Аксиомы Дедекинда—Пеано, 27 Цермело—Френкеля, 47 метрики, 134 Алгебра, 55 Кантора, 55 булева, 68 булевых функций, 189 компьютерная, 91 отношений, 73 реляционная, 74 Алгебраическая система, 55 Алгоритм Дейкстры, 137 Евклида, 99 Форда—Беллмана, 136 последовательной раскраски, 163 Алфавит, 43 Антидизъюнкция, 185 Антиконъюнкция, 185 Аргумент, 23 Арифметика многомодульная, 114 модулярная, 103 остатков, 103 по модулю M , 114 Ассоциативность, 17, 68, 189 композиции, 22 Атом, 69 Атомарная формула, 183 Базис, 208 индукции, 27 Биекция, 24 Бином Ньютона, 172 Бит, 91 Булеан, 15 Булева алгебра, 68 двойственная, 204 функция, 186 Булево кольцо, 70 В.у.м., 43 Валентность вершины, 139 Вектор, 40 значений булевой функции, 187 оснований, 113 остатков, 113 Вершина, 118 висячая, 139 266 УКАЗАТЕЛЬ ТЕРМИНОВ графа, 118 достижимая, 130 изолированная, 139 концевая, 139 периферийная, 134 центральная, 135 взвешенная, 135 Вершины взаимно достижимые, 133 смежные, 121 Вес вершины, 123 дуги, 123 маршрута, 135 Ветвь остова, 155 Включение множества, 14 Восьмеричная система, 87 Вхождение переменной, 198 Выборка неупорядоченная, 172 с возвращениями, 173 упорядоченная, 171 с возвращениями, 173 Высказывание, 183 простое, 183 сложное, 183 Гомоморфизм, 57 естественный, 63 Граница, 160 Грань верхняя, 42 нижняя, 42 точная верхняя, 42 нижняя, 42 Граф, 118 ациклический, 143 бесконтурный, 130 бихроматический, 162 взвешенный, 123 гамильтонов, 142 двудольный, 162 неориентированный, 119 ориентированный, 119 планарный, 163 полный, 128 получаемый отождествлением вер- шин, 125 помеченный, 123 разреженный, 124 связный, 130 сильно связный, 130 Графы гомеоморфные, 163 изоморфные, 122 Группа, 56 абелева, 56 коммутативная, 56 симметрическая, 170 Группоид, 56 ДНФ, 192 Двоичная система, 86 Декартова степень множества, 19 Декартово произведение алгебр, 65 множеств, 19, 64 отношений, 73 Декомпозиция функции, 209 дизъюнктивная, 210 нондизъюнктивная, 210 простая, 211 функциональная итеративная, 213 множественная, 213 Делитель, 96 наибольший общий, 97 Дерево, 143 бинарное, 154 остовное, 144 УКАЗАТЕЛЬ ТЕРМИНОВ 267 упорядоченное, 152 Диагональ, 21 Диаграмма Хассе, 45 Эйлера—Венна, 16 Диаметр графа, 134 Дизъюнкт, 191 Дизъюнктивная нормальная форма, 192 минимальная, 199 совершенная, 193 сокращенная, 198 тупиковая, 199 Дизъюнкция, 183 элементарная, 191 Дистрибутивность, 17 Длина маршрута, 129 слова, 43 Домен, 73 Дополнение графа, 126 множества, 16 функции, 189 элемента, 67 Дуга, 118 графа, 118 заходящая в вершину, 118 инцидентная вершине, 122 исходящая из вершины, 118 Дуги кратные, 119 Единица моноида, 56 решетки, 66 частично упорядоченного множества, 42 Задача коммивояжера, 143, 147 нахождения остова минимального веса, 145 о безопасном хранении ключа, 108 о кенигсбергских мостах, 140 Закон двойного отрицания, 17, 69, 189 де Моргана, 17, 69, 189 дистрибутивности, 17, 68, 189 идемпотентности, 17, 68 нуля и единицы, 17, 69 поглощения, 17, 69, 189 Значение терма, 61 функции, 23 Идеал, 71 главный, 71 Идемпотентность, 17, 189 Изображение графа, 118 плоское, 163 Изоморфизм, 58 частично упорядоченных множеств, 46 Изоморфные системы, 58 частично упорядоченные множества, 46 Импликанта простая, 198 формулы, 198 функции, 198 Импликация, 183 Инверсия, 183 Инвертор, 209 Индукционный шаг, 27 Интерпретация, 55, 184 Инфимум, 42 Инцидентор, 119 Инъекция, 23 Источник, 136 КНФ, 192 Кардинал, 29 268 УКАЗАТЕЛЬ ТЕРМИНОВ Каркас графа, 144 Карта Карно, 201 декомпозиции, 211 Квазипорядок, 40 Класс функций линейных, 206 монотонных, 206 самодвойственных, 205 эквивалентности, 38 Классы Поста, 205 Кограница, 160 Код двоичный, 85 Кольцевая сумма графов, 126 формул, 185 Кольцо булево, 70 вычетов по модулю m, 103 целых чисел, 79, 81 Комбинаторика, 168 Коммутативность, 17, 68, 189 Композиция графов, 128 отношений, 22 Компонента связности, 130 сильной, 130 сильная, 130 Компьютерная алгебра, 91 Конгруэнция, 62 единичная, 67 нулевая, 67 Конец ребра, 119 Конкатенация, 56 Константа, 25, 54, 55 0, 188 1, 188 Константный символ, 54 Конституента единицы, 193 нуля, 193 Контакт, 216 замыкающий, 216 размыкающий, 216 Континуум, 29 Контрпример, 223 Контур, 130 Конфигурация комбинаторная, 168 Конъюнкт, 191 Конъюнктивная нормальная форма, 192 минимальная, 200 совершенная, 193 Конъюнкция, 183 элементарная, 191 Координата, 19 слова, 43 Коранг, 144 Корень дерева, 146 упорядоченного, 152 характеристический, 177 Кортеж, 19 Коцикл, 157 Коэффициент биномиальный, 172 полиномиальный, 174 Л.у.м., 41 Лемма о рукопожатиях, 140 Лес, 143 упорядоченный, 152 Литера, 191 Литеры контрарные, 191 МДНФ, 199 МКНФ, 200 Маршрут, 129 кратчайший, 135 УКАЗАТЕЛЬ ТЕРМИНОВ 269 циклический, 129 Математика дискретная, 11 непрерывная, 11 прерывная, 11 Матрица Квайна, 200 бинарного отношения, 34 весов, 123 достижимости, 132 инцидентности, 122 контрдостижимости, 133 программируемая логическая, 221 расстояний, 134 связности, 132 смежности, 121 соединений, 221 фундаментальных разрезов, 158 циклов, 155 Метод Квайна, 199 бинарный, 105 Многообразие, 65 Многочлен характеристический, 177 Множества равномощные, 29 равные, 14 совпадающие, 14 эквивалентные, 29 Множество, 13 бесконечное, 29 континуальное, 29 счетное, 29 вполне упорядоченное, 43 вычетов, 102 действительных чисел, 84 коконечное, 72 комплексных чисел, 85 конечное, 29 коциклов фундаментальное, 158 линейно упорядоченное, 41 натуральных чисел, 26, 27 пустое, 15 рацинальных чисел, 82 строго включенное, 15 универсальное, 15 фундаментальных циклов, 155 целых чисел, 81 по модулю m, 102 циклов фундаментальное, 155 частично упорядоченное, 41 Множество-степень, 15 Модель, 55 Моноид, 56 Мономорфизм, 57 Мощность алгебраической системы, 55 множества, 29 Мультиграф, 119 неориентированный, 120 реберный, 162 эйлеров, 141 Мультиграфы изоморфные, 122 Мультиплексор, 220 Набор длины n, 19 остатков стандартный, 113 цепей, покрывающих граф, 142 Наибольший общий делитель, 97 Наименьшее общее кратное, 98 Неорграф, 119 ациклический, 129 связный, 130 соответствующий данному оргра- фу, 120 Неравенство Бернулли, 28 треугольника, 134 Нормальная форма дизъюнктивная, 192 270 УКАЗАТЕЛЬ ТЕРМИНОВ минимальная, 199 сокращенная, 198 тупиковая, 199 конъюнктивная, 192 минимальная, 200 Носитель алгебраической системы, 55 Нуль решетки, 66 частично упорядоченного множества, 42 Область значения, 21 определения, 21 Образ гомоморфный, 57 множества, 22, 25 Обратное отношение, 22 Обхват графа, 129 Обход графа по глубине, 146 по ширине, 146 Объединение графов, 126 конгруэнций, 67 отношений, 73 функций, 189 элементов решетки, 66 Объединение множеств, 15 Ограничение отображения, 25 Операция n-арная, 25 n-местная, 25 бинарная, 25 возведения в степень, 30 выбора, 74 добавления вершины, 125 дуги, 125 кольцевого сложения, 71 кольцевого умножения, 71 конкатенации, 56 логическая, 183 на множестве ассоциативная, 56 отождествления вершин, 125 подразбиения ребра, 163 проекции, 75 сложения, 28, 30 соединения, 75 стягивания дуги, 125 удаления вершины, 125 дуги, 125 умножения, 28, 30 унарная, 25 Определение индукционное, 27 Орграф, 119 Ортогональные подпространства, 161 Основание счисления, 86 Остаток, 97 Остов графа, 144 Отношение, 20 n-местное, 20 Парето, 42 антирефлексивное, 36 антисимметричное, 36 асимметричное, 36 бинарное, 20 иррефлексивное, 36 на множестве, 20 обратное, 22 полное, 21 рефлексивное, 36 симметричное, 36 тождественное, 21 транзитивное, 36 унарное, 20 универсальное, 21 эквивалентности, 38 Отношения совместимые, 73 Отображение, 23 Отрицание, 183 УКАЗАТЕЛЬ ТЕРМИНОВ 271 ПЛМ, 221 Перевод дробных чисел, 90 целых чисел, 89 Переменная логическая, 183 Пересечение графов, 126 конгруэнций, 67 множеств, 15 отношений, 73 функций, 189 элементов решетки, 66 Перестановка, 168 Перешеек, 141 Период дроби, 84 Петля, 121 Плоское изображение графа, 163 Поглощение, 17 Подалгебра, 60 Подграф, 124 Поддерево левое, 154 правое, 154 упорядоченное, 152 Подмножество, 14 собственное, 15 Подмодель, 60 Подпространства ортогональные, 161 Подсистема, 60 порожденная множеством, 60 Подстановка множества, 24, 169 Покрытие множества, 18 Поле действительных чисел, 83 комплексных чисел, 85 конечное, 104 рациональных чисел, 82 характеристики нуль, 104 Полином Жегалкина, 206 линейный, 207 нелинейный, 207 Полное отношение, 21 Полугруппа, 56 Полустепень захода, 140 исхода, 140 Полюс, 215 входной, 216 выходной, 216 Пометка, 123 Порядок двойственный, 41 лексикографический, 43 линейный, 41 полный, 43 строгий, 41 частичный, 41 Последователь, 124 вершины, 121 Последовательность, 25 возвратная, 177 фундаментальная, 83 Поток в сети, 156 Правило Паскаля, 172 произведения, 31 степени, 31 суммы, 31 Предикат, 20 на множестве, 20 Предпорядок, 40 Представление со смешанными основаниями, 115 Предшественник вершины, 121 Принцип двойственности для булевых функций, 204 математической индукции, 27 полного упорядочения, 48 полной индукции, 29 трансфинитной индукции, 48 272 УКАЗАТЕЛЬ ТЕРМИНОВ Программируемая логическая матри- ца, 221 Проекция, 23 Произведение алгебр, 65 бинарных отношений, 22 векторов внутреннее, 160 графов, 126 множеств, 16 декартово, 19, 64 прямое, 19 остатков, 103 отношений декартово, 73 списков, 95 элементарное, 198 Прообраз множества, 22 Противоречие, 190 Путь, 130 Радиус взвешенный, 135 графа, 135 Разбиение множества, 18 упорядоченное, 173 Разложение Шеннона, 194 Размещение, 171 с повторением, 173 Разность множеств, 16 симметрическая, 16 отношений, 73 Разрез графа, 157 простой, 157 фундаментальный, 158 Ранг коциклический, 144 циклический, 144 Раскраска вершин графа, 161 ребер мультиграфа, 162 Распределение меток, 123 вершин, 123 дуг, 123 Расстояние, 134 взвешенное, 135 Реализация декомпозиционная, 209 Решение общее, 177 частное, 178 Решетка, 66 булева, 67 дистрибутивная, 67 конгруэнций, 67 подсистем, 66 элементов &, 221 Решето Эратосфена, 101 СДНФ, 193 СКНФ, 193 Свойство, 20 делимости, 97 евклидовости, 97 Связка, 183 Сегмент начальный замкнутый, 46 открытый, 46 Сеть, 156 k-полюсная, 215 Сигнатура, 54 предикатная, 55 функциональная, 55 Система, 55 Дедекинда—Пеано, 79 аксиом ZFC, 48 алгебраическая, 55 булевых функций полная, 205 неотрицательная, 111 остатков УКАЗАТЕЛЬ ТЕРМИНОВ 273 наименьших по абсолютной ве- личине, 103 неотрицательных, 103 полная, 103 симметричная, 103, 113 реляционная, 55 симметричная, 111 счисления восьмеричная, 87 двоичная, 86 позиционная, 85 смешанная, 88 шестнадцатеричная, 87 числовая наименьшая неотрицательная, 113 наименьшая по абсолютной ве- личине, 113 Системы изоморфные, 58 Слово, 43 пустое, 43 Сложение логическое, 185 по модулю 2, 185 Сложность (1, 1)-полюсника, 217 булевой функции, 217 схемы из функциональных элемен- тов, 219 функции, 220 Смешанная система счисления, 88 Соединение графов, 126 контактов параллельное, 216 последовательное, 216 Сомножитель, 99 Соответствие, 20 взаимно однозначное, 24 Соотношение рекуррентное, 177 Сочетание, 172 с повторением, 173 Список дуг, 124 над множеством, 93 пустой, 93 уступчатый, 153 Степень вершины, 139 Стрелка Пирса, 185 Структура, 55 смежности, 124 Сумма кольцевая, 185 множеств, 16 кольцевая, 16 остатков, 103 списков, 95 Суперпозиция функций, 188 Супремум, 42 Схема X n -функициональная минимальная, 220 X n -функциональная, 219 из функциональных элементов, 218 контактов, 216 электрическая, 216 Сюръекция, 24 Таблица Кэли, 56 истинности, 184, 187 Тавтология, 190 Теорема Биркгофа, 65 Дедекинда—Пеано, 79 Жегалкина, 206 Кантора, 32 Кантора—Бернштейна, 30 Квайна, 199 Понтрягина—Куратовского, 164 Поста, 208 Стоуна, 69 Ферма малая, 105 274 УКАЗАТЕЛЬ ТЕРМИНОВ Шеннона вторая, 195 первая, 194 арифметики основная, 100 о гомоморфизме, 63 о единственности неприводимого раз- ложения, 100 о сравнении множеств, 30 о существовании неприводимого раз- ложения, 100 о функциональной полноте, 195 о четырех красках, 165 об остатках китайская, 107 Терм сигнатуры Σ, 61 Тождественное отношение, 21 Тождество сигнатуры Σ, 65 Толщина графа, 165 Транспозиция, 171 Универсальное отношение, 21 Универсум, 15 алгебраической системы, 55 Уравнение линейное диофантово, 98 рекуррентное, 177 линейное неоднородное, 178 Утверждение двойственное, 70 Фактор-алгебра, 63 Фактор-множество, 38 Факториал, 28 Фильтр, 72 Фреше, 72 главный, 72 двойственный к идеалу, 72 Форма нормальная дизъюнктивная, 192 совершенная, 193 конъюнктивная, 192 совершенная, 193 Формула алгебры логики, 183 атомарная, 183 выполнимая, 190 общезначимая, 190 опровержимая, 190 представляющая функцию, 187 тождественно истинная, 190 тождественно ложная, 190 включений и исключений, 175 рекуррентная, 177 Формулы эквивалентные, 189 Функция, 23 n-местная, 25 алгебры логики, 186 биективная, 24 булева, 186 двоичная, 186 двойственная, 204 индикаторная, 32 инъективная, 23 линейная, 206 монотонная, 206 на, 24 переключательная, 186 проводимости, 216 разложимая, 208 разнозначная, 23 реализуемая (1, k)-полюсником, 217 схемой, 219 самодвойственная, 204 сохраняющая единицу, 205 нуль, 205 ставящая в соответствие элементу элемент, 23 сюръективная, 24 частичная, 23 Характеристика поля, 104 Хорда, 155 УКАЗАТЕЛЬ ТЕРМИНОВ 275 Целая часть числа, 95 Центр графа, 135 Цепи покрывающие, 142 Цепь, 129 гамильтонова, 142 простая, 129 эйлерова, 142 Цикл, 129, 170 гамильтонов, 142 простой, 129 фундаментальный, 155 эйлеров, 141 Цифра, 86 Ч.у.м., 41 Частичная функция, 23 Частичный порядок, 41 Частное, 97 пробное, 95 Часть графа, 124 числа целая, 95 Числа Фибоначчи, 177 взаимно простые, 98 Число базисное, 86 вещественное, 84 действительное, 83 иррациональное, 84 кардинальное, 29 комплексное, 85 натуральное, 26 перестановок, 168 планарности графа, 165 разбиений, 174 неупорядоченных, 174 упорядоченных, 174 размещений, 171 с повторениями, 173 рациональное, 82, 84 с плавающей точкой, 92 нормализованное, 92 сочетаний, 172 с повторениями, 173 хроматическое, 161 целое, 81 длинное, 94 короткое, 94 неразложимое, 99 простое, 100 разложимое, 99 составное, 99 цикломатическое, 144 Член числа старший, 115 Шестнадцатеричная система, 87 Штрих Шеффера, 185 Эквивалентность, 38, 183 Эквивалентные (1, 1)-полюсники, 217 Эксцентриситет вершины, 134 взвешенный, 135 Элемент, 13 максимальный, 42 минимальный, 42 наибольший, 42 наименьший, 42 непосредственно следующий, 27 обратный, 56 покрывающий, 45 функциональный, 218 Элементы несравнимые, 41 Эндоморфизм, 57 Эпиморфизм, 57 Ядро гомоморфизма, 63 Язык, 54 Указатель обозначений (1, 1)-полюсник, 216 минимальный, 217 (1, k)-полюсник, 216 (ϕ | ψ), 185 (ϕ ⊃ ψ), 184 (ϕ & ψ), 184 (ϕ · ψ), 184 (ϕ ↓ ψ), 185 (ϕ ↔ ψ), 183 (ϕψ), 184 (ϕ → ψ), 183 (ϕ ∨ ψ), 183 (ϕ ∧ ψ), 183 (a, b), 97 (a 1 , a n+1 )-маршрут, 129 (n, m)-выборка неупорядоченная, 172 с возвращениями, 173 упорядоченная, 171 (x 1 , x 2 , . . . , x n ), 19 ∗, 35 +, 16 −, 16 0, 26, 66, 85 0 A , 67 1, 26, 66, 85 1 A , 67 2, 26 2 A , 15 <, 41 A B, 15 A + B, 16 A − B, 16 A/E, 38 A = B, 14 A ∩ B, 15 A · B, 16 A ∪ B, 15 A ÷ B, 16 A ⊕ B, 16 A \ B, 16 A ∼ B, 29 A f → B, 23 A ⊂ B, 15 A ⊆ B, 14 A n , 19 A 1 × A 2 × · · · × A n , 19 A G , 121 A m n , 171 B 6 a, 42 B A , 25 B G , 122 C, 132, 156 C(n, m), 172 C m n , 172 УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ 277 E-класс, 38 F (G), 120 GL n (K), 56 G 1 + G 2 , 126 G 1 ∩ G 2 , 126 G 1 ∪ G 2 , 126 G 1 ⊕ G 2 , 126 G 1 × G 2 , 126 K, 158 K 0 (δ 1 , . . . , δ n ), 193 K 1 (δ 1 , . . . , δ n ), 193 K 5 , 164 K n , 128 K 3,3 , 164 K [a;b] , 216 L(G), 162 L(B, X), 66 L(f ), 220 L π (f ), 217 M , 206 N (0), 176 N i 1 ...i k , 175 O(a, A), 46 O[a, A], 46 P , 134 P (X), 22 P (n, m), 171 P (x 1 , x 2 , . . . , x n ), 20 P (n) , 54 P −1 , 22 P 0 , 205 P 1 ◦ P 2 , 22 P a (x), 177 P n , 168, 170 Q, 133 Q n , 128 R 0 (n, k), 174 R(m 1 , m 2 ), 174 R(m 1 , m 2 , . . . , m k ), 174 S, 133, 205 S(T ), 152 S n , 169 T (Σ), 61 U , 15 U A , 21 V 1 ⊥V 2 , 161 V m (Z 2 ), 160 W , 123 W (X), 43 W n (X), 44 [P ], 34 [P ] ∗ [Q], 35 [P ] + [Q], 35 [P ] · [Q], 35 [a, b], 98, 119 [a; b], 216 [x], 95 &, 184 ¤, 10 C, 14, 85 Con A, 67 Λ, 43, 93 ⇔, 10 MUX 2 m , 220 N, 14, 79, 81 Φ n , 197 Π, 42 Q, 14, 83 R, 14, 84 ⇒, 10 Σ, 54 Z, 14, 81 Z m , 102 α + β, 31 278 УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ α · β, 32 α β , 32 A, 16, 184 G, 126 ϕ, 184 a, 102 f , 189 x, 67 , 16, 184 ¡ n m ¢ , 172 P(A), 15 L, 43, 206 ∩, 15 ·, 16, 56, 184 χ(G), 161 ◦, 22 ∪, 15 deg a, 139 deg(G), 162 deg + a, 140 deg − a, 140 deg G a, 139 dom P , 21 δ P , 21 ↓, 185 ≡ m , 102 ∃, 10 ∀, 10 >, 41 ˆ C(n, m), 173 ˆ R(l 1 , l 2 , . . . , l r ; m 1 , m 2 , . . . , m r ), 174 ˆ, 56 id A , 21 inf B, 42 Ker ϕ, 63 hx 1 , x 2 , . . . , x n i, 19 ↔, 183 6, 41 A, 55 A/θ, 63 A ' B, 46, 58 A ⊆ B, 60 A 1 × A 2 × . . . × A n , 65 B, 55 B(X), 60 B + , 204 B 0 , 197 B C , 160 B K , 160 B n , 188 max A, 42 char, 104 НОД(a, b), 97 НОК(a, b), 98 |, 185 min A, 42 |= ϕ, 190 µ(α), 54 ¬, 183 ¬ϕ, 183 6|= ϕ, 190 ν(G), 144 ν ∗ (G), 144 ¯, 71, 159 ω, 14, 26 ⊕, 16, 71, 159, 185 π 1 (a), 93 π A,B 1 , 23 π A,B 2 , 23 π n (a), 93 π 2,...,n (a), 93 π n,...,1 (a), 93 n Q i=1 A i , 19 Q i∈I A i , 64 Q i∈I A i , 65 УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ 279 rang P , 21 ρ(a, b), 134 ρ P , 21 ρ w (a, b), 135 , 10 \, 16 ∼, 38, 189 sup B, 42 ×, 19 →, 183 ε, 170 ∅, 15 ϕ: A → B, 57 ϕ: A ∼ → B, 58 ϕ ∼ ψ, 189 ∨, 66, 183 ∧, 66, 183 {x | P (x)}, 13 a|b, 96 a + b, 28 a · b, 28 a 6 B, 42 b ≡ a (mod m), 102 c(G), 131 d(G), 134 e, 56 e(a), 134 e w (a), 135 f| X , 25 f : A → B, 23 f : A 1−1 −−→ B, 23 f : A на −→ B, 24 f : A ↔ B, 24 f : x 7→ y, 23 f ≡ 0, 188 f ≡ 1, 188 f ¹ X, 25 f ∨ g, 189 f ∧ g, 189 f + , 204 f (n) , 54 f ϕ , 189 f a,b (X), 216 k-полюсная контактная схема, 215 сеть, 215 l(a), 93 l(x), 19 n-ка, 19 n-куб, 128 n-мерный куб, 128 n-местная алгебраическая операция, 25 функция, 25 n-местное отношение, 20 n-местный предикат, 20 n 0 , 27 n!, 28 q t , 95 r(G), 135 r w (G), 135 t 1 ≈ t 2 , 65 w-расстояние, 135 x E y, 38 x ∈ M , 13 x / ∈ M , 13 x ¯ y, 71 x ⊕ y, 71 x ≺ y, 45 x ∼ y, 38 x ∨ y, 66 x ∧ y, 66 y = f (x), 23 F n , 197 Z, 95 1-1-функция, 23 УЧЕБНОЕ ИЗДАНИЕ Судоплатов Сергей Владимирович Овчинникова Елена Викторовна ДИСКРЕТНАЯ МАТЕМАТИКА Учебник 5- е издание, исправленное Редактор Т.П. Петроченко Выпускающий редактор И.П. Брованова Художественный редактор А.В. Ладыжская Корректор И.Е. Семенова Компьютерная верстка И.Д. Черных, С.В. Судоплатов Подписано в печать 24.12.2015 Формат 70 × 100 1/16. Бумага офсетная Уч.-изд. л. 22,5. Печ. л. 17,5 Тираж 3000 экз. (3-й з-д – 301–400 экз.) Изд. № 336/15. Заказ № 195 Налоговая льгота – Общероссийский классификатор продукции Издание соответствует коду 95 3000 ОК 005-93 (ОКП) Издательство Новосибирского государственного технического университета 630073 , г. Новосибирск, пр. К. Маркса, 20 Тел. (383) 346-31-87 E-mail: office@publish.nstu.ru Отпечатано в типографии Новосибирского государственного технического университета 630073 , г. Новосибирск, пр. К. Маркса, 20 |