Ответы на вопросы из коллекции "Сборник ответов к экзаменационному тесту Дискретная математика ММА."

Если даны два высказывания - S1 («Если треугольники равны, то равны их стороны») и S2 («Стороны треугольников равны тогда и только тогда, когда равны треугольники»), - то можно утверждать, что …

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

Отношение «х – победитель у» является…

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

Найти веса следующего набора a=(110)ϵB^3

• 8
• 4
• 2

Найти общее решение линейного однородного рекуррентного уравнения
x_n-6x_(n-1)+11x_(n-2)-6x_(n-3)=0

• C_1+C_2 2^(n-1)+C_3 3^n
• C_1+C_2 2^n+C_3 3^(n-1)
• C_1+C_2 2^n+C_3 3^n

Найти общее решение линейного однородного рекуррентного уравнения
x_n-2x_(n-1)=0

• C_1 · 2^n-1
• C_1 · 2^n
• C_1 · 2^n+1

Если из высказывания S1 следует S2 и, наоборот, из S2 следует S1 , то высказывания S1 и S2 … эквивалентными

• могут являться, а могут не являться
• являются
• неопределенный случай
• не являются

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

• нельзя
• можно
• можно, но не всегда
• можно только в том случае, если А - отношение порядка

Пусть A – множество из k элементов. Сколько можно определить различных свойств на множестве A.

• 2^k-1
• 2^k
• 2^k+1

Что означает символ ∀?

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

Какое из следующих утверждений о множествах является верным?

• множество может содержать только числа
• множество не может содержать больше одного элемента
• множество может содержать только буквы
• множество может содержать различные объекты: числа, буквы, символы и прочее

Матрица бинарного отношения R ⊂А2, где А = {1, 2, 3}, заданного на рисунке: имеет вид:

• (1 1 1 0 0 1 1 0 1)
• (1 0 1 0 0 1 1 0 0)
• (1 0 1 0 0 1 1 1 1)
• (1 1 1 0 0 1 1 0 0)

… - это отрасль математики, занимающаяся подсчетом и комбинированием объектов.

К способам задания множества относят:

• описание характеристического свойства
• фигурные скобки
• угловые скобки
• диаграмму Эйлера-Венна

Что такое биекция в теории множеств?

• случайное преобразование элементов множества
• отображение, при котором каждому элементу из множества A соответствуете менее одного элемента из множества B
• взаимно однозначное отображение между элементами А и В
• отображение, при котором каждому элементу из множества A соответствуете более одного элемента из множества B

Какое из утверждений верно для функции инъекции?

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

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

• полуинтервал
• полуотрезок
• луч
• открытый луч

Города A, B, C, D и E попарно соединены дорогой. Сколько разных маршрутов путешествия из города A в город E c посещением ещё двух городов можно составить? Предполагается, что в маршруте каждый город присутствует не более одного раза, и маршруты, отличающиеся порядком следования городов, различны.

• A^2/6 = 12
• A^2/3 = 6
• A^2/4 = 8

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

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

Способы задания графа:

• Геометрический
• Матричный
• Перечисление ребер
• Указание вершин

Какой символ используется для обозначения множества?

• [ ]
• ( )
• < >
• { }

n- местная функция, определенная на произвольном множестве М и принимающая в качестве значений элементы из двухэлементного множества {0, 1}, 0 и 1 интерпретируются как ложь и истина соответственно, называется …

• сюръекция
• предикат
• отображение
• биекция

Какое множество является подмножеством любого другого множества?

• натуральные числа
• пустое множество
• рациональные числа
• положительные числа

Какой из циклов графа с множеством вершин {a,b,c,d,e,f} является гамильтоновым?

• fbecdf
• abeca
• abecdfa
• abcdfca

Множества A, B, C выражены через три других множества D, E, F следующими равенствами (знак пересечения опущен): A = D(E∪F), B = DE∪DF, C = (DE)∩(DF). Отметьте верное равенство:

• A=B
• A=C
• B=C

Способы задания графа:

• Перечисление ребер
• Матричный
• Геометрический
• Указание вершин

Какое из множеств является конечным?

• множество всех рациональных чисел
• действительные числа отрезка [0,1]
• множество всех натуральных чисел
• множество {1,2,3}

Даны множества A = {a,b,d,e,f}, B = {b,c,e,g}, С = {a,d,f}. Отметьте верное равенство:

• С = BA
• С = A∪B
• С = AB
• С = A∩B

Логическое сложение – это:

• Эквиваленция
• Импликация
• Дизъюнкция
• Конъюнкция

Соответствие G между множествами A = {a,b,c,d,e} и B = {1,2,3,4} задано множеством пар G = {(a,2),(a,3),(b,3),(c,1),(e,3),(e,4)}. Какое из множеств является прообразом элемента 3 при этом соответствии?

• {a,c}
• {a,b,e}
• {a,b,c,e}

Эйлеров цикл:

• содержит каждое ребро только один раз
• проходит через все вершины и ребра графа только один раз
• содержит каждую вершину только один раз

Граф содержит 7 дуг. Его эйлеров цикл будет состоять из:

• 7 дуг
• 6 дуг
• 8 дуг
• 5 дуг

Каким может быть дополнение к отношению строгого порядка?

• Симметричным
• Рефлексивным
• Антисимметричным

Соответствие G между множествами A = {a,b,c,d} и B = {1,2,3,4} задано множеством пар G = {(a,1),(b,2),(b,3),(c,1),(d,3)}. Отметьте верное утверждение:

• G функционально
• G сюръективно
• G всюду определено

На множестве A = {a,b,c,d} задано бинарное отношение R = {(a,b),(a,c),(b,c),(c,d)}. Какие пары нужно добавить к R, чтобы получить его транзитивное замыкание?

• (a,d), (b,d)
• (d,a)
• никакие, так как R транзитивно
• (a,d)

Графом называется:

• множество линий, соединяющих некоторые пары точек
• пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек
• пара двух конечных множеств: множество точек и множество линий
• пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек

Последовательность ребер, в которой каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза – это:

• Проекция
• Дорога
• Путь
• Цикл

Формула высказываний – это:

• выражение, составленное из высказывательных переменных
• выражение, составленное из высказывательных переменных с помощью операций над высказываниями и обращающееся в конкретное высказывание при подстановке вместо этих переменных конкретных высказываний
• выражение, обращающееся в конкретное высказывание при подстановке вместо переменных конкретных высказываний
• выражение, составленное из высказывательных переменных, обращающееся в конкретное высказывание при подстановке вместо этих переменных конкретных высказываний

Функция истинности:

• Функция, которая на множестве всех высказываний, каждому высказыванию ставит в соответствие единственное значение 0 или 1
• Функция, которая на множестве всех высказываний, каждому высказыванию ставит в соответствие значения 0 и 1
• Функция, принимающая значение «истина»
• Функция, принимающая значения «истина», «ложь», «ни истина, ни ложь»

Равносильность – это:

• Дизъюнкция
• Конъюнкция
• Эквиваленция
• Импликация

Раздел математики, посвященный изучению математических доказательств и вопросов оснований математики:

• Функция истинности
• Логика
• Высказывание
• Математическая логика

Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5?

• 18
• 20
• 10