Ответы к тесту/контрольной: Основы дискретной математики

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

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

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

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

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

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

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

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

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

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

Укажите, какие из указанных ниже формул соответствуют следующему SQL-запросу к рассмотренной в данной главе базе данных с отношениями Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты (Номер- Сотрудника, Этаж, НомерКомнаты) и Оборудование(Этаж, НомерКомнаты, Название) (в формулах имена отношений сокращены до их первых букв)? Ответом на запрос является список сотрудников торгового отдела, получающих зарплату от 6001 до 9999 и работающих не на 3-ем этажеSELECT ФИО, Этаж, ОкладFROM Сотрудники, КомнатыWHERE (Номер = НомерСотрудника) AND NOT (Этаж = 3) AND (Отдел ="торговый" ) AND (Оклад > 6000) AND (Оклад < 10000) F1(f, e, z) = ∃n∃d∃z∃k( C(n, f, "торговый", d, z) ∧ K(n, e, k) ∧ (z > 6000) ∧ (z < 10000) ∧¬(e=3)) F2(f, e, z) = ∃n∃d∃z∃e (((z > 6000) ∧ (z < 10000) ∧¬(e=3)) →​ ( C(n, f, "торговый", d, z) ∧ ∃k K(n, e, k)))F3(f, e, z) = ∃n∃f∃d∃z (( C(n, f, o, d, z) ∧ (o ="торговый")) ∧ ∃e∃k K((n, e, k))) →​ ((z > 6000) ∧ (z < 10000) ∧¬(e=3)))

Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей:R ={(a, 5, 8), (a, 6, 4), (a1, 3, 12), (a1, 3, 3)},S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебрыQ = πAD(πAB(R) >< σ C > 2 (S)и какая из указанных формул Fj (j=1,2) ему эквивалентна?Q1 ={(a,d), (a,d1), (a1,d1) } F1= ∃b ∃c (R(a, b, c) ∧ S(b, c, d) ∧ (c > 2))Q2 ={(a,d1), (a1,d2) } F2= ∃b ∃c1 ((∃c R(a, b, c) ∧ (c1 >2) ∧ S(b, c1, d))Q3 ={(a,d), (a,d1), (a1,d2) }

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

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

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

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

Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).В точности две переменных из p1, p2, p3, p4истинны (равны 1).Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).

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

В кондитерском магазине продаются 4 сорта пирожных: заварные,песочные, "картошка" и бисквитные. Сколькими способами можно купить 7 пирожных?

Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат R = {(a,b),(b,c), (b,e), (c, b), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = ?∃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)))

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть задана система 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

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

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

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

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

Детектив Ш. Холмс подозревает в совершении преступлениятрех лиц: Джонса, Брауна и Карта. Они дали следующие показания:Джонс: если Браун преступник, то Карт не виновен.Браун: если Джонс виновен, то и Карт является преступником.Карт: Джонс преступник.Ш. Холмс установил, что если Джонс сказал правду, то Браун соврал, и что показаниям Карта нельзя доверять.Какие из следующих выводов он может сделать из установленных фактов:Джонс является преступником.Браун является преступником.Карт является преступником.Преступников могло быть двое.

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

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

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

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

Сколько нулей в матрице смежности ориентированного графа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)}.

Какие из следующих равенств выражений реляционной алгебры верны для любых отношений со схемами R(A,B,C) и S(A,B,C)?πB(σA>a (R)) = σA>a (πB(R)),σA=a (σB >b(R ∩ S)) = σ B >b (σA=a (R)∩ σA=a(S)),πBC(R - S) = πBC(R) - πBC (S)

Пусть в сигнатуру системы, описывающей результаты экзаменоввходит предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?∃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)) ))

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

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

Используя алгоритм ЗАМЫКАНИЕ(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.

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

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

Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции 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

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

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

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

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

На множестве всех непустых отрезков числовой прямой определены три отношения: R = { ([a, b], [c, d]) | a< c < d < b}, P = { ([a, b], [c, d]) | c