Для студентов МГТУ им. Н.Э.Баумана по предмету Дискретная математикаДискретная математика ответы на экзаменационные вопросы, решенные экзаменационные задачи.Дискретная математика ответы на экзаменационные вопросы, решенные экзаменационные задачи.
5,0051
2025-01-302025-01-30СтудИзба
Ответы к экзамену: Дискретная математика ответы на экзаменационные вопросы, решенные экзаменационные задачи.
Описание
Вопросы для подготовки к экзамену
Дискретная математика, ФН12, 2ВО, 4 семестр.
1. Теорема о связи между отношением эквивалентности и разбиением множества (с
доказательством).
2. Теорема о монотонности непрерывного отображения (с доказательством). Пример
монотонного отображения, не являющегося непрерывным.
3. Неподвижная точка отображения. Теорема о неподвижной точке (с доказательством).
4. Что называют n-арной (n-местной) операцией на множестве A. Какую операцию
называют ассоциативной? Какую операцию называют идемпотентной? Какую
операцию называют коммутативной? Какой элемент множества A называют нулем
относительно данной операции "*"? Какой элемент множества A называют
нейтральным элементом относительно данной операции "*"?
5. Полугруппа. Моноид. Группа. Определение полугруппы. Определение моноида.
Определение группы.
6. Группа. Решение уравнений a*x=b и x*a=b в группе (G,*) (с док-вом).
7. Кольцо. Определение кольца. Теорема о тождествах кольца (аннулирующем свойстве
нуля, свойстве обратного по сложению при умножении, дистрибутивности вычитания
относительно умножения) (с док-вом).
8. Область целостности. Определение области целостности. Теорема о конечной области
целостности (с доказательством).
9. Смежные классы подгруппы по элементу.
10. Отношение эквивалентности по равенству смежных классов (с док-вом свойств).
11. Теорема о равномощности смежного класса подгруппе (с док-вом).
12. Теорема Лагранжа. Свойство группы простого порядка (с док-вом). Признак
неразложимости конечной группы (с док-вом).
13. Полукольцо. Определение полукольца. Идемпотентное полукольцо. Примеры
полуколец (с доказательством свойств).
14. Естественный порядок идемпотентного полукольца (с доказательством
рефлексивности, антисимметричности и транзитивности). Примеры.
15. Теорема о точной верхней грани конечного подмножества идемпотентного полукольца
(с док-вом).
16. Замкнутое полукольцо. Теорема о замкнутости конечного идемпотентного полукольца
(с док-вом).
17. Непрерывность операции сложения в замкнутом полукольце (формулировка).
Непрерывность линейного отображения y=a*x+b (доказательство).
18. Теорема о наименьшем решении линейного уравнения в замкнутом полукольце (с док-
вом).
19. Решение систем линейных уравнений в замкнутых полукольцах. Метод
последовательного исключения переменных.
20. Неориентированный граф, ребро, степень вершины неориентированного графа, цепь,
простая цепь, цикл, подграф, остовный подграф, отношение достижимости в
неориентированном графе, компонента связности в неориентированном графе;21. Ориентированный граф, дуга, полустепень захода вершины ор. графа, полустепень
исхода, степень вершины, путь, простой путь, контур, подграф, остовный подграф,
ассоциированный неор. граф, отношение достижимости в ориентированном графе,
бикомпонента, компонента, компонента слабой связности.
22. Поиск в ширину (алгоритм волнового фронта и поиск в размеченном орграфе).
23. Поиск в глубину в неориентированном и в ориентированном графе.
24. Деревья. Бинарные деревья. Теорема о высоте полного бинарного дерева (с док-вом).
Задача сортировки. Оценка сложности задачи сортировки.
25. Ориентированный граф, взвешенный над полукольцом, метка дуги, метка пути,
стоимость прохождения между парой вершин.
26. Задача о путях во взвешенных графах. Утверждение о вычислении стоимости
прохождения по всем путям длины l (с доказательством).
27. Полукольцо языков, его замкнутость (с доказательством выполнения аксиом
полукольца и доказательством замкнутости).
28. Регулярные языки. Индуктивная процедура порождения регулярных языков.
Регулярные выражения. Полукольцо регулярных языков. Незамкнутость полукольца
регулярных языка.
29. Конечные автоматы (КА). Представление автомата ориентированным графом,
взвешенным над полукольцом регулярных языков. Нахождение языка, допускаемого
КА.
30. Теорема Клини (с доказательством).
31. Детерминизация конечных автоматов. Теорема о детерминизации (без доказательства).
Алгоритм детерминизации.
32. Теорема о регулярности дополнения регулярного языка (с док-вом). Регулярность
пересечения, разности и симметрической разности регулярных языков.
33. Конечные детерминированные автоматы, постановка задачи о минимизации,
эквивалентные состояния, теорема о минимальном автомате.
Дискретная математика, ФН12, 2ВО, 4 семестр.
1. Теорема о связи между отношением эквивалентности и разбиением множества (с
доказательством).
2. Теорема о монотонности непрерывного отображения (с доказательством). Пример
монотонного отображения, не являющегося непрерывным.
3. Неподвижная точка отображения. Теорема о неподвижной точке (с доказательством).
4. Что называют n-арной (n-местной) операцией на множестве A. Какую операцию
называют ассоциативной? Какую операцию называют идемпотентной? Какую
операцию называют коммутативной? Какой элемент множества A называют нулем
относительно данной операции "*"? Какой элемент множества A называют
нейтральным элементом относительно данной операции "*"?
5. Полугруппа. Моноид. Группа. Определение полугруппы. Определение моноида.
Определение группы.
6. Группа. Решение уравнений a*x=b и x*a=b в группе (G,*) (с док-вом).
7. Кольцо. Определение кольца. Теорема о тождествах кольца (аннулирующем свойстве
нуля, свойстве обратного по сложению при умножении, дистрибутивности вычитания
относительно умножения) (с док-вом).
8. Область целостности. Определение области целостности. Теорема о конечной области
целостности (с доказательством).
9. Смежные классы подгруппы по элементу.
10. Отношение эквивалентности по равенству смежных классов (с док-вом свойств).
11. Теорема о равномощности смежного класса подгруппе (с док-вом).
12. Теорема Лагранжа. Свойство группы простого порядка (с док-вом). Признак
неразложимости конечной группы (с док-вом).
13. Полукольцо. Определение полукольца. Идемпотентное полукольцо. Примеры
полуколец (с доказательством свойств).
14. Естественный порядок идемпотентного полукольца (с доказательством
рефлексивности, антисимметричности и транзитивности). Примеры.
15. Теорема о точной верхней грани конечного подмножества идемпотентного полукольца
(с док-вом).
16. Замкнутое полукольцо. Теорема о замкнутости конечного идемпотентного полукольца
(с док-вом).
17. Непрерывность операции сложения в замкнутом полукольце (формулировка).
Непрерывность линейного отображения y=a*x+b (доказательство).
18. Теорема о наименьшем решении линейного уравнения в замкнутом полукольце (с док-
вом).
19. Решение систем линейных уравнений в замкнутых полукольцах. Метод
последовательного исключения переменных.
20. Неориентированный граф, ребро, степень вершины неориентированного графа, цепь,
простая цепь, цикл, подграф, остовный подграф, отношение достижимости в
неориентированном графе, компонента связности в неориентированном графе;21. Ориентированный граф, дуга, полустепень захода вершины ор. графа, полустепень
исхода, степень вершины, путь, простой путь, контур, подграф, остовный подграф,
ассоциированный неор. граф, отношение достижимости в ориентированном графе,
бикомпонента, компонента, компонента слабой связности.
22. Поиск в ширину (алгоритм волнового фронта и поиск в размеченном орграфе).
23. Поиск в глубину в неориентированном и в ориентированном графе.
24. Деревья. Бинарные деревья. Теорема о высоте полного бинарного дерева (с док-вом).
Задача сортировки. Оценка сложности задачи сортировки.
25. Ориентированный граф, взвешенный над полукольцом, метка дуги, метка пути,
стоимость прохождения между парой вершин.
26. Задача о путях во взвешенных графах. Утверждение о вычислении стоимости
прохождения по всем путям длины l (с доказательством).
27. Полукольцо языков, его замкнутость (с доказательством выполнения аксиом
полукольца и доказательством замкнутости).
28. Регулярные языки. Индуктивная процедура порождения регулярных языков.
Регулярные выражения. Полукольцо регулярных языков. Незамкнутость полукольца
регулярных языка.
29. Конечные автоматы (КА). Представление автомата ориентированным графом,
взвешенным над полукольцом регулярных языков. Нахождение языка, допускаемого
КА.
30. Теорема Клини (с доказательством).
31. Детерминизация конечных автоматов. Теорема о детерминизации (без доказательства).
Алгоритм детерминизации.
32. Теорема о регулярности дополнения регулярного языка (с док-вом). Регулярность
пересечения, разности и симметрической разности регулярных языков.
33. Конечные детерминированные автоматы, постановка задачи о минимизации,
эквивалентные состояния, теорема о минимальном автомате.
”Дискретная математика.”, 3-й курс, 5 семестр, ИУ-3, 2020 г. Задачи для подготовки к экзамену
1. На множестве упорядоченных пар (x, y), x, y ∈ R, задано отношение σ по правилу
(x1,y1)τ (x2,y2)⇔x21 −y12 =x2 −y2.
Показать, что σ — отношение эквивалентности. Указать классы эквивалентности. Для √
точек (0, 0), (1, 3) и изобразить классы эквивалентности графически.
2. На множестве упорядоченных пар (x, y), x, y ∈ R, задано отношение ρ по правилу (x1,y1)ρ(x2,y2)⇔x1 ≥x2 иy1 ≤y2.
Показать, что ρ — отношение порядка. Установить, является ли этот порядок линейным?
Для точек A(3,1) и B(1,3) найти множество нижних и верхних граней множества {A,B}. Указать inf{A, B} и sup{A, B}, если последние существуют. Привести графическую иллю- страцию.
3.Длябинарногоотношенияπ={(x,y)|x,y∈[0,1],x≥2y}найтиπ−1 иρ=π−1◦π. 3
Привести графическую иллюстрацию.Исследовать свойства отношения ρ и π.
4. Пусть τ — бинарное отношение на множестве N: (a, b) τ (c, d), если и только если a ≤ c и b ≥ d; Является ли τ отношением порядка? Если да, установить, существует ли наименьший
элемент по отношению τ? Является ли этот порядок линейным?
5. Пусть в R3 задана плоскость ax + by + cz = 0. Точки с радиус-векторами r1 и r2 связаны
бинарным отношением τ, если ((r1 − r2), n) = 0, где n — нормаль к указанно— скалярное произведение векторов. Показать, что τ есть отношение эквивалентности. Что будет классом эквивалентности точки из R3?
6. Пусть на множестве P последовательностей длины 3, элементами которых являются натуральные числа, задано бинарное отношение τ: a1a2a3 τ b1b2b3, если и только если ai делит bi нацело, i = 1, 2, 3. Установите, является ли τ отношением порядка? Линейного порядка? Существует ли наименьший элемент?
7. Пусть на множестве P последовательностей длины 2, элементами которых являются целые числа (кроме нуля), задано бинарное отношение τ: a1a2 τ b1b2, если и только если ai делит bi нацело, i = 1, 2. Установите, является ли τ отношением предпорядка? порядка?
8. Пусть на множестве неотрицательных рациональных чисел определено бинарное отно- шение υ: (a/b)υ(с/d), если и только если ad ≤ bc. Показать, что υ является отношением порядка. Существует ли наименьший элемент? Является ли этот порядок линейным?
9. В поле Z7 решить систему линейных уравнений 5x1 +5x2 −2x3 =3,
5x1 +6x2 −3x3 =2,
2x1 +1x2 −3x3 =1.
10. В группе Z37 найти циклическую подгруппу H, порожденную элементом a = 7. Ис-
пользуя полученный результат, найти элемент, обратный к 3. Решить уравнение 3 ⊙37 x ⊙37 4 = 27.
11. На множестве
A={(x,y)|a,b∈R, x̸=0,y̸=0} определена операция ⋆ по правилу
(x1, y1) ⋆ (x2, y2) = (3x1x2, 5y1y2).
Является ли алгебра (A, ⋆ ) полугруппой? Моноидом? Группой?
12. Пусть M — некоторое множество. Является ли алгебра M = (2A, ∪, ∩) полукольцом?
Кольцом?
1. На множестве упорядоченных пар (x, y), x, y ∈ R, задано отношение σ по правилу
(x1,y1)τ (x2,y2)⇔x21 −y12 =x2 −y2.
Показать, что σ — отношение эквивалентности. Указать классы эквивалентности. Для √
точек (0, 0), (1, 3) и изобразить классы эквивалентности графически.
2. На множестве упорядоченных пар (x, y), x, y ∈ R, задано отношение ρ по правилу (x1,y1)ρ(x2,y2)⇔x1 ≥x2 иy1 ≤y2.
Показать, что ρ — отношение порядка. Установить, является ли этот порядок линейным?
Для точек A(3,1) и B(1,3) найти множество нижних и верхних граней множества {A,B}. Указать inf{A, B} и sup{A, B}, если последние существуют. Привести графическую иллю- страцию.
3.Длябинарногоотношенияπ={(x,y)|x,y∈[0,1],x≥2y}найтиπ−1 иρ=π−1◦π. 3
Привести графическую иллюстрацию.Исследовать свойства отношения ρ и π.
4. Пусть τ — бинарное отношение на множестве N: (a, b) τ (c, d), если и только если a ≤ c и b ≥ d; Является ли τ отношением порядка? Если да, установить, существует ли наименьший
элемент по отношению τ? Является ли этот порядок линейным?
5. Пусть в R3 задана плоскость ax + by + cz = 0. Точки с радиус-векторами r1 и r2 связаны
бинарным отношением τ, если ((r1 − r2), n) = 0, где n — нормаль к указанно— скалярное произведение векторов. Показать, что τ есть отношение эквивалентности. Что будет классом эквивалентности точки из R3?
6. Пусть на множестве P последовательностей длины 3, элементами которых являются натуральные числа, задано бинарное отношение τ: a1a2a3 τ b1b2b3, если и только если ai делит bi нацело, i = 1, 2, 3. Установите, является ли τ отношением порядка? Линейного порядка? Существует ли наименьший элемент?
7. Пусть на множестве P последовательностей длины 2, элементами которых являются целые числа (кроме нуля), задано бинарное отношение τ: a1a2 τ b1b2, если и только если ai делит bi нацело, i = 1, 2. Установите, является ли τ отношением предпорядка? порядка?
8. Пусть на множестве неотрицательных рациональных чисел определено бинарное отно- шение υ: (a/b)υ(с/d), если и только если ad ≤ bc. Показать, что υ является отношением порядка. Существует ли наименьший элемент? Является ли этот порядок линейным?
9. В поле Z7 решить систему линейных уравнений 5x1 +5x2 −2x3 =3,
5x1 +6x2 −3x3 =2,
2x1 +1x2 −3x3 =1.
10. В группе Z37 найти циклическую подгруппу H, порожденную элементом a = 7. Ис-
пользуя полученный результат, найти элемент, обратный к 3. Решить уравнение 3 ⊙37 x ⊙37 4 = 27.
11. На множестве
A={(x,y)|a,b∈R, x̸=0,y̸=0} определена операция ⋆ по правилу
(x1, y1) ⋆ (x2, y2) = (3x1x2, 5y1y2).
Является ли алгебра (A, ⋆ ) полугруппой? Моноидом? Группой?
12. Пусть M — некоторое множество. Является ли алгебра M = (2A, ∪, ∩) полукольцом?
Кольцом?
Если M является полукольцом (но не кольцом), установить, будет ли M замкнутым полу- кольцом?
Если M является кольцом, установить, есть ли в M делители нуля? Является ли кольцо M полем?
Указание: основные теоретико-множественные тождества считать доказанными.
13. Используя алгоритм Демукрона, выяснить является граф G = (V, E) сетью, если явля-
ется, то найти порядковую функцию сети G = (V, E), где
V = {v1, v2, v3, v4, v5, v6}, E = (v1, v2), (v1, v3), (v2, v3), (v2, v4), (v3, v4), (v3, v5), (v4, v5), (v3, v6), (v4, v6) .
14. Найти остовное дерево минимального веса взвешенного графа 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}},весоваяфункцияграфа: φ({v1, v2}) = 1, φ({v1, v3}) = 2, φ({v2, v3}) = 4, φ({v3, v4}) = 2, φ({v4, v5}) = 1, φ({v4, v6}) = 3, φ({v5, v6}) = 3, φ({v6, v1}) = 2
15. Построить два различных глубинных остовных леса c корнем v2 для неориентирован-
ного графа G = (V, E), где V = {v1, v2, v3, v4, v5, v6}, E = {{v1, v2}, {v1, v3}, {v2, v3}, {v3, v4}, {v4, v5}, {v4, v6 Записать списки смежности, при которых проводились поиски в глубину и описать работу со стеками. Классификацию ребер для каждого варианта отобразить графически.
16. Выполнить поиск в ширину в ориентированном графе из вершины v2. Записать списки смежности. Привести протокол работы алгоритма (работу с очередью, изменения массива меток на каждом шаге). На графе указать номера вершин, присваиваемых им в соответствии с порядком посещения при работе алгоритма. Отметить на графе кратчайшие пути из стар- товой вершины во все остальные, используя массив ”предков”, сформированный при работе алгоритма. V ={v1,v2,v3,v4,v5,v6,v7},
E = (v1, v2), (v1, v6), (v2, v3), (v2, v4), (v3, v5), (v4, v5), (v4, v1), (v5, v6), (v6, v4), (v5, v7), (v2, v7) . 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)) = 2, φ((v1,v3)) = 6, φ((v2,v3)) = 4, φ((v3,v4)) = 3, φ((v4,v6)) = 4, φ((v5,v4)) = 2, φ((v5, v6)) = 3, φ((v6, v1)) = 2, φ((v2, v4)) = 7.Изобразить граф, проверить полученное решение по графу.
18. Решив систему уравнений в полукольце R+, вычислить первый и третий столбцы матрицы стоимости взвешенного ориентированного графа, заданного матрицей меток дуг:
O5OOO3
5O4OOO
O O O 1 3 O
O 3 O O 3 O
3 2 O O O 2
O4OOOO
Здесь O — нуль полукольца R+. Изобразить граф, проверить полученное решение по
графу.
19. Построить конечный автомат, допускающий язык в алфавите {0,1}, заданный регу-
лярным выражением ((0)∗1 + 10)∗ и детерминизировать его.
20. Построить конечный автомат, допускающий все цепочки в алфавите
цепочки bca.
21. Решить систему линейных уравнений с регулярными коэффициентами
x1=bx1 +cx2 +λ, x2=ax1 +cx2 +b∗.
{a, b, c},
кроме
}
Если M является кольцом, установить, есть ли в M делители нуля? Является ли кольцо M полем?
Указание: основные теоретико-множественные тождества считать доказанными.
13. Используя алгоритм Демукрона, выяснить является граф G = (V, E) сетью, если явля-
ется, то найти порядковую функцию сети G = (V, E), где
V = {v1, v2, v3, v4, v5, v6}, E = (v1, v2), (v1, v3), (v2, v3), (v2, v4), (v3, v4), (v3, v5), (v4, v5), (v3, v6), (v4, v6) .
14. Найти остовное дерево минимального веса взвешенного графа 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}},весоваяфункцияграфа: φ({v1, v2}) = 1, φ({v1, v3}) = 2, φ({v2, v3}) = 4, φ({v3, v4}) = 2, φ({v4, v5}) = 1, φ({v4, v6}) = 3, φ({v5, v6}) = 3, φ({v6, v1}) = 2
15. Построить два различных глубинных остовных леса c корнем v2 для неориентирован-
ного графа G = (V, E), где V = {v1, v2, v3, v4, v5, v6}, E = {{v1, v2}, {v1, v3}, {v2, v3}, {v3, v4}, {v4, v5}, {v4, v6 Записать списки смежности, при которых проводились поиски в глубину и описать работу со стеками. Классификацию ребер для каждого варианта отобразить графически.
16. Выполнить поиск в ширину в ориентированном графе из вершины v2. Записать списки смежности. Привести протокол работы алгоритма (работу с очередью, изменения массива меток на каждом шаге). На графе указать номера вершин, присваиваемых им в соответствии с порядком посещения при работе алгоритма. Отметить на графе кратчайшие пути из стар- товой вершины во все остальные, используя массив ”предков”, сформированный при работе алгоритма. V ={v1,v2,v3,v4,v5,v6,v7},
E = (v1, v2), (v1, v6), (v2, v3), (v2, v4), (v3, v5), (v4, v5), (v4, v1), (v5, v6), (v6, v4), (v5, v7), (v2, v7) . 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)) = 2, φ((v1,v3)) = 6, φ((v2,v3)) = 4, φ((v3,v4)) = 3, φ((v4,v6)) = 4, φ((v5,v4)) = 2, φ((v5, v6)) = 3, φ((v6, v1)) = 2, φ((v2, v4)) = 7.Изобразить граф, проверить полученное решение по графу.
18. Решив систему уравнений в полукольце R+, вычислить первый и третий столбцы матрицы стоимости взвешенного ориентированного графа, заданного матрицей меток дуг:
O5OOO3
5O4OOO
O O O 1 3 O
O 3 O O 3 O
3 2 O O O 2
O4OOOO
Здесь O — нуль полукольца R+. Изобразить граф, проверить полученное решение по
графу.
19. Построить конечный автомат, допускающий язык в алфавите {0,1}, заданный регу-
лярным выражением ((0)∗1 + 10)∗ и детерминизировать его.
20. Построить конечный автомат, допускающий все цепочки в алфавите
цепочки bca.
21. Решить систему линейных уравнений с регулярными коэффициентами
x1=bx1 +cx2 +λ, x2=ax1 +cx2 +b∗.
{a, b, c},
кроме
}
Построить конечный автомат, допускающий язык, заданный регулярным выражением x2. 22. Найти язык, допускаемый конечным автоматом
M = {{a, b}, {q1, q2, q3, q4}, {q1}, {q3, q4},
δ(q1, a) = {q1, q2}, δ(q1, b) = {q4}, δ(q2, a) = {q3}, δ(q2, b) = {q1, q3}, δ(q3, a) = {q3}, δ(q4, b) = {q4}}.
23. С использованием карты Карно получить все тупиковые ДНФ и найти минимальные ДНФ для функции
f = {0, 2, 4, 5, 8, 10, 13, 15}.
Для функции f указаны номера тех наборов, на которых функция принимает значение 1.
24. С использованием карты Карно перечислить все тупиковые ДНФ и найти минимальные
ДНФ для функции
f(x1,x2,x3)=x1(x1|x3)(x1 ⊕x3)⇒(x2 ∼x3).
Для функции f указаны номера тех наборов, на которых функция принимает значение 1.
25. Выяснить полноту множества F булевых функций f1 = {0,1,6,7},
f2 = x1 ⊕ (x2 ↓ x3).
Если множество не является полным, дополнить его такой булевой функцией h, чтобы мно- жество F ′ = {f1, f2, h} было полным. Выразить коньюнкцию формулой над F или F ′, считая, что отрицание доступно. Дополнительную функцию h следует использовать только для тех построений, где использование f1 и f2 невозможно.Для функции f1 указаны номера наборов, на которых она принимает значение 1.
26. Выяснить полноту множества F булевых функций f1 =(10100100),
f 2 = x 2 · ( x 1 ∨ x ̄ 3 ) .
Есть пропуски в билетах и в задачах.M = {{a, b}, {q1, q2, q3, q4}, {q1}, {q3, q4},
δ(q1, a) = {q1, q2}, δ(q1, b) = {q4}, δ(q2, a) = {q3}, δ(q2, b) = {q1, q3}, δ(q3, a) = {q3}, δ(q4, b) = {q4}}.
23. С использованием карты Карно получить все тупиковые ДНФ и найти минимальные ДНФ для функции
f = {0, 2, 4, 5, 8, 10, 13, 15}.
Для функции f указаны номера тех наборов, на которых функция принимает значение 1.
24. С использованием карты Карно перечислить все тупиковые ДНФ и найти минимальные
ДНФ для функции
f(x1,x2,x3)=x1(x1|x3)(x1 ⊕x3)⇒(x2 ∼x3).
Для функции f указаны номера тех наборов, на которых функция принимает значение 1.
25. Выяснить полноту множества F булевых функций f1 = {0,1,6,7},
f2 = x1 ⊕ (x2 ↓ x3).
Если множество не является полным, дополнить его такой булевой функцией h, чтобы мно- жество F ′ = {f1, f2, h} было полным. Выразить коньюнкцию формулой над F или F ′, считая, что отрицание доступно. Дополнительную функцию h следует использовать только для тех построений, где использование f1 и f2 невозможно.Для функции f1 указаны номера наборов, на которых она принимает значение 1.
26. Выяснить полноту множества F булевых функций f1 =(10100100),
f 2 = x 2 · ( x 1 ∨ x ̄ 3 ) .
Файлы условия, демо
Характеристики ответов (шпаргалок) к экзамену
Предмет
Учебное заведение
МГТУ им. Н.Э.БауманаПросмотров
14
Размер
140,26 Mb
Преподаватели
Список файлов
Дискретная математика (экзамен).docx
egorvar2
30 января в 00:20
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
