ДМ Практикум
.pdf
14.Дизъюнкцией высказываний Р и Q называется высказывание …
а) истинное, когда оба высказывания Р и Q истинны, и ложное во всех остальных случаях;
б) ложное, когда оба высказывания Р и Q ложны, и истинное во всех остальных случаях;
в) истинное, когда истинностные значения Р и Q совпадают, и ложное в противоположном случае;
г) истинное, когда истинностные значения Р и Q не совпадают, и ложное в противоположном случае.
15.Высказывание «для всех x из области определения P(x) истинно»
обозначается… |
|
|
|
|
||
а) xP(x) ; |
б) |
xP(x) ; |
||||
|
|
|
г) |
|
|
|
в) xP(x) |
; |
xP(x) . |
||||
16. Матрица смежности |
A(G) н-графа G , изображенного на рисунке, имеет |
|||||
вид… |
|
|
|
|
||
|
|
0 |
1 |
2 |
1 |
|
|
|
0 |
1 |
1 |
1 |
|
||
|
|
1 |
0 |
1 |
0 |
|
|
|
|
1 |
0 |
1 |
0 |
|
|
а) |
|
|
; |
б) |
|
|
; |
||||||||
|
|
2 |
1 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
2 |
|
|
|
1 |
|
||||||||
|
|
0 |
1 |
2 |
1 |
|
|
|
0 |
1 |
1 |
1 |
|
||
|
|
1 |
0 |
1 |
0 |
|
|
|
|
1 |
0 |
1 |
0 |
|
|
в) |
|
|
; |
г) |
|
. |
|||||||||
|
|
2 |
1 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
1 |
|
|
|
2 |
|
||||||||
17.Дана матрица смежности н-графа G
0 |
1 |
2 |
1 |
|
|
|
|
|
|
1 |
0 |
1 |
0 |
|
|
|
|
A(G) = |
|
. Степень вершины v равна… |
||||||
|
2 |
1 |
0 |
1 |
|
|
|
4 |
|
|
0 |
1 |
2 |
|
|
|
|
1 |
|
|
|
|
||||
а) 2; |
|
|
|
б) 4; |
в) 6; |
г) 3. |
||
101
|
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
1 . |
18. Матрица достижимости орграфа G имеет вид R(G) = |
1 |
1 |
1 |
1 |
||
|
|
0 |
0 |
0 |
1 |
|
|
|
1 |
||||
|
|
|
0 |
0 |
1 |
|
|
0 |
1 |
||||
|
|
|
|
Число компонент сильной связности орграфа G равно… |
|||
а) 2; |
б) 3; |
в) 4; |
г) 5. |
19.Матрица смежности н-графа, содержащего эйлеров цикл, может иметь вид…
|
|
0 |
1 |
2 |
1 |
|
|
|
2 |
1 |
1 |
0 |
|
||
|
|
1 |
0 |
1 |
0 |
|
|
|
|
1 |
0 |
1 |
0 |
|
|
а) |
|
|
; |
б) |
|
|
; |
||||||||
|
|
2 |
1 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
0 |
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
0 |
0 |
0 |
|
|
|
|
|
2 |
|
|
|
2 |
|
||||||||
|
|
0 |
1 |
2 |
0 |
|
|
|
0 |
2 |
0 |
0 |
|
||
|
|
1 |
0 |
0 |
0 |
|
|
|
|
2 |
0 |
0 |
0 |
|
|
в) |
|
|
; |
г) |
|
. |
|||||||||
|
|
2 |
0 |
0 |
2 |
|
|
|
|
0 |
0 |
0 |
2 |
|
|
|
|
0 |
0 |
2 |
|
|
|
|
|
0 |
0 |
2 |
|
|
|
|
|
0 |
|
|
|
0 |
|
||||||||
20.Граф задан матрицей весов
|
∞ |
1 |
∞ |
1 |
|
|
|
|
|
|
1 |
∞ |
5 |
1 |
|
. Вес его минимального остова равен… |
|
|
W (G) = |
∞ |
5 |
∞ |
5 |
|
||
|
|
|
|
|
||||
|
|
|
1 |
5 |
|
|
|
|
|
1 |
∞ |
|
|
||||
а) 5; |
б) 7; |
|
|
в) 4; |
г) 6. |
|||
21.Три шага алгоритма Дейкстры приведены в таблице
v*, d (v *), p (v *) |
d (v1 ) |
|
d (v2 ) |
d (v3 ) |
d (v4 ) |
d (v5 ) |
d (v6 ) |
d (v7 ) |
v1,0, |
– |
|
4 |
∞ |
2 |
1 |
∞ |
∞ |
v5 ,1,1 |
– |
|
4 |
6 |
2 |
_ |
∞ |
2 |
v4 , 2,1 |
– |
|
4 |
3 |
_ |
_ |
6 |
2 |
Ведущая вершина на четвертом шаге… |
|
|
|
|||||
а) v7 ; |
б) |
v2 ; в) |
v3 ; |
г) |
v6 . |
|
|
|
102
22.Две вершины н-графа называются смежными, если…
а) существует соединяющее их ребро; б) существует соединяющий их маршрут; в) их степени совпадают;
г) их соединяет единственная простая цепь.
23.Связный граф без циклов называется…
а) |
деревом; |
б) |
лесом; |
|
в) |
эйлеровым графом; |
г) |
простым графом. |
|
24.К.д.а. задан диаграммой Мура (начальное состояние s0 ):
Входное слово 0011 к.д.а. преобразует в выходное слово…
а) 0001; |
б) 0111; |
в) 0110; |
г) 0100. |
25.К.д.а. называется инициальным, если…
а) в нем выделено начальное состояние; б) входной алфавит состоит из одного элемента;
в) алфавит состояний состоит из одного элемента; г) функция выходов не зависит от элементов входного алфавита.
Вариант 2
1.. Дано множество U={a,b,c,d,e,f} и три его подмножества
A={a,b,c}, B={b,c,d,f}, C={a,c,e}.
Множество ( A È B) ÇC равно…
а) {c, d,e, f } ; |
б) {a,c} ; |
в) {a, d, f }; |
г) {a,c,e}. |
103
2.Даны произвольные множества А, В, С. Множеству ( A B) \ C соответствует диаграмма Эйлера…
а) |
б) |
в) |
г) |
3.Дано отношение R={(x,y) | x,y М, x £ y}, М={1,2,3,4,5,6,7,8}. Образом R(2)
элемента 2 относительно данного отношения является множество…
а) |
{1,2,3,4,5,6,7}; |
б) |
{1,2,3,4,5,6,7,8}; |
в) |
{2,3,4,5,6,7,8}; |
в) |
{2,3,4,5,6,7}. |
4.Из перечисленных отношений, заданных на множестве М={1,2,3,4,5,6,7,8} симметричным является…
а) R={(x,y) | x-y>10}; |
б) |
R={(x,y) | x,y М, x ³ y}; |
в) R={(x,y) | x,y М, x<y}; |
г) |
R={(x,y) | x+y>10}. |
5.Для произвольных множеств А, В и С не выполнено свойство…
а) ( A È B) È C = A È (B È C) ; б) ( A Ç B) Ç C = A Ç (B Ç C) ;
в) ( A \ B) \ C = A \ (B \ C) ;
г) ( ADB)DC = AD(BDC) .
104
6.Отношение R на множестве A называется транзитивным, если…
а) |
для всех x A |
(x, x) R ; |
|
|
|
|
|
|
|||
|
б) для всех x, y A , если (x, y) R , то ( y, x) R ; |
||||||||||
в) |
ля всех x, y A если (x, y) R и ( y, x) R , то x = y ; |
||||||||||
г) |
для всех x, y, z A если (x, y) R и ( y, z) R , то (x, z) R . |
||||||||||
7. Тавтологией является формула… |
|
|
|
|
|
|
|||||
а) (P → Q) → |
|
; |
|
б) |
(P Q) & |
|
|
|
; |
||
P |
(P Q) |
||||||||||
|
в) P Q |
|
; |
г) |
Q (P & |
|
) . |
||||
|
P |
P |
|||||||||
8. Для функции x yz xyz xz несущественными являются переменные…
а) все переменные; |
б) |
переменные |
x и |
z ; |
в) только переменная y ; |
г) |
переменные |
x и |
y . |
9. Формуле z y (xy x)(x y z) равносильна формула…
а) x y z ; |
б) |
|
|
|
|
|
|
|
; |
||
x |
y |
z |
|||||||||
в) xyz ; |
г) |
|
|
|
|
|
. |
||||
x |
y |
z |
|||||||||
10.СКНФ функции f = (10100110)T имеет вид…
а) x y z xy z x yz xy z ;
б) x yz xyz x y z xyz ;
в) (x y z )(x y z )(x y z )(x y z ); г) (x y z )(x y z )(x y z )( x y z ) .
11.Релейно-контактной схеме из двух параллельно соединенных контактов x
иy соответствует функция проводимости…
а) |
F (x, y) = x Ú y ; |
б) |
F (x, y) = x & y ; |
в) |
F (x, y) = x Å y ; |
г) |
F (x, y) = x ® y . |
12.Не является полной система логических функций…
а) |
{x ↓ y} ; |
б) |
{x | y} ; |
в) |
{x y} ; |
г) |
{ |
|
; x y} . |
x |
|||||||||
|
|
|
|
105 |
|
|
|
|
|
13.Дана программа машины Тьюринга
q10 q21R;q 1 q 0R;
T = 1 1
q2 0 q11R;q21 q01E.
и начальная конфигурация P = q11111. Число шагов работы, через ко- торое машина попадает в заключительную конфигурациюT ( P) , равно…
а) 3; б) 4; в) 5; г) машина не остановится.
14.Пусть P(x) - предикат « x3 > 27 » и Q(x) - предикат « x ≤ 5 », x . Об- ласть истинности формулы P(x) Q(x) имеет вид…
а) |
x (3;5] ; |
б) |
x (−∞;−3) (3;5] ; |
|
|
в) x (−∞;5] ; |
|
г) |
x (−∞; +∞) . |
15.Истинным является высказывание…
а) «Любая логическая функция представима в виде СДНФ»; б) «Зона работы любой машины Тьюринга конечна»; в) «Константу 1 нельзя представить в виде СКНФ»;
г) «Система логических функций является функционально полной то- гда и только тогда, когда все входящие в нее функции монотонны».
|
|
16. Матрица смежности A(G) |
орграфа G , изображенного на рисунке, имеет |
вид… |
|
|
|
0 |
1 |
1 |
1 |
|
|
|
0 |
1 |
1 |
2 |
|
||
|
|
0 |
0 |
1 |
0 |
|
|
|
|
0 |
0 |
1 |
0 |
|
|
а) |
|
|
; |
б) |
|
|
; |
||||||||
|
|
0 |
0 |
0 |
1 |
|
|
|
|
0 |
0 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
|
|
|
|
|
2 |
1 |
1 |
|
|
|
|
|
1 |
|
|
|
2 |
|
||||||||
106
|
|
0 |
1 |
1 |
2 |
|
|
|
0 |
1 |
1 |
1 |
||
|
|
1 |
0 |
1 |
1 |
|
|
|
|
0 |
0 |
1 |
0 |
|
в) |
|
|
; |
г) |
|
. |
||||||||
|
|
1 |
1 |
0 |
1 |
|
|
|
|
0 |
0 |
0 |
1 |
|
|
|
2 |
1 |
1 |
|
|
|
|
|
1 |
1 |
0 |
|
|
|
|
2 |
|
|
|
2 |
||||||||
|
1 |
1 |
0 |
0 |
|
|
|
|
|
0 |
1 |
0 |
2 |
|
|
|
|
|
. Полустепень за- |
||||
17. Дана матрица смежности орграфа G |
A(G) = |
|
|||||
|
|
0 |
0 |
1 |
0 |
|
|
|
|
|
0 |
1 |
1 |
|
|
|
1 |
|
|
||||
хода вершины v3 равна…
а) 1; |
б) 0; |
в) 2; |
г) 3. |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
. |
18. Матрица достижимости орграфа G имеет вид R(G) = |
1 |
1 |
1 |
1 |
1 |
|||||
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
|
|
1 |
|
|||||
|
|
|
|
Число компонент сильной связности орграфа G равно… |
|||
а) 2; |
б) 3; |
в) 4; |
г) 5. |
19.Матрица смежности н-графа, содержащего эйлеров цикл, может иметь вид…
|
|
0 |
1 |
0 |
1 |
|
|
|
2 |
1 |
0 |
1 |
|
||
|
|
1 |
0 |
1 |
2 |
|
|
|
|
1 |
0 |
0 |
1 |
|
|
а) |
|
|
; |
б) |
|
|
; |
||||||||
|
|
0 |
1 |
2 |
1 |
|
|
|
|
0 |
0 |
2 |
0 |
|
|
|
|
1 |
2 |
1 |
|
|
|
|
|
1 |
1 |
0 |
|
|
|
|
|
2 |
|
|
|
0 |
|
||||||||
|
|
2 |
0 |
0 |
0 |
|
|
|
0 |
2 |
0 |
0 |
|
||
|
|
0 |
2 |
0 |
0 |
|
|
|
|
2 |
0 |
0 |
0 |
|
|
в) |
|
|
; |
г) |
|
. |
|||||||||
|
|
0 |
0 |
2 |
2 |
|
|
|
|
0 |
0 |
0 |
2 |
|
|
|
|
0 |
0 |
2 |
|
|
|
|
|
0 |
0 |
2 |
|
|
|
|
|
0 |
|
|
|
0 |
|
||||||||
20.Граф задан матрицей весов
|
∞ |
3 |
∞ |
1 |
|
|
|
|
|
|
3 |
∞ |
1 |
1 |
|
. Вес его минимального остова равен… |
|
|
W (G) = |
∞ |
1 |
∞ |
5 |
|
||
|
|
|
|
|
||||
|
|
|
1 |
5 |
|
|
|
|
|
1 |
∞ |
|
|
||||
а) 3; |
б) 4; |
|
|
в) 5; |
г) 6. |
|||
107
21.Три шага алгоритма Дейкстры приведены в таблице:
v*, d (v *), p (v *) |
d (v1 ) |
|
d (v2 ) |
d (v3 ) |
d (v4 ) |
d (v5 ) |
d (v6 ) |
d (v7 ) |
|
|
|
|
|
|
|
|
|
|
|
v1,0, |
– |
|
4 |
|
∞ |
2 |
1 |
∞ |
∞ |
v5 ,1,1 |
– |
|
4 |
|
6 |
2 |
_ |
∞ |
2 |
v4 , 2,1 |
– |
|
4 |
|
3 |
_ |
_ |
6 |
2 |
Расстояние от первой вершины до четвертой равно… |
|
||||||||
а) 1; |
б) |
2; |
в) |
3; |
г) |
4. |
|
|
|
22.Н-граф называется связным, если…
а) все степени его вершин четны; б) для любых двух вершин графа существует соединяющий их
маршрут; в) любые две вершины графа соединяет единственная простая цепь;
г) суммарный вес его ребер не превосходит 10.
23.К.д.а. задан таблицей переходов-выходов (начальное состояние s1 )
S\X |
1 |
2 |
3 |
4 |
s1 |
s2 /0 |
s3 /0 |
s4 /1 |
s5 /1 |
s2 |
s2 /0 |
s3 /0 |
s4 /1 |
s5 /1 |
s3 |
s2 /0Р |
s3 /1 |
s4 /1 |
s5 /1 |
s4 |
s2 /1 |
s3 /1 |
s4 /0 |
s5 /1 |
s5 |
s2 /0 |
s3 /1 |
s4 /1 |
s5 /1 |
Автомат, эквивалентный заданному, задается таблицей …
а)
|
S\X |
1 |
2 |
3 |
4 |
|
s2 |
s2 /1 |
s3 /1 |
s4 /1 |
s3 /1 |
|
s3 |
s2 /0Р |
s3 /1 |
s4 /1 |
s3 /1 |
|
s4 |
s2 /1 |
s3 /1 |
s4 /0 |
s3 /1 |
б) |
|
|
|
|
|
|
S\X |
1 |
2 |
3 |
4 |
|
s2 |
s3 /0 |
s3 /0 |
s4 /1 |
s3 /1 |
|
s3 |
s2 /0Р |
s3 /1 |
s4 /1 |
s3 /1 |
|
s4 |
s3 /1 |
s3 /1 |
s4 /0 |
s3 /1 |
108
в)
|
S\X |
1 |
2 |
3 |
4 |
|
s2 |
s2 /0 |
s3 /0 |
s4 /1 |
s3 /1 |
|
s3 |
s2 /0Р |
s3 /1 |
s4 /1 |
s3 /1 |
|
s4 |
s2 /1 |
s3 /1 |
s4 /0 |
s3 /1 |
г) |
|
|
|
|
|
|
S\X |
1 |
2 |
3 |
4 |
|
s2 |
s2 /0 |
s3 /0 |
s4 /1 |
s3 /1 |
|
s3 |
s2 /0Р |
s3 /1 |
s4 /1 |
s3 /1 |
|
s4 |
s2 /0 |
s3 /1 |
s4 /0 |
s3 /1 |
24.Значение выражения C83 равно…
а) |
6; |
б) |
56; в) |
120; г) |
6720. |
25.Число различных перестановок, которые можно составить из букв слова «порох», равно…
а) 6; |
б) |
120; в) |
360; г) |
720. |
109
КОНТРОЛЬНЫЕ ЗАДАНИЯ
1Доказать справедливость соотношений.
1.1a) A B (A ∩ B ∩C ) (A ∩ B ∩C ) =U.
b)A = B C , если A B =C
1.2a) (A \ B) (B \C ) (B \ A) (C \ B) = A C,
b)(A \ B) B = A, еслиB A.
1.3a) (A \ B) (B \ C ) (C \ A) = (B \ A) (C \ B) (A \C ),
b)((A B) \C) (A (B \C )).
1.4a) (A B) \C = (A \ (B C)) (B \ (A C)),
b)(A ∩ B) C = A ∩(B C ) , если C A.
1.5a) (A\ (B \C )) \ ((A\ B) \C ) = A ∩C,
b)A C B C , если A B .
1.6a) (A ∩ B ∩C ) (A ∩ B) (A ∩C ) = A,
b)(C \ B) (C \ A) , если A B .
1.7a) (A B) (A C ) (B C ) = (A ∩ B) (A ∩C ) (B ∩C ),
b)((A B) \C ) ((A\C ) (B \ A)).
1.8a) (A C ) ∩(A B) ∩(B C ) ∩(A B) ∩(B C ) = ,
b)(A\ (B \C )) ((A\ B) (B ∩C )).
1.9a) A (B ∩C) = (A \C) ((A B) ∩C),
b)(A∩(B C)) ((A ∩ B) C ).
1.10a) (A \ B) (B \ A) = A B,
b)P \Q = A ∩C , если P = A\ (B \C ),Q = (A\ B) \C .
1.11a) ((A B) ∩(B C )) ((A C ) ∩(B C ) ∩(A B)) =U,
b)(A\ (B \C )) (A (B ∩C )).
1.12a) (A B) \C = (A\ C) (B \C),
b)(A \ B) \C = (A \C ) \ (B \C ).
1.13a) ((A ∩ B ∩C) ((A B) ∩C )) = (A\ B) C,
b)( A \ B) (B \ C) , если A B .
110