Учебное пособие для студентов заочного факультета по дисциплине «Дискретная математика» (90
..pdf
|
x |
y |
f |
x, y |
|
|
|
|
|
|
|
|
0 |
0 |
|
0 |
|
|
0 |
1 |
|
1 |
|
|
1 |
0 |
|
1 |
|
|
1 |
1 |
|
1 |
|
60.Данная таблица истинности соответствует булевой функции… |
|||||
|
x |
y |
f |
x, y |
|
|
|
|
|
|
|
|
0 |
0 |
|
1 |
|
|
0 |
1 |
|
0 |
|
|
1 |
0 |
|
0 |
|
|
1 |
1 |
|
1 |
|
61.Данная таблица истинности соответствует булевой функции… |
|||||
|
x |
y |
f |
x, y |
|
|
|
|
|
|
|
|
0 |
0 |
|
1 |
|
|
0 |
1 |
|
1 |
|
|
1 |
0 |
|
0 |
|
|
1 |
1 |
|
0 |
|
62.Булевой функции |
|
f x, y |
x |
y соответствует таблица истинности… |
|||
63.Булевой функции |
f |
x, y |
x |
y соответствует таблица истинности… |
|||
64.Булевой функции |
f |
x, y |
x |
y соответствует таблица истинности… |
|||
65.Булевой функции |
f |
x, y |
x |
y |
соответствует таблица истинности… |
||
66.Булевой функции |
f |
x, y |
x |
y |
соответствует таблица истинности… |
||
67.Булевой функции |
|
|
|
|
|
соответствует таблица истинности… |
|
f |
x, y |
|
x |
||||
68.Свойство коммутативности конъюнкции…
69.Свойство ассоциативности конъюнкции…
70.Свойство дистрибутивности конъюнкции…
71.Свойство коммутативности дизъюнкции…
72.Свойство ассоциативности дизъюнкции…
73.Свойство дистрибутивности дизъюнкции… 74.Законы де Моргана для булевых операций… (Укажите не менее двух
пунктов).
75.Соответствие между названиями и формулировками законов булевой алгебры…
1) |
Закон противоречия. |
1) x |
x 1 . |
|||
2) |
Закон исключения третьего. |
2) |
|
|
|
0 . |
x x |
||||||
3) |
Закон двойного отрицания. |
3) |
|
|
|
|
|
|
|
||||
x |
x |
|||||
76.x …
77.x …
78.x … (Укажите не менее двух пунктов).
79.Совершенная дизъюнктивная нормальная форма булевой функции f x1, x2 ,..., xn …
11
80.Совершенная конъюнктивная нормальная форма булевой функции
f x1, x2 ,..., xn … |
|
|
|
|
|
|
|
|
|
|
|
||||||
81.Совершенная дизъюнктивная нормальная форма булевой функции не |
|
|
|
||||||||||||||
определена для функции f x1, x2 ,..., xn |
… |
|
|
|
|||||||||||||
82.Совершенная конъюнктивная нормальная форма булевой функции не |
|
|
|
||||||||||||||
определена для функции f x1, x2 ,..., xn |
… |
|
|
|
|||||||||||||
83.При построении совершенной дизъюнктивной нормальной формы |
|
|
|
||||||||||||||
элементарная конъюнкция x 1 x |
2 ...x |
n |
соответствует каждому значению |
|
|||||||||||||
1 |
|
|
|
|
|
2 |
|
|
n |
|
|
|
|
|
|
|
|
булевой функции, равному… |
|
|
|
|
|
|
|
|
|
|
|
||||||
84.При построении совершенной конъюнктивной нормальной формы |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
элементарная дизъюнкция x 1 |
x |
2 |
|
|
... |
x |
n соответствует каждому |
|
|
|
|||||||
1 |
|
|
|
|
2 |
|
|
|
|
n |
|
|
|
||||
значению булевой функции, равному… |
|
|
|
|
|
|
|||||||||||
85.При построении совершенной дизъюнктивной нормальной формы в |
|
|
|
||||||||||||||
конъюнкции мы записываем xi , если |
i |
… |
|
|
|
||||||||||||
86.При построении совершенной дизъюнктивной нормальной формы в |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
конъюнкции мы записываем xi |
, если |
i |
… |
|
|
|
|||||||||||
87.При построении совершенной конъюнктивной нормальной формы в |
|
|
|
||||||||||||||
дизъюнкции мы записываем xi , если |
i |
… |
|
|
|
||||||||||||
88.При построении совершенной конъюнктивной нормальной формы в |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||
дизъюнкции мы записываем xi |
, если |
i |
… |
|
|
|
|||||||||||
89.Полином Жегалкина булевой функции f |
|
x1, x2 ,..., xn … |
|
|
|
||||||||||||
90.При построении полинома Жегалкина элементарная конъюнкция x 1 x |
2 |
...x |
n |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
n |
|
соответствует каждому значению булевой функции, равному…
91.При построении полинома Жегалкина выражения xi заменяются по формуле
xi …
92.При построении полинома Жегалкина подобные слагаемые приводятся по
|
правилу x |
x |
… |
|||
93.Соответствие между полиномами Жегалкина и их степенями. |
||||||
1) |
xyz |
xz |
yz |
y |
|
1) 2. |
|
|
|
|
|
|
|
2) |
xz |
xy |
yz |
y |
|
2) 3. |
|
|
|
|
|
|
|
3) 1 |
|
|
|
|
3) 1. |
|
4) |
x |
y |
|
|
|
4) 0. |
|
|
|
||||
|
Символические определения: |
|||||
94.Класс T0 |
… |
|
|
|||
95.Класс T1 |
… |
|
|
|||
96.Класс S |
… |
|
|
|
||
97.Класс M … |
|
|
||||
98.Класс L |
… |
|
|
|
||
|
Словесные определения: |
|||||
99.Класс T0 |
- это класс… |
|||||
12
100.Класс T1 - это класс…
101.Класс S - это класс…
102.Класс M - это класс…
103.Класс L - это класс…
104.Система булевых функций F функционально полна, тогда и только тогда, когда… (Укажите не менее двух пунктов).
105.Функционально полной системе булевых функций соответствует таблица Поста…
1) |
T0 |
T1 |
S |
M |
L |
f1 |
- |
- |
+ |
- |
- |
f 2 |
+ |
+ |
- |
- |
- |
f 3 |
- |
- |
+ |
+ |
- |
|
|
|
|
|
|
|
|
|
|
|
|
2) |
T0 |
T1 |
S |
M |
L |
f1 |
+ |
- |
- |
- |
+ |
f 2 |
+ |
- |
- |
- |
- |
f 3 |
+ |
- |
+ |
- |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
3) |
T0 |
T1 |
S |
M |
L |
f1 |
+ |
- |
+ |
- |
+ |
f 2 |
+ |
+ |
+ |
+ |
- |
f 3 |
- |
- |
+ |
+ |
- |
|
|
|
|
|
|
|
|
|
|
|
|
4) |
T0 |
T1 |
S |
M |
L |
f1 |
+ |
- |
+ |
- |
+ |
f 2 |
+ |
+ |
- |
- |
+ |
f 3 |
- |
+ |
+ |
+ |
+ |
106.Перестановка - это…
107.Размещение из n элементов по m - это…
108.Сочетание из n элементов по m - это…
109.Выборка называется выборкой с повторением, если…
110.Выборка называется выборкой без повторений, если…
111.Множество называется упорядоченным, если…
112.Множество называется неупорядоченным, если…
113.Укажите неупорядоченные выборки…
114.Укажите все упорядоченные выборки (не менее двух пунктов)…
115.Формула числа сочетаний из n элементов по m без повторений…
116.Формула числа размещений из n элементов по m без повторений…
117.Формула числа перестановок из n элементов…
13
118.Формула числа размещений из n элементов по m с повторениями…
119.Формула числа перестановок из n элементов с повторениями…
120. |
Формула числа сочетаний из n элементов по m с повторениями… |
||||||
|
|
k |
|
|
|
|
|
121. |
Пусть множество |
A |
Ai , |
A |
n , |
Ai |
ni , i 1,..., k . n1, n2 ,..., nk - |
|
|
i |
1 |
|
|
|
|
разбиением множества A называется совокупность множеств Ai , i 1,..., k , удовлетворяющих условиям… (Укажите не менее двух пунктов).
122. Число n , n ,..., n |
-разбиений множества A Cn1,n2 ,...,nk |
… |
|
1 2 |
k |
n |
|
123. Соответствие между соединениями и формулами…
1) |
Число сочетаний из n |
1) Anm |
nm . |
|
|
|
|
|
|
||||||
элементов |
по m |
без |
|
|
|
|
|
|
|
|
|
|
|
||
повторений. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2) |
Число размещений из |
|
n |
|
|
|
|
n! |
|
||||||
|
|
|
|
|
2) |
P(n ,n ,...,n ) |
|
|
|
|
|
, |
|||
n |
элементов |
по m |
без |
|
n1 !n2 !...nk ! |
||||||||||
1 |
2 k |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
повторений. |
|
|
|
n1 |
n2 ... |
|
nk |
|
n. |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
3) |
Число |
перестановок |
3) Pn |
n!. |
|
|
|
|
|
|
|||||
из n элементов. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
4) |
Число размещений из |
4) Cnm |
|
|
|
n! |
. |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
элементов |
по m |
с |
|
|
|
|
|
|
|
|
|
|
||
n |
|
|
|
|
m! |
n |
m ! |
|
|||||||
повторениями. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
5) |
Число |
перестановок |
5) Am |
|
n! |
. |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
из |
|
элементов |
с |
|
n |
|
|
|
|
|
|
|
|
||
n |
|
|
n |
|
m ! |
|
|||||||||
|
|
|
|
|
|
||||||||||
повторениями. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
124. Соответствие между определениями и терминами…
1)Неупорядоченное 1) Перестановка. множество из m
элементов, выбранных из данных n элементов.
2)Установленный в 2) Сочетание из n
конечном |
множестве элементов по m . |
порядок. |
|
3)Упорядоченное 3) Размещение из n
множество |
из |
m элементов по m . |
элементов, |
выбранных |
|
из данных n элементов. |
||
14
125.Если какой-либо объект A может быть выбран n способами, и после каждого такого выбора объект B можно выбрать m способами, то выбор пары A, B в указанной последовательности осуществляется … способами.
126.Если какой-либо объект A может быть выбран n способами, а какой-либо объект B - m способами, и ни один из способов выбора объекта A не совпадает ни с одним из способов выбора объекта B , то выбор либо A , либо B осуществляется … способами.
127.Число способов выбора 5 карт из 36…
36!
1)5! .
2)A365 .
3)P5 .
4)C365 .
5)120.
128.Число способами выбора 3 карт из 52…
1)P3 .
2)A523 .
3)523!! .
4)C523 .
5)3!.
129.В правление избрано 10 человек. Из них требуется выбрать председателя, секретаря и казначея. Это можно сделать … способами.
1)C103 .
2)A103 .
3)P3 .
4)310!7!! .
5)6.
130.Число способов выбора 2 дам из колоды в 36 карт при случайном извлечении трех карт…
1)6.
2)C42 .
3)P2 .
4)323!! .
5)C42C321 .
131.Число способов выбора 3 тузов из колоды в 36 карт при случайном извлечении трех карт…
1)C43 .
15
2)A43 .
3)363!! .
4)C363 .
5)3!.
132.В группе 25 студентов. Из них требуется выбрать старосту, заместителя старосты и финорга. Это можно сделать … способами.
1)P3 .
2)6.
3)A253 .
4)3!22!25! .
5)C253 .
133.Cnn k …
134.Cn0 Cn1 ... Cnn …
135.a b n …
136.a b n …
137.Общий член разложения a b n (формулы Ньютона)…
138.Общий член разложения a b n …
139. Cn0 Cn2 ... Cn2l …
140.Cnk Cnk 1 …
141.Строка треугольника Паскаля с номером n …
142. x1 x2 ... xk n …
143. |
Пусть N предметов могут обладать свойствами |
1 , |
2 ,..., n . N |
i |
- число |
|||||
предметов, обладающих свойством |
i , i |
1,..., n , |
N |
i |
- число предметов, не |
|||||
обладающих свойством |
i , i 1,..., n . Тогда N 1 |
2 ... |
n |
… |
|
|
||||
144. |
Пусть N предметов могут обладать свойствами |
1 , |
2 ,..., n . N |
i |
- число |
|||||
предметов, обладающих свойством |
i , i |
1,..., n , |
N |
i |
- число предметов, не |
|||||
обладающих свойством |
i , i 1,..., n . Тогда формула включения и |
|
|
|||||||
исключения… |
|
|
|
|
|
|
|
|
|
|
145. |
Беспорядок – это такая перестановка n элементов, при которой… |
|
||||||||
146. |
Число беспорядков из n элементов Dn |
… |
|
|
|
|
|
|||
147. |
Число перестановок, при которых r |
элементов остаются на своем месте, а |
||||||||
остальные n r меняются местами Dn,r |
… |
|
|
|
|
|
||||
148.Метод рекуррентных соотношений – это метод решения задачи …
149.Линейное рекуррентное соотношение…
16
150. Частное решение линейного рекуррентного соотношения ищут в виде…
151. |
V G |
- множество вершин графа G . Пара xi , x j называется ребром графа |
||
G , если… |
|
|||
1) |
xi , xj |
V G . |
|
|
2) |
xi , xj |
V G . |
|
|
3) |
xi |
V G , xj |
V G . |
|
4) |
xi |
V G , xj |
V G . |
|
5)xi , x j - изолированные вершины графа G .
152.Граф G имеет … ребер.
G
153. Граф G имеет … вершин.
G
154. Граф G имеет … вершин.
G
155.Вершины xi и x j графа G называют смежными, если…
156.В графе G укажите все вершины, смежные вершине x2 …
17
|
|
G |
|
|
|
|
|
x2 |
|
|
|
|
x1 |
|
x3 |
|
|
|
|
|
|
|
|
|
x4 |
x5 |
x6 |
|
|
|
|
|
|
|
|
157. |
Два ребра графа G называют смежными, если… |
|
|||
158. |
В графе G укажите все ребра, смежные ребру |
x1 , x2 |
… |
||
|
|
G |
|
|
|
|
|
x2 |
|
|
|
|
x1 |
|
|
|
|
|
x4 |
x5 |
x6 |
|
|
|
|
|
|
|
|
159. |
Вершина xi графа G инцидентна ребру… |
|
|
||
1) |
xi , x j |
E G . |
|
|
|
2) |
xi , x j |
E G . |
|
|
|
18
3) |
xk , xl |
E G . |
4) |
xk , xl |
E G . |
5) |
xk , x j |
E G . |
160. |
Ребро |
xi , x j инцидентно… (Укажите не менее двух пунктов). |
1)Вершине xi .
2)Вершине xk , не смежной xi .
3)Произвольной изолированной вершине.
4)Вершине x j .
161.Вершина xi графа G инцидентна ребру… (Укажите не менее двух пунктов).
1) |
xk , x j |
E G . |
2) |
xi , xk |
E G . |
3) |
xk , xl |
E G . |
4) |
xk , xl |
E G . |
5) |
xi , x j |
E G . |
162. |
В графе G укажите все вершины, инцидентные ребру x2 , x5 … |
|
|
G |
|
|
x2 |
|
x1 |
|
x3 |
|
|
|
x4 |
x5 |
x6 |
|
|
163. В графе G укажите все ребра, инцидентные вершине x5 …
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
|
|
|
G |
|
|
|
|
x2 |
|
|
x1 |
|
|
x3 |
|
|
|
|
|
|
x4 |
|
x5 |
x6 |
|
|
|
|
|
164. |
Ребро |
xi , x j |
графа G называются неориентированным, если… |
|
165.Нуль-граф – это граф, который…
166.Ребро xi , x j графа G называется петлей, если…
167.Граф называется ориентированным, если…
168.Граф называется неориентированным, если…
169.Граф называется смешанным, если…
170.Полный граф – это граф, содержащий…
171.Изоморфизм двух графов – это…
172.Матрицей смежности неориентированного графа G с n вершинами называется матрица…
173.Матрицей смежности ориентированного графа D с n вершинами называется матрица…
174.Матрицей инцидентности неориентированного графа G с n вершинами и m ребрами называется матрица…
175.Матрицей инцидентности ориентированного графа D с n вершинами и m ребрами называется матрица…
176.A G
ij n n
- матрица смежности неориентированного графа G . Тогда
при i |
1,..., n , |
… |
|
1) |
ij |
ji 0 . |
|
2) |
ij |
ji . |
|
3) |
ij |
ji . |
|
4) |
ij |
ji . |
|
5) |
ij |
ji . |
|
177. |
Степень вершины xi графа G ( xi ) -… |
||
20