💯 Дискретная математика [9 тем] (ответы на тест Синергия / МОИ / МТИ / МосАП, декабрь 2023) (Решение → 92804)

Дискретная математика > Дискретная математика

• правильные ответы на вопросы из теста по данной дисциплине
• вопросы отсортированы в лексикографическом порядке

1. Важно!. Информация по изучению курса
2. Тема 1. Множества
3. Тема 2. Отношения на множествах
4. Тема 3. Алгебра высказываний
5. Тема 4. Нормальные формы формул алгебры высказываний
6. Тема 5. Исчисление высказываний
7. Тема 6. Алгебра предикатов
8. Тема 7. Графы
9. Тема 8. Деревья
10. Тема 9. Экстремальные задачи на графах

– множество натуральных чисел. Определить истинное высказывание: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

– множество натуральных чисел. Равносильны ли предикаты ? @ @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• нет;
• да.

@

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• y;
• x;
• @

Будет ли пустое множество каким-либо подмножеством некоторого множества? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• будет собственным подмножеством;
• будет несобственным подмножеством;
• не будет никаким подмножеством.

В каком порядке нужно производить операции, преобразовывая формулу S = A ⋂ B ⋃ C ⋂ B' ⋃ A?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• (A ⋂ (B ⋃ C) ⋂ B') ⋃ A;
• (A ⋂ B) ⋃ (C ⋂ (B' ⋃ A));
• (A ⋂ B) ⋃ (C ⋂ B') ⋃ A.

Взаимнооднозначное соответствие между множеством A={1,6,11,16,...} и натуральным рядом устанавливается формулой?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 5k − 4, где (k ∈ N);
• 5k + 1, где (k ∈ N);
• 4k − 5, где (k ∈ N).

Взаимнооднозначное соответствие между множеством A={1,6,11,16,...} и натуральным рядом устанавливается формулой?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 5k − 4, где (k ∈ N);
• 5k + 1, где (k ∈ N);
• 4k − 5, где (k ∈ N).

Взаимнооднозначное соответствие между множеством A={7,10,13,16,19,...} и натуральным рядом устанавливается формулой?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @ 1

Выделим в бесконечном несчетном множестве M счетное подмножество . В каком отношении находятся мощности множеств M\A и M? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• мощность множества M меньше мощности множества M\A ;
• мощность множества M больше мощности множества M\A ;
• мощность множества M равна мощности множества M\A ;

Выразите дизъюнкцию A ⋃ B через импликацию и отрицание:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• (A ⟶ B)'
• A ⟶ B'
• A' ⟶ B

Выразите конъюнкцию A^B через импликацию и отрицание:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

Высказывание является: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• тождественно истинным;
• тождественно ложным;
• переменным.

Высказывание является: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• тождественно истинным;
• тождественно ложным;
• переменным.

Высказывание является: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• тождественно истинным;
• тождественно ложным;
• переменным.

Высказывание: "Если а - четное число, b – нечетное число, то их произведение делится на 2" в символической форме имеет вид

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

Высказывание: "Если а – нечетное число, b – четное число, то их произведение делится на 2" в символической форме имеет вид:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• A ∨ B' ⟶ C;
• A ⟶ B' ∧ С;
• A' ∧ B ⟶ C.

Вытекает ли из равенства A\B=C, что ? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• в общем случае неверно, но в частном случае возможно.

Граф G получен из графов G1 и G2 путем операции: ?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• пересечение;
• объединение;
• декартово произведение.

Графы G1 и G2 заданы матрицами смежности A1 и A2 соответственно. С помощью какой операции был получен граф G , заданный матрицей A ? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• пересечение;
• объединение;
• декартово произведение.

Даны два высказывания S1 : "Если треугольники равны, то равны их стороны", S2 : "Стороны треугольников равны тогда и только тогда, когда равны треугольники". Существует ли отношение следствия между S1 и S2?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• из S1 следует S2;
• из S2 следует S1;
• ни одно из высказываний не следует из другого.

Для предиката заданного на множестве действительных чисел, укажите набор значений кванторов : @ @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 0,0
• 0,1
• 1,1
• 1,0

Для предиката P(x,y)=(x+y)=0 , заданного на множестве действительных чисел, укажите набор значений кванторов : @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 0,0
• 0,1
• 1,1
• 1,0

Для сетевого графа, соответствующего некоторому проекту, критический путь представляет собой:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• путь минимальной длины от входа к выходу;
• путь максимальной длины от входа к выходу;
• путь произвольной длины от входа к выходу.

Если высказывания эквивалентны, существуют ли между ними отношения следствия?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• существуют;
• не существуют;
• могут существовать, а могут и не существовать.

Если к некоторому бесконечному множеству M прибавить счетное множество A, то в каком соотношении будут находиться мощности множеств M ∪ A и M?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• мощность множества M меньше мощности множества M ∪ A;
• мощность множества M больше мощности множества M ∪ A;
• мощность множества M равна мощности множества M ∪ A;

Если матрица смежности симметрична, то граф является:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• ориентированным с нечетным числом дуг;
• неориентированным;
• ориентированным с петлями.

Если отношение A на множестве M рефлексивно, симметрично и транзитивно, можно ли разбить множество M на непересекающиеся классы?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• можно, но не всегда.

Если при проверке правильности рассуждения получен результат , где P – конъюнкция посылок, Q – заключение, то, в таком случае, данное рассуждение является: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• правильным;
• неправильным;
• может быть правильным, а может быть и неправильным.

Если СДНФ формулы S(X1,X2,X3) содержит 3 слагаемых, сколько сомножителей содержит ее СКНФ?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 3
• 4
• 5

Какие из высказываний состоящих из двух элементарных высказываний A и B , равносильны? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• S1=S2
• S1=S3
• S2=S3

Какие из пар связок образуют полную систему связок?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• (∨, ￣);
• (∨, ⟶);
• (∧, ⟶).

Какие переменные в предикате являются свободными? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• x₁, x₂, x₃, x₄, x₅;
• x₂, x₅;
• x₁, x₃, x₄.

Каково значение X, определяемое уравнением @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

Какое свойство не является свойством дерева?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• граф связен и все его ребра являются перешейками;
• всякая пара вершин графа соединена только одной цепью;
• граф связен и содержит циклы.

Какой граф называется сетью?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• неориентированный граф с одним входом;
• ориентированный граф с циклами;
• несвязный граф, компонентами связности которого являются деревья;
• ориентированный граф без циклов с одним входом и одним выходом.

Какой граф обладает эйлеровым циклом: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• G1
• G2
• G3
• G4

Какой граф содержит эйлерову цепь, соединяющую две различные вершины: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• G1
• G2
• G3
• G4

Какой из данных графов правильно пронумерован? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• G1
• G2
• G3

Какой из данных графов является планарным? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• G1
• G2
• G3

Какой из данных графов является сетью? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• G1
• G2
• G3

Логической функции , соответствует формула алгебры высказываний: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

Минимальная полная система логических связок содержит:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• одну связку;
• две связки;
• три связки;
• четыре связки.

Минимальная полная система логических связок содержит:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• одну связку;
• две связки;
• три связки;
• четыре связки.

Могут ли быть при правильном рассуждении все посылки истинными, если заключение ложно?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• иногда да, иногда нет.

Могут ли две релейно-контактные схемы, соответствующие одной и той же функции проводимости, иметь различное число реле?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• никогда не могут.

Можно ли в любом бесконечном множестве выделить счетное подмножество?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• нельзя;
• можно;
• можно, но не всегда.

Можно ли для функции F(S1,S2,S3) заданной так, что на всех наборах значений переменных S1,S2,S3 она принимает значение 0, построить какую-либо совершенную нормальную форму?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• можно СДНФ;
• можно СКНФ;
• нельзя построить ни одной совершенной нормальной формы.

Мощность какого множества больше X или Y, если X – исходное конечное множество, Y – множество подмножеств множества X?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• мощность X больше мощности Y;
• мощность X меньше мощности Y;
• мощность X равна мощности Y.

На множестве всех треугольников на плоскости рассматривается отношение подобия. Данное отношение является отношением:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• толерантности;
• порядка;
• эквивалентности.

Обладает ли эйлеровым циклом полный неориентированный граф с числом вершин n=4?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• зависит от числа дуг.

Обладает ли эйлеровым циклом полный неориентированный граф с числом вершин n=5?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• зависит от числа дуг.

Определите значение следующего выражения на множестве действительных @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 0
• 1
• 1 < x < 2.

Определите значение следующего выражения ∀x((x² > x) ⟷ ((x > 1) ∨ (x < 0)) на множестве действительных

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 0
• 1
• x > 1

Определите минимальное число ребер, которое нужно удалить, чтобы граф стал древом: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 5
• 1
• 4

Определите фиктивные переменные логической функции : @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• x
• y
• z

Определите, каким отношением следования связаны предикаты на множестве действительных чисел: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Q(x) ⟶ P(x);
• P(x) ⟶ Q(x);
• не связаны.

Определить форму следующей формулы : @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• КНФ;
• ДНФ;
• не ДНФ и не КНФ.

Определить форму следующей формулы XY ∨ XY' ∨ X'YZ:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• СКНФ;
• СДНФ;
• не СДНФ и не СКНФ.

Определить форму следующей формулы XYZ ∨ X'YZ ∨ XY'Z':

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• СКНФ;
• СДНФ;
• не СДНФ и не СКНФ.

Отношение , заданное на множестве действительных чисел является отношением: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• толерантности;
• порядка;
• эквивалентности.

Отношение "быть старше": "х старше у" является:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• рефлексивным;
• симметричным;
• транзитивным.

Отношение "х - победитель у" является:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• антирефлексивным;
• симметричным;
• транзитивным.

Почему множество действительных чисел и множество натуральных чисел не являются эквивалентными?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• множество натуральных чисел неупорядочено;
• множество действительных чисел неупорядочено;
• не существует биективного отображения между этими множествами.

Пусть тогда: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• К=2;
• К=1;
• К=0.

Пусть тогда: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• К=-1;
• К=1;
• К=0.

Пусть n(A ⋃ B) – мощность множества, являющегося объединением конечных множеств A и B, m₁ = n(A ⋃ B), если множества пересекаются, n(A ⋂ B) > 0 и m₂ = n(A ⋃ B), если n(A ⋃ B) = 0. Как соотносятся m₁ и m₂?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• m₁ = m₂
• m₁ > m₂
• m₁ < m₂

Пусть N₂ и N₃ – множество натуральных чисел, кратных 2 и 3 соответственно. Если n=1,2..., то множество ?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• (6n);
• (6n)';
• (6n±1);
• ( 6n±2).

Результат дизъюнкции предикатов P(X)=(X 2) и Q(X)=(X 2) на множестве действительных чисел:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 0
• 1
• 1 при x ≠ 2.

Результат конъюнкции предикатов на множестве действительных чисел: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 0
• 1
• x=2

Релейно-контактной схеме соответствует формула алгебры высказываний: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

Сколько вершин имеет дерево, содержащее N ребер?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• N-1
• n²;
• N+1
• N

Сколько несобственных подмножеств имеет конечное множество, состоящее из n элементов?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 1;
• 2;
• n.

Сколько сомножителей содержит СКНФ, построенная по функции ? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 2;
• 6;
• 8.

Содержит ли конечное множество A собственное подмножество, эквивалентное всему множеству A?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• всегда содержит;
• никогда не содержит;
• иногда содержит, иногда нет.

Соответствуют ли различные релейно-контактные схемы одному и тому же высказыванию?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• всегда;
• никогда;
• могут соответствовать, могут не соответствовать.

Существует ли СДНФ у невыполнимой формулы?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет;
• иногда существует, а иногда нет.

Требуется соединить шесть городов газопроводом. Возможные соединения и стоимость строительства указана на графе. Как соединить шесть городов, чтобы построить самый дешевый газопровод? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• @
• @
• @

Чему равен путь максимальной длины от входа к выходу?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 11
• 20
• 9

Чему равен путь минимальной длины от входа к выходу? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 6
• 7
• 8

Чему равно цикломатическое число графа? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 1
• 4
• 5
• 6

Чему равно число внутренней устойчивости графа? @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 4
• 6
• 2
• 1

Через какие вершины проходит путь минимальной длины от входа к выходу: @

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• a-b-d-c-e-f;
• a-b-e-f;
• a-c-e-f.

Является ли высказывание «Солнце встает на западе» предикатом?:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• да;
• нет.

x ⋃ x'y =

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• y;
• x;
• x ⋃ y