дипломы,диссертации,курсовые,контрольные,рефераты,отчеты на заказ

Дискретная математика-1.
для специальностей 230105, 080801
Сафьянова Е.Н.
Кафедра АСУ
Томск-2006

Указаны только правильные ответы, другие варианты можно узнать скачав файл из архива → Дис_мат1.АСУ.

Тема 1. Теория множеств
дипломы,курсовые,рефераты,контрольные,диссертации,отчеты на заказ

№ 1
Описательный способ задания множества состоит:
• в том, что указывается характерное свойство, которым обладают все элементы множества.

№ 2
Как записать математически следующее множество: «Множество X состоит из элементов x множества M таких, что x является менеджером фирмы»?
• X = {x ∈ M/x - менеджер фирмы}.

№ 3
Что означает следующая запись: X ⊂ Y?
• Множество X является подмножеством множества Y.

№ 4
Какое подмножество может быть сформулировано в виде: ∀x [x∈X => x∈Y]?
• Для любого элемента x утверждение «x принадлежит X» влечет за собой утверждение «x принадлежит Y».

№ 5
Какое множество отмечено на рисунке затемнением?
Пересечение множеств
• Пересечение множеств Х и Y.

№ 6
Что означает выражение:
Объединение множеств
• Объединение множеств Xi (i = 1, 2, ... N).

№ 7
Каков правильный вывод из следующего выражения: X \\ Y= ∅ ?
• Множество Х является подмножеством множества Y.

№ 8
Какое множество называется дополнительным к множеству M по отношению к множеству N, если M⊂N ?
• Множество, состоящее из элементов N, не принадлежащих множеству M.

№ 9
Даны множества X = {1, 2, 3, 4, 5}, Y = {2, 4, 6, 7}, найдите Y \\ X.
• Y \\ X = {6, 7}.

№ 10
Верно ли, что:
а) {1, 2} ⊆ {{1, 2, 3}, {1, 3}, 1, 2}
б) {1, 2} ∈ {{1, 2, 3}, {1, 3}, 1, 2}?
• Утверждение а) верно, утверждение б) неверно..

№ 11
Пусть I={x1, x2, x3} - универсальное множество, а X={x1, x2}, Y={x2, x3} его подмножества. Определите перечислением декартовы произведения множеств: X×Y, Y×X.
• X×Y = {(x1, x2), (x1, x3), (x2, x2), (x2, x3) }; Y×X={(x2, x1), (x2, x2), (x3, x1), (x3, x2)}.

№ 12
На множестве X={x / x∈N, x<10} задано отношение R: “x и y имеют один и тот же остаток при делении на 2” (x∈X, y∈X). Определите, на какие классы эквивалентности разбивается множество данным отношением.
• {2, 4, 6, 8}; {1, 3, 5, 7, 9}.

№ 13
Отношение R между элементами множества X называется транзитивным, если:
• ∀ x,y,z ∈ X справедливо утверждение: x R y, y R z => x R z.

№ 14
Отношение R между элементами множества X называется симметричным, если:
• ∀ x,y ∈ X справедливо утверждение: x R y => y R x.

№ 15
Отношение R между элементами множества X называется тождественным, если:
• ∀ x,y ∈ X справедливо утверждение: x R y и y R x => x = y.

№ 16
Может ли антисимметрическое отношение одновременно являться тождественным?
• Не может.

№ 17
Может ли антирефлексивное отношение одновременно являться антисимметричным?
• Может.

№ 18
Какими свойствами обладает следующее отношение: “число x не меньше числа y” - на множестве натуральных чисел?
• Рефлексивность, тождественность, транзитивность, полнота.

№ 19
Отношение называется отношением квазипорядка, если оно обладает свойствами:
• рефлексивности и транзитивности.

№ 20
Отношение называется отношением порядка, если оно обладает свойствами:
• рефлексивности, тождественности и транзитивности.

№ 21
Отношение называется отношением эквивалентности, если оно обладает свойствами:
• рефлексивности, симметричности и транзитивности.

№ 22
Какие из отношений являются отношениями строгого порядка?
• “Oтрезок x длиннее отрезка y”.
• “x старше по возрасту, чем y”.

№ 23
Какие из отношений являются отношениями эквивалентности?
• “х и y - оба учатся в ТУСУРе”.

№ 24
Пусть имеется подмножество X′⊂ X, где X - множество, для элементов которого определено отношение порядка. Как называется элемент x∈X, предшествующий всем элементам множества X′, если он может и не принадлежать множеству X′?
• Минорантой множества X′.

№ 25
Решите систему уравнений:
{A∩X=B,
A∪X=C,
где А, В и С – данные множества и В⊆А⊆С.
• X = B U C \\ A.

Тема 2. Теория графов

№ 26
Какой из способов задания графов является верным?
а) Граф G задается множеством точек (вершин) X={x1,..xn} и соответствия G(х), которое показывает, как между собой связаны вершины.
б) Граф G задается множеством точек (вершин) X={x1,..xn} и множеством линий (ребер) A={a1,..,a m}, соединяющих между собой все или часть этих точек.
• Оба способа верны.

№ 27
Что означает запись g(xi, xj) при описании графа?
• Запись g(xi, xj) говорит, что ребро g инцидентно вершинам xi, xj и вершины xi, xj инцидентны ребру g.

№ 28
Какие две вершины в графе называются смежными?
• Две вершины xi, xj называются смежными, если они определяют ребро графа.

№ 29
Что такое ноль-граф?
• Ноль-графом называется граф, состоящий из изолированных вершин.

№ 30
Какое ребро графа называется ориентированным?
• Ребро графа называется ориентированным, если порядок расположения его концов (направление стрелок) в графе является существенным.

№ 31
Какой граф называется смешанным?
• Граф называется смешанным, если он содержит как ориентированные, так и неориентированные ребра.

№ 32
Граф U(x), ребрами которого являются всевозможные пары g(xi, xj) для двух возможных xi, xj ∈ X, i≠j называется:
• полным неориентированным графом.

№ 33
Что такое элементарная цепь?
• Цепь, в которой ни одна из вершин не повторяется.

№ 34
Для каких графов определены такие понятия, как путь и контур?
• Для ориентированных графов.

№ 35
Определение симметрического графа?
• Граф называется симметрическим, если любые две смежные вершины графа xi, xj соединены неориентированными ребрами.
• Граф называется симметрическим, если любые две смежные вершины графа xi, xj соединены противоположно ориентированными дугами.

№ 36
Какой граф изображен на рисунке справа по отношению к графу, изображенному на рисунке слева?
#ris36.JPGris
• Частичный граф.

№ 37
Какой граф изображен на рисунке справа по отношению к графу, изображенному на рисунке слева?
Частичный подграф
• Частичный подграф.

№ 38
Какие вершины называются связными?
• Две вершины xi, xj называются связными, если существует цепь S с концами xi, и xj.

№ 39
Сколько компонент сильной связности имеет граф, изображенный на рисунке?
Компоненты сильной связности
• Две.

№ 40
Какой граф называется деревом?
• Деревом называется конечный связный неориентированный граф, состоящий по крайней мере из двух вершин и не содержащий циклов.

№ 41
Какой из двух графов, изображенных на рисунке, является плоским?
Плоский граф
• Только а).

№ 42
Какие из графов, изображенных на рисунке, являются изоморфными?
Изоморфный граф
• Все графы изоморфны.

№ 43
Как должен выглядеть граф G(X), соответствующий рефлексивному отношению?
• Граф G(X) должен иметь петлю в каждой своей вершине.

№ 44
Как должен выглядеть граф G(X), соответствующий антисимметричному отношению?
• Все ребра графа G(X) должны быть ориентированными.

№ 45
Как должен выглядеть граф G(X), соответствующий транзитивному отношению?
• Граф G(X) должен обладать следующими свойствами: для любой пары ребер (дуг) графа (xi, xj), (xj, xk) должно иметься замыкающее ребро (дуга) (xi, xk).

№ 46
Как должен выглядеть граф G(X), соответствующий антирефлексивному отношению?
• Граф G(X) ни в одной из вершин не должен иметь петли.

№ 47
Как должен выглядеть граф G(X), соответствующий симметричному отношению?
• Все ребра графа G(X) должны быть неориентированными.

№ 48
Как должен выглядеть граф G(X), соответствующий тождественному отношению?
• Граф G(X) должен быть ориентированным и иметь петлю в каждой своей вершине.

№ 49
Какому отношению соответствует изображенный на рисунке граф?
Отношение квазипорядка
• Отношению квазипорядка.

№ 50
Какому отношению соответствует изображенный на рисунке граф?
Отношение строгого порядка
• Отношению строгого порядка.

№ 51
Какая матрица задается описанным ниже способом?
Пусть g1,...,gm – дуги, а x1,...,xn – вершины ориентированного графа G(X). Матрица S = || sij || (i = 1, …, n – номер вершины графа, j = 1, …, m – номер дуги графа), такая что:
sij= {1, если gj исходит из xi,
-1, если gj заходит в xi,
0, если gj не инцидентна xi,
• Матрица инциденций для дуг.

№ 52
Какая матрица задается описанным ниже способом?
Пусть g1,...,gm – дуги, а x1,...,xn – вершины неориентированного графа G(X). Матрица В = || bij || (i = 1, …, m; j = 1, …, m, где m – число ребер графа), такая что:
bij={1, если ребра gi и gj имеют общий конец,
0, в противном случае.
• Матрица смежности ребер.

№ 53
Какой граф называется пересечением двух графов G1(X) и G2(X), заданных на одном и том же множестве вершин?
• Граф, состоящий из ребер, принадлежащих и G1(X), и G2(X).

№ 54
Какой граф называется композицией двух графов G1(X) и G2(X), заданных на одном и том же множестве вершин?
• Граф, у которого множество вершин, смежных с вершиной xi, состоит из всех вершин, достижимых из xi цепью длины два, первое ребро которой принадлежит G2(X), а второе – G1(X).

№ 55
Какой граф называется суммой двух графов G1(X) и G2(X), заданных на одном и том же множестве вершин?
• Граф, состоящий из ребер, принадлежащих G1(X), либо G2(X).

№ 56
Какой граф называется суммой двух графов G1(X) и G2(X), заданных на различных множествах вершин?
• Граф, для которого справедливо Х = Х1 ∪ Х2 и G(xj) = G1(xj) ∪ G2(xj).

№ 57
Сколько компонент связности будет иметь граф, являющийся декартовым произведением двух графов, изображенных на рисунке?
Декартовое произведение двух графов
• Две.

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

№ 59
На рисунке изображены два графа и одна из их композиций G(X). Какая композиция изображена на рисунке?
Композиция
• G(X)=G2(G1(X)).

№ 60
Закончите фразу: “В конечном графе число вершин с нечетной степенью...”
• четно.

№ 61
Граф, степени всех вершин в котором равны, называется:
• однородным.

№ 62
Что для ориентированного графа означает формула:
Полустепень исхода вершины
• Полустепень исхода вершины xi равна сумме числа дуг, входящих во все вершины графа из вершины xi.

№ 63
Формула
Расстояние между вершинами
для неориентированного графа характеризует:
• Расстояние между вершинами xi и xj.

№ 64
Формула
Отклоненность вершины
для ориентированного графа характеризует:
• Отклоненность вершины xi.

№ 65
Формула
Радиус графа
для ориентированного графа характеризует:
• Радиус графа.

№ 66
Формула
Отклонение вершины
для ориентированного графа характеризует:
• Отклонение вершины xi от вершины xj.

№ 67
Формула
Удаленность вершины
для неориентированного графа характеризует:
• Удаленность вершины xi.

№ 68
Дана матрица отклонений:
 X1X2X3X4
X14231
X25221
X33243
X44115
Каков радиус графа?
• 2.

№ 69
Дана матрица отклонений:
 X1X2X3X4
X14221
X23213
X32122
X44314
Каков диаметр графа?
• 4.

№ 70
Дана матрица отклонений:
 X1X2X3X4
X14231
X25221
X33243
X44115
Какие из вершин графа являются периферийными?
• X1.

№ 71
Дана матрица отклонений:
 X1X2X3X4
X14221
X23213
X32122
X44314
Какая из вершин графа является центром?
• X3.

№ 72
На рисунке изображен граф. Каждое ребро графа имеет вес, обозначенный соответствующим числом. С помощью алгоритма Дейкстры определите все кратчайшие пути от вершины X1 ко всем остальным вершинам.
Определение всех кратчайшие путей от вершины
• X2 – 8, X3 – 8, X4 – 5, X5 – 6.

№ 73
Конечный связный неориентированный мультиграф является эйлеровым графом тогда и только тогда:
• когда в нем отсутствуют вершины нечетной степени.

№ 74
В связном графе будет существовать эйлерова цепь тогда и только тогда:
• когда в нем все вершины имеют четную степень, за исключением начальной и конечной вершин.

№ 75
В конечном связном неориентированном графе G(X) с k вершинами нечетной степени минимальное число непересекающихся по ребрам цепей, покрывающих G(X) равно:
• k/2.

№ 76
Чтобы в конечном ориентированном графе существовал эйлеров цикл (контур), необходимо и достаточно, чтобы полустепени исхода и захода вершин этого графа по входящим и исходящим дугам удовлетворяли следующему соотношению:
• m´(xi)=m´´(xj), ∀xi∈X.

№ 77
В полном конечном графе всегда существует:
• Гамильтонов путь.

№ 78
Гамильтоновой цепью в неориентированном графе называется:
• цепь, проходящая через каждую его вершину один и только один раз.

№ 79
Пусть G(X) – неориентированный граф, имеющий n вершин, m ребер и r компонент связности. Цикломатическим числом графа G называется число ν(G)=
• m – n + r.

№ 80
Числом внутренней устойчивости можно назвать:
• наибольшее количество вершин графа, не смежных между собой.

№ 81
Числом внешней устойчивости можно назвать:
• наименьшее количество вершин графа, которые в совокупности смежны со всеми остальными вершинами.

№ 82
Чему равно число внутренней устойчивости для графа, имеющего вид куба?
• 4.

№ 83
Чему равно число внешней устойчивости для графа, имеющего вид куба?
• 2.

№ 84
Чему равен радиус графа, имеющего вид куба?
• 3.

№ 85
Чему равно число внутренней устойчивости для графа, имеющего вид октаэдра?
• 2.

№ 86
Чему равно число внешней устойчивости для графа, имеющего вид октаэдра?
• 2.

№ 87
Чему равен радиус графа, имеющего вид октаэдра?
• 2.

№ 88
Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
• Нет.

№ 89
Каково число ребер в полном неориентированном графе с n вершинами?
• n(n-1)/2.

Тема 3. Алгебра высказываний, булевы функции

№ 90
Какие из графов трех правильных многогранников имеют эйлеровы циклы?
• Октаэдр.

№ 91
Перечислите по порядку операции над высказываниями, имеющие следующие обозначения: А→В, ∨(А,В), А∼В, А, ∧(А,В) ?
• Импликация, дизъюнкция, эквивалентность, отрицание, конъюнкция.

№ 92
Высказывание, которое истинно тогда и только тогда, когда А и В оба истинны или оба ложны, называется:
• эквивалентностью высказываний А и В.

№ 93
Высказывание, истинное только в том случае, когда А и В истинны, называется:
• конъюнкцией высказываний А и В.

№ 94
Высказывание, которое истинно, когда А ложно, и ложно, когда А истинно, называется:
• отрицанием высказывания А.

№ 95
Высказывание, которое ложно тогда и только тогда, когда А истинно, а В ложно, называется:
• импликацией высказываний А и В.

№ 96
Высказывание, которое истинно, если хотя бы одно из высказываний А или В является истинным, называется:
• дизъюнкцией высказываний А и В.

№ 97
Являются ли равносильными следующие формулы: ∧((X→Y),(X→Z)) и X→(∧(Y,Z)) ?
• Да.

№ 98
Являются ли равносильными следующие формулы: X→(Y→Z) и (∧(X,Y))→ Z) ?
• Нет.

№ 99
Чему равно количество входных наборов для булевой функции n переменных?
• 2n.

№ 100
Чему равно количество различных булевых функций n переменных, задаваемых k различными наборами?
• 2k.

№ 101
Какая элементарная булева функция двух переменных задается следующей таблицей истинности?
x10011
x20101
f(x1,x2)0111
• Дизъюнкция.

№ 102
Какая элементарная булева функция двух переменных задается следующей таблицей истинности?
x10011
x20101
f(x1,x2)0110
• Сложение по модулю 2.

№ 103
Какая из приведенных ниже формул, характеризующих свойства элементарных функций, неверна?
Свойства элементарных функций
• 5.

№ 104
Функция f(x1, x2, x3) принимает единичные значения на наборах №№ 0, 1, 3, 4, 6, 7. Какое количество конъюнкций будет иметь совершенная ДНФ этой функции?
• Шесть.

№ 105
Функция f(x1, x2, x3) принимает единичные значения на наборах №№ 0, 2, 4, 5, 7. Какое количество дизъюнкций будет иметь совершенная КНФ этой функции?
• Три.

№ 106
Функция f(x1, ...,xn) называется не сохраняющей ноль, если она:
• на наборе из нулей принимает значение 1.

№ 107
Функция f(x1, ...,xn) называется сохраняющей единицу, если она:
• на наборе из единиц принимает значение 1.

№ 108
Является ли самодвойственной следующая элементарная булева функция?
x10011
x20101
f(x1,x2)0100
• Нет.

№ 109
Является ли монотонной следующая элементарная булева функция?
x10011
x20101
f(x1,x2)0101
• Да.

№ 110
Является ли линейной следующая элементарная булева функция?
x10011
x20101
f(x1,x2)0010
• Нет.

№ 111
Для того, чтобы система булевых функций была полна, необходимо и достаточно, чтобы она содержала функцию:
• не сохраняющую 0; не сохраняющую 1; несамодвойственную; немонотонную; нелинейную.

№ 112
Является ли полной система булевых функций, состоящая из сложения по модулю два, константы 1 и эквивалентности?
• Нет.

№ 113
Является ли полной система булевых функций, состоящая из константы 0 и импликации?
• Да.

№ 114
Является ли полной система булевых функций, состоящая из одной функции – стрелки Пирса?
• Да.

№ 115
Какой термин математической логики определяется следующей формулой:
Импликант,
где все xij (j = 1,...,r) – различны, и если выполнено соотношение Ui→f(x1,...,xn)≡1 ?
• Импликант.

№ 116
Какая ДНФ получается дизъюнкций всех простых импликантов функции f(x1,...,xn) ?
• Сокращенная ДНФ.

№ 117
В чем состоит операция неполного склеивания?
• В замене выражения ∨(Ax,Ax) на ∨(∨(Ax,Ax), A).

№ 118
В чем состоит операция поглощения?
• В замене выражения ∨(AB,A) на A.

№ 119
Как называется импликант функции f(x1,...,xn), обладающий следующим свойством: элементарная конъюнкция, получающаяся из него удалением любой буквы, не является импликантом функции?
• Простой импликант.

№ 120
Как называется импликант функции f(x1,...,xn), обладающий следующим свойством: существует набор α=(α1,...,αn), на котором этот импликант обращается в 1, а все остальные импликанты сокращённой ДНФ - в ноль?
• Ядерный импликант.

№ 121
Что означает термин “тупиковая ДНФ” функции f (x1,...,xn)?
• ДНФ, из которой нельзя удалить ни одного простого импликанта.

№ 122
Перечислите по порядку этапы минимизации ДНФ.
• Нахождение сокращенной ДНФ, нахождение тупиковых ДНФ, выбор минимальной ДНФ.

№ 123
Верно ли утверждение: “Дизъюнкция всех ядерных импликантов любой функции f(x1,...,xn) представляет собой ее минимальную ДНФ”?
• Нет.

№ 124
Как обозначаются столбцы импликантной таблицы при минимизации ДНФ методом Квайна?
• Элементарными конъюнкциями.

№ 125
Функция f(x1,x2,x3) принимает единичные значения на наборах №№ 1, 2, 3, 5, 6. Сколько букв будет иметь совершенная ДНФ данной функции?
• Пятнадцать.

№ 126
Функция f(x1,x2,x3) принимает единичные значения на наборах №№ 0, 2, 5, 6, 7. Сколько букв будет иметь сокращенная ДНФ данной функции?
• Восемь.

№ 127
Функция f(x1,x2,x3) принимает единичные значения на наборах №№ 1, 2, 5, 6, 7. Сколько тупиковых ДНФ будет найдено на этапе минимизации данной функции?
• Две.

№ 128
Функция f(x1,x2,x3) принимает единичные значения на наборах №№ 0, 1, 3, 6, 7. Сколько букв будет иметь минимальная ДНФ данной функции?
• Шесть.

№ 129
Функция f(x1,x2,x3) принимает единичные значения на наборах №№ 0, 2, 3, 6, 7. Какова минимальная ДНФ данной функции?
• ∨(x2,x1x3).

№ 130
Что представляет собой множество вершин графа переходов при автоматном описании некоего объекта?
• Множество внутренних состояний системы.

№ 131
Для какого автомата составляется таблица переходов?
• Для автомата с памятью.

№ 132
Какой элемент при построении логической схемы имеет следующее обозначение?
Конъюнкция
• Конъюнкция.

№ 133
Минимальная ДНФ имеет вид: ∨(x3,x1)x2. Сколько логических элементов будет иметь логическая схема данной минимальной ДНФ в базисе, состоящем только из элементов {V,   }?
• Четыре.

№ 134
Минимальная ДНФ имеет вид: ∨(x3,x1)x2. Сколько логических элементов будет иметь логическая схема данной минимальной ДНФ в базисе, состоящем только из элементов {∧( , ),   }?
• Шесть.

№ 135
Какое множество называется полем предиката P(x1, x2,.., xn)?
• Множество M1×M2×...Mn (декартово произведение) множеств значений предметных переменных.

№ 136
Применимы ли к предикатам все операции алгебры высказываний?
• Да.

№ 137
Что означает символ ∀ ?
• Квантор общности.

№ 138
Высказывание, истинное только в том случае, когда предикат Р (х) истинен хотя бы для одного предмета из поля М, обозначается выражением:
• ∃xP(x).

№ 139
Являются ли равносильными следующие формулы логики предикатов: ∀xW(x) и ∃xW(x) ?
• Нет.

№ 140
Дано высказывание А: “Существуют четные простые числа”. Укажите отрицание высказывания А:
• “любое простое число нечетно”

№ 141
Является ли тавтологией формула: ∧((X→Y),X) → Y ?
• Да.


на главную база по специальностям база по дисциплинам статьи