Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф

• Название: Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
• Анкор: Судоплатов С.В., Овчинникова Е.В. Дискретная математика.pdf
• Дата: 24.04.2018
• Размер: 1.36 Mb.
• Имя файла: Судоплатов С.В., Овчинникова Е.В. Дискретная математика.pdf
• Тип: Учебник; #18441
• страница: 6 из 7

а){→, ¬}; б) {↔, ⊕}; в) {↓}; г) {∧, →, Какие из указанных систем образуют базис?
После изучения главы 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).

ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ
135
Вариант 17 1. (A \ B) \ C = (A \ C) \ (B \ C);
A ⊆ B, C ⊆ D ⇒ A × C ⊆ B × D.
2. n(2n
2
− 3n + 1) кратно 6 для всех натуральных n.
3. 2
ω
+ n = 2
ω
4. P
1
= { a, 2 , a, 3 , a, 4 , c, 3 , c, 1 , c, 4 },
P
2
= { 1, 4 , 2, 3 , 2, 1 , 3, 4 , 4, 2 }.