💯 Математическая логика и теория алгоритмов.ои(dor_БАК) — ответы на тест Синергия / МОИ / МТИ / МосАП

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

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

Математическая логика и теория алгоритмов.ои(dor_БАК)

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

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

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

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

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

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

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

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

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

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

Даны два множества: А = {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, 2, 3, …, n, … @244.jpg 

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

• 1 @244-4.jpg 
• 2 @244-1.jpg 
• 3 @244-3.jpg 
• 4 @244-2.jpg 

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

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

• 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

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

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

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

Если полный граф имеет n вершин, то количество рёбер будет равно

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

• @40-1.jpg 
• @40-2.jpg 
• @40-3.jpg 
• @40-4.jpg 

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

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

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

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

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

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

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

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

• @19-1.jpg 
• @19-2.jpg 
• @19-3.jpg 
• @19-4.jpg 

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

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

• @29-1.jpg 
• @29-2.jpg 
• @29-3.jpg 
• @29-4.jpg 

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

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

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

Множество 2^А называется … множества А. @5.jpg 

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

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

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

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

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

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

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

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

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

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

Произведение всех натуральных чисел от 1 до n называют … числа n.

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

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

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

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

Расположите недостающие слова в определении в правильном порядке: <...> @4.jpg 

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

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

Расположите недостающие слова в формулировке теоремы Кантора-Бернштейна в правильном порядке <...> @3.jpg 

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

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

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

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

• 1 @24-1.jpg 
• 2 @24-2.jpg 
• 3 @24-4.jpg 
• 4 @24-3.jpg 

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

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

• 16
• 10
• 8
• 6

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

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

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

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

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

• 1 @23-2.jpg 
• 2 @23-3.jpg 
• 3 @23-4.jpg 
• 4 @23-1.jpg 

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

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

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

Установите соответствие между графом, представленным на рисунке и матрицей смежности

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

• A. @32-1.jpg 
• B. @32-2.jpg 
• C. @32-3.jpg 
• D. @32-4.jpg 
• E. @32-33.jpg 
• F. @32-11.jpg 
• G. @32-44.jpg 
• H. @32-22.jpg 

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

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

• A. @1-1.jpg 
• B. @1-2.jpg 
• C. @1-3.jpg 
• D. @1-4.jpg 
• E. @1-v.jpg 
• F. @1-a.jpg 
• G. @1-b.jpg 
• H. @1-g.jpg 

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

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

• A. Числа Стирлинга второго рода
• B. Числа Люкаса
• C. Числа Белла
• D. Числа Фибоначчи
• E. представляют собой число разбиений k-элементного множества на n частей.
• F. @11-1.jpg 
• G. представляют собой количество разбиений множества из n элементов на произвольное количество непустых подмножеств, которые не пересекаются.
• H. @11-3.jpg 

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

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

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

Установите соответствие между определением понятия и его характеристикой

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

• A. Формула алгебры логики называется …, если она принимает значение 1 при всех значениях входящих в неё элементарных переменных высказываний.
• B. Формула алгебры логики называется …, если она принимает значение 0 при любых значениях входящих в неё элементарных переменных высказываний.
• C. Формула алгебры логики называется …, если она принимает одно значение 1 хотя бы на одном наборе значений входящих в неё элементарных переменных высказываний.
• D. Формула алгебры логики называется …, если она принимает одно значение 0 хотя бы на одном наборе значений входящих в неё элементарных переменных высказываний.
• E. тавтологией
• F. противоречием
• G. выполнимой
• H. опровержимой

Установите соответствие между условием задачи и методом её решения:

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

• A. На тарелке лежат 5 груш и 4 яблока. Сколькими способами можно выбрать один фрукт?
• B. В канцелярском магазине продают 5 видов шариковых ручек и 4 вида тетрадей. Сколькими способами можно выбрать набор из ручки и тетради (т.е. одну ручку и одну тетрадь)?
• C. Каждый ученик класса побывал в театре или в кино. В театр сходили 22 человека. В кино были 15 человек. И в театре, и в кино были 7 человек. Сколько учеников в классе?
• D. Сколькими способами можно развесить 5 цветных шаров на гирлянде?
• E. Правило суммы
• F. Правило произведения
• G. Формула включений и исключений для двух множеств
• H. Формула перестановки

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

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

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

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

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

• @28-1.jpg 
• @28-2.jpg 
• @28-3.jpg 
• @28-4.jpg 

Число ребер на дереве с 6-ю вершинами будет равно

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

• 4
• 5
• 6
• 7

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

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

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

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