Дискретная математика. Часть 1

Из двух пар чисел (7, 11) и (11, 11) бинарное отношение R(a, b) = b

ни для одной пары
только для второй пары
для обеих пар
только для первой пары

• ни для одной пары
• только для второй пары
• для обеих пар
• только для первой пары

Число размещений без повторений из 4 элементов по 3 равно _____ . (дать цифровой ответ)

Схема из трех функциональных элементов , где , , , реализует функцию

В сети кратчайшим путем [a, b] является путь

• [a, C, B, b]
• [a, A, B, b]
• [a, C, D, b]
• [a, A, D, b]

Схема из трех функциональных элементов , где , , , реализует функцию

Цикломатическое число графа

• 7
• 8
• 0
• 2

СДНФ булевой функции, задаваемой таблицей, содержит элементарную конъюнкцию

• X Y
• Y
• X

Функция, заданная на трехмерном единичном кубе , имеет СДНФ

• ÚX Z
• Y Z ÚX
• YÚZ
• Z Ú X Y

Из полюса  в полюс  в данной сети ведут ___ различных элементарных путей (ответ – целое число).

Функция, получаемая применением оператора примитивной рекурсии

• x, y, k
• x, y, k, f
• x, y
• k

Схема из трех функциональных элементов , где , , , реализует функцию

В алфавите {a, b, d}, если d не может находиться с краю, число слов длины 4 равно

• 64
• 54
• 36
• 81

Вычисление попарных расстояний Хэмминга для кодовых слов алфавита V = {a, b, c} a: 00101, b: 10110, c: 11011 b: 10110, c: 11011, a: 00101 (второй ряд записан под первым для удобства вычислений) показывает, что кодовое расстояние данного кода равно

• 3
• 2
• 5
• 4

СДНФ булевой функции, задаваемой таблицей, содержит элементарную конъюнкцию

• Y
• X
• X Y

Подстановка значений Х = 0 и Х = 1 показывает, что булева функция  тождественно равна функции

• 1

Матрица представляет собой матрицу соседства вершин ориентированного графа

Цикломатическое число графа

• 12
• 6
• 10
• 8

Размерность матрицы переходов автомата с входным алфавитом {a, b}, выходным алфавитом {a, b, d} и 5-тью состояниями:

• 5х5
• 2х5
• 5х3
• 5х2

В полном двудольном графе К3,3 число различных элементарных циклов длины 3 равно

• 36
• 9
• 0
• 3

Число сочетаний с повторениями из 6 элементов по 2 равно

• 21
• 0
• 15
• 30

Цикломатическое число графа равно _____ . (дать цифровой ответ)

Столбцами значений  и  задаются булевы функции  и . Столбцом значений функции  является [ ____ ]T. (дать цифровой ответ)

Кодом сообщения сасb в коде алфавита {a: 001, b: 01, c: 10} служит

• 010011001
• 101000101
• 100101001
• 100011001

Минимальное число красок при правильной раскраске полного графа К6 равно

• 2
• 15
• 6
• 5

Кодовое расстояние для двоичных кодов передаваемых сообщений равно 8. Тогда возможно обнаружение до ____ ошибок замещения (ответ дать числом)

Сопоставьте наборы булевых переменных функции трех переменных и соответствующие элементарные конъюнкции:

• 010
• Z
• 101
• X Z
• 001
• Y

Для множеств A={2, 4, 6} и B={3, 4} декартовым произведением  является

• {(2, 3), (2, 4), (4, 3), (4, 4), (6, 3), (6, 4)}
• {2 ∙ 4 ∙ 6 ∙ 3 ∙ 4}
• {6, 8, 12, 16, 18, 24}

____ двоичных знаков содержит двоичная запись десятичного числа 57. (дать цифровой ответ)

___ различных элементарных цепей длины 3 связывают вершины (0 0 0) и (1 1 1) в графе Е3 (трехмерном единичном кубе) (ответ – целое число).

Бинарное отношение «правее» между точками на числовой прямой является

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

Матрица представляет собой матрицу соседства вершин ориентированного графа

Определите свободные и связанные переменные в кванторных формулах

• «Z $Y P(X, Y, Z)
• X, Y, Z – связанные
• «X P(X, Y, Z)
• X – связанная, Y, Z — свободные
• $Z»X,Y P(X, Y, Z)
• Y, Z – связанные, X — свободная

Число размещений с повторениями из 6 элементов по 3 вычисляется по формуле

• 63
• C63
• A63
• 63

Последовательность ребер в графе G представляет собой

• [b e a]
• Путь
• [d a b]
• Цепь
• [b e d]
• Контур

В графе с заданными длинами ребер расстояние между вершинами А и В равно

• 16
• 2
• 4
• 18

Булева функция, задаваемая таблицей выражается формулой

• ¬X & Y
• ¬X & ¬Y
• X & ¬Y
• X & Y

Булева функция, задаваемая таблицей выражается формулой

• X & ¬Y
• ¬X & ¬Y
• X & Y
• ¬X & Y

В полном двудольном графе К5,5 число ребер равно

• 10
• 25
• 24
• 20

Булева функция, задаваемая таблицей называется

• суммой по модулю 2
• дизъюнкцией
• эквивалентностью
• импликацией

Кодовое расстояние для двоичных кодов передаваемых сообщений равно 9. Тогда возможно исправление до ____ ошибок замещения.(дать цифровой ответ)

Матрица представляет собой матрицу соседства вершин ориентированного графа

Столбцами значений  и  задаются булевы функции  и . Столбцом значений функции  является [ ____ ]T. (дать цифровой ответ)

Ребра, образующие остов графа:

• {a, b, c, d, e}
• {a, b, c, d}
• {b, c, d, g}
• {a, b, f, e}

Критерий Поста – это критерий _______ системы булевых функций.

Если в частично упорядоченном множестве М есть наименьший элемент, то в нем

• есть ровно один минимальный
• есть наибольший элемент
• есть хотя бы два различных минимальных элемента
• нет ни одного максимального элемента

На множестве действительных чисел бинарное отношение P: X

транзитивным
нетранзитивным
симметричным
антисимметричным

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

Функция, реализуемая схемой из функциональных элементов

• X ∙ Y — X
• X — X ∙ Y
• (Y-X) ∙ X
• (X — Y) ∙ Y

Кодовый замок имеет 10 клавиш с цифрами 0, 1, 2,…, 9. Для открывания двери нужно одновременно нажать 4 клавиши. Число всевозможных кодов такого замка равно

• 5040
• 400
• 10000
• 210

Матрица представляет собой матрицу соседства вершин неориентированного графа

В алфавите {a, b, c}, если a и c — соседние, число слов длины 2 равно

• 8
• 9
• 6
• 2