💯 Математическая логика и теория алгоритмов [Тема 1-4] (ответы на тесты Синергия / МОИ / МТИ / МосАП, октябрь 2023)

Математическая логика и теория алгоритмов > Тест 1 / Тест 2 / Тест 3 / Тест 4 / Итоговый тест / Компетентностный тест

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

Математическая логика и теория алгоритмов

• Введение в курс
• Тема 1. Теория множеств
• Тема 2. Комбинаторика
• Тема 3. Математическая логика
• Тема 4. Теория графов
• Заключение
• Итоговая аттестация

… – это система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов

Тип ответа: Текcтовый ответ

… множество – это множество, не содержащее элементов

Тип ответа: Текcтовый ответ

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

Тип ответа: Текcтовый ответ

… функция – это функция, которая возвращает свое собственное отображение при применении операции двойного отрицания

Тип ответа: Текcтовый ответ

… число – это вещественное число, не являющееся алгебраическим, т.е. число, не являющееся корнем многочлена с рациональными коэффициентами

Тип ответа: Текcтовый ответ

… число графа – это наименьшее число цветов, в которое можно раскрасить его вершины

Тип ответа: Текcтовый ответ

2. Ниже изображен граф: Как должна выглядеть матрица идентичности для данного графа? @30857_16.png

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

• а
• б
• в
• г

Алгоритм Дейкстры находит …

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

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

Базис {Å,Ù,1} называется базисом …

Тип ответа: Текcтовый ответ

Булева функция называется … функцией, если она может быть представлена многочленом Жегалкина, который содержит только слагаемые нулевой и первой степени, и не содержит конъюнкций разных переменных

Тип ответа: Текcтовый ответ

Была дана задача найти количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут. Был получен следующий ответ: 210. Назовите комбинаторную конструкцию, с помощью которой был получен этот ответ.

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

• Перестановка.
• Размещение.
• Сочетание.
• Размещение с повторением

В проверочном задании в учебнике «Дискретная математика» был дан ряд функций: И дано задание определить, функцию, которая является функцией, сохраняющей только константу 1 (то есть относится только к классу Т1)

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

• Верным будет вариант № 1.
• Верным будет вариант № 2.
• Верным будет вариант № 3.
• Верным будет вариант № 4.

Вставьте недостающие слова в определения в правильной последовательности. «Матрица … – это … матрица, в которой и число строк, и число столбцов равно n – числу … графа. Матрица … – это матрица размера n x m, где n – число вершин графа, m – число рёбер графа»

Тип ответа: Сортировка

• 1 смежности
• 2 квадратная
• 3 вершин
• 4 инцидентности

Всякое множество, элементам которого можно поставить во взаимно однозначное соответствие множество натуральных чисел, называется …

Тип ответа: Текcтовый ответ

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

Тип ответа: Текcтовый ответ

Граф является … тогда и только тогда, когда степени всех его вершин четные.

Тип ответа: Текcтовый ответ

Дана некоторая последовательность последовательности, заданная с помощью рекурентного соотношения: a_(n+2)=2a_(n+1)-a_n,если a_0=1,a_1=2 Чему будет равно значение a_5?

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

• 4
• 5
• 6
• 7

Дано множество А = {1, 2, 3}. Из данного множества было получено следующее Р(А) = {{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, ∅}. Какая операция была произведена над исходным множеством А?

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

• Найдено дополнение множества А.
• Найден булеан множества А.
• Найдено разбиение множества А.
• Найден кортеж множества А.

Дано множество корней уравнения x^2+4x-5=0. В каком виде они должны быть записаны?

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

• {-1, 5}
• {-5, 1}
• {-5, 4}
• {-4, 5}

Даны два множества: А = {1, 2, 3}, B = {4, 5}. Укажите Декартово (прямое) произведение множеств А и В.

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

• {(1,1), (2,2), (3,3), (4,4), (5,5)}
• {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)}
• {(1,2), (1,3), (1,4), (1,5)}
• {(5,1), (5,2), (5,3), (4,1), (4,2), (4,3)}

Даны четыре линейных рекуррентных соотношения. Запишите их по следующему правилу: от рекуррентного соотношения меньшего порядка до рекуррентного соотношения большего порядка.

Тип ответа: Сортировка

• 1 aₙ₊₂ = 4aₙ₊₁ – 3
• 2 aₙ₊₂ = 3aₙ₊₁ + 2an
• 3 aₙ₊₂ = 2aₙ₊₁ – 3an + 2aₙ₋₁
• 4 aₙ₊₂ = 4aₙ₊₁ – 2an + 3aₙ₋₁ − aₙ₋₂

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

Тип ответа: Текcтовый ответ

Для логической формулы равносильной x→y ей логической формулой будет …

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

• x→у ̅
• y→x
• x&y

Для перечисления комбинаторных чисел и установления тождеств между ними используют …

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

• числа Стирлинга первого рода
• рекуррентные соотношения
• формулу обращения Мёбиуса
• метод производящих функций

Для связного плоского графа, где V – количество вершин графа, E – количество ребер графа, F – количество граней графа, справедлива формула Эйлера:

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

• V – F + E = 2
• F – V + E = 2
• E – V + F = 2
• V – E + F = 2

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

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

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

Если даны два множества А = {1, 2, 3} и B = {4, 5}, то декартово (прямое) произведение множеств А и В равно …

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

• {(1,1), (2,2), (3,3), (4,4), (5,5)}
• {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)}
• {(1,2), (1,3), (1,4), (1,5)}
• {(5,1), (5,2), (5,3), (4,1), (4,2), (4,3)}

Если на сети сформирован некоторый поток, то для ответа на вопрос о том, будет ли он максимальным, используют …

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

• алгоритм Беллмана–Форда
• теорему Форда–Фалкерсона
• алгоритм Краскаля
• формулу Эйлера

Если элемент А можно выбрать m способами, а после этого элемент В – n способами, то А и В можно выбрать … способами

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

• mn
• m + n
• m – n

Какая из указанных последовательностей, не является разбиением числа 5?

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

• {2, 1, 1, 1}
• {3, 2}
• {1, 1, 1, 1, 1, 0}
• {3, 1, 1}

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

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

• Уходя из аудитории, выключите компьютеры
• Гренландия – самый большой остров в мире.
• с помощью дискриминанта решаются полные квадратные уравнения.
• В начале 18 века столица Росси была перенесена из Москвы в Санкт-Петербург.

Какое из тождеств носит название «Закон де Моргана»? @30857_11.png

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

• а
• б
• в
• г

Какой будет иметь вид Эйлеров цикл (путь) для данного графа? @30857_15.png

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

• v4 – v5 – v6 – v3 – v2 – v5 – v1 – v3 – v6 – v4.
• v1 – v5 – v2 – v3 – v6 – v5 – v4 – v5 – v2 – v1.
• v1 – v5 – v2 – v6 – v4 – v5 – v6 – v3 – v2 – v1
• v4 – v6 – v5 – v1 – v2 – v3 – v2 – v5 – v6 – v4

Комбинаторика – это раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Чему будет равно значение комбинаторного выражения С_9^7∙Р_2?

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

• 94
• 82
• 72
• 96

Метод производящих функций был разработан

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

• Леонардом Эйлером
• Джеймсом Стирлингом
• Эриком Беллом
• Питером Дирихле

Множество В является … множества А, если каждый элемент множества В является также элементом множества А

Тип ответа: Текcтовый ответ

Множество формул алгебры логики {f1, f2, …, fm} называется …, если при всяком наборе значений переменных, входящих в эти формулы, по крайней мере одна из формул принимает значение 0.

Тип ответа: Текcтовый ответ

Неверно, что множество … чисел является счетным

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

• действительных
• рациональных
• натуральных
• натуральных

Неверно, что свойством деревьев является утверждение «…»

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

• Если к дереву добавить ребро, соединяющее его несмежные вершины, то появится ровно один простой цикл
• Любое дерево с p вершинами содержит количество ребер q = p + 1
• Если из дерева удалить ребро, то останется граф с двумя компонентами связности
• В любом дереве любые две вершины соединены ровно одной простой цепью

Неверно, что утверждение «…» является свойством счетных множеств

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

• Если к бесконечному множеству присоединить конечное или счетное, то получится множество, эквивалентное исходному
• Декартово произведение конечного числа счетных множеств счетно
• Всякое бесконечное множество не имеет счетных подмножеств
• Объединение конечного или счетного числа счетных множеств счетно

Операции, при выполнении которых появляются новые элементы, называют … операциями.

Тип ответа: Текcтовый ответ

Основателем теории графов считается:

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

• Густав Кирхгоф
• Артур Кэли
• Леонард Эйлер
• Роберт Бунзен

Пересечением числового отрезка [0, 4] с числовым отрезком [2, 5] является числовой отрезок

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

• [0, 2]
• [2, 4]
• [4, 5]
• [0, 5]

Подмножество, составленное из элементов некоторого конечного множества, называют … данного множества.

Тип ответа: Текcтовый ответ

Полином Жегалкина — многочлен над полем Z₂, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой. Какой вид будет иметь многочлен Жегалкина для функции f(x, y, z) = хy̅ v x̅z? @30857_14.png

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

• а
• б
• в
• г

Представление натурального числа n в виде n = x1 + x2 + … + xm, где x1, x2, …, xm ∈ ℕ, называется … натурального числа n на m слагаемых

Тип ответа: Текcтовый ответ

Пусть а – высказывание «Студент Иванов изучает английский язык», b – высказывание «Студент Иванов успевает по математической логике». Укажите верную словесную формулировку для высказывания b ̅ ↔ a ̅.

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

• Если студент Иванов не успевает по математической логике, то он и не успевает по английскому языку».
• Студент Иванов не изучает английский язык и не успевает по математической логике».
• Если студент Иванов не изучает английский язык, то он не успевает по математической логике».
• «Студент Иванов не успевает по математической логике тогда и только тогда, когда он не изучает английский язык».

Пусть дана числовая последовательность a0; a1; a2; ... an; …, тогда, если мы образуем степенной ряд с коэффициентами данной числовой последовательности a0 + a1 * x+ a2 * x2 + ... + an * xn + ... и если этот ряд сходится в некоторой области к функции f(x), то эту функцию называют … функцией для последовательности чисел a0; a1; a2; ... an; ...

Тип ответа: Текcтовый ответ

Пусть множество А содержит m элементов, а множество В содержит n элементов, тогда общее количество отображений множества А в множество В будет равно …

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

• m^n
• mn
• m + n

Пусть X – множество точек отрезка [4, 5], a Y– множество точек отрезка [5, 6]. Тогда X☐Y – это множество точек квадрата с вершинами в точках. Укажите, в каких точках расположены вершигы точек этого квадратп?

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

• (4, 5), (5, 6), (5, 4), (6, 5)
• (20, 25), (25, 30), (5, 5), (5, 6)
• (4, 5), (4, 6), (5, 5), (5, 6)
• (16, 25), (25, 16), (25, 36), (36, 25)

Расположите его вершины в порядке увеличения их степени, т. е. от меньшей степени к большей. @30857_12.png

Тип ответа: Сортировка

• 1 D
• 2 C
• 3 B
• 4 A

Расположите недостающие слова в формулировке теоремы Кантора-Бернштейна в правильном порядке «Пусть даны два множества А и В. Тогда если существуют … … f : A → B и g : B →A, то существует и … h : A ↔ B, то есть множества А и В …»

Тип ответа: Сортировка

• 1 инъективные
• 2 отображения
• 3 биекция
• 4 равномощны

Расположите указанные логические следствия схемы доказательств в следующем порядке: доказательство разбором случаев, доказательство построением цепочки импликаций, доказательство от противного или метод косвенного доказательства, доказательство теорем типа «если х, то у» @30857_10.png

Тип ответа: Сортировка

• 1 а
• 2 б
• 3 г
• 4 в

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

Тип ответа: Сортировка

• 1 an + 2 = 4an + 1 – 3
• 2 an + 2 = 3an + 1 + 2an
• 3 an + 2 = 2an + 1 – 3an + 2an – 1
• 4 an + 2 = 4an + 1 – 2an + 3an – 1 – an – 2

Связный граф без циклов называется …

Тип ответа: Текcтовый ответ

Согласно теореме Кэли, число деревьев, которые можно построить на 4-х нумерованных вершинах будет равно:

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

• 16
• 10
• 8
• 6

Таблицей истинности сложного высказывания F = (A Ú B) Ù B¯ при указанных значениях исходных переменных является таблица … @30857_4.png

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

• а
• б
• в
• г

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

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

• пересечение множеств
• объединение множеств
• разность множеств
• деление множеств

Установите последовательность операций в приведенном ниже выражении по убыванию их приоритета: @30857_3.png

Тип ответа: Сортировка

• 1 отрицание
• 2 ∧конъюнкция
• 3 ∨дизъюнкция
• 4 → импликация

Установите правильный порядок пропущенных слов в приведенной ниже формулировке теоремы Кантора–Бернштейна, от (1) до (4): Пусть даны два множества А и В. Тогда, если существуют ___(1) ___(2) f : A → B и g : B →A, то существует и ___(3) h : A ↔ B, то есть множества А и В ___(4)

Тип ответа: Сортировка

• 1 инъективные
• 2 отображения
• 3 биекция
• 4 равномощны

Установите правильный порядок пропущенных слов в приведенных ниже определениях, от (1) до (4): Матрица ___(1) – это ___(2) матрица, в которой и число строк, и число столбцов равно n – числу ___(3) графа. Матрица ___(4) – это матрица размера n x m, где n – число вершин графа, m – число ребер графа.

Тип ответа: Сортировка

• 1 смежности
• 2 квадратная
• 3 вершин
• 4 инцидентности

Установите соответствие между видом графа и его определением.

Тип ответа: Сопоставление

• A. Полный граф
• B. Нулевой граф
• C. Регулярный граф
• D. Связный граф
• E. граф, в котором проведены все возможные ребра.
• F. граф, состоящий только из изолированных вершин, т.е. граф, не содержащий ни одного ребра.
• G. связный граф, все вершины которого имеют одинаковую степень.
• H. граф, между любыми вершинами которого существует путь.

Установите соответствие между действием, выполняемым над множеством и обозначением этого действия с помощью диаграммы Эйлера-Венна @30857_7.png

Тип ответа: Сопоставление

• A. Дополнение множества (А ̅)
• B. Пересечение множеств (А ∩B)
• C. Разность множеств (АВ)
• D. Объединение множеств (А ∪B)
• E. в
• F. а
• G. б
• H. г

Установите соответствие между действием, выполняемым над множеством, и обозначением этого действия с помощью диаграммы Эйлера–Венна @30857_1.png

Тип ответа: Сопоставление

• A. 1
• B. 2
• C. 3
• D. 4
• E. в
• F. а
• G. б
• H. г

Установите соответствие между названием специального числа и его характеристикой.

Тип ответа: Сопоставление

• A. Числа Стирлинга второго рода
• B. Числа Люкаса
• C. Числа Белла
• D. Числа Фибоначчи
• E. – представляют собой число разбиений k-элементного множества на n частей.
• F. представляют собой последовательность, задаваемую соотношениями u(n)=u(n-1)+u(n-2), при n>2, где u(1)=1, u(2)=3
• G. представляют собой количество разбиений множества из n элементов на произвольное количество непустых подмножеств, которые не пересекаются.
• H. – представляют собой последовательность, задаваемую соотношениями F1 = F2 и Fn+1 = Fn +Fn-1 при n>1

Установите соответствие между названиями специальных чисел и их характеристиками:

Тип ответа: Сопоставление

• A. Числа Стирлинга второго рода
• B. Числа Белла
• C. Числа Фибоначчи
• D. представляют собой число разбиений k-элементного множества на n частей
• E. представляют собой количество разбиений множества из n элементов на произвольное количество непустых подмножеств, которые не пересекаются
• F. представляют собой последовательность, задаваемую соотношениями F1 = F2 и Fn + 1 = Fn + Fn – 1 при n >1

Установите соответствие между операцией над высказываниями и ее определением:

Тип ответа: Сопоставление

• A. Конъюнкция
• B. Эквиваленция
• C. Импликация
• D. Дизъюнкция
• E. логическая операция, образующая сложное высказывание, истинное тогда и только тогда, когда истинны оба исходных высказывания
• F. логическая операция, образующая сложное высказывание, которое является истинным тогда, когда оба простых логических выражения имеют одинаковую истинность
• G. логическая операция, которая двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда из истины следует ложь
• H. логическая операция, образующая сложное высказывание, истинное в том случае, когда хотя бы одно из высказываний истинно

Установите соответствие между формулой и названием закона алгебры множеств: @30857_8.png

Тип ответа: Сопоставление

• A. 1
• B. 2
• C. 3
• D. 4
• E. в
• F. а
• G. г
• H. б

Формулы, в которых очередной член последовательности выражается через один или несколько предыдущих членов, называются … соотношениями.

Тип ответа: Текcтовый ответ

Число различных булевых (логических) функций, зависящих от n переменных вычисляется по формуле:

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

• 2^2n
• 2n
• n^2
• 2^(2^n )

Число различных булевых (логических) функций, зависящих от n переменных, вычисляется по формуле …

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

• 2^2n
• 2n
• n^2
• 2^(2^n )

Число сочетаний без повторений из n элементов по k вычисляется по формуле … @30857_2.png

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

• а
• б
• в
• г

Элементарная дизъюнкция называется ____ относительно переменных x, y, z, ..., если в неё входит каждая из этих переменных не менее одного раза, включая и их вхождение под знаком отрицания.

Тип ответа: Текcтовый ответ

Элементарная конъюнкция называется …, если в неё каждая переменная входит не более одного раза, включая её вхождение и под знаком отрицания.

Тип ответа: Текcтовый ответ