Специальные главы математики. Часть 1.
для специальности 075500
Дискретная математика.
для специальностей 220500, 220507

Давыдова Е.М., Мещеряков Р.В.
(Кафедра КИБЭВС)
Томск-2004

Множества.

№ 1
Что понимается под совокупностью объектов, обладающих определенными свойствами?
• Множество.

№ 2
Что строится из некоторых элементов, обладающих определенными свойствами и находящихся в каких-то отношениях между собой и с элементами других множеств?
• Множество.

№ 3
Какой знак называется знаком принадлежности множеству?
• ∈.

№ 4
Какой знак называется знаком включения подмножества?
• ⊂.

№ 5
Как обозначается пустое множество?
• ∅;
• { }.

№ 6
Как обозначается универсальное множество?
• T;
• I.

№ 7
Как называется количество элементов в множестве?
• Мощность.

№ 8
Как называется множество, имеющее мощность равную единице?
• Синглетон.

№ 9
Если о каждом предмете можно сказать, принадлежит он множеству или нет, то это множество называется ...
• полностью определенным.

№ 10
Укажите основные способы задания множества.
• С помощью характеристического свойства.
• Прямое перечисление.

№ 11
А = {а|а обладает свойством Q}. Назовите способ задания множества.
• С помощью характеристического свойства.

№ 12
Дано множество А = {1, 2, 3}, укажите все его несобственные подмножества.
• ∅;
• {а,в,с}.

№ 13
Определите операцию: A?В={x | x∈А и/или х∈В}.
• ∪;
• Объединение.

№ 14
Определите операцию: A?В={x | x∈А и х∉В}.
• \;
• Разность.

№ 15
Определите операцию: A?В={x | x∈А/B или х∈В\A}.
• ∆;
• Симметрическая разность.

№ 16
Определите операцию: A?В={x | x ∈А и х ∈В}.
• ∩;
• Пересечение.

№ 17
Дополните формулу и укажите закон A∩B=
• B∩A;
• Закон коммутативности.

№ 18
Дополните формулу и укажите закон A∪B=
• B∪A;
• Закон коммутативности.

№ 19
Дополните формулу и укажите закон A∪(B∪C)=
• (A∪B)∪C;
• Закон ассоциативности.

№ 20
Дополните формулу и укажите закон A∩(B∩C)=
• (A∩B)∩C;
• Закон ассоциативности.

№ 21
Дополните формулу и укажите закон A∩(B∪C)=
• A∩B∪A∩C;
• Закон дистрибутивности.

№ 22
Дополните формулу и укажите закон A∪(B∩C)=
• (A∪B)∩(A∪C);
• Закон дистрибутивности.

№ 23
Дополните формулу и укажите закон A∪A∩B=
• A;
• Закон поглощения.

№ 24
Дополните формулу и укажите закон A∩(A∪B)=
• A;
• Закон поглощения.

№ 25
Дополните формулу и укажите закон A∩B∪A∩B=
• A;
• Закон склеивания.

№ 26
Дополните формулу и укажите закон (A∪B)∩(A∪B)=
• A;
• Закон склеивания.

№ 27
Дополните формулу и укажите закон A∩(A∪B)=
• A∪B;
• Закон Порецкого.

№ 28
Дополните формулу и укажите закон A∩B=
• A∪B;
• Закон де Моргана.

№ 29
Дополните формулу и укажите закон A∪B=
• A∩B;
• Закон де Моргана.

№ 30
Что называется совокупностью множества М с заданными в нем операциями: S={f₁,f₂, . . . ,f_m1,f_m2, . . ,f_m,nm}, A=‹M,S›, здесь множество М - носитель, S - сигнатура. Нижний индекс у идентификатора операции указывает ее местность.
• Алгебра.

Отношения.

№ 31
Как называется упорядоченное множество?
• Кортеж.

№ 32
Как называют множество, элементами которого служат пары всех элементов множеств А и В , первый элемент берется из А второй из В?
• Декартово произведение.

№ 33
Как называется любое подмножество декартова произведения?
• Отношение.

№ 34
Если для любых а,b∈A выполнено: aRb следует bRa; или (a,b)∈R⇒(b,a)∈Ra≠b. Каким свойством обладает отношение?
• Симметричность.

№ 35
Если для каждого элемента а∈А справедливо утверждение aRa. Каким свойством обладает отношение?
• Рефлексивность.

№ 36
Если для любых а,b,c∈A выполняется: aRb и bRc⇒aRc при этом a≠b, b≠c, a≠с. Каким свойством обладает отношение?
• Транзитивность.

№ 37
Если бинарное отношение R в множестве А, обладает свойствами: рефлексивности: для каждого a∈A,(a,а)∈R, транзитивности: для любых a,b,с∈A следует (a,b)∈R, (b,с)∈R⇒(a,с)∈R. Каким свойством обладает отношение?
• Линейная упорядоченность.

№ 38
Если бинарное отношение в множестве А, обладает свойствами антирефлексивности, антисимметричности и транзитивности. Каким свойством обладает отношение?
• Строгая упорядоченность.

№ 39
Если отношение R, определенное на множестве А, является рефлексивным, симметричным и транзитивным. Каким свойством обладает отношение?
• Эквивалентность.

№ 40
Пусть R - произвольное отношение, определенное на множестве А. Как называется наименьшее рефлексивное отношение, определенное на множестве А, для которого отношение R является подмножеством?
• Рефлексивное замыкание.

Логика высказываний и Булевы функции.

№ 41
Какой операции соответствует приведенная ниже таблица истинностей?

a b	a ? b
Л Л  Л И  И Л  И И	Л  Л  Л  И

• конъюнкция;
• a&b;
• а∧b.

№ 42
Какой операции соответствует приведенная ниже таблица истинностей?

a b	a ? b
Л Л  Л И  И Л  И И	Л  И  И  И

• дизъюнкция;
• ∨(a,b);
• oперация логического сложения.

№ 43
Какой операции соответствует приведенная ниже таблица истинностей?

a b	a ? b
Л Л  Л И  И Л  И И	И  И  Л  И

• a→b
; • импликация;
• если a, то b.

№ 44
Какой операции соответствует приведенная ниже таблица истинностей?

a b	a ? b
Л Л  Л И  И Л  И И	И  Л  Л  И

• a если и только если b;
• эквивалентность;
• a∼b.

№ 45
Какой операции соответствует приведенная ниже таблица истинностей?

a b	a ? b
Л Л  Л И  И Л  И И	Л  И  И  Л

• или a или b;
• дизъюнкция с исключением;
• ∆.

№ 46
Как называется формула принимающая истинное значение на любом наборе переменных?
• Тавтологией.
• Тождественно истинной.

№ 47
Какой закон указан в следующем утверждении: (∨(А,В)) С =∨(АС,ВС)?
• Дистрибутивности.

№ 48
Какой закон указан в следующем утверждении: ∨(А,ВС)=(∨(А,В)) (∨(А,С))?
• Дистрибутивности.

№ 49
Какой закон указан в следующем утверждении: А∧(B∧C)=(А∧В)∧С ?
• Ассоциативности.

№ 50
Какой закон указан в следующем утверждении: ∨(a,|b|)=∧(a,b), ∧(a,b)=∨(a,b) ?
• Де Моргана.

№ 51
Какой закон указан в следующем утверждении: |∨(a,b)|=|∨(b,a)|, ∧(a,b)=∧(b,a) ?
• Коммутативности.

№ 52
Какой закон указан в следующем утверждении: |∨(a,∧(a,b))|=a, |∧(a,(|∨(a,b)|))|=a ?
• Поглощения.

№ 53
Какой закон указан в следующем утверждении: ∧(∧(a,∨(b,a)),b)=a, ∧((∨(a,b)),(∨(a,b))=a ?
• Склеивания.

№ 54
Как называется двоичная функция двоичного аргумента?
• Булевой функцией.

№ 55
Какие способы задания булевой функции Вы знаете?
• Табличный способ.
• Представление вершинами n-мерного куба.
• Задание формулами.

№ 56
Как называется система функций, если любая булева функция может быть представлена в виде суперпозиции функций этой системы?
• Функционально полной.
• Базисом.

№ 57
Какая система называется базисом?
• Функционально полная.

№ 58
Как называется базис, если ни одну из функций базиса нельзя исключить так, чтобы оставшаяся система функций была функционально полной?
• Безизбыточным.

№ 59
Как называются две формулы, представляющие одну и ту же функцию?
• Равносильными.

№ 60
Как называется выражение вида x₁^δ1 x₂^δ2... x_n^δn ?
• Элементарной конъюнкцией.

№ 61
Как называется конъюнкция различных, полных элементарных дизъюнкций?
• СКНФ.

№ 62
Как называется дизъюнкция различных, полных элементарных конъюнкций?
• СДНФ.

№ 63
Что является канонической формой булевой функции?
• СДНФ.
• СКНФ.

№ 64
Какая формула является разложением Шеннона?
• .

№ 65
Как называется элементарная конъюнкция К над множеством переменных {x₁, . . . ,x_n} такая, что ∨(К,f) (x₁, . . . ,x_n)=f(x₁, . . .,x_n) ?
• Импликантой.

№ 66
Как называется дизъюнкция всех простых импликант функции f?
• Сокращенной.

№ 67
Как называется импликанта, если удаление ее из сокращенной ДНФ приводит к ДНФ, которая не эквивалентна исходной?
• Ядерной.

К-значная логика и комбинаторика.

№ 68
Cколько функций у 5-значной логики для 2-х переменных?
• 25.

№ 69
Какое количество всех функций в P₃, зависящих от 3 переменных?
• 7625597484987

№ 70
Отрицание Поста - это:
• обобщение отрицания в смысле “циклического” сдвига значений.

№ 71
Минимум x₁ и x₂ - это:
• обобщение конъюнкции.

№ 72
Отрицание Лукасевича:
• общение отрицания в смысле “зеркального” отображения значений.

№ 73
Максимум x₁ и x₂ - это:
• обобщение дизъюнкции.

№ 74
Система S функций f₁,f₂,...,f_n, из P_k называется (функционально) полной, если любая функция из P_k может быть записана в виде формулы через функции этой системы.

№ 75
Пусть M - произвольное множество функций из P_k. Замыканием M называется множество [M] всех функций из P_k, представимы в виде формул через функции множества М.

№ 76
Существует ли алгоритм для распознавания полноты системы функций?
• Да.

№ 77
Для всякого ли k(k≥3) существует в P_k замкнутый класс, со счетным базисом?
• Да.

№ 78
Каково число размещений U(6,3)?
• 216.

№ 79
Kаково число размещений без повторений A(6,3)?
• 120.

№ 80
Подсчитайте число сочетаний C(6,3)?
• 20.

№ 81
Азбука Морзе - это:
• схема алфавитного кодирования.

№ 82
Допустимо ли сжатие текстов с потерей информации?
• Нет.

№ 83
Алгоритм Лемпела-Зива используется для:
• адаптивного сжатия.

№ 84
Кодирование данных с целью защиты от несанкционированного доступа?
• Шифрование.

№ 85
Свойство шифра противостоять раскрытию называется:
• криптостойкостью.

№ 86
Как называются шифры, в которых для зашифровки и расшифровки используется один и тот же ключ?
• Cимметричными.

№ 87
Как называются шифры, в которых для зашифровки и расшифровки используется разные ключи?
• Aсиметричными.

Графы.

№ 88
Как называется объект, состоящий из двух множеств (множества точек и множества линий), которые находятся между собой в некотором отношении?
• Граф

№ 89
Как называется подмножество неориентированных линий?
• Подмножество Рёбер.

№ 90
Что определяется упорядоченной парой вершин x_i,х_j, которые u_k соединяет и записывается u_k=‹x_i,х_j›?
• Ребро.

№ 91
Если ребро u_k∈U графа G = (X,U) соединяет вершины x_i,x_j∈X, т.е. u_k=(x_i,x_j), то говорят, что ребро u_k инцидентно вершинам x_i,x_j.

№ 92
Любые две вершины x_i,x_j∈X графа G=(X,U) называют смежными, если существует соединяющее эти вершины ребро u_k∈U, т.е. u_k=(x_i,x_j).
• .

№ 93
Говорят, что задан граф если заданы множество вершин Х, множество ребер U и инцидентор F, определяющий, какую пару вершин x_i,x_j∈X соединяет ребро u_k=(x_i,x_j).

№ 94
Как называется граф, у которого множество вершин Х≠ ∅ и множество ребер U=∅?
• Нуль-граф.

№ 95
Как называется граф G=(X,U) |X|=n, если между любой парой вершин x_i,x_j∈X имеется ребро u_k∈U, i≠j?
• Полный.

№ 96
Как называется число ребер, инцидентных вершине x_i∈X графа?
• Локальной степенью вершины.

№ 97
Как называется граф, у которого все ребра и вершины принадлежат графу G, т.е. G´´=(X´,U´) , если X´⊆X,U´⊆U и ребра U´ соединяют только вершины X´.
• Подграф.

№ 98
Как называют граф G'=(X',U') графа G=(X,U), у которого X´=X,U´⊆U?
• Суграф.

№ 99
Как называется маршрут в графе в котором нет повторяющихся ребер и вершин?
• Простая цепь.

№ 100
Если существует маршрут S, в котором вершины x_i,x_j будут концевыми, то две произвольные вершины называются связными.

№ 101
Граф называется связный, если любые две его вершины связны, т.е. 2 вершины объединены простой цепью.

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

№ 103
Конечный граф G является эйлеровым, если он связан и все его локальные степени четные.

№ 104
Цикл, проходящий по всем вершинам графа G один раз, называется гамильтоновый, а граф G называется гамильтоновым графом.

№ 105
Если в графе с n(n≥3) вершин для любой пары несмежных вершин x_i,x_j ρ(x_i)+ρ(x_j)≥n, то граф имеет гамильтонов цикл.

№ 106
Связный граф без циклов называется деревом и обозначается Т=(Х,U), |X|=n, |T|=n-1.
Ответ:

№ 107
Дерево, у которого число вершин равно числу вершин графа из которого выделено дерево, а ребра является подмножеством этого графа, называется покрывающим деревом.

№ 108
Как называется функция d(x_i,x_j), определенная на множестве ребер графа G и удовлетворяющая аксиомам Фреше?
• Метрика.

№ 109
Раскраской вершин графа называется разбиение множества вершин графа на l непересекающихся классов (подмножеств) X₁,X₂,. . . .,X_l; ; X_i∩X_j=0; i,j∈1,l; i≠j.

№ 110
Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом и обозначается K(G).

№ 111
Наименьшее число ребер, которое необходимо удалить из графа G, чтобы он стал ациклическим, называется цикломатическим числом графа.

№ 112
Граф G_n1,n2 является двудольным тогда, и только тогда, когда он не имеет простых циклов нечетной длины.

№ 113
Два графа G=(X,U) и G´=(X´,U´) называют изоморфными, если можно установить взаимно-однозначное соответствие X↔X´, U↔U´ такое, что если (x_i,x_j)∈X↔(x_i,x_j)∈X´, то ребро u=(x_i,x_j)∈U↔u´=(x´_i,x´_j)∈U´.

№ 114
Граф G=(X,U) называется плоским, если он расположен на плоскости таким образом, что ребра имеют общие точки лишь в вершинах.

№ 115
Как называется граф, изоморфный плоскому, расположенный на плоскости и имеющий пересечения ребер?
• Планарным.

№ 116
Число дуг, положительно инцидентных вершине x_j, называется полустепенью захода и обозначается ρ⁺(x_j).

№ 117
Число дуг, отрицательно инцидентных x_j, т.е. выходящих из x_j, называется полустепенью исхода и обозначается через ζ^-(x_j).
• .

№ 118
Граф D называют сильносвязным, если любые две его вершины взаимнодостижимы.