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

Предикатная формула на предметной области натуральных чисел представляет собой

• ложное высказывание
• линейное уравнение
• истинное высказывание
• одноместный предикат

Для функции f(X) = (2Х-1) / X2 суперпозиция f(X2) равна

• (4Х2 –1) / Х4
• Х2 / (2Х –1)2
• Х2 / (4Х2 –1)
• (2Х2 –1) / Х4

Равномерными кодами являются

• {a: 000, b: 01, c: 101, d: 11}
• {a: 010, b: 101, c: 110}
• {a: 00, b: 10, c: 11, d: 01}
• {a: 01, b: 001, c: 110, d: 11}

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

• [c d e]
• путь
• [a e c]
• цепь
• [c d a]
• цикл

Число различных 4-значных четных чисел, которые можно составить из всех цифр числа 8416, равно _____ (ответ дать цифрой)

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

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

Количество способов, которыми Андрей, Борис и Василий могут разместиться в электричке из 8 вагонов, так что все они – в разных вагонах, равно

• 336
• 512
• 210
• 8!

Число строк в таблице булевой функции f(X, Y, Z) равно

• 4
• 8
• 9
• 2

Предикатная формула $X,Z (X • Y = Z + Y / X) представляет собой

• одноместный предикат P(Y)
• трехместный предикат P(X, Y, Z)
• высказывание
• двуместный предикат P(X, Z)

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

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

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

• [a b c]
• цепь
• [c d e]
• цикл
• [a d c]
• путь

Максимальное число абонентов, которых можно обеспечить 4-значными телефонными номерами, составляет

• 1024
• 10000
• 256
• 120

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

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

В таблице булевой функции «дизъюнкция» значения p, q равны

• p = 1, q = 1
• p = 1, q = 0
• p = 0, q = 0
• p = 0, q = 1

На множестве натуральных чисел в десятичной записи упорядочение по возрастанию и алфавитное упорядочение

• совпадают на подмножестве четных чисел
• совпадают
• не совпадают
• совпадают на подмножестве нечетных чисел

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

• X

Укажите соответствие между примером множества и способом его задания

• X = (1, 3) È [4, 7]
• рекуррентное
• Xn = 5n2 – n + 1
• явное
• Xn = 3Xn-1 + 1
• с помощью теоретико-множественных операций

В коде алфавита {a: 00, b: 101, c: 11} последовательность 1100101101 служит кодом сообщения

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

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

Булева функция принимает значение 1 на наборе переменных X, Y

• 0 1
• 1 0
• 0 0
• 1 1

Укажите соответствие между сообщениями в алфавите {a, b, c} и их кодами при побуквенном кодировании [a: 0, b: 10, c: 11]

• Bca
• 11010
• Abc
• 01011
• Cab
• 10110

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

• [d a b c]
• путь
• [a e c]
• цепь
• [b e d]
• цикл

(число строк ´ число столбцов)

• 5 ´ 4
• 4 ´ 4
• 5 ´ 5
• 4 ´ 5

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

• X Y
• Y

Число различных 4-значных чисел, которые можно составить из всех цифр числа 8196, равно _____ (ответ дать цифрой)

Тождество ¬(X Ú Y) = ¬X & ¬Y называется законом

• де Моргана
• Поста
• исключенного третьего
• тождества

Число слов длины 6 в алфавите {p, q, r, s} вычисляется по формуле

• A46
• 64
• 46
• C64

(число строк ´ число столбцов)

• 5 ´ 5
• 5 ´ 7
• 7 ´ 5
• 7 ´ 7

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

• неупорядоченным
• частично упорядоченным
• линейно упорядоченным
• неопределенным

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

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

Предикатная формула на предметной области натуральных чисел представляет собой

• линейное уравнение
• истинное высказывание
• одноместный предикат
• ложное высказывание

Число ребер графа равно

• 24
• 16
• 15
• 12

Для частично упорядоченного множества М справедливо:

• если в М есть хотя бы один минимальный элемент, то есть и наименьший
• если в М есть хотя бы один максимальный элемент, то есть и наибольший
• если в М есть наибольший элемент, то есть и максимальный
• если в М есть наименьший элемент, то есть и минимальный

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

• 310
• 100
• 120
• 720

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

Число различных 4-значных чисел, которые можно составить из всех цифр числа 5436, можно выразить

• Р4
• А44

Префиксными кодами являются

• {a: 001, b: 01, c: 101, d: 10}
• {a: 00, b: 01, c: 10, d: 11}
• {a: 10, b: 001, c: 110}
• {a: 01, b: 011, c: 110, d: 11}

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

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

Префиксными кодами являются

• {a: 00, b: 01, c: 110}
• {a: 01, b: 011, c: 110, d: 11}
• {a: 001, b: 01, c: 101, d: 10}
• {a: 00, b: 100, c: 11, d: 01}

Число вершин графа равно

• 8
• 24
• 20
• 16

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

• 103
• С103
• А103
• 310

Булева функция тождественно равна

• ¬ (X & Y)
• (X à Y) & (Y à X)
• ¬(X Å Y)
• 1

Подстановка константы 0 вместо Y превращает булеву функцию в

• логическую константу
• 0

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

Предикатная формула $X (X • Y = Z + Y / X) представляет собой

• высказывание
• двуместный предикат P(Y, Z)
• трехместный предикат P(X, Y, Z)
• одноместный предикат P(X)

Кратчайший путь между вершинами А и В в графе с заданными длинами ребер равен

• [ACEDB]
• [ACDB]
• [AEB]
• [ACEB]

Количество способов, которыми можно выбрать 3 экзаменационных билета из 9, равно

• 504
• 84
• 42
• 36