Для подготовки к экзамену (Архив шпаргалок для РК и экзамена)

Задачи для подготовки к экзамену по курсу ”Дискретная математика”ИУ5, 3 семестр. Лектор - Ткачев С.Б.1) На множестве упорядоченных пар (x, y), x, y ∈ R, задано отношение τ по правилу(x1 , y1 ) τ (x2 , y2 ) ⇔ x21 − 2y12 = x22 − 2y22 .Показать, что τ — отношение эквивалентности.√Указать классы эквивалентности. Для точек (0, 0) и ( 3, 1) изобразить классы эквивалентности графически.2) На множестве M = {(x, y) | x, y ∈ R} упорядоченных пар задано отношение π поправилу(x1 , y1 ) π (x2 , y2 ) ⇔ x1 ≤ x2 и y1 ≥ y2 .Показать, что π — отношение порядка.

Установить, является ли упорядоченное множество (M, π) индуктивным?Найти множество нижних и верхних граней множества {A, B, C}, где A = (1, 3),B = (2, 1), C = (1, 1). Указать inf{A, B} и sup{A, B}, если последние существуют. Привести графическую иллюстрацию.3) На множестве N натуральных чисел определено отношение делимости | по правилуm | n ⇔ m делит нацело n.Показать, что | есть отношение порядка.Установить, будет ли упорядоченное множество (N, |) индуктивным? Существуют лиA ⊂ N, такие, что (A, |) будут индуктивными?4) Для бинарного отношенияρ = {(x, y) | x, y ∈ {1, 2, 3, 4, 5}, x + y ≤ 6}исследовать свойства (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность).5) Показать, что в общем случаеρ ◦ (σ ∩ τ ) ⊆ (ρ ◦ σ) ∩ (ρ ◦ τ )для бинарных отношений ρ, σ и τ на некотором множестве M , однако равенство не имеетместа.

Привести пример трех бинарных отношений на множестве {1, 2, 3}, для которыхимеет место строгое включение.6) Пусть M — некоторое множество. Является ли алгебра A = (2M , ∩, ∪) полукольцом?Кольцом?Если A является полукольцом (но не кольцом), установить, будет ли A замкнутымполукольцом?Если A является кольцом, установить, есть ли в A делители нуля? Является ли кольцоA полем?7) Пусть M — некоторое множество. Является ли алгебра A = (2M , 4, ∩) кольцом?Полем? Если A является кольцом, установить, есть ли в A делители нуля?8) На множестве R \ {0} определена операция по правилуa b = 2ab.1Установить, является ли алгебра (M, ) полугруппой? Моноидом? Группой?9) В полукольце S[0,1] = ([0, 1], ⊕, ), носителем которого является отрезок [0, 1]числовой прямой, x ⊕ y = max{x, y}, x y = max{x, y} решить систему уравненийx1 = 0,3x1 ⊕ 0,2x2 ⊕ 0,1,x2 = 0,4x1 ⊕ 0,3x2 ⊕ 0,2.10) В полукольце S = (2M , ∪, ∩), где M = [0, 1] — отрезок числовой прямой, решитьсистему уравненийx1 = Ax1 + Bx2 + C,x2 = Dx1 + Ex2 + F.Здесь A = [0, 0,5], B = [0,2, 0,9], С = [0,4, 0,7], D = [0, 0,5], E = [0,3, 0,8], F = [0,4, 0,7].11) Показать, что полукольцоD12 = (Дел(12), ⊕ , ),где Дел(12) — множество делителей числа 12, ⊕ — операция вычисления наименьшегообщего кратного, — операция вычисления наибольшего общего делителя, является замкнутым.Представить множество Дел(12) с естественным порядком идемпотентного полукольцадиаграммой Хассе.Установить, сравнимы ли число 3 и наименьшее решение уравнения x = 2 x ⊕ 4?12) В группе подстановок S7 решить уравнение(1 3 2)(7 5 4)X(2 4 6)2009 = (2 3 5).13) В поле Z7 решить систему линейных уравнений 1x1 + 3x2 + 2x3 = 4,3x1 + 5x2 + 3x3 = 4,2x1 + 2x2 + 4x3 = 2.13) В группе Z11 найти циклическую подгруппу H, порожденную элементом a = 5.Используя полученный результат, найти элемент, обратный к 5.Решить уравнение 5 11 x 11 6 = 7.14) Для ориентированного графа G = (V, E), где V = {v1 , v2 , v3 , v4 , v5 , v6 },E = {(v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v3 , v4 ), (v4 , v6 ), (v5 , v4 ), (v5 , v6 ), (v6 , v1 ), (v2 , v4 ), (v3 , v5 )}, выполнить поиск в глубину из вершины v5 .

Привести протокол работы алгоритма (работу состеком, классификацию дуг в порядке их обработки, контуры в порядке их нахождения).Считать, что вершины в списке смежности упорядочены в порядке возрастания номеров.15) Выполнить поиск в ширину из вершины v1 для ориентированного графаG = (V, E), где V = {v1 , v2 , v3 , v4 , v5 , v6 }, E =(v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v2 , v4 ),(v3 , v5 ), (v4 , v5 ), (v5 , v6 ), (v6 , v4 ) .Построить два различных глубинных остовных леса c корнем v4 для неориентированного графа G = (V, E), где V = {v1 , v2 , v3 , v4 , v5 , v6 }, E = {{v1 , v2 }, {v1 , v3 }, {v2 , v3 }, {v3 , v4 },{v4 , v5 }, {v4 , v6 }, {v5 , v6 }, {v6 , v1 }}. Записать списки смежности, при которых проводилисьпоиски в глубину и описать работу со стеками.

Классификацию ребер для каждого варианта отобразить графически.216) Решив систему уравнений в полукольце B, вычислить матрицу достижимостиориентированного графа G = (V, E), где V = {v1 , v2 , v3 , v4 , v5 , v6 },E = (v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v4 , v2 ), (v3 , v5 ), (v4 , v5 ), (v5 , v6 ), (v6 , v3 ), (v6 , v4 ) .

C использованием матрицы достижимости найти его бикомпоненты.17) Решив систему уравнений в полукольце R+ , вычислить матрицы стоимости взвешенного ориентированного графа G = (V, E), где V = {v1 , v2 , v3 , v4 , v5 , v6 },E = {(v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v3 , v4 ), (v4 , v6 ), (v5 , v4 ), (v5 , v6 ), (v6 , v1 ), (v2 , v4 )}, а весоваяфункция которого определена следующим образом: ϕ((v1 , v2 )) = 1, ϕ((v1 , v3 )) = 5,ϕ((v2 , v3 )) = 3, ϕ((v3 , v4 )) = 2, ϕ((v4 , v6 )) = 3, ϕ((v5 , v4 )) = 1, ϕ((v5 , v6 )) = 2, ϕ((v6 , v1 )) = 1,ϕ((v2 , v4 )) = 7.18) Решив систему уравнений в полукольце R+ , вычислить матрицу стоимости взвешенного ориентированного графа, заданного матрицей меток дуг:2 O O O O 1 2 3 2 O 6 O  O O O 1 5 O  2 O O O 2 O  O 1 O O O 7 O 3 O 1 O OЗдесь O — нуль полукольца R+ .19) Построить конечный автомат по регулярному выражению ((aba)∗ + bab)∗ и детерминизировать его.20) Построить конечный автомат, допускающий множество всех цепочек в алфавите{a, b}, кроме цепочки aab.21) Построить конечный автомат, допускающий множество всех цепочек в алфавите{0, 1}, не содержащих подцепочки 010.22) Решить систему линейных уравнений с регулярными коэффициентамиx1 = ax1 + bx2 + b,x2 = bx1 + ax2 + λ.Построить конечный автомат, допускающий язык, заданный регулярным выражением x2 .23) Доказать, что множество всех цепочек в алфавите {a, b}, содержащих каждая одинаковое число символов a и b, нерегулярно.24) Найти язык, допускаемый конечным автоматомM = {{a, b}, {q1 , q2 , q3 , q4 }, {q1 }, {q2 , q4 }, δ(q1 , a) = {q1 , q3 }, δ(q1 , b) = {q2 },δ(q2 , b) = {q1 }, δ(q2 , a) = {q3 , q4 }, δ(q3 , a) = {q4 }, δ(q4 , b) = {q3 }}.25) С использованием карты Карно выписать все тупиковые и найти минимальныеДНФ для функцииf = (0, 1, 2, 3, 7, 8, 10, 12, 13, 15).Для функции f указаны номера тех наборов, на которых функция принимает значение 1.26) С использованием карты Карно перечислить все тупиковые ДНФ и найти минимальные ДНФ для функцииf = (0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0).327) С использованием карты Карно найти все тупиковые ДНФ и указать минимальныеДНФ для функцииf = (x1 ∨ x2 ∨ x3 )(x̄1 ∨ x̄2 ∨ x̄3 ).28) Выяснить полноту множества F булевых функцийf1 = {0, 1, 2, 4, 7},f2 = {1, 3, 5}.Если множество не является полным, дополнить его такой булевой функцией h, чтобымножество F 0 = {f1 , f2 , h} было полным.Реализовать коньюнкцию в виде схемы из функциональных элементов над F или F 0 .Дополнительную функцию h следует использовать только для тех построений, где использование f1 и f2 невозможно.Для функций указаны номера наборов, на которых она принимает значение 1.29) Установить, можно ли выразить константы 0, 1 и коньюнкцию формулами надмножеством булевых функций F = {f, }, гдеf = (1 1 0 1 1 0 1 1)Если можно, привести эти формулы.

Если нельзя, дополнить множество F так, чтобы этоможно было сделать и привести указанные формулы над дополненным множеством.Выразить булеву функцию f = (1 1 1 0) формулой над F или дополненным множеством.30) Проверить, является ли полным множество булевых функций F = {∼, 0}. В случаенеполноты дополнить множество F так, чтобы оно стало полным. Выразить формулойнад множеством F (или дополненым множеством) булеву функцию x1 ∨ x1 x2 .4.