Главная / Алгоритмы и дискретные структуры / Основы дискретной математики

Основы дискретной математики - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Пусть множество 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?
    (1) только D
    (2) только B, D и E
    (3) только D, F и G
    (4) только D и E
    (5) только F и G
    (6) только C и F
    (7) только D, E, F и G
    Построить для заданного нагруженного неориентированного графа 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 ). Каков вес этого остова?
    (1) 66
    (2) 77
    (3) 79
    (4) 81
    (5) 84
    Пусть X ={a, b, c} – множество из трех элементов. Число трехместных функций f: X3 →​ X, которые можно определить на X равно:
    (1) 33
    (2) 312
    (3) 327
    (4) 39
    (5) 227
    Построить таблицу для функции, заданной формулой math и определить число наборов аргументов, на которых она равна 1.
    (1) 2
    (2) 3
    (3) 4
    (4) 5
    (5) 6
    (6) 7
    Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1101 1100). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
    (1) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
    (2) (X ∨ ¬Y∨ Z) ∧ (¬X ∨ ¬Y)
    (3) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
    (4) (¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)
    (5) (¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)
    Какие из следующих формул задают несамодвойственные функции: A= (X ∧¬ Z) ∨ (Y ∧ ¬Z) ∨( X ∧ Y), B = X+Z+ Y*Z, C= X ∨(Y ∧¬ Z)
    (1) только A
    (2) только B
    (3) A и B
    (4) A и C
    (5) B и C
    (6) все
    Пусть задана система 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
    •
    (1) только A
    (2) только B
    (3) только C
    (4) A и B
    (5) A и C
    (6) все
    Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). \begin{array}{llllllllll} (\forall x(P(x,y) & \rightarrow &\exists z (\forall y(Q(x,y,z) &\rightarrow & P(x,z)) \vee P(z,y))) &\rightarrow& \exists zQ(x,y,z))\\ \phantom{ (\forall x(P(}1\phantom{,}2 & & \phantom{\exists z (\forall y(Q(}3 \phantom{,y,}4 & & \phantom{P(x,}5 \phantom{)) \vee P(}6 \phantom{,}7 & & \phantom{\exists zQ(x,}8 \phantom{,}9 \end{array}
    (1) F={2,3,5,6} C= {1, 4,7,8,9}
    (2) F={1,5,8,9} C= {2, 4,6,7}
    (3) F={2,6,8} C= {1,3,4,5,7,9}
    (4) F={2,5,7,8,9} C= {1,3,4,6}
    (5) F={2,7,8} C= {1,3,4,5,6,9}
    Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами 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)
    •
    (1) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    (6) ни одно
    Сколько нулей в матрице смежности ориентированного графа 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)}.
    (1) 4
    (2) 6
    (3) 8
    (4) 10
    (5) 16
    Пусть заданы три множества: A={ a, {∅}, {a,c,d}}, B={a, c, e, {a}, {b},∅} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) ∩ C?
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    (7) 7
    Сколько вершин в полном бинарном дереве высоты 6?
    (1) 63
    (2) 96
    (3) 112
    (4) 120
    (5) 127
    Пусть задан неориентированный нагруженный граф 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)

    (1) только I
    (2) только II
    (3) только III
    (4) I и II
    (5) I и III
    (6) II и III
    (7) I, II и III
    Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 3 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?
    (1) 12400
    (2) 1200
    (3) 2400
    (4) 480
    (5) 14400
    Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: ¬ (¬x →​ (y + z))
    (1) (¬x ∨¬y) ∧ (¬x ∨ z)
    (2) ¬y ∧ (¬x ∨ z) ∧ (¬x ∨ y ∨ z)
    (3) (x ∨ ¬y ∨¬z) ∧ (y ∨ z)
    (4) ¬x ∧ ¬y ∧ (x∨ z)
    (5) ¬x ∧ (¬y ∨ ¬z) ∧ (y ∨ ¬z)
    Какие из следующих формул задают немонотонные функции: A= (Y →​¬X) →​ ( Y ∧ Z), B = (¬ X →​( Y∧ ¬Z)) →​Y, C= ¬ Z →​( Y∧ ¬X)
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Используя алгоритм ЗАМЫКАНИЕ(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.
    •
    (1) {b, f, g, e}
    (2) {b, f, g, e, c}
    (3) { b, f, g, e, c, k}
    (4) {a, b, f, g, e, c,d, k}
    (5) { b, c, g, k}
    Предположим, что 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)?
    (1) v - это брат w
    (2) v - это племянник w
    (3) v - это дядя w
    (4) v - это дед w
    (5) v - это двоюродный брат w
    Пусть отношения 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 &lt;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) }
    (1) Q1 и F1
    (2) Q1 и F2
    (3) Q2 и F1
    (4) Q2 и F2
    (5) Q3 и F1
    (6) Q3 и F2
    (7) ни один из предыдущих ответов не подходит
    Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 7-вершинном графе?
    (1) 7
    (2) 14
    (3) 21
    (4) 28
    (5) 49
    Пусть заданы множества A = {0, 1, 2}, B = {1, 2, 3}, C = {a, b, c} и D = {a, d, e}. Чему равно множество F = (A ∩ B) × (C \ D)?
    (1) { 1, 2, b, c}
    (2) {(0,b), (0, c), (1, b), (1,c)}
    (3) {(1,a), (1,b), (1,d), (2, a), (2,b), (2,d)}
    (4) {(1, b), (1, c), (2, b), (2, c)}
    (5) {(1,b), (1, c), (3, b), (3,c)}
    Какое выражение представляет ориентированное дерево? files
    (1) ((v * y) + a)) + (x - (z*x))
    (2) (z*x -x) * (a + v*y)
    (3) (x * (y - z)) + (x - (y*z))
    (4) ((v * y)+a) * ((z*x) - x)
    (5) (v + (y *a)) * (z*x -z)
    Пусть неориентированный граф 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, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
    (1) math
    (2) math
    (3) math
    (4) math
    (5) math
    Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 16 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 4 анекдота и не повторять никакие два года одни и те же четыре анекдота. Каково минимальное число анекдотов, которые он должен приготовить?
    (1) 4
    (2) 5
    (3) 6
    (4) 7
    (5) 8
    Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?
    (1) ((X0 ∨ ¬X1) ∨ ¬X2)
    (2) ((X0 ∧ X1) ∨ (X2 ∧ ¬X1))
    (3) ((¬X1 ∧ X0) ∨ (X2 ∧ ¬X0))
    (4) ((X2 ∧ X1) ∧ X0) ∨ (X2 ∧ ¬X1))
    (5) (X2 ∨ (¬X1 ∧ X0))
    Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1100 1101).

    I ) ¬ Y ∧ Z , II) ¬X, III) X ∧ Y ∧ Z, IV) ¬Y, V) X ∧ Z

    (1) I и III
    (2) только IV
    (3) только V
    (4) II, IV и V
    (5) II и IV
    (6) IV и V
    (7) I и V
    Какие из следующих формул задают нелинейные функции: A= (Y →​X) ∧ Z, B = (X∧ Y) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= (¬ Z→​ X) ∨¬ Y
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
  • a, c →​ d ;
  • a, b, d →​ c ;
  • c,b →​ a;
  • a,c →​ b;
  • a,d →​ c;
  • b,d →​ a.
    •  A: B: C: СЧЕТ = [2, 3, 2, 2, 2, 2] СЧЕТ = [ 2, 3, 2, 2, 2, 2] СЧЕТ = [2,3, 2, 2, 2, 2] СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1,2,3, 4,5,6) СПИСОК[b] = (2, 3, 6) CПИСОК[b] = (2, 3, 6) СПИСОК[b] = (2, 3,4, 6) СПИСОК[c] = (1,3, 4) СПИСОК[c] = (1,3,4) СПИСОК[c] = (1,2,3,4,5) СПИСОК[d] = (1, 2,5,6) СПИСОК[d] = (2,5,6) СПИСОК[d] = (1,2,5,6)
    (1) A
    (2) B
    (3) C
    (4) все ошибочны
    Какие из следующих формул логики предикатов являются тождественно истинными?
  • ( ∀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) только 1
    (2) только 2
    (3) 1 и 2
    (4) 1 и 3
    (5) 2 и 3
    Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры 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, 'компьютер')))
    • (1) E1 и F1
    (2) E1 и F2
    (3) E2 и F1
    (4) E2 и F2
    (5) E3 и F1
    (6) E3 и F2
    (7) ни один из предыдущих ответов не подходит
    Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?
  • Сумма степеней всех вершин G четна.
  • Если в G имеется ровно две вершины четной степени, то они связаны путем
  • Если в G имеется ровно две вершины нечетной степени, то они связаны путем
    • (1) только 1
    (2) только 3
    (3) только 1 и 3
    (4) только 1 и 2
    (5) 1, 2, и 3
    Какие из следующих равенств справедливы для всех множеств A и B?
  • (а) (A ∩ B) = A \ (A \ B)
  • (б) A ∩ (B \ A) = ∅
  • (в) (A \ B) ∪ B = A
    •
    (1) только (а)
    (2) только (б)
    (3) только (в)
    (4) только (а) и (б)
    (5) только (а) и (в)
    (6) только (б) и (в)
    (7) все
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в обратном (суффиксном) порядке?
    (1) abefdcgh
    (2) debfhgca
    (3) abdefcgh
    (4) debhgfca
    (5) dbefchga
    Пусть задан неориентированный граф 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) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
    (1) 0
    (2) 1
    (3) 2
    (4) 3
    (5) 4
    В кондитерском магазине продаются 4 сорта пирожных: заварные, песочные, "картошка" и бисквитные. Сколькими способами можно купить 7 пирожных?
    (1) 120
    (2) 330
    (3) 35
    (4) 165
    (5) 180
    Какие из следующих формул являются тождественно истинными?
  • math,
  • math,
  • math,
  • math
    •
    (1) ни одна
    (2) только A
    (3) только B
    (4) A и B
    (5) A и C
    (6) B и C
    (7) A, Cи D
    (8) все
    Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ((X ∧ Y) →​ ¬ Z) ∧ (¬ X →​ ¬ Y)
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→​ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) →​ (Z→​X), C= (X∨Y) →​¬Z
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов 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.
    (1) 2
    (2) 3
    (3) 4
    (4) 5
    (5) 6
    (6) получить e нельзя
    Пусть на множестве 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) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    Укажите, какие из указанных ниже формул соответствуют следующему 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 &lt; 10000) ∧¬(e=3))
  • F2(f, e, z) = ∃n∃d∃z∃e (((z > 6000) ∧ (z &lt; 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 &lt; 10000) ∧¬(e=3)))
    •
    (1) только F1
    (2) F1 и F2
    (3) F1 и F3
    (4) только F2
    (5) F2 и F3
    (6) ни одна

    Пусть граф G=(V,E) задан своей матрицей смежности

    A_G=\begin{array}{ccccc} 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 \end{array}

    Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.

    (1) 4
    (2) 5
    (3) 6
    (4) 7
    (5) 8
    Пусть бинарное отношение R над {a,b,c} задано как R = { (a,a), (a,с), (c, b), (a, b), (b,b), (c,c)}Какие из следующих свойств:
  • Симметричность
  • Антисимметричность
  • Рефлексивность
  • Транзитивность
    •  для него выполняются?
    (1) ни одно
    (2) только 2 и 3
    (3) только 2 и 4
    (4) 1, 3 и 4
    (5) 2, 3 и 4
    (6) только 1 и 3
    (7) все
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в прямом (префиксном) порядке?
    (1) abefdcgh
    (2) debfhgca
    (3) abdefcgh
    (4) debhgfca
    (5) abdecfgh
    Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
    (1) 32
    (2) 34
    (3) 35
    (4) 44
    (5) 48
    В стране N в первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебренных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места). Найдите число не совпадающих в главном возможных исходов первенства.
    (1) 180 180
    (2) 30 030
    (3) 360 360
    (4) 47 775
    (5) 436 860
    Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
  • По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
  • В точности две переменных из p1, p2, p3, p4истинны (равны 1).
  • Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 2
    (5) 1 и 3
    (6) 2 и 3
    Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0101).
    (1) X*Y
    (2) X*Z
    (3) Y
    (4) Z
    (5) X*Y*Z
    (6) Y*Z
    Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1011 0010), (0110 1001), (0110 1001 }.
    (1) только F
    (2) только G
    (3) только H
    (4) F и G
    (5) G и H
    (6) все
    Пусть в сигнатуру системы, описывающей результаты экзаменов входит предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?
  • ∃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) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    (6) ни одна
    Пусть база данных включает отношение Книга(Автор, Название, Издательство, ГодИздания). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Автор и Название образуют ключ отношения.
  • Ф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)))
    •
    (1) только Ф1
    (2) Ф1 и Ф2
    (3) Ф1 и Ф3
    (4) только Ф2
    (5) Ф2 и Ф3
    (6) ни одна
    Чему равно число связных компонент неориентированного графа 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)}?
    (1) 5
    (2) 3
    (3) 7
    (4) 6
    (5) 4
    На множестве всех непустых отрезков числовой прямой определены три отношения: 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}. Какие из них являются отношениями частичного порядка?
    (1) P
    (2) Q
    (3) R
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в инфиксном порядке?
    (1) dbieafchg
    (2) dbeiafchg
    (3) dbeiacfgh
    (4) dbeiacfhg
    (5) dfeibghca
    Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?
  • А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.
  • Б) Число этапов (итераций основного цикла) не превосходит (n - 1).
  • В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
    •
    (1) только А
    (2) только Б
    (3) только В
    (4) А и Б
    (5) А и В
    (6) Б и В
    (7) все
    При игре в преферанс колоду из 32 карт раздают трем игрокам – каждому по 10 карт, а оставшиеся 2 карты оставляют в прикупе. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
    (1) C(32,2)*C(30, 10)3
    (2) (C(32,2)*P(32)) / P(10)3
    (3) C(32, 2)*C(30,10)*C(20,10)
    (4) P(32) / (P(2) * P(10)3)
    (5) A(32,30)* C(32,2)
    Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Они дали следующие показания:
  • Джонс: если Браун преступник, то Карт не виновен.
  • Браун: если Джонс виновен, то и Карт является преступником.
  • Карт: Джонс преступник.
    •  Ш. Холмс установил, что если Джонс сказал правду, то Браун соврал, и что показаниям Карта нельзя доверять. Какие из следующих выводов он может сделать из установленных фактов:
  • Джонс является преступником.
  • Браун является преступником.
  • Карт является преступником.
  • Преступников могло быть двое.
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 4
    (5) 2 и 3
    (6) 2 и 4
    (7) 1 и 3
    Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле (¬( ( X→​Y) ∨ ¬(Y →​ X)) ∧ Z) и укажите, сколько в нем слагаемых.
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y, g = X →​ Y , h = X+Y
    (1) f
    (2) g
    (3) h
    (4) f и g
    (5) g и h
    (6) f и h
    Пусть 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) )
    •
    (1) только A
    (2) A и B
    (3) A и C
    (4) только B
    (5) B и C
    (6) ни одна
    Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад) и Комнаты(ФИО_Сотрудника, Этаж, Комната). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: для каждого сотрудника из таблицы Сотрудники в таблице Комнаты определено его место работы.
  • Ф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))
    •
    (1) только Ф1
    (2) Ф1 и Ф2
    (3) Ф1 и Ф3
    (4) только Ф2
    (5) Ф2 и Ф3
    (6) ни одна
    Определите все базы следующего ориентированного графа G: files
    (1) {a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}
    (2) {a, m}, {g, m}, {h,m}, {a, n}, {g, n}, {h, n}
    (3) {a, g, h, m, n}
    (4) {g, m}, {g, n}, {h, m}, {h,n}
    (5) {a, m, e}, {g, m, e}, {h,m,e}, {a, n, e}, {g, n, e}, {h, n,e}
    Сколько чисел в первой сотне не делится ни на одно из чисел 3, 5, 7?
    (1) 58
    (2) 64
    (3) 42
    (4) 45
    (5) 48
    Пусть множество 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?
    (1) только B
    (2) только C, D и E
    (3) только D и F
    (4) только C, D, E и F
    (5) только D, E, F и G
    (6) только C, F и G
    Пусть корень ориентированного дерева T имеет 7 сыновей, а каждая из остальных внутренних вершин имеет три или три четыре сына, при этом число вершин с 3-я сыновьями втрое больше числа вершин с 4-я. Сколько всего вершин в T, если известно, что число его листьев равно 52?
    (1) 68
    (2) 73
    (3) 78
    (4) 83
    (5) 88
    Построить для заданного нагруженного неориентированного графа 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 ). Каков вес этого остова?
    (1) 80
    (2) 77
    (3) 82
    (4) 85
    (5) 78
    Пусть X ={a, b, c} – множество из трех элементов. Число трехместных отношений, которые можно определить на X равно:
    (1) 33
    (2) 312
    (3) 327
    (4) 29
    (5) 227
    Построить таблицу для функции, заданной формулой math и определить число наборов аргументов, на которых она равна 1.
    (1) 2
    (2) 3
    (3) 4
    (4) 5
    (5) 6
    (6) 7
    Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1011 0011). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
    (1) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
    (2) (X ∨ Y∨ ¬Z) ∧ (¬X ∨ Y)
    (3) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)
    (4) (X ∧ Y ∧¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ Y ∧ ¬Z)
    (5) (X ∨ Y ∨ ¬Z) ∧ (¬X ∨Y ∨ Z) ∧ (¬X ∨ Y ∨¬ Z)
    Какие из следующих формул задают несамодвойственные функции: A= (Y ∧¬ Z) ∨ (X ∧ ¬Z) ∨( X ∧ Y), B =(¬ X∧ (Y|Z)) ∨(¬ Y ∧¬ Z) , C= Z ∨(Y ∧¬ X)
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Пусть задана система 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
    •
    (1) только A
    (2) только B
    (3) только C
    (4) A и B
    (5) A и C
    (6) все
    Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). \begin{array}{llllllllll} ((\forall xP(x,y) & \rightarrow & \exists z (\forall y(Q(x,y,z) &\wedge &P(x,z)) &\vee & P(z,y))) &\rightarrow &\exists zQ(x,y,z)) \\ \phantom{ ((\forall xP(}1\phantom{,}2 & & \phantom{\exists z (\forall y(Q(}3\phantom{,y,}4& &\phantom{P(x,}5& &\phantom{P(}6\phantom{,}7 & & \phantom{\exists zQ(x,}8\phantom{,}9 \end{array}
    (1) F={2,3,7,8} C= {1, 4, 5, 6, 9}
    (2) F={1,3,7,8 } C= {2, 4,5, 6, 9}
    (3) F={2,6,8} C= {1,3,4,5,7,9}
    (4) F={2,3,7,8,9} C= {1,4,6}
    (5) F={2,7,8} C= {1,3,4,5,6,9}
    Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами 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))
    •
    (1) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    (6) ни одно
    Сколько нулей в матрице смежности ориентированного графа G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,d), (b,a), (b,b), (c, a), (c,d), (d,b)}.
    (1) 6
    (2) 7
    (3) 8
    (4) 9
    (5) 10
    Пусть заданы три множества: A={ a, b, c,{∅}, {a}}, B={a, e, {a}, {b},∅} и C = {a, b, d, {e}, {∅}}. Какова мощность множества D = (A \ B) ∩ C?
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    Сколько вершин в полном бинарном дереве высоты 4?
    (1) 16
    (2) 18
    (3) 27
    (4) 31
    (5) 47
    Пусть задан неориентированный нагруженный граф 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)

    (1) только I
    (2) только II
    (3) только III
    (4) I и II
    (5) I и III
    (6) II и III
    (7) I, II и III
    Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 4 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?
    (1) 1800
    (2) 43200
    (3) 600
    (4) 48000
    (5) 14400
    files Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9 (коды начинаются с 4-ой строки). Какие из булевых формул задают множество всех ошибочных кодов?
    (1) (¬A ∨ ¬B) ∧(¬C ∨ ¬D))
    (2) (((A ~ B) ∧ ¬(C~D)) ∨ ((A ∧ B) ∧ (C ∧ D)))
    (3) (((¬A ∧ ¬B) ∧(¬C ∨ ¬D)) ∨ ((A ∧ B) ∧(C ∨ D)))
    (4) (((A ↓ B) ∧(¬C ∨ ¬D)) ∨ ( (A ∧ C) ∧ D))
    (5) ((¬A ∧ ¬B) ∨ (C →​ ¬D))
    Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (¬x+y) →​ (y ∧ z)
    (1) (x ∨¬y) ∧ (¬x ∨¬y∨ z)
    (2) y ∧ (¬x ∨ z) ∧ (x ∨ y ∨ z)
    (3) (x ∨ y) ∧ (¬x ∨¬y∨ z)
    (4) x ∧ ¬y ∧ (x∨ z)
    (5) (x ∨ y) ∧ (¬y ∨ ¬z)
    Какие из следующих формул задают немонотонные функции: A= (Y →​¬X) →​ ( Y ∧ Z), B = ((¬ X∧ Z) →​( Y∧ ¬Z)) ∧ Y, C= X +Y + Y*Z +X*Y*Z
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Используя алгоритм ЗАМЫКАНИЕ(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.
    • (1) {b, c, f, g, e}
    (2) {b, c, d, f, g, e}
    (3) {a, b, c , d, f, g, e }
    (4) {a, b, c, d, e, f, g, h}
    (5) {a, d, e, g, h}
    Предположим, что 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)?
    (1) v это сестра w
    (2) v это племянница w
    (3) v это тетя w
    (4) v это бабушка w
    (5) v это двоюродная сестра w
    Пусть отношения 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) }
    (1) Q1 и F1
    (2) Q1 и F2
    (3) Q2 и F1
    (4) Q2 и F2
    (5) Q3 и F1
    (6) Q3 и F2
    (7) ни один из предыдущих ответов не подходит
    Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 8-вершинном графе?
    (1) 8
    (2) 16
    (3) 24
    (4) 28
    (5) 32
    Пусть заданы множества A = {0, 1, 2, 3}, B = {1, 2, 4}, C = {a, b, c} и D = {b, d, e}. Чему равно множество F = (A\ B) × (C \ D)?
    (1) {0, 3, a, c}
    (2) {(1, a), (1, c), (2, b), (2,c)}
    (3) {(0,a), (0,c), (3, a), (3,c)}
    (4) {(0, a), (0, c), (2, a), (2, c)}
    (5) {(0,b), (0, c), (3, b), (3,c)}
    Какое выражение представляет ориентированное дерево? files
    (1) ((v * y) + x)) + (t- (z*x))
    (2) (z*x -x) * (a + v*y)
    (3) (x * (y - v)) + (z * x * t))
    (4) ((v * y)+x) + ((z*x) - t)
    (5) ((v *y) +x) + (z * x * t)
    Пусть неориентированный граф 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, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
    (1) math
    (2) math
    (3) math
    (4) math
    (5) math
    Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 2, 3или 5. Какая из следующих формул задает эту функцию?
    (1) ((X0∨ ¬X1 ) ∨ ¬X2)
    (2) ( (X0 ∧ X1 ) ∨ (X2 ∧ ¬X1))
    (3) ((¬X1 ∧ X0) ∨ (X2 ∧ ¬X0))
    (4) ((X1 ∧ ¬X2) ∨ (X0 ∧ ¬X1))
    (5) (X2 ∨ (¬X1 ∧ X0))
    Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1011 1010).

    I ) ¬ X∧Y ∧ Z , II) ¬Z, III) ¬ X∧Y , IV) ¬Y, V) X ∧ ¬Z

    (1) I и III
    (2) только IV
    (3) только V
    (4) II, IV и V
    (5) II иIII
    (6) III , IV и V
    (7) I и V
    Какие из следующих формул задают нелинейные функции: A= (X∧ Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) →​ Z, C= ¬Z∨ X∨Y
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
  • a, c, d →​ b ;
  • a, b, d →​ c ;
  • c,b,d →​ a;
  • a,c →​ b;
  • a →​ c;
  • b,d →​ a.
    •  A: B: C: СЧЕТ = [3, 2, 2, 2, 3,1] СЧЕТ = [3, 2, 2, 2, 2,1] СЧЕТ = [3, 2, 2, 2, 3,1] СПИСОК[a] = (1,2, 3, 4,5) СПИСОК[a] = (1,4,5) СПИСОК[a] = (1,4,5) СПИСОК[b] = (1, 2, 3, 4, 5,6) CПИСОК[b] = (1, 2, 3, 5) СПИСОК[b] = (1, 2, 3, 5,6) СПИСОК[c] = (1,3,5) СПИСОК[c] = (1,3) СПИСОК[c] = (1,3) СПИСОК[d] = (1,2,4,5) СПИСОК[d] = (2,4,5) СПИСОК[d] = (2,4,5)
    (1) A
    (2) B
    (3) C
    (4) все ошибочны
    Какие из следующих формул логики предикатов являются тождественно истинными?
  • ( ∀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) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 3
    (5) ни одна
    Пусть G=( V, E) - это конечный неориентированный граф. Какие из следующих утверждений верны?
  • Если |E| < |V| - 1, то .граф G не является связным.
  • Если |E| > |V| - 1, то в G имеется цикл.
  • Если в G имеется цикл, то |E| > |V| - 1
    • (1) только 1
    (2) только 2
    (3) только 1 и 3
    (4) только 1 и 2
    (5) 1, 2, и 3
    Какие из следующих равенств справедливы для всех множеств A, B и C?
    (1) (A \ B) \ C = A \ (B \ C)
    (2) (A \ B) ∪ (A \ C) = A \ (B ∩ C)
    (3) A ∩ (B \ C) = (A ∩ B) \ C
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в обратном (суффиксном) порядке?
    (1) abefdcghk
    (2) kdbfehgca
    (3) abdkfecgh
    (4) kdfebhgca
    (5) kfdebhgca
    Пусть задан неориентированный граф 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) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
    (1) 0
    (2) 1
    (3) 2
    (4) 3
    (5) 4
    В кондитерском магазине продаются 5 сортов пирожных: заварные, песочные, "картошка", корзинка и бисквитные. Сколькими способами можно купить 6 пирожных?
    15625
    Какие из следующих формул являются тождественно истинными?
  • math,
  • math,
  • math,
  • math
    •
    (1) ни одна
    (2) только A
    (3) только B
    (4) A и B
    (5) A и C
    (6) A, C и D
    (7) A, B и C
    (8) B, C и D
    Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ((¬ X ∧ ¬ Y) →​ (¬ Z ∨ (¬ X →​ ( Y ∧ Z)) ))
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→​ ¬Y ) ∨ (¬ X∧ ¬ Z ), B = (¬X∨ Z) →​ ¬Y, C= (Y + ¬X) →​ (Z→​ ¬Y ),
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов 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.
    (1) 2
    (2) 3
    (3) 4
    (4) 5
    (5) 6
    (6) получить e нельзя
    Пусть на множестве 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) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    Укажите, какие из указанных ниже формул соответствуют следующему 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 &lt; 5500)))
  • F2(e, k) = ∃n∃o∃d∃z ( C(n, f, o, d, z) ∧ K(n, e, k) ∧ O(e, k, "компьютер") ∧ ((z > 7500) ∨ (z &lt; 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 &lt; 5500)) →​ (c="компьютер"))
    • (1) только F1
    (2) F1 и F2
    (3) F1 и F3
    (4) только F2
    (5) F2 и F3
    (6) ни одна

    Пусть граф G=(V,E) задан своей матрицей смежности

    A_G=\begin{array}{ccccc} 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 \end{array}

    Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.

    (1) 15
    (2) 16
    (3) 17
    (4) 18
    (5) 19
    Пусть бинарное отношение R над {a,b,c} задано как R = {(a,a), (a,с), (c, b), (a, b)}Какие из следующих свойств:
  • Симметричность
  • Антисимметричность
  • Рефлексивность
  • Транзитивность
    •  для него выполняются?
    (1) ни одно
    (2) только 2 и 4
    (3) только 1 и 4
    (4) 1, 3 и 4
    (5) 2, 3 и 4
    (6) только 1 и 3
    (7) все
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в прямом (префиксном) порядке?
    (1) abefdcghk
    (2) kdbfehgca
    (3) abdkfecgh
    (4) abdkfechg
    (5) akfdebhgc
    Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
    (1) 49
    (2) 35
    (3) 45
    (4) 37
    (5) 47
    В первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебряных и бронзовых медалей, а также три команды, покидающие премьер-лигу (т.е. занявшие три последних места). Найдите число не совпадающих в главном возможных исходов первенства.
    (1) 1201200
    (2) 207025
    (3) 100100
    (4) 600600
    (5) 436860
    Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
  • По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
  • Не все из переменных из p1, p2, p3, p4ложны (равны 0).
  • Нечетное число переменных из p1, p2, p3, p4истинны (равны 1).
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 2
    (5) 1 и 3
    (6) 2 и 3
    Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0001 0111).
    (1) X*Y
    (2) X
    (3) Y
    (4) X*Z
    (5) X*Y*Z
    (6) Z
    Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1111 0000), (0101 1111)}.
    (1) F
    (2) G
    (3) H
    (4) ни одна
    Пусть в сигнатуру системы, описывающей результаты экзаменов входит предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Все студенты, успешно сдавшие алгебру, успешно сдали дискретную математику или информатику".
  • ∀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, инф, неуд)))
    •
    (1) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    (6) ни одна
    Пусть база данных включает отношение Счет(Номер,Товар,Дата,Сумма). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибут Номер является ключом отношения.
  • Ф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) только Ф1
    (2) Ф1 и Ф2
    (3) Ф1 и Ф3
    (4) только Ф2
    (5) Ф2 и Ф3
    (6) ни одна
    Чему равно число связных компонент неориентированного графа 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)}?
    (1) 5
    (2) 3
    (3) 7
    (4) 6
    (5) 4
    На множестве всех непустых отрезков числовой прямой определены три отношения: 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}Какие из них являются отношениями частичного порядка.
    (1) ни одно
    (2) только R
    (3) только P
    (4) только Q
    (5) P и R
    (6) R и Q
    (7) все
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в инфиксном порядке?
    (1) jdbieafchg
    (2) djbeiafchg
    (3) djbeiacfgh
    (4) djbeiacfhg
    (5) jdfeibghca
    Какие из следующих утверждений о работе алгоритма Дейкстры верны?
  • А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.
  • Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
  • В) Если длины всех ребер в графе попарно различны, то дерево кратчайших путей из заданной вершины единственно.
    • (1) только А
    (2) только Б
    (3) только В
    (4) А и Б
    (5) А и В
    (6) Б и В
    (7) ни одно
    При игре в "дурака" колоду из 36 карт раздают четырем игрокам – каждому по 6 карт, а оставшиеся 12 карт и оставляют в прикупе в фиксированном порядке. Далее в процессе игры карты из прикупа замещают в указанном порядке карты, выбывшие из игры, поэтому их порядок существенен. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
    (1) A(36,12)*P(24)/ P(6)4
    (2) (C(36,12)*P(24)) / P(6)4
    (3) C(36,12)*C(30,10)*C(20,10)
    (4) A(36,12)*C(24,6)*C(18,6)*C(12,6)
    (5) A(36,12)* P(24)
    Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что
  • если Джонс не преступник, то Браун является преступником ;
  • кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
  • Браун и Карт вместе не совершали преступление.
    •  Какие из следующих выводов он может сделать из установленных фактов:
  • Джонс является преступником.
  • Браун является преступником.
  • Карт является преступником.
  • Преступник действовал в одиночку.
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 4
    (5) 2 и 3
    (6) 3 и 4
    (7) 1 и 3
    Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((X ∨Y∨ Z) ∧ (X ∨ (Y→​ Z))) ∧ (X ∨¬ Y∨ ¬ Z) и укажите, сколько в нем слагаемых.
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∧ Y∧ ¬ Z, g = X ∨ Y , h = X+Y+1
    (1) f
    (2) g
    (3) h
    (4) f и g
    (5) g и h
    (6) f и h
    Пусть 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) )
    •
    (1) только C
    (2) A и B
    (3) A и C
    (4) только B
    (5) B и C
    (6) ни одна
    Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад), Комнаты(ФИО_Сотрудника, Комната) и Оборудование( Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: стоимость любого аппарата в комнате сотрудника превышает его оклад не более чем в два раза.
  • Ф1 = ∀f∀o∀d∀z∀k∀s( (Сотрудники(f,o,d,z) ∧ Комнаты(f , k) ∧ Оборудование(k,n,s)) →​ (s &lt; 2z))
  • Ф2 = ∀f∀o∀d∀z(Сотрудники(f,o,d,z) →​ ∃k∀s( Комнаты(f , k) ∧ Оборудование(k,n,s) ∧ (s &lt; 2z)))
  • Ф3 = ∀f∀s (∃o∃d∃zСотрудники(f,o,d,z) →​ ∃k( Комнаты(f ,e, k) ∧ Оборудование(k,n,s) ∧ (s &lt; 2z)))
    •
    (1) только Ф1
    (2) Ф1 и Ф2
    (3) Ф1 и Ф3
    (4) только Ф2
    (5) Ф2 и Ф3
    (6) ни одна
    Определите все базы следующего ориентированного графа G: files
    (1) {d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}
    (2) {d, h}, {e, h}, {k, h}, {m, h}
    (3) {d, e, k, m, f, h}
    (4) {d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}, {n,f,h}
    (5) {d, f, h}, {k, f, h}, {m, f, h}
    Сколько чисел в первой сотне не делится ни на одно из чисел 2, 5, 7?
    (1) 34
    (2) 43
    (3) 41
    (4) 32
    (5) 38
    Пусть заданы три множества: A ={ a, b, {∅}, {a,c,d}}, B={a, c, e, {a}, {b}} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) \ C?
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    (7) 7
    Сколько вершин в полном бинарном дереве высоты 5?
    (1) 25
    (2) 33
    (3) 63
    (4) 71
    (5) 88
    Пусть задан неориентированный нагруженный граф 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)

    (1) только I
    (2) только II
    (3) только III
    (4) I и II
    (5) I и III
    (6) II и III
    (7) I, II и III
    Фотограф хочет для групповой фотографии расположить в одну шеренгу 4 юноши и 2 девушки так, чтобы две девушки не стояли рядом. Сколькими способами он может это сделать?
    (1) 240
    (2) 96
    (3) 560
    (4) 480
    (5) 1440
    files Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9. Какие из булевых формул задают множество всех ошибочных кодов?
    (1) (A ∨ (B ∧ C))
    (2) ((A ∧ B) ∧ (C ∧ D))
    (3) ((A ∧ B) ∨ (A ∧ D))
    (4) ((A ∧ B) ∨ (C ∧ D))
    (5) ((A ∧ B) ∨ (A ∧ C))
    Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (x ∨ y) →​ (x ∧¬y ∧ z)
    (1) (¬x ∨¬y) ∧ (¬x ∨ z)
    (2) ¬y ∧ (¬x ∨ z)
    (3) (x ∨ y ∨ z) ∧ (¬y ∨ z)
    (4) ¬y ∧ (x∨ z)
    (5) ¬y ∧ (¬x ∨¬y)
    Какие из следующих формул задают немонотонные функции: A= X*Z+ Y*Z+X*Y*Z, B = ¬ X →​( Y∧ ¬Z), C= (X →​¬Z) →​ ( X ∧ Y)
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Используя алгоритм ЗАМЫКАНИЕ(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.
    •
    (1) {b, f, g, e}
    (2) {b, f, g, e, c}
    (3) {a, b, f, g, e, c}
    (4) {a, b, f, g, e, c,d}
    (5) {a, g, e, c,d}
    Предположим, что 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)?
    (1) v это брат w
    (2) v это племянник w
    (3) v это дядя w
    (4) v это дед w
    (5) v это двоюродный брат w
    Пусть отношения 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) }
    (1) Q1 и F1
    (2) Q1 и F2
    (3) Q2 и F1
    (4) Q2 и F2
    (5) Q3 и F1
    (6) Q3 и F2
    (7) ни один из предыдущих ответов не подходит
    Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 6-вершинном графе?
    (1) 6
    (2) 9
    (3) 12
    (4) 15
    (5) 30
    Пусть заданы множества A = {0, 1, 2}, B = {2, 3}, C = {a, b, c} и D = {a, c, e}. Чему равно множество F = (A \ B) × (C ∩ D)?
    (1) {0, 1, a, c}
    (2) {(0,a), (0,b), (0, c), (1, a), (1, b), (1,c)}
    (3) {(0,a), (0,c), (1,a), (1,c), (2,a), (2,c)}
    (4) {(0, a), (0, c), (0,e), (1, a), (1, b), (1,e)}
    (5) {(0,a), (0, c), (1,a), (1,c)}
    Какое выражение представляет ориентированное дерево? files
    (1) ((x + y) - z)) * (x - (y*z))
    (2) (x + (y - z)) * (x - (y*z))
    (3) (x * (y - z)) + (x - (y*z))
    (4) (x + (y - z)) * ((y*z) - x)
    (5) (x + (y - z)) * (x * (y-z))
    Пусть неориентированный граф 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, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
    (1) math
    (2) math
    (3) math
    (4) math
    (5) \begin{array}{ccccccccc}a&b&c&d&e&f&g&h&i\\ 1&6&3&2&4&5&8&7&9\end{array}
    Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 22 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 5 анекдотов и не повторять никакие два года подряд одни и те же пять анекдотов. Каково минимальное число анекдотов, которые он должен приготовить?
    (1) 6
    (2) 7
    (3) 8
    (4) 9
    (5) 10
    Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 4, 5или 6. Какая из следующих формул задает эту функцию?
    (1) ((¬X0 ∨ ¬X1 ) ∨ ¬X2)
    (2) ((¬X2 ∧ X0) ∨ (X2 ∧ X1))
    (3) ((¬X1∧ X0) ∨ (X2 ∧ ¬X0))
    (4) ((¬X2 ∧ (X1 ∧ X0)) ∨ (X2 ∧ ¬X1))
    (5) (X2 ∨ (¬X1 ∧ X0))
    Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0011 1011).

    I ) ¬X ∧ Y ∧ Z , II) X ∧ ¬Z, III) Y ∧ ¬Z, IV) Y, V) X ∧ ¬Y ∧ ¬Z

    (1) I и III
    (2) только IV
    (3) только II
    (4) II и IV
    (5) II, IV и V
    (6) II , III , IV и V
    (7) I и V
    Какие из следующих формул задают нелинейные функции: A= (Y →​¬X) →​ Z, B = (X∧ Y∧ Z) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= ( Z→​ X) ∨Y
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов F:
  • a ,b, c →​ d ;
  • b, d →​ a ;
  • c,b →​ a;
  • a,d →​ b;
  • a,b,d →​ c;
  • b →​ a.
    •  A: B: C: СЧЕТ = [3, 3, 3, 2, 1, 2] СЧЕТ = [ 2, 3, 3, 2, 1, 2] СЧЕТ = [3, 2, 3, 2, 1, 2] СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1,2, 4,5) СПИСОК[a] = (1, 2, 3, 4,5,6) СПИСОК[b] = (2, 3, 6) CПИСОК[b] = (2, 3, 6) СПИСОК[b] = (1, 2, 3, 4, 6) СПИСОК[c] = (1,3, 4) СПИСОК[c] = (1,3,4) СПИСОК[c] = (1,2,3,4,5) СПИСОК[d] = (1, 2, 3, 6) СПИСОК[d] = (1,2,5,6) СПИСОК[d] = (1,2,3,6)
    (1) A
    (2) B
    (3) C
    (4) все ошибочны
    Какие из следующих формул логики предикатов являются тождественно истинными?
  • ( ∀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) только 1
    (2) только 3
    (3) 1 и 2
    (4) 1 и 3
    (5) 2 и 3
    Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры 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)))
    • (1) E1 и F1
    (2) E1 и F2
    (3) E2 и F1
    (4) E2 и F2
    (5) E3 и F1
    (6) E3 и F2
    (7) ни один из предыдущих ответов не подходит
    Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?
  • В G есть вершина, в которую не входят ребра.
  • В G есть вершина, из которой не выходят ребра.
  • В G есть изолированная вершина, т.е. вершина, у которой нет инцидентных ребер.
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) только 1 и 2
    (5) 1, 2, и 3
    Какие из следующих равенств справедливы для всех множеств A, B и C?
  • (а) (A ∩ B) \ C = A ∩ (B \ C)
  • (б) (A ∩ B) ∪ C = A ∩ (B ∪ C)
  • (в) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
    •
    (1) только (а)
    (2) только (а) и (б)
    (3) только (а) и (в)
    (4) только (б) и (в)
    (5) все
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в обратном (суффиксном) порядке?
    (1) abefdcgh
    (2) dbfeahgc
    (3) abdefcgh
    (4) dfebhgca
    (5) dfebghca
    Пусть задан неориентированный граф 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) 0
    (2) 1
    (3) 2
    (4) 3
    (5) 4
    В кондитерском магазине продаются 4 сорта пирожных: заварные, песочные, "картошка'' и бисквитные. Сколькими способами можно купить 6 пирожных?
    (1) 210
    (2) 15
    (3) 30
    (4) 84
    (5) 120
    Какие из следующих формул являются тождественно истинными?
  • math,
  • math,
  • math,
  • math
    •
    (1) ни одна
    (2) только A
    (3) только B
    (4) A и B
    (5) A и C
    (6) A, B и C
    (7) A, C и D
    (8) все
    Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле ¬ (X →​ ( ¬Y →​ (X ∧ ¬ Z))) ∧ (Z ∨ ¬ (X ∧ Y))
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1: A= (X→​ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) →​ (Z→​X), C= ¬Z∨ X∨Y
    (1) только A
    (2) только B
    (3) только C
    (4) A и C
    (5) B и C
    (6) все
    Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов 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.
    (1) 2
    (2) 3
    (3) 4
    (4) 5
    (5) 6
    (6) получить a нельзя
    Пусть на множестве 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)))
    •
    (1) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    Укажите, какие из указанных ниже формул соответствуют следующему 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)))
    •
    (1) только F1
    (2) F1 и F2
    (3) F1 и F3
    (4) только F2
    (5) F2 и F3
    (6) ни одна

    Пусть граф G=(V,E) задан своей матрицей смежности

    A_G=\begin{array}{ccccc} 0& 1 &0 &0 &0\\ 0 &1& 0& 0& 0\\ 0 &0 &0 &1 &0\\ 0 &1 &0 &0 &1\\ 1 &0 &0 &0 &1 \end{array}

    Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.

    (1) 4
    (2) 5
    (3) 6
    (4) 7
    (5) 8
    Какими свойствами обладает бинарное отношение R над {a,b,c} заданное как R = { (a,a), (a,b), (b,a),(b,b), (c,c)}?
    (1) Симметричность
    (2) Антисимметричность
    (3) Рефлексивность
    (4) Транзитивность
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в прямом (префиксном) порядке?
    (1) abdefcgh
    (2) adbefhgc
    (3) abdefchg
    (4) dbefhgca
    (5) dfebghca
    Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
    (1) 38
    (2) 42
    (3) 44
    (4) 43
    (5) 50
    В стране N в первенстве премьер-лиги по футболу участвуют 16 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебрянных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места). Найдите число не совпадающих в главном возможных исходов первенства.
    (1) 524 160
    (2) 4368
    (3) 462 280
    (4) 262 080
    (5) 43680
    Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∨и ∧(без отрицания ¬)?
  • По крайней мере три переменных из p1, p2, p3, p4истинны (равны 1).
  • В точности три переменных из p1, p2, p3, p4истинны (равны 1).
  • Четное число переменных из p1, p2, p3, p4истинны (равны 1).
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 2
    (5) 1 и 3
    (6) 2 и 3
    Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции 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

    (1) только I и III
    (2) только IV и VI
    (3) I, II и V
    (4) II, IV и V
    (5) I, IV и VI
    (6) III , IV и V
    (7) только I и V
    Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F={ (1001 0110), (0111 1100), (0001 0011) }, G={ (1111 1111), (0101 0101), (0000 0011) }, H= { (0011 0111), (0110 1000), (1111 0000) }.
    (1) только F
    (2) только G
    (3) только H
    (4) F и H
    (5) G и H
    (6) все
    Пусть база данных включает отношение Оборудование(Этаж, Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Этаж и НомерКомнаты образуют ключ отношения.
  • Ф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))
    •
    (1) только Ф1
    (2) Ф1 и Ф2
    (3) Ф1 и Ф3
    (4) только Ф2
    (5) Ф2 и Ф3
    (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)}?
    (1) 5
    (2) 3
    (3) 7
    (4) 6
    (5) 4
    На множестве всех непустых отрезков числовой прямой определены три отношения: 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} Какие из них являются отношениями частичного порядка.
    (1) ни одно
    (2) только R
    (3) только P
    (4) только Q
    (5) P и R
    (6) R и Q
    (7) все
    Какое из следующих перечислений вершин бинарного дерева T: files представляет его обход в инфиксном порядке?
    (1) dbiefacgh
    (2) adbefhgc
    (3) dbfeiacgh
    (4) dbfeiachg
    (5) dfeibghca
    Какие из следующих утверждений о работе алгоритма Дейкстры верны?
  • А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не убывают.
  • Б) В дереве кратчайших путей, построенном алгоритмом Дейкстры, длины ребер на каждой ветви не убывают.
  • В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.
    •
    (1) только А
    (2) только Б
    (3) только В
    (4) А и Б
    (5) А и В
    (6) Б и В
    (7) все
    При игре в бридж колоду из 52 карт раздают 4 игрокам – каждому по 13 карт. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
    (1) (C(52, 13))4
    (2) P(52) / P(13)4
    (3) A(52, 13)*A(39,13)*A(26,13)
    (4) C(52, 13)*C(39,13)*C(26,13)
    (5) P(52) / C(52,3)
    Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что
  • если Браун преступник, то и Карт является преступником ;
  • кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
  • если Карт не преступник, то и Джонс не преступник.
    •  Какие из следующих выводов он может сделать из установленных фактов:
  • Джонс является преступником.
  • Браун является преступником.
  • Карт является преступником.
  • Преступник действовал в одиночку.
    •
    (1) только 1
    (2) только 2
    (3) только 3
    (4) 1 и 4
    (5) 2 и 3
    (6) 3 и 4
    (7) 1 и 3
    Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((( Y ∧ Z) →​ ¬ (X ∨ Z)) ∧ ¬ (¬ Y∧ Z∧X)) и укажите, сколько в нем слагаемых.
    (1) 1
    (2) 2
    (3) 3
    (4) 4
    (5) 5
    (6) 6
    Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y , g = X →​ ¬ Y , h = X+Y
    (1) f
    (2) g
    (3) h
    (4) f и g
    (5) g и h
    (6) f и h
    Пусть 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) )
    •
    (1) только A
    (2) A и B
    (3) A и C
    (4) только B
    (5) B и C
    (6) ни одна
    Пусть база данных включает отношения Комнаты(ФИО_Сотрудника, Этаж, Комната) и Оборудование(Этаж, Комната, Название, Стоимость) . Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: в комнате у каждого сотрудника имеется некоторое оборудование стоимостью больше 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 ))
    •
    (1) только Ф1
    (2) Ф1 и Ф2
    (3) Ф1 и Ф3
    (4) только Ф2
    (5) Ф2 и Ф3
    (6) ни одна
    Определите все базы следующего ориентированного графа G: files
    (1) {a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}
    (2) {g, k, m, f}, {g, k, n, f}
    (3) {g, m, n, f}
    (4) {g, m, f}, {g, n, f}
    (5) {g, m, e, f}, {g, n, e, f}
    Пусть корень ориентированного дерева T имеет 4-х сыновей, а каждая из остальных внутренних вершин имеет два или три сына, при этом число вершин с 2-я сыновьями вдвое превосходит число вершин с 3-я. Сколько всего вершин в T, если известно, что число его листьев равно 36?
    (1) 48
    (2) 54
    (3) 58
    (4) 61
    (5) 74
    Построить для заданного нагруженного неориентированного графа 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 ). Каков вес этого остова?
    (1) 36
    (2) 38
    (3) 42
    (4) 44
    (5) 48
    Пусть X ={a, b, c} – множество из трех элементов. Число бинарных операций, которые можно определить на X равно:
    (1) 33
    (2) 32
    (3) 38
    (4) 29
    (5) 23
    Построить таблицу для функции, заданной формулой math и определить число наборов аргументов, на которых она равна 1.
    (1) 2
    (2) 3
    (3) 4
    (4) 5
    (5) 6
    (6) 7
    Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1100 0111). Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?
    (1) (¬X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬ Z) ∧ (¬ X ∨ ¬Y ∨ Z)
    (2) (X ∨ ¬Y) ∧ (¬X ∨ Y ∨ Z)
    (3) (¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ ¬Z) ∧ (X ∨ Y ∨ Z)
    (4) (¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)
    (5) (¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z)
    Какие из следующих формул задают несамодвойственные функции: A= X ∨ (¬ Y ∧ Z), B = (¬ X ∧ Y) ∨ (Z ∧ ¬(X+Y)), C= (X ∧ ¬Z) ∨ (Y ∧ ¬Z) ∨ ( X ∧ Y)
    (1) только A
    (2) только B
    (3) A и B
    (4) A и C
    (5) B и C
    (6) все
    Пусть задана система 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
    •
    (1) только A
    (2) только B
    (3) только C
    (4) A и B
    (5) A и C
    (6) все
    Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). \begin{array}{llllllllll} (\forall x(P(x,y) & \rightarrow & \exists y(\forall z(Q(x,y,z) &\rightarrow & P(x,z)) &\rightarrow & P(z,y))) & \rightarrow & Q(x,y,z)) \\ \phantom{ (\forall x(P(}1\phantom{,}2 & & \phantom{\exists y(\forall z(Q(}3\phantom{,y,}4 & & \phantom{P(x,}5 & & \phantom{P(}6\phantom{,} 7& & \phantom{Q(}8\phantom{,}9\end{array}
    (1) F={2,3,5,6,9} C= {1, 4,7,8}
    (2) F={1,5,8,9} C= {2, 4,6,7}
    (3) F={2,6,8,9} C= {1,3,4,5,7}
    (4) F={2,5,7,8,9} C= {1,4,6}
    (5) F={2,6,8,9} C= {1,4,5,7}
    Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами 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)
    •
    (1) только 1
    (2) 1 и 2
    (3) 1 и 3
    (4) только 2
    (5) 2 и 3
    (6) ни одно
    Сколько нулей в матрице смежности ориентированного графа 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)}.
    (1) 5
    (2) 7
    (3) 9
    (4) 11
    (5) 16
    Сколько чисел в первой сотне не делится ни на одно из чисел 2, 3, 7?
    (1) 20
    (2) 33
    (3) 22
    (4) 16
    (5) 28