- •Индивидуальное домашнее задание по дискретной математике
- •5. Выяснить взаимное расположение множеств d, e, f, если а, в, х – произвольные подмножества универсального множества u.
- •6. Упростить выражение.
- •8. Для данного графика р найти: р-1, р°р, р-1°р, пр2(р-1°р) ´ пр1(р°р).
- •13. Сколькими способами из колоды в 36 листов можно выбрать не упорядоченный набор из 5 карт так, чтобы в этом наборе было бы точно:
- •14. Сколько различных слов можно получить перестановкой букв слова ?
- •16. Из данной пропорции найти х и y
- •17. Найти коэффициенты при xk в разложении данного выражения р по полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов.
- •18. Сколько натуральных чисел от 1до 10000 не делится ни на , ни на , ни на , ни на ?
- •19. Подсчитать количество различных перестановок цифр данного числа , при которых никакие n одинаковых цифр не идут друг за другом.
- •20. Сколько существует перестановок n различных предметов, при которых на своих первоначальных местах окажутся ровно k или ровно m предметов?
- •21. Составив таблицы истинности, выясните, равносильны ли следующие формулы алгебры высказываний:
- •22. Докажите, что следующая формула является тавтологией алгебры высказываний:
- •23. Построить таблицу данной булевой функции f(X, y, z)
- •27. Преобразовать данную формулу f(X,y,z) в эквивалентную ей, но не содержащую фиктивных переменных.
- •28. Выяснить вопрос о равносильности днф сведением их к сднф. Преобразовать с помощью дистрибутивных законов в кнф, упростить полученное выражение.
- •29. Найти двумя способами полином функции. Найти сднф, скнф.
- •30. Для функции f(x1, x2, x3, x4) минимизировать ее сднф двумя способами.
- •31. Доопределить функции f(X,y,z), g(X,y,z), h(X,y,z) так, чтобы f Если построение какой-либо функции невозможно, докажите это. Выясните вопрос о принадлежности построенных функций к классам
6. Упростить выражение.
№ |
Выражение |
№ |
Выражение |
1 |
16 |
||
2 |
17 |
||
3 |
18 |
||
4 |
19 |
||
5 |
20 |
||
6 |
21 |
||
7 |
22 |
||
8 |
23 |
||
9 |
24 |
||
10 |
25 |
||
11 |
26 |
||
12 |
27 |
||
13 |
28 |
||
14 |
29 |
||
15 |
30 |
7. Проверить справедливость равенства для А=1,2, В=2,3, С=1,3. Выяснить, верно ли равенство для произвольных А, В, С.
№ |
|
№ |
|
1 |
АС=(А(С\В)) (А(СВ)) |
16 |
BA=(B(AС)) (BA) |
2 |
АС=(А(СВ)) (АС) |
17 |
BA=(BA) (B(A\С)) |
3 |
А(ВС)=(А(СВ)) \ (А(СВ)) |
18 |
B(AС)=(B(A\С)) (BС) |
4 |
АС=(А(С\В)) (АС) |
19 |
BA=(BA) (B(AС)) |
5 |
А(ВС)=(АВ) (А(С\В)) |
20 |
B(A\С)=(BA) \ (B(AС)) |
6 |
А(С\B)=(АС) (А(СВ)) |
21 |
BA=(B(AC)) \ (B(C\A)) |
7 |
АС=(А(СВ)) (АС) |
22 |
B(AС)=(BA) \ (B(A\С)) |
8 |
А(C (ВС))=(А(СВ)) (АС) |
23 |
B(A\С)=(BA) (B(AС)) |
9 |
А(С\B)=(АС) \ (А(СВ)) |
24 |
B(A\С)=(BAС)) \ (BС) |
10 |
А(ВС)=(А(ВС)) (А(СВ)) |
25 |
CB=(C(B\A)) (C(BA)) |
11 |
АС=(А(СВ)) \ (А(B\С)) |
26 |
CB=(C(BA)) (CB) |
12 |
А(ВС)=(АС) \ (А(С\В)) |
27 |
C(AB)=(C(AВ)) \ (C(AВ)) |
13 |
А(ВС)=(А(ВС)) \ (А(ВС)) |
28 |
CB=(C(B\A)) (CB) |
14 |
А(С\B)=(А(ВС)) \ (АВ) |
29 |
C(AB)=(CA) (C(B\A)) |
15 |
BA=(B(A\С)) (B(AC)) |
30 |
C(B\A)=(CB) (C(AB)) |
8. Для данного графика р найти: р-1, р°р, р-1°р, пр2(р-1°р) ´ пр1(р°р).
№ |
Р |
№ |
Р |
1 |
(1,2), (1,3), (4,2), (2,3), (3,3) |
16 |
(c,c), (c,b), (b,b), (a,b), (c,a) |
2 |
(2,2), (4,4), (1,2), (3,1), (3,4) |
17 |
(e,a), (a,a), (a,e), (e,b), (b,a) |
3 |
(1,2), (2,3), (3,1), (2,2), (3,2) |
18 |
(f,d), (b,d), (d,d), (c,b), (f,c) |
4 |
(3,3), (3,2), (2,2), (1,2), (3,1) |
19 |
(a,a), (a,b), (b,c), (c,a), (c,b) |
5 |
(0,1), (1,1), (1,0), (0,2), (2,1) |
20 |
(a,c), (c,a), (b,b), (a,b), (a,d) |
6 |
(5,4), (2,4), (4,4), (3,2), (5,3) |
21 |
(c,g), (g,d), (d,d), (g,c), (d,c) |
7 |
(1,1), (1,2), (2,3), (3,1), (3,2) |
22 |
(e,b), (b,c), (c,c), (c,e), (e,e) |
8 |
(3,1), (1,3), (2,2), (1,2), (1,4) |
23 |
(a,f), (f,b), (b,b), (a,a), (a,c) |
9 |
(3,8), (8,4), (4,4), (8,3), (4,3) |
24 |
(e,b), (e,c), (e,e), (a,b), (b,c) |
10 |
(0,2), (2,3), (3,0), (3,3), (0,0) |
25 |
(x,y), (x,z), (t,y), (z,z), (y,z) |
11 |
(1,5), (5,2), (2,2), (1,1), (1,3) |
26 |
(y,y), (t,t), (x,y), (z,x), (z,t) |
12 |
(0,2), (0,3), (0,0), (1,2), (2,3) |
27 |
(x,y), (y,z), (z,x), (y,y), (z,y) |
13 |
(а,b), (a,c), (d,b), (c,c), (b,c) |
28 |
(z,z), (z,y), (y,y), (x,y), (z,x) |
14 |
(b,b), (d,d), (a,b), (c,a), (c,d) |
29 |
(t,x), (x,x), (x,t), (t,y), (y,x) |
15 |
(a,b), (b,c), (c,a), (b,b), (c,b) |
30 |
(w,t), (y,t), (t,t), (z,y), (w,z) |
9. Дано соответствие Г=(X, Y, G). Выяснить, какими из 4 основных свойств (всюду определенность, сюръективность, функциональность, инъективность) обладает Г. Найти образ множества А и прообраз множества В при данном соответствии. Построить соответствие между бесконечными множествами, обладающее тем же набором свойств, что и Г. Построить соответствие между конечными множествами, обладающее набором свойств, противоположным данному.
№ |
X |
Y |
G |
A |
B |
1 |
a, b, c, d, e |
1, 2, 3 |
(a,2), (b,3), (c,1), (d,2), (e,1) |
e,c |
2,3 |
2 |
a, b, c, d |
1, 2, 3, 4 |
(a,4), (b,3), (c,2), (d,1) |
a,b |
1,3 |
3 |
a, b, c, d |
1, 2, 3, 4, 5 |
(a,3), (b,5), (c,4), (d,1) |
a,c |
1,4 |
4 |
a, b, c, d, e |
1, 2, 3, 4 |
(d,1), (b,2), (e,4), (a,3) |
b,c |
1,2 |
5 |
a, b, c, d, e |
1, 2, 3 |
(b,2), (c,1), (e,3), (a,3) |
e,c |
3,1 |
6 |
a, b, c, d |
1, 2, 3, 4 |
(a,2), (b,3), (c,1), (a,4) |
a,b |
1,2 |
7 |
a, b, c, d, e |
1, 2, 3, 4, 5 |
(a,5), (b,3), (d,1), (e,2) |
d,e |
1,3 |
8 |
a, b, c, d |
1, 2, 3, 4 |
(a,3), (b,4), (c,3), (d,1) |
a,c |
1,3 |
9 |
a, b, c |
1, 2, 3, 4, 5 |
(a,2), (b,1), (c,5), (a,3) |
a,b |
3,4 |
10 |
a, b, c |
1, 2, 3 |
(a,1), (a,3), (b,2), (c,3) |
a,c |
2,3 |
11 |
a, b, c, d |
1, 2, 3, 4, 5 |
(a,2), (c,1), (d,5), (c,3) |
b,c |
1,2 |
12 |
a, b, c, d, e |
1, 2, 3, 4 |
(b,1), (c,3), (d,2), (c,1) |
a,c |
1,2 |
13 |
a, b, c, d |
1, 2, 3 |
(a,1), (b,1), (c,3), (b,2) |
b,d |
1,3 |
14 |
a, b, c, d |
1, 2, 3, 4 |
(a,4), (b,3), (b,2), (c,3), (d,4) |
a,b |
3,4 |
15 |
a, b, c, d |
1, 2, 3, 4 |
(a,4), (c,4), (b,2) (a,3) |
a,b |
2,4 |
16 |
a, b, c, d, e |
1, 2, 3 |
(a,2), (b,1), (d,3), (e,1) |
a,b |
1,2 |
17 |
a, b, c, d |
1, 2, 3, 4 |
(b,3), (a,2), (c,2), (d,1) |
a,c |
1,4 |
18 |
a, b, c, d |
1, 2, 3, 4 |
(a,3), (c,2), (d,1), (c,4) |
c,d |
2,3 |
19 |
a, b, c |
1, 2, 3, 4, 5 |
(a,2), (b,5), (c,4), (b,3) |
a,b |
2,5 |
20 |
a, b, c, d |
1, 2, 3 |
(a,1), (b,3), (a,2), (c,4) |
a,b |
2,3 |
21 |
a, b, c, d |
1, 2, 3 |
(a,3), (b,3), (c,1), (d,2) |
c,d |
1,3 |
22 |
a, b, c, d |
1, 2, 3 |
(a,1), (b,3), (c,2), (a,2) |
c,d |
2,3 |
23 |
a, b, c, d |
1, 2, 3, 4 |
(a,3), (b,4), (c,1), (d,2) |
a,b |
1,4 |
24 |
a, b, c |
1, 2, 3, 4 |
(a,3), (b,1), (c,2), (c,1) |
a,c |
4,2 |
25 |
a, b, c, d, e |
1, 2, 3 |
(c,2), (d,1), (a,3), (b,3) |
a,d |
3,1 |
26 |
a, b, c, d |
1, 2, 3, 4 |
(b,2), (c,3), (d,1), (b,4) |
b,c |
1,2 |
27 |
a, b, c, d, e |
1, 2, 3, 4, 5 |
(b,5), (c,3), (e,1), (a,2) |
a,e |
1,3 |
28 |
a, b, c, d |
1, 2, 3, 4 |
(b,3), (c,4), (d,3), (a,1) |
b,d |
3,1 |
29 |
a, b, c |
1, 2, 3, 4, 5 |
(b,2), (c,1), (a,5), (b,3) |
b,c |
4,3 |
30 |
a, b, c |
1, 2, 3 |
(b,1), (b,3), (c,2), (a,3) |
a,b |
2,3 |
10. Дано соответствие Г=(X, Y, G). Выяснить, какими из 4 основных свойств (всюду определенность, сюръективность, функциональность, инъективность) обладает Г. Построить соответствие между конечными множествами, обладающее набором свойств, противоположным данному.
№ |
Х |
Y |
G |
1 |
Многочлены 2 степени от одной переменной с действительными коэффициентами |
R |
(многочлен, его корень) |
2 |
Множество кругов на плоскости |
Множество точек плоскости |
(круг, его центр) |
3 |
(0, +) |
[-1, 1] |
(x, y): x2<y |
4 |
N={1, 2, …} |
R |
(x, lnx) |
5 |
R |
Непрерывные на [a, b] функции |
(max f(x), f(x)) x[a, b] |
6 |
Вузы г. Тольятти |
Жители г. Тольятти |
(вуз; человек, окончивший этот вуз) |
7 |
(0, +) |
Отрезки на прямой |
(х, отрезок длины х) |
8 |
Фамилии студентов вашей группы |
{1, 2, …, 100} |
(фамилия, число букв в фамилии) |
9 |
Окружности на плоскости |
Z |
(окружность, ее длина) |
10 |
Функции, определенные на [0, 1] |
R |
(функция, ордината ее точки максимума) |
11 |
R2 |
N |
((x, y), ) |
12 |
Имена студентов вашей группы |
Буквы русского алфавита |
(имя, буква из имени) |
13 |
N |
Студенты нашего вуза |
(n, человек с годом рождения n) |
14 |
[0, 1] |
{0, 1} |
(x, f(x)) 0, xR\Q f(x)= 1, xQ
|
15 |
R |
R10 |
(max ai, (a1, a2,…,a10)) 1i10 |
16 |
Окружности на плоскости |
Прямые на плоскости |
(окружность, касательная к окружности) |
17 |
[(P(U)]3 |
P(U) |
((A, B, C), ABC) |
18 |
[0, 1] |
R2 |
(x, (x,y): x2+y2=1) |
19 |
R |
Функции непре-рывные на [0, 1] |
(m, f(x): min f(x)=m) 0x1 |
20 |
{0, 1, 2} |
N |
(x,y): х – остаток от деления y на 3 |
21 |
[1, 3] |
R+ |
(x,y): (x-2)2+(y-2)21 |
22 |
Пары окружностей на плоскости |
R2 |
(пара окружностей, координаты точки пересечения этих окружностей) |
23 |
Множество книг в библиотеке РГГУ |
Z |
(книга, число страниц в этой книге) |
24 |
(-4, 4) |
[1, 6] |
(x,y): y=x-2+1 |
25 |
Мужчины г. Тольятти |
Женщины г. Тольятти |
(x,y): x и y состоят или когда-либо состояли друг с другом в законном браке |
26 |
[(P(U)]2 |
P(U) |
((A, B), A\B) |
27 |
Политические партии г. Тольятти |
Жители г. Тольятти |
(партия, человек, состоящий в этой партии) |
28 |
P(U) |
[(P(U)]2 |
(D, (A, B, C,): ABC=D) |
29 |
P(U), где U={1, 2, …, 40} |
N |
(A, A), где АP(U) |
30 |
Пары прямых на плоскости |
R |
(пара прямых, абсцисса точки пересечения прямых) |
11. Проверить для произвольных отношений F и Y справедливость утверждения: «Если отношения F и Y обладают свойством a, то отношение Т также обладает свойством a». Обозначения: 1 – рефлексивность, 2 – антирефлексивность, 3 – симметричность, 4 – антисимметричность, 5 – транзитивность, 6 – связность.
№ |
a |
Т |
№ |
a |
Т |
№ |
a |
Т |
1 |
2 |
FÈY |
11 |
3 |
F°Y |
21 |
5 |
F\Y |
2 |
2 |
FÇY |
12 |
3 |
F-1 |
22 |
5 |
FDY |
3 |
2 |
F\Y |
13 |
4 |
FÈY |
23 |
5 |
F°Y |
4 |
2 |
FDY |
14 |
4 |
FÇY |
24 |
5 |
F-1 |
5 |
2 |
F°Y |
15 |
4 |
F\Y |
25 |
5 |
Y-1 |
6 |
2 |
F-1 |
16 |
4 |
FDY |
26 |
6 |
FÇY |
7 |
3 |
FÈY |
17 |
4 |
F°Y |
27 |
6 |
F\Y |
8 |
3 |
FÇY |
18 |
4 |
F-1 |
28 |
6 |
FDY |
9 |
3 |
F\Y |
19 |
5 |
FÈY |
29 |
6 |
F°Y |
10 |
3 |
FDY |
20 |
5 |
FÇY |
30 |
6 |
F-1 |
12. Выяснить, какими из свойств обладает данное отношение F=(A, G). Выяснить, что представляет собой отношение F°F, F°F-1. Построить на конечном множестве отношение, обладающее таким же набором свойств, что и данное. Построить на бесконечном множестве отношение, обладающее набором свойств, противоположным данному. В случае невозможности построения доказать противоречивость набора требований.
№ |
A |
G |
1 |
Множество студентов РГГУ |
x r y Û x и y учатся на одном курсе |
2 |
P(U), гдеU – множество точек плоскости |
А r В Û А Ç В =Æ |
3 |
Множество окружностей на плоскости |
x r y Û x касается y |
4 |
Жители Тольятти на начало этого года |
x r y Û x и y супруги |
5 |
Жители России на начало этого года |
x r y Û x и y состоят в одной и той же политической партии |
6 |
Прямые в пространстве |
x r y Û x и y имеют хотя бы одну общую точку |
7 |
Жители Тольятти на начало этого года |
x r y Û x и y разного возраста |
8 |
N |
x r y Û x и y имеют одинаковый остаток от деления на 3 |
9 |
P(N) |
А r В Û ½А½=½В½ |
10 |
R |
x r y Û 2x > y2 |
11 |
{(a1, a2,…, an): aiÎ{0,1}} |
x r y Û x и y отличаются только в одной координате |
12 |
R2 |
(x, y) r (z, t) Û x=z и y=t |
13 |
R |
x r y Û x2 + y2=1 |
14 |
Жители России на начало этого года |
x r y Û x старше y |
15 |
[0, 4] |
x r y Û x >2y+1 |
16 |
R |
x r y Û x и y имеют одинаковую целую часть |
17 |
N |
x r y Û xy кратно трем |
18 |
P(U), гдеU – множество точек плоскости |
А r В Û А и В – в общем положении |
19 |
Жители Тольятти на начало этого года |
x r y Û y – теща для х |
20 |
[0, 2] |
x r y Û x + y<1 |
21 |
N2 |
(x, y) r (z, t) Û xz = yt |
22 |
N |
x r y Û x +y кратно трем |
23 |
Непрерывные на [0, 1] функции |
|
24 |
Rn |
(a1, …, an) r (b1,…, bn) Û {max ai, 1£i£n}={max bi, 1£i£n} |
25 |
Жители Тольятти на начало этого года |
x r y Û x - отец для y |
26 |
R |
x r y Û x =2y+3 |
27 |
Читатели библиотеки РГГУ |
x r y Û x и y прочитали одну и ту же книгу |
28 |
P(U), гдеU – множество точек плоскости |
А r В Û А Ç В =Æ |
29 |
Векторы на плоскости |
x r y Û ½x½=½y½ |
30 |
Жители России на начало этого года |
x r y Û x внук y |