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

Количество вопросов - 189

Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?

Какие из следующих формул задают немонотонные функции:A= X*Z+ Y*Z+X*Y*Z, B = ¬ X →​( Y∧ ¬Z), C= (X →​¬Z) →​ ( X ∧ Y)

Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0011 1011).

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

Пусть 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) )
  • Предположим, что 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)?

    Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (¬x+y) →​ (y ∧ z)

    Пусть X ={a, b, c} – множество из трех элементов. Число трехместных отношений, которые можно определить на X равно:

    Пусть задан неориентированный нагруженный граф 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)

    Сколько вершин в полном бинарном дереве высоты 4?

    Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1101 1100).Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?

    Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
    La: d, c, b           Lb: a                   Lc: i, hLd: a, e, f           Le: d, g, f             Lf: d, e, gLg: e, f              Lh: c, i                Li: c, h
    Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?

    Чему равно число связных компонент неориентированного графа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)}?

    Используя алгоритм БыстроеЗамыкание, вычислить замыканиедля набора исходных продуктов 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.

    Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1:A= (X→​ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) →​ (Z→​X), C= (X∨Y) →​¬Z

    Какими свойствами обладает бинарное отношение R над {a,b,c} заданное как R = { (a,a), (a,b), (b,a),(b,b), (c,c)}?

    Какие из следующих формул являются тождественно истинными?
  • A = ((X \to Y) \to ((X \to\lnot Z) \to (Y \to \lnot Z))),
  • B = ((\lnot X \to \lnot Y) \to ((\lnot X \to (\lnot Y \to Z)) \to (\lnot X \to Z))),
  • C= ((\lnot X \to Y) \to ((Y \to Z) \to (\lnot X \to Z))),
  • D = ((X \to Y) \to ((\lnot Y \to \lnot Z) \to (\lnot X \to \lnot Z)))
  • Пусть множество 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?

    Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки и (без отрицания ¬)?
  • По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
  • Не все из переменных из p1, p2, p3, p4ложны (равны 0).
  • Нечетное число переменных из p1, p2, p3, p4истинны (равны 1).
  • Пусть заданы три множества: A ={ a, b, {∅}, {a,c,d}}, B={a, c, e, {a}, {b}} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) \ C?

    Пусть корень ориентированного дерева T имеет 7 сыновей, а каждая из остальных внутренних вершин имеет три или три четыре сына, при этом число вершин с 3-я сыновьями втрое больше числа вершин с 4-я. Сколько всего вершин в T, если известно, что число его листьев равно 52?

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в обратном (суффиксном) порядке?

    Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 22 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 5 анекдотов и не повторять никакие два года подряд одни и те же пять анекдотов. Каково минимальное число анекдотов, которые он должен приготовить?

    Пусть база данных включает отношение Оборудование(Этаж, Комната, Название, Стоимость). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Этаж и НомерКомнаты образуют ключ отношения.
  • Ф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))
  • Укажите, какие из указанных ниже формул соответствуют следующему 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="компьютер"))
  • В кондитерском магазине продаются 4 сорта пирожных: заварные,песочные, "картошка'' и бисквитные. Сколькими способами можно купить 6 пирожных?

    Пусть отношения 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) }

    Пусть граф 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|.

    Какие из следующих равенств справедливы для всех множеств A и B?
  • (а) (A ∩ B) = A \ (A \ B)
  • (б) A ∩ (B \ A) = ∅
  • (в) (A \ B) ∪ B = A
  • Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?
  • А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.
  • Б) Число этапов (итераций основного цикла) не превосходит (n - 1).
  • В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
  • Пусть задан неориентированный граф 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) }.Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

    Пусть множество 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?

    Пусть заданы три множества: A={ a, b, c,{∅}, {a}}, B={a, e, {a}, {b},∅} и C = {a, b, d, {e}, {∅}}. Какова мощность множества D = (A \ B) ∩ C?

    Пусть заданы множества A = {0, 1, 2}, B = {1, 2, 3}, C = {a, b, c} и D = {a, d, e}. Чему равно множество F = (A ∩ B) × (C \ D)?

    Какие из следующих равенств справедливы для всех множеств A, B и C?

    Пусть бинарное отношение R над {a,b,c} задано как R = {(a,a), (a,с), (c, b), (a, b)}Какие из следующих свойств:
  • Симметричность
  • Антисимметричность
  • Рефлексивность
  • Транзитивность
  • для него выполняются?

    На множестве всех непустых отрезков числовой прямой определены три отношения: 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}. Какие из них являются отношениями частичного порядка?

    Пусть X ={a, b, c} – множество из трех элементов. Число трехместных функций f: X3 →​ X, которые можно определить на X равно:

    Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 4 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?

    Преподаватель рассчитывает читать один и тот же курс дискретной математики в течение 16 лет. Чтобы не наскучить студентам, он решил рассказывать им каждый год 4 анекдота и не повторять никакие два года одни и те же четыре анекдота. Каково минимальное число анекдотов, которые он должен приготовить?

    В первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебряных и бронзовых медалей, а также три команды, покидающие премьер-лигу (т.е. занявшие три последних места). Найдите число не совпадающих в главном возможных исходов первенства.

    При игре в преферанс колоду из 32 карт раздают трем игрокам – каждому по 10 карт, а оставшиеся 2 карты оставляют в прикупе. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).

    Сколько чисел в первой сотне не делится ни на одно из чисел 2, 3, 7?

    Построить таблицу для функции, заданной формулой
    ((\lnot A + (\lnot B \wedge C)) \to ( A \vee \lnot B))
    и определить число наборов аргументов, на которых она равна 1.

    Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9. Какие из булевых формул задают множество всех ошибочных кодов?

    Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 2, 3или 5. Какая из следующих формул задает эту функцию?

    Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки и (без отрицания ¬)?
  • По крайней мере три переменных из p1, p2, p3, p4истинны (равны 1).
  • В точности три переменных из p1, p2, p3, p4истинны (равны 1).
  • Четное число переменных из p1, p2, p3, p4истинны (равны 1).
  • Детектив Ш. Холмс подозревает в совершении преступлениятрех лиц: Джонса, Брауна и Карта. Он установил, что
  • если Джонс не преступник, то Браун является преступником ;
  • кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
  • Браун и Карт вместе не совершали преступление.
  • Какие из следующих выводов он может сделать из установленных фактов:
  • Джонс является преступником.
  • Браун является преступником.
  • Карт является преступником.
  • Преступник действовал в одиночку.
  • Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1100 0111).Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?

    Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (x ∨ y) →​ (x ∧¬y ∧ z)

    Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1011 1010).

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

    Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле((¬ X ∧ ¬ Y) →​ (¬ Z ∨ (¬ X →​ ( Y ∧ Z)) ))

    Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0001 0111).

    Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле (¬( ( X→​Y) ∨ ¬(Y →​ X)) ∧ Z)и укажите, сколько в нем слагаемых.

    Какие из следующих формул задают несамодвойственные функции:A= (Y ∧¬ Z) ∨ (X ∧ ¬Z) ∨( X ∧ Y), B =(¬ X∧ (Y|Z)) ∨(¬ Y ∧¬ Z) , C= Z ∨(Y ∧¬ X)

    Какие из следующих формул задают немонотонные функции:A= (Y →​¬X) →​ ( Y ∧ Z), B = (¬ X →​( Y∧ ¬Z)) →​Y, C= ¬ Z →​( Y∧ ¬X)

    Какие из следующих формул задают нелинейные функции:A= (X∧ Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) →​ Z, C= ¬Z∨ X∨Y

    Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически).F={ (1001 0110), (0111 1100), (0001 0011) }, G={ (1111 1111), (0101 0101), (0000 0011) }, H= { (0011 0111), (0110 1000), (1111 0000) }.

    Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом?F: f = X ∧ Y∧ ¬ Z, g = X ∨ Y , h = X+Y+1

    Пусть задана система 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
  • Используя алгоритм ЗАМЫКАНИЕ(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.
  • Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов 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)

    Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (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}

    Предположим, что 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)?

    Какие из следующих формул логики предикатов являются тождественно истинными?
  • ( ∀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) )
  • Пусть на множестве 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)))
  • Пусть в сигнатуру системы, описывающей результаты экзаменоввходит предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения"Все студенты, успешно сдавшие алгебру, успешно сдали дискретную математику или информатику".
  • ∀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, инф, неуд)))
  • Пусть 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) )
  • Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
  • σA=aAB(R) >< πBC (S)) = σA=a BA(R)) >< πBC (S),
  • πBC(R ∩ S) = πBC(R) ∩ πBC (S)
  • σA=aB >b(R - S)) = σ B >bA=a (R) - σA=a(S))
  • Пусть отношения 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) }

    Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры 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, 'компьютер')))
  • Укажите, какие из указанных ниже формул соответствуют следующему 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 = ∀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 = ∀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)))
  • Сколько нулей в матрице смежности ориентированного графа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)}.

    Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 8-вершинном графе?

    Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?
  • В G есть вершина, в которую не входят ребра.
  • В G есть вершина, из которой не выходят ребра.
  • В G есть изолированная вершина, т.е. вершина, у которой нет инцидентных ребер.
  • Пусть граф 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|.

    Чему равно число связных компонент неориентированного графа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)}?

    Определите все базы следующего ориентированного графа G:

    Сколько вершин в полном бинарном дереве высоты 6?

    Какое выражение представляет ориентированное дерево?

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в обратном (суффиксном) порядке?

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в прямом (префиксном) порядке?

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в инфиксном порядке?

    Построить для заданного нагруженного неориентированного графа 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 ).Каков вес этого остова?

    Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
    La: c, d, b           Lb: a, f, g             Lc: a, d, eLd: a, c, e           Le: c, d                Lf: bLg: 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) }.Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

    Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?

    Какие из следующих утверждений о работе алгоритма Дейкстры верны?
  • А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не убывают.
  • Б) В дереве кратчайших путей, построенном алгоритмом Дейкстры, длины ребер на каждой ветви не убывают.
  • В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.
  • Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
  • σA=aB >b(R- S)) = σ B >bA=a (R-S)),
  • πBAA=a (R)) = σA=a BA(R)),
  • πBC(R ∩ S) = πBC(R) ∩ πBC (S)
  • Какие из следующих формул задают несамодвойственные функции:A= X ∨ (¬ Y ∧ Z), B = (¬ X ∧ Y) ∨ (Z ∧ ¬(X+Y)), C= (X ∧ ¬Z) ∨ (Y ∧ ¬Z) ∨ ( X ∧ Y)

    Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом?F: f = X ∨ Y , g = X →​ ¬ Y , h = X+Y

    Пусть X ={a, b, c} – множество из трех элементов. Число бинарных операций, которые можно определить на X равно:

    Какие из следующих формул задают нелинейные функции:A= (Y →​X) ∧ Z, B = (X∧ Y) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= (¬ Z→​ X) ∨¬ Y

    Построить для заданного нагруженного неориентированного графа 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 ).Каков вес этого остова?

    Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 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 ))
  • Используя алгоритм БыстроеЗамыкание, вычислить замыканиедля набора исходных продуктов 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.

    Пусть 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) )
  • Пусть на множестве 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)))
  • В кондитерском магазине продаются 5 сортов пирожных: заварные,песочные, "картошка", корзинка и бисквитные. Сколькими способами можно купить 6 пирожных?

    При игре в бридж колоду из 52 карт раздают 4 игрокам – каждому по 13 карт. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).

    Какие из следующих формул логики предикатов являются тождественно истинными?
  • ( ∀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) )
  • Определите все базы следующего ориентированного графа G:

    Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом?F: f = X ∨ Y, g = X →​ Y , h = X+Y

    На множестве всех непустых отрезков числовой прямой определены три отношения: 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}Какие из них являются отношениями частичного порядка.

    Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (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}

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в инфиксном порядке?

    Построить таблицу для функции, заданной формулой
    ((A \to (\lnot B \wedge C)) + (\lnot A | \lnot B))
    и определить число наборов аргументов, на которых она равна 1.

    Пусть задан неориентированный граф 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) }.Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

    Сколько нулей в матрице смежности ориентированного графаG= (V, E), где V={a, b, c, d}, E={ (a,b), (a,d), (b,a), (b,b), (c, a), (c,d), (d,b)}.

    Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?
  • Сумма степеней всех вершин G четна.
  • Если в G имеется ровно две вершины четной степени, то они связаны путем
  • Если в G имеется ровно две вершины нечетной степени, то они связаны путем
  • Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1:A= (X→​ ¬Y ) ∨ (¬ X∧ ¬ Z ), B = (¬X∨ Z) →​ ¬Y, C= (Y + ¬X) →​ (Z→​ ¬Y ),

    Пусть задана система 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
  • Используя алгоритм ЗАМЫКАНИЕ(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 = ∀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)))
  • Сколько вершин в полном бинарном дереве высоты 5?

    Пусть заданы множества A = {0, 1, 2}, B = {2, 3}, C = {a, b, c} и D = {a, c, e}. Чему равно множество F = (A \ B) × (C ∩ D)?

    На множестве всех непустых отрезков числовой прямой определены три отношения: 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}Какие из них являются отношениями частичного порядка.

    Фотограф хочет для групповой фотографии расположить в одну шеренгу 4 юноши и 2 девушки так, чтобы две девушки не стояли рядом. Сколькими способами он может это сделать?

    В стране N в первенстве премьер-лиги по футболу участвуют 16 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебрянных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места).Найдите число не совпадающих в главном возможных исходов первенства.

    Построить таблицу для функции, заданной формулой
    ((\lnot A \to (\lnot B \wedge C)) + (\lnot A \downarrow \lnot B))
    и определить число наборов аргументов, на которых она равна 1.

    Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9 (коды начинаются с 4-ой строки). Какие из булевых формул задают множество всех ошибочных кодов?

    Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 1, 4, 5или 6. Какая из следующих формул задает эту функцию?

    Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле¬ (X →​ ( ¬Y →​ (X ∧ ¬ Z))) ∧ (Z ∨ ¬ (X ∧ 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

    Какие из следующих формул задают немонотонные функции:A= (Y →​¬X) →​ ( Y ∧ Z), B = ((¬ X∧ Z) →​( Y∧ ¬Z)) ∧ Y, C= X +Y + Y*Z +X*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 }.

    Используя алгоритм ЗАМЫКАНИЕ(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.
  • Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов 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)

    Предположим, что 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)?

    Пусть в сигнатуру системы, описывающей результаты экзаменоввходит предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?
  • ∃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)) ))
  • Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?
  • πBA>a (R)) = σA>a B(R)),
  • σA=aB >b(R ∩ S)) = σ B >bA=a (R)∩ σA=a(S)),
  • πBC(R - S) = πBC(R) - πBC (S)
  • Сколько нулей в матрице смежности ориентированного графа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)}.

    Пусть G=( V, E) - это конечный неориентированный граф. Какие из следующих утверждений верны?
  • Если |E| < |V| - 1, то .граф G не является связным.
  • Если |E| > |V| - 1, то в G имеется цикл.
  • Если в G имеется цикл, то |E| > |V| - 1
  • Пусть граф 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|.

    Какое выражение представляет ориентированное дерево?

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в обратном (суффиксном) порядке?

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в прямом (префиксном) порядке?

    Пусть задан неориентированный нагруженный граф 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)

    Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
    La: b, c, d, g           Lb: a, f, d             Lc: a, d, eLd: a, b, c, e           Le: c, d, f             Lf: b, eLg: a, i, h              Lh: g, i                Li: g, h
    Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?

    Сколько чисел в первой сотне не делится ни на одно из чисел 2, 5, 7?

    Пусть заданы три множества: A={ a, {∅}, {a,c,d}},B={a, c, e, {a}, {b},∅} и C = {a, b, c, d, {e}, ∅}. Какова мощность множества D = (A ∪ B) ∩ C?

    Пусть корень ориентированного дерева T имеет 4-х сыновей, а каждая из остальных внутренних вершин имеет два или три сына, при этом число вершин с 2-я сыновьями вдвое превосходит число вершин с 3-я. Сколько всего вершин в T, если известно, что число его листьев равно 36?

    Детектив Ш. Холмс подозревает в совершении преступлениятрех лиц: Джонса, Брауна и Карта. Они дали следующие показания:
  • Джонс: если Браун преступник, то Карт не виновен.
  • Браун: если Джонс виновен, то и Карт является преступником.
  • Карт: Джонс преступник.
  • Ш. Холмс установил, что если Джонс сказал правду, то Браун соврал, и что показаниям Карта нельзя доверять.Какие из следующих выводов он может сделать из установленных фактов:
  • Джонс является преступником.
  • Браун является преступником.
  • Карт является преступником.
  • Преступников могло быть двое.
  • Пусть база данных включает три отношения, рассмотренных в лекции: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название). Какое из следующих выражений реляционной алгебры 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)))
  • Какие из следующих формул являются тождественно истинными?
  • A = ((\lnot X \to \lnot Y) \to ((\lnot X \toY) \to \lnot X))),
  • B = ((\lnot X \to \lnot Y) \to ((\lnot X \to (\lnot Y \to Z)) \to (\lnot X \to Z))),
  • C= ((\lnot X \to Y) \to ((Y \to \lnot Z) \to (\lnot X \to \lnot Z))),
  • D = ((X \to Y) \to ((\lnot Y \to \lnot Z) \to (\lnot X \to \lnot Z)))
  • При игре в "дурака" колоду из 36 карт раздают четырем игрокам – каждому по 6 карт, а оставшиеся 12 карт и оставляют в прикупе в фиксированном порядке. Далее в процессе игры карты из прикупа замещают в указанном порядке карты, выбывшие из игры, поэтому их порядок существенен. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).

    Какие из следующих формул задают нелинейные функции:A= (Y →​¬X) →​ Z, B = (X∧ Y∧ Z) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= ( Z→​ X) ∨Y

    Какое выражение представляет ориентированное дерево?

    Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?

    Пусть задана система 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
  • Пусть бинарное отношение R над {a,b,c} задано как R = { (a,a), (a,с), (c, b), (a, b), (b,b), (c,c)}Какие из следующих свойств:
  • Симметричность
  • Антисимметричность
  • Рефлексивность
  • Транзитивность
  • для него выполняются?

    Сколько чисел в первой сотне не делится ни на одно из чисел 3, 5, 7?

    Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1100 1101).

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

    Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((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)

    Каковы будут структуры данных СЧЕТ и СПИСОК после этапа инициализации алгоритма БыстроеЗамыкание для следующей системы технологических процессов 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)

    Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (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}

    Какие из следующих формул логики предикатов являются тождественно истинными?
  • ( ∀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) )
  • Чему равно число связных компонент неориентированного графа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)}?

    Пусть задан неориентированный нагруженный граф 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)

    Какие из следующих утверждений о работе алгоритма Дейкстры верны?
  • А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.
  • Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
  • В) Если длины всех ребер в графе попарно различны, то дерево кратчайших путей из заданной вершины единственно.
  • Определите все базы следующего ориентированного графа G:

    Детектив Ш. Холмс подозревает в совершении преступлениятрех лиц: Джонса, Брауна и Карта. Он установил, что
  • если Браун преступник, то и Карт является преступником ;
  • кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
  • если Карт не преступник, то и Джонс не преступник.
  • Какие из следующих выводов он может сделать из установленных фактов:
  • Джонс является преступником.
  • Браун является преступником.
  • Карт является преступником.
  • Преступник действовал в одиночку.
  • В стране N в первенстве премьер-лиги по футболу участвуют 15 команд. Назовем два возможных исхода этого первенства совпадающими в главном, если в этих исходах совпадают обладатели золотых, серебренных и бронзовых медалей, а также две команды, покидающие премьер-лигу (т.е. занявшие два последних места).Найдите число не совпадающих в главном возможных исходов первенства.

    Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((( Y ∧ Z) →​ ¬ (X ∨ Z)) ∧ ¬ (¬ Y∧ Z∧X))и укажите, сколько в нем слагаемых.

    Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в прямом (префиксном) порядке?

    Пусть на множестве 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)))
  • В кондитерском магазине продаются 4 сорта пирожных: заварные,песочные, "картошка" и бисквитные. Сколькими способами можно купить 7 пирожных?

    Фотограф хочет для групповой фотографии расположить в одну шеренгу 5 юношей и 3 девушки так, чтобы никакие две девушки не стояли рядом. Сколькими способами он может это сделать?

    Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки и (без отрицания ¬)?
  • По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).
  • В точности две переменных из p1, p2, p3, p4истинны (равны 1).
  • Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
  • Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0101).

    Какие из следующих формул задают функции, не сохраняющие 0 и не сохраняющие 1:A= (X→​ ¬Y) ∨ (¬ X∧ ¬Y ), B = (Y ∧ ¬X) →​ (Z→​X), C= ¬Z∨ X∨Y

    Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически).F= { (0111 1100), (1100 1100), (0101 0111) }, G= { (0110 1001), (1110 1000), (0001 0011) }, H= { (1111 0000), (0101 1111)}.

    Используя алгоритм БыстроеЗамыкание, вычислить замыканиедля набора исходных продуктов 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.

    Пусть отношения 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 = πADAB(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) }

    Укажите, какие из указанных ниже формул соответствуют следующему 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)))
  • Построить для заданного нагруженного неориентированного графа 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 ).Каков вес этого остова?

    Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?

    Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле((X ∧ Y) →​ ¬ Z) ∧ (¬ X →​ ¬ Y)

    Какие из следующих равенств справедливы для всех множеств A, B и C?
  • (а) (A ∩ B) \ C = A ∩ (B \ C)
  • (б) (A ∩ B) ∪ C = A ∩ (B ∪ C)
  • (в) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
  • Пусть база данных включает отношения Сотрудники(ФИО, Отдел, Должность, Оклад) и Комнаты(ФИО_Сотрудника, Этаж, Комната). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: для каждого сотрудника из таблицы Сотрудники в таблице Комнаты определено его место работы.
  • Ф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))
  • Какое из следующих перечислений вершин бинарного дерева T:представляет его обход в инфиксном порядке?

    Какие из следующих формул являются тождественно истинными?
  • A = ((X \to \lnot Y) \to ((\lnot Y \to Z) \to (X \to Z))),
  • B = ((X \to \lnot Y) \to ((X \to Z) \to (\lnot Y \to Z))),
  • C = ((X \to \lnot Y) \to ((X \to (\lnot Y \to Z)) \to (X \to Z))),
  • D = ((\lnot X \to Y) \to ((\lnot Y \to Z) \to (X \to Z)))
  • Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 7-вершинном графе?

    Пусть заданы множества A = {0, 1, 2, 3}, B = {1, 2, 4}, C = {a, b, c} и D = {b, d, e}. Чему равно множество F = (A\ B) × (C \ D)?

    Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: ¬ (¬x →​ (y + z))

    Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1011 0011).Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?