Основы дискретной математики
700,00 руб.
В течение часа!
Экзамен "Основы дискретной математики" для пользователей и системных администраторов.
Форма сдачи теста: Экстерн
Количество вопросов: 30
Проходной балл: 90% и выше
Срок действия сертификата: неограничен
Сертификат появляется в профиле ресурса INTUIT, и Вы можете заказать его бумажную версию на сайте INTUIT.
Количество вопросов: 30
Проходной балл: 90% и выше
Срок действия сертификата: неограничен
Сертификат появляется в профиле ресурса INTUIT, и Вы можете заказать его бумажную версию на сайте INTUIT.
11447 шт.
Внимание !
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Пусть множество A={0,{0, 1,2}, {3}, 4, {{5}}, 6}. Какие из следующих множеств
B={0, {4}},
C={4, {3}, 0},
D={0, 1, 2},
E={{0, 1,2},{5}},
F={0, {{5}}},
G={{3}, 4, {{5}}, 6}
не являются подмножествами множества A?
только D, F и G
только B, D и E
только F и G
только C и F
только D и E
только D, E, F и G
только D
Пусть множество A={0,{0, 1,2}, {3}, 4, {{5}}, 6}. Какие из следующих множеств
B={0, {{5}}, 6},
C={4, {3}, {5}},
D={0, 1, 2},
E={0, {0, 1,2},{4}},
F={0, {{0,1}}},
G={{3}, 4, {{5}}, 6}
не являются подмножествами множества A?
только C, D, E и F
только D, E, F и G
только C, D и E
только B
только D и F
только C, F и G
Пусть заданы три множества: A={ a, b, c,{∅}, {a}}, B={a, e, {a}, {b},∅} и C = {a, b, d, {e}, {∅}}. Какова мощность множества D = (A \ B) ∩ C?
4
2
1
5
3
Пусть заданы три множества: A ={ a, b, {∅}, {a,c,d}}, B={a, c, e, {a}, {b}} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) \ C?
5
3
7
1
4
6
2
Пусть заданы три множества: A={ a, {∅}, {a,c,d}}, B={a, c, e, {a}, {b},∅} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) ∩ C?
4
7
2
6
5
3
1
Пусть заданы множества A = {0, 1, 2}, B = {2, 3}, C = {a, b, c} и D = {a, c, e}. Чему равно множество F = (A \ B) × (C ∩ D)?
{(0,a), (0,c), (1,a), (1,c), (2,a), (2,c)}
{0, 1, a, c}
{(0,a), (0,b), (0, c), (1, a), (1, b), (1,c)}
{(0,a), (0, c), (1,a), (1,c)}
{(0, a), (0, c), (0,e), (1, a), (1, b), (1,e)}
Пусть заданы множества A = {0, 1, 2, 3}, B = {1, 2, 4}, C = {a, b, c} и D = {b, d, e}. Чему равно множество F = (A\ B) × (C \ D)?
{(0, a), (0, c), (2, a), (2, c)}
{(0,a), (0,c), (3, a), (3,c)}
{(0,b), (0, c), (3, b), (3,c)}
{0, 3, a, c}
{(1, a), (1, c), (2, b), (2,c)}
Какими свойствами обладает бинарное отношение R над {a,b,c} заданное как R = { (a,a), (a,b), (b,a),(b,b), (c,c)}?
Рефлексивность
Транзитивность
Симметричность
Антисимметричность
Какие из следующих равенств справедливы для всех множеств A и B?
(а) (A ∩ B) = A \ (A \ B)
(б) A ∩ (B \ A) = ∅
(в) (A \ B) ∪ B = A
только (б)
только (а) и (б)
только (а)
все
только (а) и (в)
только (в)
только (б) и (в)
Какие из следующих равенств справедливы для всех множеств A, B и C?
(A \ B) \ C = A \ (B \ C)
(A \ B) ∪ (A \ C) = A \ (B ∩ C)
A ∩ (B \ C) = (A ∩ B) \ C
Какие из следующих равенств справедливы для всех множеств A, B и C?
(а) (A ∩ B) \ C = A ∩ (B \ C)
(б) (A ∩ B) ∪ C = A ∩ (B ∪ C)
(в) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
только (а)
только (а) и (б)
только (а) и (в)
все
только (б) и (в)
Пусть бинарное отношение R над {a,b,c} задано как R = {(a,a), (a,с), (c, b), (a, b)}Какие из следующих свойств:
Симметричность
Антисимметричность
Рефлексивность
Транзитивность
для него выполняются?
только 2 и 4
только 1 и 3
все
только 1 и 4
ни одно
1, 3 и 4
2, 3 и 4
Пусть бинарное отношение R над {a,b,c} задано как R = { (a,a), (a,с), (c, b), (a, b), (b,b), (c,c)}Какие из следующих свойств:
Симметричность
Антисимметричность
Рефлексивность
Транзитивность
для него выполняются?
ни одно
только 2 и 3
1, 3 и 4
только 2 и 4
2, 3 и 4
все
только 1 и 3
На множестве всех непустых отрезков числовой прямой определены три отношения: P = { ([a, b], [c, d]) | c < a< b < d }, Q = { ([a, b], [c, d]) | a < c < b < d } и R = { ([a, b], [c, d]) | c <a < d < b}Какие из них являются отношениями частичного порядка.
все
только P
P и R
только R
ни одно
только Q
R и Q
На множестве всех непустых отрезков числовой прямой определены три отношения: R = { ([a, b], [c, d]) | a< c < d < b}, P = { ([a, b], [c, d]) | c <a < d < b} и Q = { ([a, b], [c, d]) | b < c} Какие из них являются отношениями частичного порядка.
P и R
только Q
все
R и Q
ни одно
только R
только P
Пусть заданы множества A = {0, 1, 2}, B = {1, 2, 3}, C = {a, b, c} и D = {a, d, e}. Чему равно множество F = (A ∩ B) × (C \ D)?
{(1,b), (1, c), (3, b), (3,c)}
{(1,a), (1,b), (1,d), (2, a), (2,b), (2,d)}
{(0,b), (0, c), (1, b), (1,c)}
{ 1, 2, b, c}
{(1, b), (1, c), (2, b), (2, c)}
Пусть X ={a, b, c} – множество из трех элементов. Число бинарных операций, которые можно определить на X равно:
23
32
29
33
38
Пусть X ={a, b, c} – множество из трех элементов. Число трехместных отношений, которые можно определить на X равно:
227
327
33
312
29
Пусть X ={a, b, c} – множество из трех элементов. Число трехместных функций f: X3 → X, которые можно определить на X равно:
312
327
227
33
39
Фотограф хочет для групповой фотографии расположить в одну шеренгу 4 юноши и 2 девушки так, чтобы две девушки не стояли рядом. Сколькими способами он может это сделать?
1440
96
240
480
560
Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 4 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?
1800
48000
14400
600
43200
Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 3 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?
1200
14400
2400
480
12400
Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 16 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 4 анекдота и не повторять никакие два года одни и те же четыре анекдота. Каково минимальное число анекдотов, которые он должен приготовить?
4
6
7
8
5
Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 22 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 5 анекдотов и не повторять никакие два года подряд одни и те же пять анекдотов. Каково минимальное число анекдотов, которые он должен приготовить?
10
7
9
8
6
В кондитерском магазине продаются 5 сортов пирожных: заварные, песочные, "картошка", корзинка и бисквитные. Сколькими способами можно купить 6 пирожных?
В кондитерском магазине продаются 4 сорта пирожных: заварные, песочные, "картошка" и бисквитные. Сколькими способами можно купить 7 пирожных?
165
330
35
180
120
В кондитерском магазине продаются 4 сорта пирожных: заварные, песочные, "картошка'' и бисквитные. Сколькими способами можно купить 6 пирожных?
30
120
84
15
210
На множестве всех непустых отрезков числовой прямой определены три отношения: P = { ([a, b], [c, d]) | c < a< b < d }, Q = { ([a, b], [c, d]) | a < c < b < d } и R = { ([a, b], [c, d]) | b < c}. Какие из них являются отношениями частичного порядка?
Q
R
P
В первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебряных и бронзовых медалей, а также три команды, покидающие премьер-лигу (т.е. занявшие три последних места). Найдите число не совпадающих в главном возможных исходов первенства.
100100
600600
1201200
207025
436860
В стране N в первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебренных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места). Найдите число не совпадающих в главном возможных исходов первенства.
436 860
180 180
30 030
47 775
360 360
В стране N в первенстве премьер-лиги по футболу участвуют 16 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебрянных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места). Найдите число не совпадающих в главном возможных исходов первенства.
524 160
4368
462 280
262 080
43680
При игре в преферанс колоду из 32 карт раздают трем игрокам – каждому по 10 карт, а оставшиеся 2 карты оставляют в прикупе. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
P(32) / (P(2) * P(10)3)
A(32,30)* C(32,2)
(C(32,2)*P(32)) / P(10)
C(32, 2)*C(30,10)*C(20,10)
C(32,2)*C(30, 10)3
При игре в бридж колоду из 52 карт раздают 4 игрокам – каждому по 13 карт. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
P(52) / P(13)
A(52, 13)*A(39,13)*A(26,13)
(C(52, 13))
C(52, 13)*C(39,13)*C(26,13)
P(52) / C(52,3)
При игре в "дурака" колоду из 36 карт раздают четырем игрокам – каждому по 6 карт, а оставшиеся 12 карт и оставляют в прикупе в фиксированном порядке. Далее в процессе игры карты из прикупа замещают в указанном порядке карты, выбывшие из игры, поэтому их порядок существенен. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
(C(36,12)*P(24)) / P(6)
(36,12)*C(24,6)*C(18,6)*C(12,6)
C(36,12)*C(30,10)*C(20,10)
A(36,12)* P(24)
A(36,12)*P(24)/ P(6)
Сколько чисел в первой сотне не делится ни на одно из чисел 2, 5, 7?
32
34
41
43
38
Сколько чисел в первой сотне не делится ни на одно из чисел 2, 3, 7?
33
28
16
22
20
Сколько чисел в первой сотне не делится ни на одно из чисел 3, 5, 7?
42
45
58
48
64
Построить таблицу для функции, заданной формулой
и определить число наборов аргументов, на которых она равна 1.
4
5
6
3
7
2
Построить таблицу для функции, заданной формулой
и определить число наборов аргументов, на которых она равна 1.
2
4
7
3
5
6
Построить таблицу для функции, заданной формулой
и определить число наборов аргументов, на которых она равна 1.
6
3
2
7
4
5
Задание:
Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9. Какие из булевых формул задают множество всех ошибочных кодов?
((A ∧ B) ∧ (C ∧ D))
((A ∧ B) ∨ (A ∧ D))
((A ∧ B) ∨ (C ∧ D))
((A ∧ B) ∨ (A ∧ C))
(A ∨ (B ∧ C))
Задание:
Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9 (коды начинаются с 4-ой строки). Какие из булевых формул задают множество всех ошибочных кодов?
((¬A ∧ ¬B) ∨ (C → ¬D))
(((A ↓ B) ∧(¬C ∨ ¬D)) ∨ ( (A ∧ C) ∧ D))
(((A ~ B) ∧ ¬(C~D)) ∨ ((A ∧ B) ∧ (C ∧ D)))
(¬A ∨ ¬B) ∧(¬C ∨ ¬D))
(((¬A ∧ ¬B) ∧(¬C ∨ ¬D)) ∨ ((A ∧ B) ∧(C ∨ D)))
Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?
((X0 ∨ ¬X1) ∨ ¬X2)
((X2 ∧ X1) ∧ X0) ∨ (X2 ∧ ¬X1))
((¬X1 ∧ X0) ∨ (X2 ∧ ¬X0))
(X2 ∨ (¬X1 ∧ X0))
((X0 ∧ X1) ∨ (X2 ∧ ¬X1))
Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 4, 5или 6. Какая из следующих формул задает эту функцию?
(X2 ∨ (¬X1 ∧ X0))
((¬X2 ∧ X0) ∨ (X2 ∧ X1))
((¬X2 ∧ (X1 ∧ X0)) ∨ (X2 ∧ ¬X1))
((¬X1∧ X0) ∨ (X2 ∧ ¬X0))
((¬X0 ∨ ¬X1 ) ∨ ¬X2)
Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 2, 3или 5. Какая из следующих формул задает эту функцию?
((X1 ∧ ¬X2) ∨ (X0 ∧ ¬X1))
(X2 ∨ (¬X1 ∧ X0))
((¬X1 ∧ X0) ∨ (X2 ∧ ¬X0))
( (X0 ∧ X1 ) ∨ (X2 ∧ ¬X1))
((X0∨ ¬X1 ) ∨ ¬X2)
Какие из следующих формул являются тождественно истинными?
только A
только B
ни одна
A, C и D
A и C
A, B и C
все
A и B
Какие из следующих формул являются тождественно истинными?
ни одна
A и B
B, C и D
только A
A и C
A, C и D
только B
A, B и C
Какие из следующих формул являются тождественно истинными?
ни одна
A и B
B и C
A и C
A, Cи D
только A
все
только B
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∨и ∧(без отрицания ¬)?
По крайней мере три переменных из p1, p2, p3, p4истинны (равны 1).
В точности три переменных из p1, p2, p3, p4истинны (равны 1).
Четное число переменных из p1, p2, p3, p4истинны (равны 1).
1 и 3
1 и 2
2 и 3
только 1
только 3
только 2
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
Не все из переменных из p1, p2, p3, p4ложны (равны 0).
Нечетное число переменных из p1, p2, p3, p4истинны (равны 1).
1 и 3
только 2
только 3
2 и 3
только 1
1 и 2
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
В точности две переменных из p1, p2, p3, p4истинны (равны 1).
Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
только 1
1 и 3
2 и 3
только 2
1 и 2
только 3
Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что
если Браун преступник, то и Карт является преступником ;
кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
если Карт не преступник, то и Джонс не преступник.
Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступник действовал в одиночку.
3 и 4
1 и 3
2 и 3
только 2
только 1
1 и 4
только 3
Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что
если Джонс не преступник, то Браун является преступником ;
кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
Браун и Карт вместе не совершали преступление.
Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступник действовал в одиночку.
только 2
1 и 3
только 3
2 и 3
3 и 4
только 1
1 и 4
Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Они дали следующие показания:
Джонс: если Браун преступник, то Карт не виновен.
Браун: если Джонс виновен, то и Карт является преступником.
Карт: Джонс преступник.
Ш. Холмс установил, что если Джонс сказал правду, то Браун соврал, и что показаниям Карта нельзя доверять. Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступников могло быть двое.
2 и 3
2 и 4
только 1
только 2
1 и 3
только 3
1 и 4
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1011 0011). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(X ∨ Y∨ ¬Z) ∧ (¬X ∨ Y)
(X ∧ Y ∧¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ Y ∧ ¬Z)
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(X ∨ Y ∨ ¬Z) ∧ (¬X ∨Y ∨ Z) ∧ (¬X ∨ Y ∨¬ Z)
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1101 1100). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
(¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(X ∨ ¬Y∨ Z) ∧ (¬X ∨ ¬Y)
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1100 0111). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
(¬X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬ Z) ∧ (¬ X ∨ ¬Y ∨ Z)
(X ∨ ¬Y) ∧ (¬X ∨ Y ∨ Z)
(¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)
(¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z)
(¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ ¬Z) ∧ (X ∨ Y ∨ Z)
Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: ¬ (¬x → (y + z))
¬y ∧ (¬x ∨ z) ∧ (¬x ∨ y ∨ z)
¬x ∧ (¬y ∨ ¬z) ∧ (y ∨ ¬z)
(x ∨ ¬y ∨¬z) ∧ (y ∨ z)
¬x ∧ ¬y ∧ (x∨ z)
(¬x ∨¬y) ∧ (¬x ∨ z)
Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (x ∨ y) → (x ∧¬y ∧ z)
(¬x ∨¬y) ∧ (¬x ∨ z)
(x ∨ y ∨ z) ∧ (¬y ∨ z)
¬y ∧ (x∨ z)
¬y ∧ (¬x ∨ z)
¬y ∧ (¬x ∨¬y)
Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (¬x+y) → (y ∧ z)
(x ∨ y) ∧ (¬x ∨¬y∨ z)
(x ∨ y) ∧ (¬y ∨ ¬z)
(x ∨¬y) ∧ (¬x ∨¬y∨ z)
y ∧ (¬x ∨ z) ∧ (x ∨ y ∨ z)
x ∧ ¬y ∧ (x∨ z)
Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1100 1101).
I ) ¬ Y ∧ Z , II) ¬X, III) X ∧ Y ∧ Z, IV) ¬Y, V) X ∧ Z
II и IV
только V
II, IV и V
IV и V
I и III
только IV
I и V
Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1011 1010).
I ) ¬ X∧Y ∧ Z , II) ¬Z, III) ¬ X∧Y , IV) ¬Y, V) X ∧ ¬Z
II иIII
I и III
II, IV и V
только V
I и V
III , IV и V
только IV
Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0011 1011).
I ) ¬X ∧ Y ∧ Z , II) X ∧ ¬Z, III) Y ∧ ¬Z, IV) Y, V) X ∧ ¬Y ∧ ¬Z
только II
II, IV и V
I и III
только IV
II и IV
II , III , IV и V
I и V
Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ¬ (X → ( ¬Y → (X ∧ ¬ Z))) ∧ (Z ∨ ¬ (X ∧ Y))
3
1
2
6
5
4
Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ((X ∧ Y) → ¬ Z) ∧ (¬ X → ¬ Y)
4
6
1
5
3
2
Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ((¬ X ∧ ¬ Y) → (¬ Z ∨ (¬ X → ( Y ∧ Z)) ))
2
4
1
5
3
6
Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0001 0111).
X*Y*Z
X*Z
X
Y
X*Y
Z
Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0101).
X*Y
X*Z
X*Y*Z
Z
Y*Z
Y
Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0111).
I) X*Y, II) X, III) Y, IV) X*Z, V) X*Y*Z, VI) Y*Z
III , IV и V
I, IV и VI
только I и V
II, IV и V
только IV и VI
I, II и V
только I и III
Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((( Y ∧ Z) → ¬ (X ∨ Z)) ∧ ¬ (¬ Y∧ Z∧X)) и укажите, сколько в нем слагаемых.
6
1
5
3
2
4
Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((X ∨Y∨ Z) ∧ (X ∨ (Y→ Z))) ∧ (X ∨¬ Y∨ ¬ Z) и укажите, сколько в нем слагаемых.
2
4
5
1
6
3
Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле (¬( ( X→Y) ∨ ¬(Y → X)) ∧ Z) и укажите, сколько в нем слагаемых.
2
5
3
6
4
1
Какие из следующих формул задают несамодвойственные функции: A= (X ∧¬ Z) ∨ (Y ∧ ¬Z) ∨( X ∧ Y), B = X+Z+ Y*Z, C= X ∨(Y ∧¬ Z)
только B
только A
A и B
B и C
все
A и C
Какие из следующих формул задают несамодвойственные функции: A= X ∨ (¬ Y ∧ Z), B = (¬ X ∧ Y) ∨ (Z ∧ ¬(X+Y)), C= (X ∧ ¬Z) ∨ (Y ∧ ¬Z) ∨ ( X ∧ Y)
только A
B и C
только B
все
A и C
A и B
Какие из следующих формул задают несамодвойственные функции: A= (Y ∧¬ Z) ∨ (X ∧ ¬Z) ∨( X ∧ Y), B =(¬ X∧ (Y|Z)) ∨(¬ Y ∧¬ Z) , C= Z ∨(Y ∧¬ X)
только C
только B
только A
A и C
B и C
все
Какие из следующих формул задают немонотонные функции: A= (Y →¬X) → ( Y ∧ Z), B = ((¬ X∧ Z) →( Y∧ ¬Z)) ∧ Y, C= X +Y + Y*Z +X*Y*Z
только A
A и C
только C
только B
B и C
Все
Какие из следующих формул задают немонотонные функции: A= (Y →¬X) → ( Y ∧ Z), B = (¬ X →( Y∧ ¬Z)) →Y, C= ¬ Z →( Y∧ ¬X)
A и C
B и C
только C
все
только B
только A
Какие из следующих формул задают немонотонные функции: A= X*Z+ Y*Z+X*Y*Z, B = ¬ X →( Y∧ ¬Z), C= (X →¬Z) → ( X ∧ Y)
только C
A и C
все
только B
B и C
только A
Какие из следующих формул задают нелинейные функции: A= (Y →¬X) → Z, B = (X∧ Y∧ Z) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= ( Z→ X) ∨Y
все
B и C
только A
только C
только B
A и C
Какие из следующих формул задают нелинейные функции: A= (X∧ Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) → Z, C= ¬Z∨ X∨Y
B и C
только C
все
A и C
только A
только B
Какие из следующих формул задают нелинейные функции: A= (Y →X) ∧ Z, B = (X∧ Y) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= (¬ Z→ X) ∨¬ Y
A и C
все
B и C
только B
только A
только C
Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→ ¬Y ) ∨ (¬ X∧ ¬ Z ), B = (¬X∨ Z) → ¬Y, C= (Y + ¬X) → (Z→ ¬Y ),
только A
A и C
только C
только B
все
B и C
Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) → (Z→X), C= ¬Z∨ X∨Y
только A
все
только B
A и C
только C
B и C
Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) → (Z→X), C= (X∨Y) →¬Z
только A
только C
только B
B и C
A и C
все
Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1111 0000), (0101 1111)}.
F
ни одна
H
G
Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F={ (1001 0110), (0111 1100), (0001 0011) }, G={ (1111 1111), (0101 0101), (0000 0011) }, H= { (0011 0111), (0110 1000), (1111 0000) }.
только H
F и H
только G
все
только F
G и H
Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1011 0010), (0110 1001), (0110 1001 }.
G и H
только G
только F
все
только H
F и G
Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y, g = X → Y , h = X+Y
f
f и g
f и h
g
h
g и h
Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∧ Y∧ ¬ Z, g = X ∨ Y , h = X+Y+1
f и g
f и h
g
g и h
h
f
Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y , g = X → ¬ Y , h = X+Y
h
g и h
f и h
f и g
g
f
Пусть задана система H-формул F={ (X∧ Y∧ Z) → U, (V∧ Z)→X, (V∧ Z)→Y, (U∧ W)→ V, (U∧X)→ W }. Какие из следующих H-формул являются следствиями системы F?
A) (V∧ Z)→ W
B) (X∧ Y∧ Z) → V
C) (X∧ Y∧ Z) → W
все
только C
A и C
только B
только A
A и B
Используя алгоритм ЗАМЫКАНИЕ(X,F), вычислить замыкание Cl(X,F) набора исходных продуктов X = {b, c, f } с помощью следующей системы технологических процессов F:
a ,b, c → h;
e, d → a ;
g ,b → e;
e, f → c;
c, f → d;
b, f → g.
{b, c, f, g, e}
{b, c, d, f, g, e}
{a, b, c, d, e, f, g, h}
{a, d, e, g, h}
{a, b, c , d, f, g, e }
Пусть задана система H-формул F={ (X∧ Y) → Z , (V∧ Z)→X, (V∧ Z)→Y, (Z ∧V)→ U, (U∧X)→ W }. Какие из следующих H-формул являются следствиями системы F?
A) (V∧ Z)→ W,
B) (X∧ Y) → W ,
C) (X∧ Y∧ Z) → W
все
только B
A и C
только C
только A
A и B
Используя алгоритм ЗАМЫКАНИЕ(X,F), вычислить замыкание Cl(X,F) набора исходных продуктов X = { b,f } с помощью следующей системы технологических процессов F:
a,b,c → d;
b,c,d → a;
g,b → e;
e,f → c;
f,e →d;
b,f → g.
{b, f, g, e}
{a, b, f, g, e, c,d}
{a, g, e, c,d}
{b, f, g, e, c}
{a, b, f, g, e, c}
Используя алгоритм ЗАМЫКАНИЕ(X,F), вычислить замыкание Cl(X,F) набора исходных продуктов X = { e, f } с помощью следующей системы технологических процессов F:
a,b,c → d;
c, f → b ;
g,b → k;
e,f → c;
a,f,e → d;
b,f → g.
{b, f, g, e, c}
{b, f, g, e}
{a, b, f, g, e, c,d, k}
{ b, f, g, e, c, k}
{ b, c, g, k}
Пусть задана система H-формул F={ (X∧ Y∧ Z) → U, V→X, (V∧ Z)→Y, (U∧V)→W, W→ T, (U∧X)→V}. Какие из следующих H-формул являются следствиями системы F?
A) (V∧ Z)→ W,
B) (X∧ Y∧ Z) → W,
C) (X∧ U ∧ Z) → T
A и B
только A
A и C
все
только B
только C
Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
a ,b, c → d ;
b, d → a ;
c,b → a;
a,d → b;
a,b,d → c;
b → a.
C
B
все ошибочны
A
Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
a, c → d ;
a, b, d → c ;
c,b → a;
a,c → b;
a,d → c;
b,d → a.
A
B
все ошибочны
C
Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = {c, d} и следующей системы технологических процессов F:
a, b → h;
a, b, c, g → f;
d, g → a; .
d, f → k;
b, k → d;
c, f, k → h;
h, d, c → e;
c, d → g;
c, d → f
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e.
4
получить e нельзя
6
2
5
3
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Пусть множество A={0,{0, 1,2}, {3}, 4, {{5}}, 6}. Какие из следующих множеств
B={0, {4}},
C={4, {3}, 0},
D={0, 1, 2},
E={{0, 1,2},{5}},
F={0, {{5}}},
G={{3}, 4, {{5}}, 6}
не являются подмножествами множества A?
только D, F и G
только B, D и E
только F и G
только C и F
только D и E
только D, E, F и G
только D
Пусть множество A={0,{0, 1,2}, {3}, 4, {{5}}, 6}. Какие из следующих множеств
B={0, {{5}}, 6},
C={4, {3}, {5}},
D={0, 1, 2},
E={0, {0, 1,2},{4}},
F={0, {{0,1}}},
G={{3}, 4, {{5}}, 6}
не являются подмножествами множества A?
только C, D, E и F
только D, E, F и G
только C, D и E
только B
только D и F
только C, F и G
Пусть заданы три множества: A={ a, b, c,{∅}, {a}}, B={a, e, {a}, {b},∅} и C = {a, b, d, {e}, {∅}}. Какова мощность множества D = (A \ B) ∩ C?
4
2
1
5
3
Пусть заданы три множества: A ={ a, b, {∅}, {a,c,d}}, B={a, c, e, {a}, {b}} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) \ C?
5
3
7
1
4
6
2
Пусть заданы три множества: A={ a, {∅}, {a,c,d}}, B={a, c, e, {a}, {b},∅} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) ∩ C?
4
7
2
6
5
3
1
Пусть заданы множества A = {0, 1, 2}, B = {2, 3}, C = {a, b, c} и D = {a, c, e}. Чему равно множество F = (A \ B) × (C ∩ D)?
{(0,a), (0,c), (1,a), (1,c), (2,a), (2,c)}
{0, 1, a, c}
{(0,a), (0,b), (0, c), (1, a), (1, b), (1,c)}
{(0,a), (0, c), (1,a), (1,c)}
{(0, a), (0, c), (0,e), (1, a), (1, b), (1,e)}
Пусть заданы множества A = {0, 1, 2, 3}, B = {1, 2, 4}, C = {a, b, c} и D = {b, d, e}. Чему равно множество F = (A\ B) × (C \ D)?
{(0, a), (0, c), (2, a), (2, c)}
{(0,a), (0,c), (3, a), (3,c)}
{(0,b), (0, c), (3, b), (3,c)}
{0, 3, a, c}
{(1, a), (1, c), (2, b), (2,c)}
Какими свойствами обладает бинарное отношение R над {a,b,c} заданное как R = { (a,a), (a,b), (b,a),(b,b), (c,c)}?
Рефлексивность
Транзитивность
Симметричность
Антисимметричность
Какие из следующих равенств справедливы для всех множеств A и B?
(а) (A ∩ B) = A \ (A \ B)
(б) A ∩ (B \ A) = ∅
(в) (A \ B) ∪ B = A
только (б)
только (а) и (б)
только (а)
все
только (а) и (в)
только (в)
только (б) и (в)
Какие из следующих равенств справедливы для всех множеств A, B и C?
(A \ B) \ C = A \ (B \ C)
(A \ B) ∪ (A \ C) = A \ (B ∩ C)
A ∩ (B \ C) = (A ∩ B) \ C
Какие из следующих равенств справедливы для всех множеств A, B и C?
(а) (A ∩ B) \ C = A ∩ (B \ C)
(б) (A ∩ B) ∪ C = A ∩ (B ∪ C)
(в) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
только (а)
только (а) и (б)
только (а) и (в)
все
только (б) и (в)
Пусть бинарное отношение R над {a,b,c} задано как R = {(a,a), (a,с), (c, b), (a, b)}Какие из следующих свойств:
Симметричность
Антисимметричность
Рефлексивность
Транзитивность
для него выполняются?
только 2 и 4
только 1 и 3
все
только 1 и 4
ни одно
1, 3 и 4
2, 3 и 4
Пусть бинарное отношение R над {a,b,c} задано как R = { (a,a), (a,с), (c, b), (a, b), (b,b), (c,c)}Какие из следующих свойств:
Симметричность
Антисимметричность
Рефлексивность
Транзитивность
для него выполняются?
ни одно
только 2 и 3
1, 3 и 4
только 2 и 4
2, 3 и 4
все
только 1 и 3
На множестве всех непустых отрезков числовой прямой определены три отношения: P = { ([a, b], [c, d]) | c < a< b < d }, Q = { ([a, b], [c, d]) | a < c < b < d } и R = { ([a, b], [c, d]) | c <a < d < b}Какие из них являются отношениями частичного порядка.
все
только P
P и R
только R
ни одно
только Q
R и Q
На множестве всех непустых отрезков числовой прямой определены три отношения: R = { ([a, b], [c, d]) | a< c < d < b}, P = { ([a, b], [c, d]) | c <a < d < b} и Q = { ([a, b], [c, d]) | b < c} Какие из них являются отношениями частичного порядка.
P и R
только Q
все
R и Q
ни одно
только R
только P
Пусть заданы множества A = {0, 1, 2}, B = {1, 2, 3}, C = {a, b, c} и D = {a, d, e}. Чему равно множество F = (A ∩ B) × (C \ D)?
{(1,b), (1, c), (3, b), (3,c)}
{(1,a), (1,b), (1,d), (2, a), (2,b), (2,d)}
{(0,b), (0, c), (1, b), (1,c)}
{ 1, 2, b, c}
{(1, b), (1, c), (2, b), (2, c)}
Пусть X ={a, b, c} – множество из трех элементов. Число бинарных операций, которые можно определить на X равно:
23
32
29
33
38
Пусть X ={a, b, c} – множество из трех элементов. Число трехместных отношений, которые можно определить на X равно:
227
327
33
312
29
Пусть X ={a, b, c} – множество из трех элементов. Число трехместных функций f: X3 → X, которые можно определить на X равно:
312
327
227
33
39
Фотограф хочет для групповой фотографии расположить в одну шеренгу 4 юноши и 2 девушки так, чтобы две девушки не стояли рядом. Сколькими способами он может это сделать?
1440
96
240
480
560
Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 4 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?
1800
48000
14400
600
43200
Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 3 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?
1200
14400
2400
480
12400
Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 16 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 4 анекдота и не повторять никакие два года одни и те же четыре анекдота. Каково минимальное число анекдотов, которые он должен приготовить?
4
6
7
8
5
Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 22 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 5 анекдотов и не повторять никакие два года подряд одни и те же пять анекдотов. Каково минимальное число анекдотов, которые он должен приготовить?
10
7
9
8
6
В кондитерском магазине продаются 5 сортов пирожных: заварные, песочные, "картошка", корзинка и бисквитные. Сколькими способами можно купить 6 пирожных?
В кондитерском магазине продаются 4 сорта пирожных: заварные, песочные, "картошка" и бисквитные. Сколькими способами можно купить 7 пирожных?
165
330
35
180
120
В кондитерском магазине продаются 4 сорта пирожных: заварные, песочные, "картошка'' и бисквитные. Сколькими способами можно купить 6 пирожных?
30
120
84
15
210
На множестве всех непустых отрезков числовой прямой определены три отношения: P = { ([a, b], [c, d]) | c < a< b < d }, Q = { ([a, b], [c, d]) | a < c < b < d } и R = { ([a, b], [c, d]) | b < c}. Какие из них являются отношениями частичного порядка?
Q
R
P
В первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебряных и бронзовых медалей, а также три команды, покидающие премьер-лигу (т.е. занявшие три последних места). Найдите число не совпадающих в главном возможных исходов первенства.
100100
600600
1201200
207025
436860
В стране N в первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебренных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места). Найдите число не совпадающих в главном возможных исходов первенства.
436 860
180 180
30 030
47 775
360 360
В стране N в первенстве премьер-лиги по футболу участвуют 16 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебрянных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места). Найдите число не совпадающих в главном возможных исходов первенства.
524 160
4368
462 280
262 080
43680
При игре в преферанс колоду из 32 карт раздают трем игрокам – каждому по 10 карт, а оставшиеся 2 карты оставляют в прикупе. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
P(32) / (P(2) * P(10)3)
A(32,30)* C(32,2)
(C(32,2)*P(32)) / P(10)
C(32, 2)*C(30,10)*C(20,10)
C(32,2)*C(30, 10)3
При игре в бридж колоду из 52 карт раздают 4 игрокам – каждому по 13 карт. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
P(52) / P(13)
A(52, 13)*A(39,13)*A(26,13)
(C(52, 13))
C(52, 13)*C(39,13)*C(26,13)
P(52) / C(52,3)
При игре в "дурака" колоду из 36 карт раздают четырем игрокам – каждому по 6 карт, а оставшиеся 12 карт и оставляют в прикупе в фиксированном порядке. Далее в процессе игры карты из прикупа замещают в указанном порядке карты, выбывшие из игры, поэтому их порядок существенен. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
(C(36,12)*P(24)) / P(6)
(36,12)*C(24,6)*C(18,6)*C(12,6)
C(36,12)*C(30,10)*C(20,10)
A(36,12)* P(24)
A(36,12)*P(24)/ P(6)
Сколько чисел в первой сотне не делится ни на одно из чисел 2, 5, 7?
32
34
41
43
38
Сколько чисел в первой сотне не делится ни на одно из чисел 2, 3, 7?
33
28
16
22
20
Сколько чисел в первой сотне не делится ни на одно из чисел 3, 5, 7?
42
45
58
48
64
Построить таблицу для функции, заданной формулой
и определить число наборов аргументов, на которых она равна 1.
4
5
6
3
7
2
Построить таблицу для функции, заданной формулой
и определить число наборов аргументов, на которых она равна 1.
2
4
7
3
5
6
Построить таблицу для функции, заданной формулой
и определить число наборов аргументов, на которых она равна 1.
6
3
2
7
4
5
Задание:
Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9. Какие из булевых формул задают множество всех ошибочных кодов?
((A ∧ B) ∧ (C ∧ D))
((A ∧ B) ∨ (A ∧ D))
((A ∧ B) ∨ (C ∧ D))
((A ∧ B) ∨ (A ∧ C))
(A ∨ (B ∧ C))
Задание:
Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9 (коды начинаются с 4-ой строки). Какие из булевых формул задают множество всех ошибочных кодов?
((¬A ∧ ¬B) ∨ (C → ¬D))
(((A ↓ B) ∧(¬C ∨ ¬D)) ∨ ( (A ∧ C) ∧ D))
(((A ~ B) ∧ ¬(C~D)) ∨ ((A ∧ B) ∧ (C ∧ D)))
(¬A ∨ ¬B) ∧(¬C ∨ ¬D))
(((¬A ∧ ¬B) ∧(¬C ∨ ¬D)) ∨ ((A ∧ B) ∧(C ∨ D)))
Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?
((X0 ∨ ¬X1) ∨ ¬X2)
((X2 ∧ X1) ∧ X0) ∨ (X2 ∧ ¬X1))
((¬X1 ∧ X0) ∨ (X2 ∧ ¬X0))
(X2 ∨ (¬X1 ∧ X0))
((X0 ∧ X1) ∨ (X2 ∧ ¬X1))
Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 4, 5или 6. Какая из следующих формул задает эту функцию?
(X2 ∨ (¬X1 ∧ X0))
((¬X2 ∧ X0) ∨ (X2 ∧ X1))
((¬X2 ∧ (X1 ∧ X0)) ∨ (X2 ∧ ¬X1))
((¬X1∧ X0) ∨ (X2 ∧ ¬X0))
((¬X0 ∨ ¬X1 ) ∨ ¬X2)
Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 2, 3или 5. Какая из следующих формул задает эту функцию?
((X1 ∧ ¬X2) ∨ (X0 ∧ ¬X1))
(X2 ∨ (¬X1 ∧ X0))
((¬X1 ∧ X0) ∨ (X2 ∧ ¬X0))
( (X0 ∧ X1 ) ∨ (X2 ∧ ¬X1))
((X0∨ ¬X1 ) ∨ ¬X2)
Какие из следующих формул являются тождественно истинными?
только A
только B
ни одна
A, C и D
A и C
A, B и C
все
A и B
Какие из следующих формул являются тождественно истинными?
ни одна
A и B
B, C и D
только A
A и C
A, C и D
только B
A, B и C
Какие из следующих формул являются тождественно истинными?
ни одна
A и B
B и C
A и C
A, Cи D
только A
все
только B
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∨и ∧(без отрицания ¬)?
По крайней мере три переменных из p1, p2, p3, p4истинны (равны 1).
В точности три переменных из p1, p2, p3, p4истинны (равны 1).
Четное число переменных из p1, p2, p3, p4истинны (равны 1).
1 и 3
1 и 2
2 и 3
только 1
только 3
только 2
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
Не все из переменных из p1, p2, p3, p4ложны (равны 0).
Нечетное число переменных из p1, p2, p3, p4истинны (равны 1).
1 и 3
только 2
только 3
2 и 3
только 1
1 и 2
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
В точности две переменных из p1, p2, p3, p4истинны (равны 1).
Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
только 1
1 и 3
2 и 3
только 2
1 и 2
только 3
Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что
если Браун преступник, то и Карт является преступником ;
кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
если Карт не преступник, то и Джонс не преступник.
Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступник действовал в одиночку.
3 и 4
1 и 3
2 и 3
только 2
только 1
1 и 4
только 3
Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что
если Джонс не преступник, то Браун является преступником ;
кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
Браун и Карт вместе не совершали преступление.
Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступник действовал в одиночку.
только 2
1 и 3
только 3
2 и 3
3 и 4
только 1
1 и 4
Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Они дали следующие показания:
Джонс: если Браун преступник, то Карт не виновен.
Браун: если Джонс виновен, то и Карт является преступником.
Карт: Джонс преступник.
Ш. Холмс установил, что если Джонс сказал правду, то Браун соврал, и что показаниям Карта нельзя доверять. Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступников могло быть двое.
2 и 3
2 и 4
только 1
только 2
1 и 3
только 3
1 и 4
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1011 0011). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(X ∨ Y∨ ¬Z) ∧ (¬X ∨ Y)
(X ∧ Y ∧¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ Y ∧ ¬Z)
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(X ∨ Y ∨ ¬Z) ∧ (¬X ∨Y ∨ Z) ∧ (¬X ∨ Y ∨¬ Z)
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1101 1100). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
(¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)
(X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
(X ∨ ¬Y∨ Z) ∧ (¬X ∨ ¬Y)
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1100 0111). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
(¬X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬ Z) ∧ (¬ X ∨ ¬Y ∨ Z)
(X ∨ ¬Y) ∧ (¬X ∨ Y ∨ Z)
(¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)
(¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z)
(¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ ¬Z) ∧ (X ∨ Y ∨ Z)
Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: ¬ (¬x → (y + z))
¬y ∧ (¬x ∨ z) ∧ (¬x ∨ y ∨ z)
¬x ∧ (¬y ∨ ¬z) ∧ (y ∨ ¬z)
(x ∨ ¬y ∨¬z) ∧ (y ∨ z)
¬x ∧ ¬y ∧ (x∨ z)
(¬x ∨¬y) ∧ (¬x ∨ z)
Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (x ∨ y) → (x ∧¬y ∧ z)
(¬x ∨¬y) ∧ (¬x ∨ z)
(x ∨ y ∨ z) ∧ (¬y ∨ z)
¬y ∧ (x∨ z)
¬y ∧ (¬x ∨ z)
¬y ∧ (¬x ∨¬y)
Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (¬x+y) → (y ∧ z)
(x ∨ y) ∧ (¬x ∨¬y∨ z)
(x ∨ y) ∧ (¬y ∨ ¬z)
(x ∨¬y) ∧ (¬x ∨¬y∨ z)
y ∧ (¬x ∨ z) ∧ (x ∨ y ∨ z)
x ∧ ¬y ∧ (x∨ z)
Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1100 1101).
I ) ¬ Y ∧ Z , II) ¬X, III) X ∧ Y ∧ Z, IV) ¬Y, V) X ∧ Z
II и IV
только V
II, IV и V
IV и V
I и III
только IV
I и V
Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1011 1010).
I ) ¬ X∧Y ∧ Z , II) ¬Z, III) ¬ X∧Y , IV) ¬Y, V) X ∧ ¬Z
II иIII
I и III
II, IV и V
только V
I и V
III , IV и V
только IV
Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0011 1011).
I ) ¬X ∧ Y ∧ Z , II) X ∧ ¬Z, III) Y ∧ ¬Z, IV) Y, V) X ∧ ¬Y ∧ ¬Z
только II
II, IV и V
I и III
только IV
II и IV
II , III , IV и V
I и V
Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ¬ (X → ( ¬Y → (X ∧ ¬ Z))) ∧ (Z ∨ ¬ (X ∧ Y))
3
1
2
6
5
4
Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ((X ∧ Y) → ¬ Z) ∧ (¬ X → ¬ Y)
4
6
1
5
3
2
Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ((¬ X ∧ ¬ Y) → (¬ Z ∨ (¬ X → ( Y ∧ Z)) ))
2
4
1
5
3
6
Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0001 0111).
X*Y*Z
X*Z
X
Y
X*Y
Z
Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0101).
X*Y
X*Z
X*Y*Z
Z
Y*Z
Y
Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0111).
I) X*Y, II) X, III) Y, IV) X*Z, V) X*Y*Z, VI) Y*Z
III , IV и V
I, IV и VI
только I и V
II, IV и V
только IV и VI
I, II и V
только I и III
Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((( Y ∧ Z) → ¬ (X ∨ Z)) ∧ ¬ (¬ Y∧ Z∧X)) и укажите, сколько в нем слагаемых.
6
1
5
3
2
4
Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((X ∨Y∨ Z) ∧ (X ∨ (Y→ Z))) ∧ (X ∨¬ Y∨ ¬ Z) и укажите, сколько в нем слагаемых.
2
4
5
1
6
3
Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле (¬( ( X→Y) ∨ ¬(Y → X)) ∧ Z) и укажите, сколько в нем слагаемых.
2
5
3
6
4
1
Какие из следующих формул задают несамодвойственные функции: A= (X ∧¬ Z) ∨ (Y ∧ ¬Z) ∨( X ∧ Y), B = X+Z+ Y*Z, C= X ∨(Y ∧¬ Z)
только B
только A
A и B
B и C
все
A и C
Какие из следующих формул задают несамодвойственные функции: A= X ∨ (¬ Y ∧ Z), B = (¬ X ∧ Y) ∨ (Z ∧ ¬(X+Y)), C= (X ∧ ¬Z) ∨ (Y ∧ ¬Z) ∨ ( X ∧ Y)
только A
B и C
только B
все
A и C
A и B
Какие из следующих формул задают несамодвойственные функции: A= (Y ∧¬ Z) ∨ (X ∧ ¬Z) ∨( X ∧ Y), B =(¬ X∧ (Y|Z)) ∨(¬ Y ∧¬ Z) , C= Z ∨(Y ∧¬ X)
только C
только B
только A
A и C
B и C
все
Какие из следующих формул задают немонотонные функции: A= (Y →¬X) → ( Y ∧ Z), B = ((¬ X∧ Z) →( Y∧ ¬Z)) ∧ Y, C= X +Y + Y*Z +X*Y*Z
только A
A и C
только C
только B
B и C
Все
Какие из следующих формул задают немонотонные функции: A= (Y →¬X) → ( Y ∧ Z), B = (¬ X →( Y∧ ¬Z)) →Y, C= ¬ Z →( Y∧ ¬X)
A и C
B и C
только C
все
только B
только A
Какие из следующих формул задают немонотонные функции: A= X*Z+ Y*Z+X*Y*Z, B = ¬ X →( Y∧ ¬Z), C= (X →¬Z) → ( X ∧ Y)
только C
A и C
все
только B
B и C
только A
Какие из следующих формул задают нелинейные функции: A= (Y →¬X) → Z, B = (X∧ Y∧ Z) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= ( Z→ X) ∨Y
все
B и C
только A
только C
только B
A и C
Какие из следующих формул задают нелинейные функции: A= (X∧ Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) → Z, C= ¬Z∨ X∨Y
B и C
только C
все
A и C
только A
только B
Какие из следующих формул задают нелинейные функции: A= (Y →X) ∧ Z, B = (X∧ Y) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= (¬ Z→ X) ∨¬ Y
A и C
все
B и C
только B
только A
только C
Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→ ¬Y ) ∨ (¬ X∧ ¬ Z ), B = (¬X∨ Z) → ¬Y, C= (Y + ¬X) → (Z→ ¬Y ),
только A
A и C
только C
только B
все
B и C
Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) → (Z→X), C= ¬Z∨ X∨Y
только A
все
только B
A и C
только C
B и C
Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) → (Z→X), C= (X∨Y) →¬Z
только A
только C
только B
B и C
A и C
все
Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1111 0000), (0101 1111)}.
F
ни одна
H
G
Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F={ (1001 0110), (0111 1100), (0001 0011) }, G={ (1111 1111), (0101 0101), (0000 0011) }, H= { (0011 0111), (0110 1000), (1111 0000) }.
только H
F и H
только G
все
только F
G и H
Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1011 0010), (0110 1001), (0110 1001 }.
G и H
только G
только F
все
только H
F и G
Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y, g = X → Y , h = X+Y
f
f и g
f и h
g
h
g и h
Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∧ Y∧ ¬ Z, g = X ∨ Y , h = X+Y+1
f и g
f и h
g
g и h
h
f
Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y , g = X → ¬ Y , h = X+Y
h
g и h
f и h
f и g
g
f
Пусть задана система H-формул F={ (X∧ Y∧ Z) → U, (V∧ Z)→X, (V∧ Z)→Y, (U∧ W)→ V, (U∧X)→ W }. Какие из следующих H-формул являются следствиями системы F?
A) (V∧ Z)→ W
B) (X∧ Y∧ Z) → V
C) (X∧ Y∧ Z) → W
все
только C
A и C
только B
только A
A и B
Используя алгоритм ЗАМЫКАНИЕ(X,F), вычислить замыкание Cl(X,F) набора исходных продуктов X = {b, c, f } с помощью следующей системы технологических процессов F:
a ,b, c → h;
e, d → a ;
g ,b → e;
e, f → c;
c, f → d;
b, f → g.
{b, c, f, g, e}
{b, c, d, f, g, e}
{a, b, c, d, e, f, g, h}
{a, d, e, g, h}
{a, b, c , d, f, g, e }
Пусть задана система H-формул F={ (X∧ Y) → Z , (V∧ Z)→X, (V∧ Z)→Y, (Z ∧V)→ U, (U∧X)→ W }. Какие из следующих H-формул являются следствиями системы F?
A) (V∧ Z)→ W,
B) (X∧ Y) → W ,
C) (X∧ Y∧ Z) → W
все
только B
A и C
только C
только A
A и B
Используя алгоритм ЗАМЫКАНИЕ(X,F), вычислить замыкание Cl(X,F) набора исходных продуктов X = { b,f } с помощью следующей системы технологических процессов F:
a,b,c → d;
b,c,d → a;
g,b → e;
e,f → c;
f,e →d;
b,f → g.
{b, f, g, e}
{a, b, f, g, e, c,d}
{a, g, e, c,d}
{b, f, g, e, c}
{a, b, f, g, e, c}
Используя алгоритм ЗАМЫКАНИЕ(X,F), вычислить замыкание Cl(X,F) набора исходных продуктов X = { e, f } с помощью следующей системы технологических процессов F:
a,b,c → d;
c, f → b ;
g,b → k;
e,f → c;
a,f,e → d;
b,f → g.
{b, f, g, e, c}
{b, f, g, e}
{a, b, f, g, e, c,d, k}
{ b, f, g, e, c, k}
{ b, c, g, k}
Пусть задана система H-формул F={ (X∧ Y∧ Z) → U, V→X, (V∧ Z)→Y, (U∧V)→W, W→ T, (U∧X)→V}. Какие из следующих H-формул являются следствиями системы F?
A) (V∧ Z)→ W,
B) (X∧ Y∧ Z) → W,
C) (X∧ U ∧ Z) → T
A и B
только A
A и C
все
только B
только C
Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
a ,b, c → d ;
b, d → a ;
c,b → a;
a,d → b;
a,b,d → c;
b → a.
C
B
все ошибочны
A
Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
a, c → d ;
a, b, d → c ;
c,b → a;
a,c → b;
a,d → c;
b,d → a.
A
B
все ошибочны
C
Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = {c, d} и следующей системы технологических процессов F:
a, b → h;
a, b, c, g → f;
d, g → a; .
d, f → k;
b, k → d;
c, f, k → h;
h, d, c → e;
c, d → g;
c, d → f
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e.
4
получить e нельзя
6
2
5
3
Внимание !
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = {a,b} и следующей системы технологических процессов F:
a, b → h;
a, b, c, g → f;
a, g → c;
e, f → c;
b, k → d;
a, h → k;
h, d, c → e;
h, b → g;
d, k → c.
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e.
5
6
2
получить e нельзя
4
3
Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = { c,d} и следующей системы технологических процессов F:
a, b, d → h;
a, c, d, g → f;
d, g → b;
e, f → c;
b, k → a;
d, c → k;
h, d, c → b;
h, d → g;
c, d, k → h.
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению a.
2
3
6
4
5
получить a нельзя
Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C).
F={1,3,7,8 } C= {2, 4,5, 6, 9}
F={2,3,7,8} C= {1, 4, 5, 6, 9}
F={2,7,8} C= {1,3,4,5,6,9}
F={2,6,8} C= {1,3,4,5,7,9}
F={2,3,7,8,9} C= {1,4,6}
Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C).
F={1,5,8,9} C= {2, 4,6,7}
F={2,5,7,8,9} C= {1,4,6}
F={2,6,8,9} C= {1,3,4,5,7}
F={2,6,8,9} C= {1,4,5,7}
F={2,3,5,6,9} C= {1, 4,7,8}
Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C).
F={2,3,5,6} C= {1, 4,7,8,9}
F={2,5,7,8,9} C= {1,3,4,6}
F={1,5,8,9} C= {2, 4,6,7}
F={2,6,8} C= {1,3,4,5,7,9}
F={2,7,8} C= {1,3,4,5,6,9}
Предположим, что P(x,y) означает "x - это родитель y ", а F(x) означает " x - это женщина". Если G(v, w) равно
(F(v) ∧ ∃x∃y ( P(x,y) ∧ P(x,w) ∧ ¬ (y = w) ∧ P(y,v) )),
то каково значение выражения G(v, w)?
v это двоюродная сестра w
v это племянница w
v это бабушка w
v это сестра w
v это тетя w
Предположим, что P(x,y) означает "x - это родитель y ", а M(x) означает " x - это мужчина". Если F(v, w) равно
(M(v) ∧ ∃x∃y∃z ( P(x,y) ∧ P(x,z) ∧ ¬ (y = z) ∧ P(y,v) ∧ P(z,w))),
то каково значение выражения F(v, w)?
v - это дед w
v - это двоюродный брат w
v - это брат w
v - это дядя w
v - это племянник w
Предположим, что P(x,y) означает "x - это родитель y ", а M(x) означает " x - это мужчина". Если F(v, w) равно
(M(v) ∧ ∃x∃y ( P(x,y) ∧ P(x,v) ∧ ¬ (y = v) ∧ P(y,w))),
то каково значение выражения F(v, w)?
v это брат w
v это двоюродный брат w
v это племянник w
v это дед w
v это дядя w
Какие из следующих формул логики предикатов являются тождественно истинными?
( ∀x P(x) ∧ ∀x Q(x) ) → ∀x ( P(x) ∧ Q(x) )
∀x ( P(x) ∧ Q(x) ) → ( ∀x P(x) ∧ ∀x Q(x) )
(∃x P(x) ∧ ∃x Q(x) ) → ∃x ( P(x) ∧ Q(x) )
1 и 3
только 1
только 2
2 и 3
1 и 2
Какие из следующих формул логики предикатов являются тождественно истинными?
( ∀x P(x) ∨ ∀x Q(x) ) → ∀x ( P(x) ∨ Q(x) )
∀x ( P(x) ∨ Q(x) ) → ( ∀x P(x) ∨ ∀x Q(x) )
(∃x P(x) ∨ ∃x Q(x) ) → ∃x ( P(x) ∨ Q(x) )
2 и 3
только 3
только 1
1 и 2
1 и 3
Какие из следующих формул логики предикатов являются тождественно истинными?
( ∀x P(x) → ∀x Q(x) ) → ∀x ( P(x) → Q(x) )
∀x ( P(x) → Q(x) ) → ( ∀x P(x) → ∀x Q(x) )
(∃x P(x) → ∃x Q(x) ) → ∃x ( P(x) → Q(x) )
только 3
только 2
ни одна
1 и 3
только 1
Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,e), (c, b), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?
∃x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∃ x ∀y ( R(x,y) ∨ ∃u(R(x,u) ∧ R(u,y))
∀x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
1 и 2
только 2
только 1
1 и 3
2 и 3
Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,e), (c, a), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?
∃x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∃ x ∀y (¬ (y = x) → ( R(x,y) ∨ ∃u(R(x,u) ∧ R(u,y))))
∀x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
1 и 2
2 и 3
1 и 3
только 1
только 2
Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,d), (c,d), (d,a), (d,b), (e,d)}. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?
∃x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∀x ∃y ( R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∀x (∃yR(y,x) → ∀z ((z = x) ∨ R(z,x) ∨ ∃u(R(z,u) ∧ R(u,x)))
2 и 3
только 2
1 и 2
1 и 3
только 1
Пусть F = ∀y ∃xP(x,y,z) → ∀z∃x Q(x,y,z). Какие из следующих формул являются предваренными формами эквивалентными F?
A= ∀q ∃p ∃ x∃u ( P(u,p,z) → Q(x,y,q) )
B= ∀q ∃x ∃p∀u ( P(u,p,z) → Q(x,y,q) )
C= ∃p ∀q∀u ∃x ( P(u,p,z) → Q(x,y,q) )
только B
ни одна
A и B
только C
B и C
A и C
Пусть в сигнатуру системы, описывающей результаты экзаменов входит предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?
∃x ∀p (Экз(x, p, отл) ∧ ∀y (∀p Экз(y, p, отл) → (y=x) ))
∃x (∀p Экз(x, p, отл) ∧ ∀y ((Студ(y) ∧ ¬ (y=x)) → (∀p∀o¬ Экз(y, p, o) ∨ ∃o∃p (¬ (o= отл ) ∧ Экз(y, p, o)))))
∀x ∀y ((Студ(x) ∧(Студ(y) ∧¬ (y=x)) → ∃o∃p (¬ (o= отл ) ∧ (Экз(x, p, o) ∨ Экз(y, p, o)) ))
1 и 3
ни одна
только 1
1 и 2
2 и 3
только 2
Пусть в сигнатуру системы, описывающей результаты экзаменов входит предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Все студенты, успешно сдавшие алгебру, успешно сдали дискретную математику или информатику".
∀x ∀o∃b( Экз(x, алг, o) ∧ ¬ (o= неуд ) ∧ ¬(b= неуд ) ∧ (Экз(x, дм , b) ∨ Экз(y, инф, b))
∀x (¬ Экз(x, алг, неуд) → ∃b (¬ (b= неуд )∧ (Экз(x, дм , b) ∨ Экз(x, инф, b))))
∀x (∃o( Экз(x, алг, o) ∧ ¬ (o= неуд )) → ( Экз(x, дм , неуд ) → ¬Экз(y, инф, неуд)))
2 и 3
ни одна
1 и 3
только 1
только 2
1 и 2
Пусть F = ∃x∀yP(x,y,z) → ∀y∃z Q(x,y,z). Какие из следующих формул являются предваренными формами эквивалентными F?
A= ∀y ∃q ∀u∃p ( P(u,p,z) → Q(x,y,q) )
B= ∀u ∃q∃p∀y ( P(u,p,z) → Q(x,y,q) )
C= ∀u∀y ∃p ∃q ( P(u,p,z) → Q(x,y,q) )
A и B
только A
только B
A и C
ни одна
B и C
Пусть F = ∀x∀yP(x,y,z) → ∃z∀yQ(x,y,z). Какие из следующих формул являются предваренными формами эквивалентными F?
A= ∃q∀y∃u∃p ( P(u,p,z) → Q(x,y,q) )
B= ∃u ∃q∃p∀y ( P(u,p,z) → Q(x,y,q) )
C= ∃u∀y ∃q∃p ( P(u,p,z) → Q(x,y,q) )
ни одна
только B
только A
B и C
A и B
A и C
Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
πB(σA>a (R)) = σA>a (πB(R)),
σA=a (σB >b(R ∩ S)) = σ B >b (σA=a (R)∩ σA=a(S)),
πBC(R - S) = πBC(R) - πBC (S)
только 2
ни одно
только 1
2 и 3
1 и 3
1 и 2
Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
σA=a (πAB(R) >< πBC (S)) = σA=a (πBA(R)) >< πBC (S),
πBC(R ∩ S) = πBC(R) ∩ πBC (S)
σA=a (σB >b(R - S)) = σ B >b (σA=a (R) - σA=a(S))
2 и 3
1 и 2
1 и 3
только 2
ни одно
только 1
Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
σA=a (σB >b(R- S)) = σ B >b (σA=a (R-S)),
πBA(σA=a (R)) = σA=a (πBA(R)),
πBC(R ∩ S) = πBC(R) ∩ πBC (S)
только 2
ни одно
только 1
2 и 3
1 и 2
1 и 3
Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 8), (a1, 3, 12), (a1, 6, 2)},
S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πAD(σ B >3(R) >< S) и какая из указанных формул Fj (j=1,2) ему эквивалентна?
Q1 ={(a,d), (a,d1), (a1,d1) } F1= ∃b ∃c (R(a, b, c) ∧ S(b, c, d) ∧ (b > 3))
Q2 ={(a,d), (a,d1), (a1,d), (a1,d1) } F2= ∃b ∃c ((R(a, b, c) ∧ S(b, c, d) )→ (b > 3))
Q3 ={(a,d), (a,d1), (a1,d), (a1,d1), (a1,d2) }
Q2 и F2
Q2 и F1
Q1 и F1
ни один из предыдущих ответов не подходит
Q3 и F2
Q1 и F2
Q3 и F1
Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 4), (a1, 3, 12), (a1, 3, 3)},
S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πAD(πAB(R) >< σ C > 2 (S) и какая из указанных формул Fj (j=1,2) ему эквивалентна?
Q1 ={(a,d), (a,d1), (a1,d1) } F1= ∃b ∃c (R(a, b, c) ∧ S(b, c, d) ∧ (c > 2))
Q2 ={(a,d1), (a1,d2) } F2= ∃b ∃c1 ((∃c R(a, b, c) ∧ (c1 >2) ∧ S(b, c1, d))
Q3 ={(a,d), (a,d1), (a1,d2) }
Q2 и F1
ни один из предыдущих ответов не подходит
Q1 и F1
Q1 и F2
Q3 и F1
Q2 и F2
Q3 и F2
Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 8), (a1, 3, 12), (a1, 6, 8)},
S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πBCD( R >< σ C <10(S)) и какая из указанных формул Fj (j=1,2) ему эквивалентна?
Q1 ={ (6, 8, d), (5, 8,d1) } F1= ∃a (R(a, b, c) ∧ S(b, c, d) ∧ (c > 10))
Q2 ={ (5, 8, d), (6, 8, d), (5, 8,d1) } F2= ∃a ∃c ((R(a, b, c) ∧ S(b, c, d) ) ∧ (c > 10))
Q3 = {(5, 8, d), (6, 8, d), (6, 2, d), (5, 8,d1) }
Q3 и F2
Q2 и F1
Q2 и F2
ни один из предыдущих ответов не подходит
Q1 и F1
Q1 и F2
Q3 и F1
Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры Ei (i=1,2,3) и какая из формул логики предикатов Fj (j=1,2) задает список сотрудников, во всех комнатах которых нет никаких аппаратов (в выражениях и формулах имена отношений сокращены до их первых букв).
E1 = πФИО(С) - πФИО(С >< Номер= НомерСотрудника (К >< О))
E2 = πФИО(С >< Номер= НомерСотрудника (К >< (πНомерКомнаты (К) - πНомерКомнаты (О)))
E3 = πФИО(С) - πФИО(С >< Номер= НомерСотрудника К) >< πЭтаж, НомерКомнаты (О)
F1(f)= ∃n∃o∃d ∃z ∃e∃k (C(n, f, o, d, z) ∧ K(n, e, k) ∧ ∀c ¬ O(e, k, c))
F2(f)= ∃n∃o∃d ∃z( C(n, f, o, d, z) ∧ ∀e ∀k∀c ( K(n, e, k) → ¬ O(e, k, c)))
E3 и F1
E2 и F1
E1 и F1
ни один из предыдущих ответов не подходит
E2 и F
E1 и F2
E3 и F2
Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры Ei (i=1,2,3) и какая из формул логики предикатов Fj (j=1,2) задает список отделов, некоторые сотрудники которых имеют в своих комнатах доступ к компьютерам (в выражениях и формулах имена отношений сокращены до их первых букв)?
E1= π Отдел (С >< Номер= НомерСотрудника (σНазвание='компьютер' (К × О)))
E2 = πОтдел(С >< Номер= НомерСотрудника (К >< σ Название='компьютер'( О))
E3 = πОтдел (С × (К >< σ Название='компьютер'( О)))
F1(o)= ∃n ∃f ∃d ∃z ∃e∃k (C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, 'компьютер'))
F2(o)= ∃n ∃f ∃d ∃z( C(n, f, o, d, z) ∧ ∃e∃k ( K(n, e, k) → O(e, k, 'компьютер')))
E3 и F1
ни один из предыдущих ответов не подходит
E1 и F2
E3 и F2
E1 и F1
E2 и F1
E2 и F2
Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список сотрудников торгового отдела, получающих зарплату от 6001 до 9999 и работающих не на 3-ем этаже
SELECT ФИО, Этаж, Оклад
FROM Сотрудники, Комнаты
WHERE (Номер = НомерСотрудника) AND NOT (Этаж = 3)
AND (Отдел ="торговый" )
AND (Оклад > 6000)
AND (Оклад < 10000)
F1(f, e, z) = ∃n∃d∃z∃k( C(n, f, "торговый", d, z) ∧ K(n, e, k) ∧ (z > 6000) ∧ (z < 10000) ∧¬(e=3))
F2(f, e, z) = ∃n∃d∃z∃e (((z > 6000) ∧ (z < 10000) ∧¬(e=3)) → ( C(n, f, "торговый", d, z) ∧ ∃k K(n, e, k)))
F3(f, e, z) = ∃n∃f∃d∃z (( C(n, f, o, d, z) ∧ (o ="торговый")) ∧ ∃e∃k K((n, e, k))) → ((z > 6000) ∧ (z < 10000) ∧¬(e=3)))
ни одна
F1 и F2
только F1
F2 и F3
F1 и F3
только F2
Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список сотрудников планового отдела с указанием их комнат и доступного оборудования.
SELECT ФИО, НомерКомнаты, Название
FROM Сотрудники, Комнаты, Оборудование
WHERE Номер = НомерСотрудника AND Комнаты.Этаж = Оборудование.Этаж
AND Комнаты.НомерКомнаты = Оборудование.НомерКомнаты
AND Отдел ="плановый"
F1(f, k,c) = ∃n∃f∃d∃z∃e∃k( C(n, f, "плановый", d, z) ∧ K(n, e, k) ∧ O(e, k, c))
F2(f, k,c) = ∃n∃f∃d∃z∃e∃k(( C(n, f, "плановый", d, z) ∧ K(n, e, k)) → O(e, k, c))
F3(f, k,c) = ∃n∃f∃d∃z (( C(n, f, o, d, z) ∧ (o ="плановый")) ∧ ∃e∃k K((n, e, k) ∧ O(e, k, c)))
F2 и F3
F1 и F2
только F1
только F2
F1 и F3
ни одна
Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (НомерСотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список комнат, в которых есть компьютеры и сидят сотрудники с окладом меньше 5500 или больше 7500.
SELECT Этаж, НомерКомнаты
FROM Сотрудники, Комнаты, Оборудование
WHERE (Номер = НомерСотрудника) AND Комнаты.Этаж = Оборудование.Этаж
AND Комнаты.НомерКомнаты = Оборудование.НомерКомнаты
AND Название="компьютер"
AND ((Оклад > 7500) OR (Оклад < 5500))
F1(e, k) = ∃n∃o∃d∃z∃c (( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, c)∧ (c="компьютер")) → ((z > 7500) ∨ (z < 5500)))
F2(e, k) = ∃n∃o∃d∃z ( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, "компьютер") ∧ ((z > 7500) ∨ (z < 5500)))
F3(e, k) = ∃n∃o∃d∃z ( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, c) ∧ ((z > 7500) ∨ (z < 5500)) → (c="компьютер"))
F2 и F3
только F2
F1 и F3
только F1
F1 и F2
ни одна
Пусть база данных включает отношение Счет(Номер,Товар,Дата,Сумма). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибут Номер является ключом отношения.
Ф1 = ∀n∃t∃d∃s (Счет (n,t,d,s) → ∃t1∃d1∃s1 (Счет (n,t1,d1,s1) → (t=t1 ∧ d=d1 ∧ s=s1)))
Ф2 = ∀n∀t∀d∀s∀n1∀t1∀d1∀s1 ((Счет (n,t,d,s) ∧ Счет (n1,t1,d1,s1) ∧ (t≠t1 ∨ d≠d1 ∨ s≠s1)) → (n ≠ n1))
Ф3 = ∀n∀t∀d∀s∀t1∀d1∀s1 ((Счет (n,t,d,s) ∧ (Счет (n,t1,d1,s1)) → (t=t1 ∧ d=d1 ∧ s=s1)))
ни одна
Ф1 и Ф2
Ф1 и Ф3
только Ф2
Ф2 и Ф3
только Ф1
Пусть база данных включает отношение Книга(Автор, Название, Издательство, ГодИздания). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Автор и Название образуют ключ отношения.
Ф1 = ∀a∀k∀p∀y∀a1∀k1∀p1∀y1 ((Книга (a,k,p,y) ∧ (Книга (a1,k1,p1,y1) ∧ (p≠p1 ∨ y≠y1)) → (a ≠ a1 ∨ k≠k1))
Ф2 = ∀a∀k∃p∃y (Книга (a,k,p,y) → ∃p1∃y1 (Книга (a,k,p1,y1) → (p=p1 ∧ y=y1)))
Ф3 = ∀a∀k∀p∀y∀p1∀y1 ((Книга (a,k,p,y) ∧ (Книга (a,k,p1,y1)) → (p=p1 ∧ y=y1)))
только Ф2
ни одна
только Ф1
Ф2 и Ф3
Ф1 и Ф3
Ф1 и Ф2
Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад) и Комнаты(ФИО_Сотрудника, Этаж, Комната). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: для каждого сотрудника из таблицы Сотрудники в таблице Комнаты определено его место работы.
Ф1 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) →∃e∃k Комнаты(f ,e, k))
Ф2 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) ∧ ∃e∃k Комнаты(f ,e, k))
Ф3 = ∀f (∃o∃d∃zСотрудники(f,o,d,z) → ∃e∃k Комнаты(f ,e, k))
Ф2 и Ф3
только Ф1
ни одна
Ф1 и Ф3
Ф1 и Ф2
только Ф2
Пусть база данных включает отношения Комнаты(ФИО_Сотрудника, Этаж, Комната) и Оборудование(Этаж, Комната, Название, Стоимость) . Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: в комнате у каждого сотрудника имеется некоторое оборудование стоимостью больше 10000.
Ф1 = ∀x∀k∀e(Комнаты(x,e, k) → ∃n∃s( Оборудование(e,k,n,s) ∧ (s > 10000 )))
Ф2 = ∀x∃k∃e(Комнаты(x,e, k) ∧ ∃n∃s (Оборудование(e,k,n,s) → (s > 10000 ))
Ф3 = ∀x ∃n∃s ∀k∀e (Комнаты(x,e, k) ∧ Оборудование(e,k,n,s) ∧ (s > 10000 ))
Ф2 и Ф3
только Ф2
только Ф1
Ф1 и Ф2
ни одна
Ф1 и Ф3
Пусть база данных включает отношение Оборудование(Этаж, Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Этаж и НомерКомнаты образуют ключ отношения.
Ф1 = ∀e∀k∃n∃с (Оборудование(e,k,n,c) → ∃n1∃с1 (Оборудование(e,k,n1,c1) → (n=n1 ∧ c=c1)))
Ф2 = ∀e∀k∀n∀c∀n1∀c1 ((Оборудование(e,k,n,c) ∧ (Оборудование(e,k,n1,c1)) → (n=n1 ∧ c=c1)))
Ф3 = ∀e∀k∀n∀c∀e1∀k1∀n1∀c1 ((Оборудование(e,k,n,c) ∧ (Оборудование(e1,k1,n1,c1) ∧ (n≠n1 ∨ c≠c1)) → (e ≠ e1 ∨ k≠k1))
ни одна
Ф2 и Ф3
Ф1 и Ф2
только Ф1
Ф1 и Ф3
только Ф2
Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад), Комнаты(ФИО_Сотрудника, Комната) и Оборудование( Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: стоимость любого аппарата в комнате сотрудника превышает его оклад не более чем в два раза.
Ф1 = ∀f∀o∀d∀z∀k∀s( (Сотрудники(f,o,d,z) ∧ Комнаты(f , k) ∧ Оборудование(k,n,s)) → (s < 2z))
Ф2 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) → ∃k∀s( Комнаты(f , k) ∧ Оборудование(k,n,s) ∧ (s < 2z)))
Ф3 = ∀f∀s (∃o∃d∃zСотрудники(f,o,d,z) → ∃k( Комнаты(f ,e, k) ∧ Оборудование(k,n,s) ∧ (s < 2z)))
только Ф2
ни одна
только Ф1
Ф2 и Ф3
Ф1 и Ф3
Ф1 и Ф2
Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,c), (a,a), (b,a), (b,b), (c, a), (c,d), (d,b)}.
4
6
16
10
8
Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,d), (b,a), (b,b), (c, a), (c,d), (d,b)}.
6
7
9
10
8
Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,c), (a,a), (b,a), (c,d), (c, a), (c,c), (d,a), (d,b)}.
11
5
16
7
9
Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 7-вершинном графе?
7
21
28
49
14
Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 6-вершинном графе?
30
6
12
9
15
Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 8-вершинном графе?
8
32
28
24
16
Пусть G=( V, E) - это конечный неориентированный граф. Какие из следующих утверждений верны?
Если |E| < |V| - 1, то .граф G не является связным.
Если |E| > |V| - 1, то в G имеется цикл.
Если в G имеется цикл, то |E| > |V| - 1
только 1
только 2
1, 2, и 3
только 1 и 3
только 1 и 2
Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?
В G есть вершина, в которую не входят ребра.
В G есть вершина, из которой не выходят ребра.
В G есть изолированная вершина, т.е. вершина, у которой нет инцидентных ребер.
только 3
только 1 и 2
только 1
только 2
1, 2, и 3
Пусть граф G=(V,E) задан своей матрицей смежности
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.
6
5
8
4
7
Пусть граф G=(V,E) задан своей матрицей смежности
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.
15
16
19
18
17
Пусть граф G=(V,E) задан своей матрицей смежности
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.
6
7
4
8
5
Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (7,4), (1,5), (6,7)}?
3
7
5
4
6
Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (5,4), (1,5), (6,7)}?
5
3
6
7
4
Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (1,7), (3,9), (7,4), (8,5), (6,7)}?
6
4
3
5
7
Определите все базы следующего ориентированного графа G:
{a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}
{g, m, e, f}, {g, n, e, f}
{g, k, m, f}, {g, k, n, f}
{g, m, n, f}
{g, m, f}, {g, n, f}
Определите все базы следующего ориентированного графа G:
{a, m, e}, {g, m, e}, {h,m,e}, {a, n, e}, {g, n, e}, {h, n,e}
{a, m}, {g, m}, {h,m}, {a, n}, {g, n}, {h, n}
{a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}
{a, g, h, m, n}
{g, m}, {g, n}, {h, m}, {h,n}
Определите все базы следующего ориентированного графа G:
{d, f, h}, {k, f, h}, {m, f, h}
{d, h}, {e, h}, {k, h}, {m, h}
{d, e, k, m, f, h}
{d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}, {n,f,h}
{d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}
Пусть корень ориентированного дерева T имеет 7 сыновей, а каждая из остальных внутренних вершин имеет три или три четыре сына, при этом число вершин с 3-я сыновьями втрое больше числа вершин с 4-я. Сколько всего вершин в T, если известно, что число его листьев равно 52?
88
73
78
83
68
Пусть корень ориентированного дерева T имеет 4-х сыновей, а каждая из остальных внутренних вершин имеет два или три сына, при этом число вершин с 2-я сыновьями вдвое превосходит число вершин с 3-я. Сколько всего вершин в T, если известно, что число его листьев равно 36?
54
58
61
48
74
Сколько вершин в полном бинарном дереве высоты 6?
63
127
120
112
96
Сколько вершин в полном бинарном дереве высоты 5?
88
33
25
71
63
Сколько вершин в полном бинарном дереве высоты 4?
16
31
18
27
47
Какое выражение представляет ориентированное дерево?
((v * y)+a) * ((z*x) - x)
((v * y) + a)) + (x - (z*x))
(x * (y - z)) + (x - (y*z))
(z*x -x) * (a + v*y)
(v + (y *a)) * (z*x -z)
Какое выражение представляет ориентированное дерево?
((x + y) - z)) * (x - (y*z))
(x * (y - z)) + (x - (y*z))
(x + (y - z)) * ((y*z) - x)
(x + (y - z)) * (x - (y*z))
(x + (y - z)) * (x * (y-z))
Какое выражение представляет ориентированное дерево?
((v *y) +x) + (z * x * t)
(x * (y - v)) + (z * x * t))
((v * y) + x)) + (t- (z*x))
(z*x -x) * (a + v*y)
((v * y)+x) + ((z*x) - t)
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в обратном (суффиксном) порядке?
debfhgca
dbefchga
debhgfca
abdefcgh
abefdcgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в обратном (суффиксном) порядке?
kdbfehgca
kdfebhgca
abdkfecgh
kfdebhgca
abefdcghk
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в обратном (суффиксном) порядке?
dfebhgca
abefdcgh
abdefcgh
dfebghca
dbfeahgc
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в прямом (префиксном) порядке?
dbefhgca
dfebghca
abdefchg
adbefhgc
abdefcgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в прямом (префиксном) порядке?
abdefcgh
debhgfca
debfhgca
abdecfgh
abefdcgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в прямом (префиксном) порядке?
abdkfecgh
kdbfehgca
akfdebhgc
abefdcghk
abdkfechg
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в инфиксном порядке?
dfeibghca
dbiefacgh
adbefhgc
dbfeiachg
dbfeiacgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в инфиксном порядке?
dbeiafchg
dbieafchg
dbeiacfgh
dbeiacfhg
dfeibghca
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в инфиксном порядке?
jdbieafchg
jdfeibghca
djbeiacfhg
djbeiacfgh
djbeiafchg
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h },
E= {(a,b; 10), (a,c; 14),(a,f; 13), (a,g; 17), (h,a; 19) ,(b, d; 10), (b,f; 20), (b,g; 10), (c, d; 15), ( c,g; 13), (d, e; 5), (d,f; 13), (e,f; 12), (h, g; 21) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
66
81
79
77
84
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h, k },
E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20), (h,g; 10), (h,k; 12) }.
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
85
77
82
80
78
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {1,2,3,4,5,6,7,8, 9 },
E={(1,2;15), (1,3; 2), (1,4; 8), (1,7; 9), (2,3; 4), (2,5; 9), (2,9; 8), (3,4; 6), (6,3; 5), (6,5; 7), (6,4; 3), (6,8; 16), (4,7; 10), (4,8; 8), (7,8; 7), (8,9; 15)}
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
36
42
44
38
48
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k },
E= {(a, b; 10), (a, c; 7), (b, f; 21), (b, d; 9), (c, d; 8), (f, e; 7), (f, g; 8), (e, k; 12), (e, h; 10), (g, h; 8) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (a, b) II) (e, h) III) (b, f)
I и III
только I
I, II и III
только II
I и II
II и III
только III
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= {(a,b; 5), (a, h; 7), (b, c; 4), (b, f; 3), (c, d; 6), (c,f; 7), (d, e; 10), (e, f; 9), ( b,g; 15), (g, h; 10) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, g) II) (c, f) III) (d, l)
I и II
только III
I и III
только I
только II
I, II и III
II и III
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k },
E= {(a, b; 9), (a, c; 6), (b, c; 10), (b, d; 5), (b, e; 4), (d, e; 6), (d, f; 4), (e, f; 25),(f, g; 20), (g, h; 8), (g, k; 10), (h, k; 7) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, c) II) (f, g) III) (g, k)
только I
I и II
только II
I и III
II и III
I, II и III
только III
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: b, c, d, g Lb: a, f, d Lc: a, d, e
Ld: a, b, c, e Le: c, d, f Lf: b, e
Lg: a, i, h Lh: g, i Li: g, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: d, c, b Lb: a Lc: i, h
Ld: a, e, f Le: d, g, f Lf: d, e, g
Lg: e, f Lh: c, i Li: c, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: c, d, b Lb: a, f, g Lc: a, d, e
Ld: a, c, e Le: c, d Lf: b
Lg: b, i, h Lh: g, i Li: g, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, f), (d, e), (f, e), (a, g), (g, i), (h, g), (i, h) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
4
2
3
0
1
Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (d, e), (d, f), (f, g), (f, h), (f,i) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
1
4
2
0
3
Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, e), (f, e), (f, g), (d, h), (f, i), (h, a) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
3
0
1
2
4
Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= {(a,b; 21), (a, c; 5), (a, d; 4), (a, e; 16), (a, f; 13), (a, g; 10), (b, e; 10), (b, f; 8), ( b,g; 5), (b, h; 2), (c, e; 10), (c,f; 7), (d, b; 10), (d, g; 5), (d, h; 21), (g,b; 10), (g, h; 10) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
42
50
38
44
43
Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= { (a, c; 24), (a, d; 8), (a, e; 12), (a, f; 2), (a, g; 15), (b, c; 5), ( b,g; 15), (c, h; 5), (d, b; 10), (d, e; 3), (d, g; 10), (d, h; 21), (e, g; 2), (f, d; 5), (f, b; 17) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
48
44
35
34
32
Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= { (a, b; 5), (a, c; 32), (a, d; 2), (a, e; 32), (a, f; 12), (a, g; 15), (b, f; 6), (b, e; 20), ( b, h; 4), (c, h; 5), (d, g; 8), (d, h; 21), (g, c; 10), (g; e; 12), (f, d; 5), (f, b; 17) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
47
37
45
35
49
Какие из следующих утверждений о работе алгоритма Дейкстры верны?
А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.
Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
В) Если длины всех ребер в графе попарно различны, то дерево кратчайших путей из заданной вершины единственно.
только А
только В
А и Б
ни одно
только Б
А и В
Б и В
Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?
А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.
Б) Число этапов (итераций основного цикла) не превосходит (n - 1).
В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
только Б
все
А и Б
А и В
только А
только В
Б и В
Какие из следующих утверждений о работе алгоритма Дейкстры верны?
А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не убывают.
Б) В дереве кратчайших путей, построенном алгоритмом Дейкстры, длины ребер на каждой ветви не убывают.
В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.
Б и В
А и В
А и Б
только В
все
только Б
только А
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = {a,b} и следующей системы технологических процессов F:
a, b → h;
a, b, c, g → f;
a, g → c;
e, f → c;
b, k → d;
a, h → k;
h, d, c → e;
h, b → g;
d, k → c.
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e.
5
6
2
получить e нельзя
4
3
Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = { c,d} и следующей системы технологических процессов F:
a, b, d → h;
a, c, d, g → f;
d, g → b;
e, f → c;
b, k → a;
d, c → k;
h, d, c → b;
h, d → g;
c, d, k → h.
Определите длину кратчайшей цепочки технологических процессов, приводящей к получению a.
2
3
6
4
5
получить a нельзя
Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C).
F={1,3,7,8 } C= {2, 4,5, 6, 9}
F={2,3,7,8} C= {1, 4, 5, 6, 9}
F={2,7,8} C= {1,3,4,5,6,9}
F={2,6,8} C= {1,3,4,5,7,9}
F={2,3,7,8,9} C= {1,4,6}
Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C).
F={1,5,8,9} C= {2, 4,6,7}
F={2,5,7,8,9} C= {1,4,6}
F={2,6,8,9} C= {1,3,4,5,7}
F={2,6,8,9} C= {1,4,5,7}
F={2,3,5,6,9} C= {1, 4,7,8}
Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C).
F={2,3,5,6} C= {1, 4,7,8,9}
F={2,5,7,8,9} C= {1,3,4,6}
F={1,5,8,9} C= {2, 4,6,7}
F={2,6,8} C= {1,3,4,5,7,9}
F={2,7,8} C= {1,3,4,5,6,9}
Предположим, что P(x,y) означает "x - это родитель y ", а F(x) означает " x - это женщина". Если G(v, w) равно
(F(v) ∧ ∃x∃y ( P(x,y) ∧ P(x,w) ∧ ¬ (y = w) ∧ P(y,v) )),
то каково значение выражения G(v, w)?
v это двоюродная сестра w
v это племянница w
v это бабушка w
v это сестра w
v это тетя w
Предположим, что P(x,y) означает "x - это родитель y ", а M(x) означает " x - это мужчина". Если F(v, w) равно
(M(v) ∧ ∃x∃y∃z ( P(x,y) ∧ P(x,z) ∧ ¬ (y = z) ∧ P(y,v) ∧ P(z,w))),
то каково значение выражения F(v, w)?
v - это дед w
v - это двоюродный брат w
v - это брат w
v - это дядя w
v - это племянник w
Предположим, что P(x,y) означает "x - это родитель y ", а M(x) означает " x - это мужчина". Если F(v, w) равно
(M(v) ∧ ∃x∃y ( P(x,y) ∧ P(x,v) ∧ ¬ (y = v) ∧ P(y,w))),
то каково значение выражения F(v, w)?
v это брат w
v это двоюродный брат w
v это племянник w
v это дед w
v это дядя w
Какие из следующих формул логики предикатов являются тождественно истинными?
( ∀x P(x) ∧ ∀x Q(x) ) → ∀x ( P(x) ∧ Q(x) )
∀x ( P(x) ∧ Q(x) ) → ( ∀x P(x) ∧ ∀x Q(x) )
(∃x P(x) ∧ ∃x Q(x) ) → ∃x ( P(x) ∧ Q(x) )
1 и 3
только 1
только 2
2 и 3
1 и 2
Какие из следующих формул логики предикатов являются тождественно истинными?
( ∀x P(x) ∨ ∀x Q(x) ) → ∀x ( P(x) ∨ Q(x) )
∀x ( P(x) ∨ Q(x) ) → ( ∀x P(x) ∨ ∀x Q(x) )
(∃x P(x) ∨ ∃x Q(x) ) → ∃x ( P(x) ∨ Q(x) )
2 и 3
только 3
только 1
1 и 2
1 и 3
Какие из следующих формул логики предикатов являются тождественно истинными?
( ∀x P(x) → ∀x Q(x) ) → ∀x ( P(x) → Q(x) )
∀x ( P(x) → Q(x) ) → ( ∀x P(x) → ∀x Q(x) )
(∃x P(x) → ∃x Q(x) ) → ∃x ( P(x) → Q(x) )
только 3
только 2
ни одна
1 и 3
только 1
Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,e), (c, b), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?
∃x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∃ x ∀y ( R(x,y) ∨ ∃u(R(x,u) ∧ R(u,y))
∀x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
1 и 2
только 2
только 1
1 и 3
2 и 3
Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,e), (c, a), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?
∃x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∃ x ∀y (¬ (y = x) → ( R(x,y) ∨ ∃u(R(x,u) ∧ R(u,y))))
∀x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
1 и 2
2 и 3
1 и 3
только 1
только 2
Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,d), (c,d), (d,a), (d,b), (e,d)}. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?
∃x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∀x ∃y ( R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
∀x (∃yR(y,x) → ∀z ((z = x) ∨ R(z,x) ∨ ∃u(R(z,u) ∧ R(u,x)))
2 и 3
только 2
1 и 2
1 и 3
только 1
Пусть F = ∀y ∃xP(x,y,z) → ∀z∃x Q(x,y,z). Какие из следующих формул являются предваренными формами эквивалентными F?
A= ∀q ∃p ∃ x∃u ( P(u,p,z) → Q(x,y,q) )
B= ∀q ∃x ∃p∀u ( P(u,p,z) → Q(x,y,q) )
C= ∃p ∀q∀u ∃x ( P(u,p,z) → Q(x,y,q) )
только B
ни одна
A и B
только C
B и C
A и C
Пусть в сигнатуру системы, описывающей результаты экзаменов входит предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?
∃x ∀p (Экз(x, p, отл) ∧ ∀y (∀p Экз(y, p, отл) → (y=x) ))
∃x (∀p Экз(x, p, отл) ∧ ∀y ((Студ(y) ∧ ¬ (y=x)) → (∀p∀o¬ Экз(y, p, o) ∨ ∃o∃p (¬ (o= отл ) ∧ Экз(y, p, o)))))
∀x ∀y ((Студ(x) ∧(Студ(y) ∧¬ (y=x)) → ∃o∃p (¬ (o= отл ) ∧ (Экз(x, p, o) ∨ Экз(y, p, o)) ))
1 и 3
ни одна
только 1
1 и 2
2 и 3
только 2
Пусть в сигнатуру системы, описывающей результаты экзаменов входит предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Все студенты, успешно сдавшие алгебру, успешно сдали дискретную математику или информатику".
∀x ∀o∃b( Экз(x, алг, o) ∧ ¬ (o= неуд ) ∧ ¬(b= неуд ) ∧ (Экз(x, дм , b) ∨ Экз(y, инф, b))
∀x (¬ Экз(x, алг, неуд) → ∃b (¬ (b= неуд )∧ (Экз(x, дм , b) ∨ Экз(x, инф, b))))
∀x (∃o( Экз(x, алг, o) ∧ ¬ (o= неуд )) → ( Экз(x, дм , неуд ) → ¬Экз(y, инф, неуд)))
2 и 3
ни одна
1 и 3
только 1
только 2
1 и 2
Пусть F = ∃x∀yP(x,y,z) → ∀y∃z Q(x,y,z). Какие из следующих формул являются предваренными формами эквивалентными F?
A= ∀y ∃q ∀u∃p ( P(u,p,z) → Q(x,y,q) )
B= ∀u ∃q∃p∀y ( P(u,p,z) → Q(x,y,q) )
C= ∀u∀y ∃p ∃q ( P(u,p,z) → Q(x,y,q) )
A и B
только A
только B
A и C
ни одна
B и C
Пусть F = ∀x∀yP(x,y,z) → ∃z∀yQ(x,y,z). Какие из следующих формул являются предваренными формами эквивалентными F?
A= ∃q∀y∃u∃p ( P(u,p,z) → Q(x,y,q) )
B= ∃u ∃q∃p∀y ( P(u,p,z) → Q(x,y,q) )
C= ∃u∀y ∃q∃p ( P(u,p,z) → Q(x,y,q) )
ни одна
только B
только A
B и C
A и B
A и C
Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
πB(σA>a (R)) = σA>a (πB(R)),
σA=a (σB >b(R ∩ S)) = σ B >b (σA=a (R)∩ σA=a(S)),
πBC(R - S) = πBC(R) - πBC (S)
только 2
ни одно
только 1
2 и 3
1 и 3
1 и 2
Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
σA=a (πAB(R) >< πBC (S)) = σA=a (πBA(R)) >< πBC (S),
πBC(R ∩ S) = πBC(R) ∩ πBC (S)
σA=a (σB >b(R - S)) = σ B >b (σA=a (R) - σA=a(S))
2 и 3
1 и 2
1 и 3
только 2
ни одно
только 1
Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
σA=a (σB >b(R- S)) = σ B >b (σA=a (R-S)),
πBA(σA=a (R)) = σA=a (πBA(R)),
πBC(R ∩ S) = πBC(R) ∩ πBC (S)
только 2
ни одно
только 1
2 и 3
1 и 2
1 и 3
Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 8), (a1, 3, 12), (a1, 6, 2)},
S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πAD(σ B >3(R) >< S) и какая из указанных формул Fj (j=1,2) ему эквивалентна?
Q1 ={(a,d), (a,d1), (a1,d1) } F1= ∃b ∃c (R(a, b, c) ∧ S(b, c, d) ∧ (b > 3))
Q2 ={(a,d), (a,d1), (a1,d), (a1,d1) } F2= ∃b ∃c ((R(a, b, c) ∧ S(b, c, d) )→ (b > 3))
Q3 ={(a,d), (a,d1), (a1,d), (a1,d1), (a1,d2) }
Q2 и F2
Q2 и F1
Q1 и F1
ни один из предыдущих ответов не подходит
Q3 и F2
Q1 и F2
Q3 и F1
Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 4), (a1, 3, 12), (a1, 3, 3)},
S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πAD(πAB(R) >< σ C > 2 (S) и какая из указанных формул Fj (j=1,2) ему эквивалентна?
Q1 ={(a,d), (a,d1), (a1,d1) } F1= ∃b ∃c (R(a, b, c) ∧ S(b, c, d) ∧ (c > 2))
Q2 ={(a,d1), (a1,d2) } F2= ∃b ∃c1 ((∃c R(a, b, c) ∧ (c1 >2) ∧ S(b, c1, d))
Q3 ={(a,d), (a,d1), (a1,d2) }
Q2 и F1
ни один из предыдущих ответов не подходит
Q1 и F1
Q1 и F2
Q3 и F1
Q2 и F2
Q3 и F2
Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 8), (a1, 3, 12), (a1, 6, 8)},
S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πBCD( R >< σ C <10(S)) и какая из указанных формул Fj (j=1,2) ему эквивалентна?
Q1 ={ (6, 8, d), (5, 8,d1) } F1= ∃a (R(a, b, c) ∧ S(b, c, d) ∧ (c > 10))
Q2 ={ (5, 8, d), (6, 8, d), (5, 8,d1) } F2= ∃a ∃c ((R(a, b, c) ∧ S(b, c, d) ) ∧ (c > 10))
Q3 = {(5, 8, d), (6, 8, d), (6, 2, d), (5, 8,d1) }
Q3 и F2
Q2 и F1
Q2 и F2
ни один из предыдущих ответов не подходит
Q1 и F1
Q1 и F2
Q3 и F1
Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры Ei (i=1,2,3) и какая из формул логики предикатов Fj (j=1,2) задает список сотрудников, во всех комнатах которых нет никаких аппаратов (в выражениях и формулах имена отношений сокращены до их первых букв).
E1 = πФИО(С) - πФИО(С >< Номер= НомерСотрудника (К >< О))
E2 = πФИО(С >< Номер= НомерСотрудника (К >< (πНомерКомнаты (К) - πНомерКомнаты (О)))
E3 = πФИО(С) - πФИО(С >< Номер= НомерСотрудника К) >< πЭтаж, НомерКомнаты (О)
F1(f)= ∃n∃o∃d ∃z ∃e∃k (C(n, f, o, d, z) ∧ K(n, e, k) ∧ ∀c ¬ O(e, k, c))
F2(f)= ∃n∃o∃d ∃z( C(n, f, o, d, z) ∧ ∀e ∀k∀c ( K(n, e, k) → ¬ O(e, k, c)))
E3 и F1
E2 и F1
E1 и F1
ни один из предыдущих ответов не подходит
E2 и F
E1 и F2
E3 и F2
Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры Ei (i=1,2,3) и какая из формул логики предикатов Fj (j=1,2) задает список отделов, некоторые сотрудники которых имеют в своих комнатах доступ к компьютерам (в выражениях и формулах имена отношений сокращены до их первых букв)?
E1= π Отдел (С >< Номер= НомерСотрудника (σНазвание='компьютер' (К × О)))
E2 = πОтдел(С >< Номер= НомерСотрудника (К >< σ Название='компьютер'( О))
E3 = πОтдел (С × (К >< σ Название='компьютер'( О)))
F1(o)= ∃n ∃f ∃d ∃z ∃e∃k (C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, 'компьютер'))
F2(o)= ∃n ∃f ∃d ∃z( C(n, f, o, d, z) ∧ ∃e∃k ( K(n, e, k) → O(e, k, 'компьютер')))
E3 и F1
ни один из предыдущих ответов не подходит
E1 и F2
E3 и F2
E1 и F1
E2 и F1
E2 и F2
Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список сотрудников торгового отдела, получающих зарплату от 6001 до 9999 и работающих не на 3-ем этаже
SELECT ФИО, Этаж, Оклад
FROM Сотрудники, Комнаты
WHERE (Номер = НомерСотрудника) AND NOT (Этаж = 3)
AND (Отдел ="торговый" )
AND (Оклад > 6000)
AND (Оклад < 10000)
F1(f, e, z) = ∃n∃d∃z∃k( C(n, f, "торговый", d, z) ∧ K(n, e, k) ∧ (z > 6000) ∧ (z < 10000) ∧¬(e=3))
F2(f, e, z) = ∃n∃d∃z∃e (((z > 6000) ∧ (z < 10000) ∧¬(e=3)) → ( C(n, f, "торговый", d, z) ∧ ∃k K(n, e, k)))
F3(f, e, z) = ∃n∃f∃d∃z (( C(n, f, o, d, z) ∧ (o ="торговый")) ∧ ∃e∃k K((n, e, k))) → ((z > 6000) ∧ (z < 10000) ∧¬(e=3)))
ни одна
F1 и F2
только F1
F2 и F3
F1 и F3
только F2
Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список сотрудников планового отдела с указанием их комнат и доступного оборудования.
SELECT ФИО, НомерКомнаты, Название
FROM Сотрудники, Комнаты, Оборудование
WHERE Номер = НомерСотрудника AND Комнаты.Этаж = Оборудование.Этаж
AND Комнаты.НомерКомнаты = Оборудование.НомерКомнаты
AND Отдел ="плановый"
F1(f, k,c) = ∃n∃f∃d∃z∃e∃k( C(n, f, "плановый", d, z) ∧ K(n, e, k) ∧ O(e, k, c))
F2(f, k,c) = ∃n∃f∃d∃z∃e∃k(( C(n, f, "плановый", d, z) ∧ K(n, e, k)) → O(e, k, c))
F3(f, k,c) = ∃n∃f∃d∃z (( C(n, f, o, d, z) ∧ (o ="плановый")) ∧ ∃e∃k K((n, e, k) ∧ O(e, k, c)))
F2 и F3
F1 и F2
только F1
только F2
F1 и F3
ни одна
Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (НомерСотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список комнат, в которых есть компьютеры и сидят сотрудники с окладом меньше 5500 или больше 7500.
SELECT Этаж, НомерКомнаты
FROM Сотрудники, Комнаты, Оборудование
WHERE (Номер = НомерСотрудника) AND Комнаты.Этаж = Оборудование.Этаж
AND Комнаты.НомерКомнаты = Оборудование.НомерКомнаты
AND Название="компьютер"
AND ((Оклад > 7500) OR (Оклад < 5500))
F1(e, k) = ∃n∃o∃d∃z∃c (( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, c)∧ (c="компьютер")) → ((z > 7500) ∨ (z < 5500)))
F2(e, k) = ∃n∃o∃d∃z ( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, "компьютер") ∧ ((z > 7500) ∨ (z < 5500)))
F3(e, k) = ∃n∃o∃d∃z ( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, c) ∧ ((z > 7500) ∨ (z < 5500)) → (c="компьютер"))
F2 и F3
только F2
F1 и F3
только F1
F1 и F2
ни одна
Пусть база данных включает отношение Счет(Номер,Товар,Дата,Сумма). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибут Номер является ключом отношения.
Ф1 = ∀n∃t∃d∃s (Счет (n,t,d,s) → ∃t1∃d1∃s1 (Счет (n,t1,d1,s1) → (t=t1 ∧ d=d1 ∧ s=s1)))
Ф2 = ∀n∀t∀d∀s∀n1∀t1∀d1∀s1 ((Счет (n,t,d,s) ∧ Счет (n1,t1,d1,s1) ∧ (t≠t1 ∨ d≠d1 ∨ s≠s1)) → (n ≠ n1))
Ф3 = ∀n∀t∀d∀s∀t1∀d1∀s1 ((Счет (n,t,d,s) ∧ (Счет (n,t1,d1,s1)) → (t=t1 ∧ d=d1 ∧ s=s1)))
ни одна
Ф1 и Ф2
Ф1 и Ф3
только Ф2
Ф2 и Ф3
только Ф1
Пусть база данных включает отношение Книга(Автор, Название, Издательство, ГодИздания). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Автор и Название образуют ключ отношения.
Ф1 = ∀a∀k∀p∀y∀a1∀k1∀p1∀y1 ((Книга (a,k,p,y) ∧ (Книга (a1,k1,p1,y1) ∧ (p≠p1 ∨ y≠y1)) → (a ≠ a1 ∨ k≠k1))
Ф2 = ∀a∀k∃p∃y (Книга (a,k,p,y) → ∃p1∃y1 (Книга (a,k,p1,y1) → (p=p1 ∧ y=y1)))
Ф3 = ∀a∀k∀p∀y∀p1∀y1 ((Книга (a,k,p,y) ∧ (Книга (a,k,p1,y1)) → (p=p1 ∧ y=y1)))
только Ф2
ни одна
только Ф1
Ф2 и Ф3
Ф1 и Ф3
Ф1 и Ф2
Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад) и Комнаты(ФИО_Сотрудника, Этаж, Комната). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: для каждого сотрудника из таблицы Сотрудники в таблице Комнаты определено его место работы.
Ф1 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) →∃e∃k Комнаты(f ,e, k))
Ф2 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) ∧ ∃e∃k Комнаты(f ,e, k))
Ф3 = ∀f (∃o∃d∃zСотрудники(f,o,d,z) → ∃e∃k Комнаты(f ,e, k))
Ф2 и Ф3
только Ф1
ни одна
Ф1 и Ф3
Ф1 и Ф2
только Ф2
Пусть база данных включает отношения Комнаты(ФИО_Сотрудника, Этаж, Комната) и Оборудование(Этаж, Комната, Название, Стоимость) . Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: в комнате у каждого сотрудника имеется некоторое оборудование стоимостью больше 10000.
Ф1 = ∀x∀k∀e(Комнаты(x,e, k) → ∃n∃s( Оборудование(e,k,n,s) ∧ (s > 10000 )))
Ф2 = ∀x∃k∃e(Комнаты(x,e, k) ∧ ∃n∃s (Оборудование(e,k,n,s) → (s > 10000 ))
Ф3 = ∀x ∃n∃s ∀k∀e (Комнаты(x,e, k) ∧ Оборудование(e,k,n,s) ∧ (s > 10000 ))
Ф2 и Ф3
только Ф2
только Ф1
Ф1 и Ф2
ни одна
Ф1 и Ф3
Пусть база данных включает отношение Оборудование(Этаж, Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Этаж и НомерКомнаты образуют ключ отношения.
Ф1 = ∀e∀k∃n∃с (Оборудование(e,k,n,c) → ∃n1∃с1 (Оборудование(e,k,n1,c1) → (n=n1 ∧ c=c1)))
Ф2 = ∀e∀k∀n∀c∀n1∀c1 ((Оборудование(e,k,n,c) ∧ (Оборудование(e,k,n1,c1)) → (n=n1 ∧ c=c1)))
Ф3 = ∀e∀k∀n∀c∀e1∀k1∀n1∀c1 ((Оборудование(e,k,n,c) ∧ (Оборудование(e1,k1,n1,c1) ∧ (n≠n1 ∨ c≠c1)) → (e ≠ e1 ∨ k≠k1))
ни одна
Ф2 и Ф3
Ф1 и Ф2
только Ф1
Ф1 и Ф3
только Ф2
Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад), Комнаты(ФИО_Сотрудника, Комната) и Оборудование( Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: стоимость любого аппарата в комнате сотрудника превышает его оклад не более чем в два раза.
Ф1 = ∀f∀o∀d∀z∀k∀s( (Сотрудники(f,o,d,z) ∧ Комнаты(f , k) ∧ Оборудование(k,n,s)) → (s < 2z))
Ф2 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) → ∃k∀s( Комнаты(f , k) ∧ Оборудование(k,n,s) ∧ (s < 2z)))
Ф3 = ∀f∀s (∃o∃d∃zСотрудники(f,o,d,z) → ∃k( Комнаты(f ,e, k) ∧ Оборудование(k,n,s) ∧ (s < 2z)))
только Ф2
ни одна
только Ф1
Ф2 и Ф3
Ф1 и Ф3
Ф1 и Ф2
Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,c), (a,a), (b,a), (b,b), (c, a), (c,d), (d,b)}.
4
6
16
10
8
Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,d), (b,a), (b,b), (c, a), (c,d), (d,b)}.
6
7
9
10
8
Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,c), (a,a), (b,a), (c,d), (c, a), (c,c), (d,a), (d,b)}.
11
5
16
7
9
Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 7-вершинном графе?
7
21
28
49
14
Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 6-вершинном графе?
30
6
12
9
15
Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 8-вершинном графе?
8
32
28
24
16
Пусть G=( V, E) - это конечный неориентированный граф. Какие из следующих утверждений верны?
Если |E| < |V| - 1, то .граф G не является связным.
Если |E| > |V| - 1, то в G имеется цикл.
Если в G имеется цикл, то |E| > |V| - 1
только 1
только 2
1, 2, и 3
только 1 и 3
только 1 и 2
Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?
В G есть вершина, в которую не входят ребра.
В G есть вершина, из которой не выходят ребра.
В G есть изолированная вершина, т.е. вершина, у которой нет инцидентных ребер.
только 3
только 1 и 2
только 1
только 2
1, 2, и 3
Пусть граф G=(V,E) задан своей матрицей смежности
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.
6
5
8
4
7
Пусть граф G=(V,E) задан своей матрицей смежности
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.
15
16
19
18
17
Пусть граф G=(V,E) задан своей матрицей смежности
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.
6
7
4
8
5
Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (7,4), (1,5), (6,7)}?
3
7
5
4
6
Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (5,4), (1,5), (6,7)}?
5
3
6
7
4
Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (1,7), (3,9), (7,4), (8,5), (6,7)}?
6
4
3
5
7
Определите все базы следующего ориентированного графа G:
{a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}
{g, m, e, f}, {g, n, e, f}
{g, k, m, f}, {g, k, n, f}
{g, m, n, f}
{g, m, f}, {g, n, f}
Определите все базы следующего ориентированного графа G:
{a, m, e}, {g, m, e}, {h,m,e}, {a, n, e}, {g, n, e}, {h, n,e}
{a, m}, {g, m}, {h,m}, {a, n}, {g, n}, {h, n}
{a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}
{a, g, h, m, n}
{g, m}, {g, n}, {h, m}, {h,n}
Определите все базы следующего ориентированного графа G:
{d, f, h}, {k, f, h}, {m, f, h}
{d, h}, {e, h}, {k, h}, {m, h}
{d, e, k, m, f, h}
{d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}, {n,f,h}
{d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}
Пусть корень ориентированного дерева T имеет 7 сыновей, а каждая из остальных внутренних вершин имеет три или три четыре сына, при этом число вершин с 3-я сыновьями втрое больше числа вершин с 4-я. Сколько всего вершин в T, если известно, что число его листьев равно 52?
88
73
78
83
68
Пусть корень ориентированного дерева T имеет 4-х сыновей, а каждая из остальных внутренних вершин имеет два или три сына, при этом число вершин с 2-я сыновьями вдвое превосходит число вершин с 3-я. Сколько всего вершин в T, если известно, что число его листьев равно 36?
54
58
61
48
74
Сколько вершин в полном бинарном дереве высоты 6?
63
127
120
112
96
Сколько вершин в полном бинарном дереве высоты 5?
88
33
25
71
63
Сколько вершин в полном бинарном дереве высоты 4?
16
31
18
27
47
Какое выражение представляет ориентированное дерево?
((v * y)+a) * ((z*x) - x)
((v * y) + a)) + (x - (z*x))
(x * (y - z)) + (x - (y*z))
(z*x -x) * (a + v*y)
(v + (y *a)) * (z*x -z)
Какое выражение представляет ориентированное дерево?
((x + y) - z)) * (x - (y*z))
(x * (y - z)) + (x - (y*z))
(x + (y - z)) * ((y*z) - x)
(x + (y - z)) * (x - (y*z))
(x + (y - z)) * (x * (y-z))
Какое выражение представляет ориентированное дерево?
((v *y) +x) + (z * x * t)
(x * (y - v)) + (z * x * t))
((v * y) + x)) + (t- (z*x))
(z*x -x) * (a + v*y)
((v * y)+x) + ((z*x) - t)
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в обратном (суффиксном) порядке?
debfhgca
dbefchga
debhgfca
abdefcgh
abefdcgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в обратном (суффиксном) порядке?
kdbfehgca
kdfebhgca
abdkfecgh
kfdebhgca
abefdcghk
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в обратном (суффиксном) порядке?
dfebhgca
abefdcgh
abdefcgh
dfebghca
dbfeahgc
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в прямом (префиксном) порядке?
dbefhgca
dfebghca
abdefchg
adbefhgc
abdefcgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в прямом (префиксном) порядке?
abdefcgh
debhgfca
debfhgca
abdecfgh
abefdcgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в прямом (префиксном) порядке?
abdkfecgh
kdbfehgca
akfdebhgc
abefdcghk
abdkfechg
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в инфиксном порядке?
dfeibghca
dbiefacgh
adbefhgc
dbfeiachg
dbfeiacgh
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в инфиксном порядке?
dbeiafchg
dbieafchg
dbeiacfgh
dbeiacfhg
dfeibghca
Какое из следующих перечислений вершин бинарного дерева T:
представляет его обход в инфиксном порядке?
jdbieafchg
jdfeibghca
djbeiacfhg
djbeiacfgh
djbeiafchg
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h },
E= {(a,b; 10), (a,c; 14),(a,f; 13), (a,g; 17), (h,a; 19) ,(b, d; 10), (b,f; 20), (b,g; 10), (c, d; 15), ( c,g; 13), (d, e; 5), (d,f; 13), (e,f; 12), (h, g; 21) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
66
81
79
77
84
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h, k },
E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20), (h,g; 10), (h,k; 12) }.
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
85
77
82
80
78
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {1,2,3,4,5,6,7,8, 9 },
E={(1,2;15), (1,3; 2), (1,4; 8), (1,7; 9), (2,3; 4), (2,5; 9), (2,9; 8), (3,4; 6), (6,3; 5), (6,5; 7), (6,4; 3), (6,8; 16), (4,7; 10), (4,8; 8), (7,8; 7), (8,9; 15)}
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
36
42
44
38
48
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k },
E= {(a, b; 10), (a, c; 7), (b, f; 21), (b, d; 9), (c, d; 8), (f, e; 7), (f, g; 8), (e, k; 12), (e, h; 10), (g, h; 8) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (a, b) II) (e, h) III) (b, f)
I и III
только I
I, II и III
только II
I и II
II и III
только III
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= {(a,b; 5), (a, h; 7), (b, c; 4), (b, f; 3), (c, d; 6), (c,f; 7), (d, e; 10), (e, f; 9), ( b,g; 15), (g, h; 10) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, g) II) (c, f) III) (d, l)
I и II
только III
I и III
только I
только II
I, II и III
II и III
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k },
E= {(a, b; 9), (a, c; 6), (b, c; 10), (b, d; 5), (b, e; 4), (d, e; 6), (d, f; 4), (e, f; 25),(f, g; 20), (g, h; 8), (g, k; 10), (h, k; 7) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, c) II) (f, g) III) (g, k)
только I
I и II
только II
I и III
II и III
I, II и III
только III
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: b, c, d, g Lb: a, f, d Lc: a, d, e
Ld: a, b, c, e Le: c, d, f Lf: b, e
Lg: a, i, h Lh: g, i Li: g, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: d, c, b Lb: a Lc: i, h
Ld: a, e, f Le: d, g, f Lf: d, e, g
Lg: e, f Lh: c, i Li: c, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: c, d, b Lb: a, f, g Lc: a, d, e
Ld: a, c, e Le: c, d Lf: b
Lg: b, i, h Lh: g, i Li: g, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, f), (d, e), (f, e), (a, g), (g, i), (h, g), (i, h) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
4
2
3
0
1
Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (d, e), (d, f), (f, g), (f, h), (f,i) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
1
4
2
0
3
Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, e), (f, e), (f, g), (d, h), (f, i), (h, a) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
3
0
1
2
4
Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= {(a,b; 21), (a, c; 5), (a, d; 4), (a, e; 16), (a, f; 13), (a, g; 10), (b, e; 10), (b, f; 8), ( b,g; 5), (b, h; 2), (c, e; 10), (c,f; 7), (d, b; 10), (d, g; 5), (d, h; 21), (g,b; 10), (g, h; 10) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
42
50
38
44
43
Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= { (a, c; 24), (a, d; 8), (a, e; 12), (a, f; 2), (a, g; 15), (b, c; 5), ( b,g; 15), (c, h; 5), (d, b; 10), (d, e; 3), (d, g; 10), (d, h; 21), (e, g; 2), (f, d; 5), (f, b; 17) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
48
44
35
34
32
Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h },
E= { (a, b; 5), (a, c; 32), (a, d; 2), (a, e; 32), (a, f; 12), (a, g; 15), (b, f; 6), (b, e; 20), ( b, h; 4), (c, h; 5), (d, g; 8), (d, h; 21), (g, c; 10), (g; e; 12), (f, d; 5), (f, b; 17) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
47
37
45
35
49
Какие из следующих утверждений о работе алгоритма Дейкстры верны?
А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.
Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
В) Если длины всех ребер в графе попарно различны, то дерево кратчайших путей из заданной вершины единственно.
только А
только В
А и Б
ни одно
только Б
А и В
Б и В
Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?
А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.
Б) Число этапов (итераций основного цикла) не превосходит (n - 1).
В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
только Б
все
А и Б
А и В
только А
только В
Б и В
Какие из следующих утверждений о работе алгоритма Дейкстры верны?
А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не убывают.
Б) В дереве кратчайших путей, построенном алгоритмом Дейкстры, длины ребер на каждой ветви не убывают.
В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.
Б и В
А и В
А и Б
только В
все
только Б
только А
Вы можете обратится к нам напрямую, через:
По Skype: molodoyberkut
По Telegram: @MolodoyBerkut
По ICQ: 657089516
Или через форму обратной связи на нашем сайте
По Skype: molodoyberkut По Telegram: @MolodoyBerkut По ICQ: 657089516Или через форму обратной связи на нашем сайте
Пока сочиняется...
Экзамен "Основы дискретной математики" для пользователей и системных администраторов.
