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

Заказать решение
Количество вопросов 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).Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?

    перейти к ответу ->>