|
5.11.3. Вычисление значения булевой функции
по бинарному графу Если булева функция задана бинарным графом (или деревом, то можно написать программу вычисления ее значения с использованием только команд двух типов условная команда
метка если аргумент то метка иначе метка операторная команда
метка значение конец Для того, чтобы написать программу, необходимо произвольным образом пронумеровать вершины бинарного графа, начиная с начальной вершины (рис. Каждой вершине графа соответствует команда программы. Начальной и условным вершинам соответствуют условные команды, а заключительным — операторные. Если в начальной или условной вершине с номером m записан аргумент x
i
, дуга, отмеченная нулем, Вычисление значения булевой функции по ДНФ
P := 0; i := 1; F := 1
i
KT и P = 0
T[i] = 0
T[i] > 0
F = Конец
+
+
+
286 идет в вершину с номером n, а дуга, отмеченная единицей, идет в вершину с номером k, то такой вершине соответствует команда
m если x
i
то k иначе n Заключительной вершине с номером l, в которой записано f = 0, соответствует команда
l F := 0 конец Заключительной вершине с номером p, в которой записано f = 1, соответствует команда
p F := 1 конец
Рис.5.7. Бинарный граф булевой функции с пронумерованными вершинами Программа вычисления значения булевой функции по бинарному графу (рис) будет такой
1 если x
1
то 3 иначе 2 2 если x
2
то 4 иначе 5 3 если x
2
то 7 иначе 4 4 если x
3
то 7 иначе 5 5 если x
4
то 7 иначе 6 6 F := 1 конец
7 F := 0 конец Рассмотрим еще один способ вычисления значения булевой функции по бинарному графу. Представим бинарный граф таблицей. Таблица имеет три столбца, нумерация которых начинается с нуля. Строки таблицы соответствуют вершинам графа. Если в начальной или условной вершине с номером m записан аргумент x
i
, дуга, отмеченная нулем, идет в вершину с номером n, а дуга, отмеченная единицей, идет в вершину с номером k, то такой вершине соответствует строка таблицы с номером
m, нулевой столбец которой содержит n, первый — k и второй — i.
1 0
2
0 1
7
0 1
6
0 1
4
0 1
3
0 1
2
0 1
1
0 1
0 1 0 1 1 0
0 1
x
1
x
2
x
3
x
2
f=1
f=0
5
0 1
x
4
287 Заключительной вершине с номером l, в которой записано f = 0, соответствует строка таблицы с номером l, в которой все столбцы содержат нули. Заключительной вершине с номером p, в которой записано f = 1, соответствует строка таблицы с номером p, в которой нулевой и первый столбцы содержат нули, а второй — единицу. Другими словами, если строка соответствует начальной или условной вершине, то нулевой и первый столбцы таблицы содержат номера вершин, в которые идут дуги из вершины, отмеченные соответственно нулем и единицей, а второй — содержит номер аргумента. Если же строка соответствует заключительной вершине, то нулевой и первый столбцы содержат нули, а второй — значение функции. Бинарный граф (рис) представлен табл. 5.19. Таблица 5.19
Таблица бинарного графа
0 1
2 1
2 3
1 2
5 4
2 3
4 7
2 4
5 7
3 5
6 7
4 6
0 0
1 7
0 0
0 Такую таблицу можно сохранить в двумерном массиве T и использовать для вычисления значения булевой функции последующему алгоритму. Алгоритм вычисления значения булевой функции по бинарному графу. Вход X — набор значений аргументов
T — таблица бинарного графа булевой функции. Выход F — значение булевой функции.
1. v := 1;
2. Пока T[v,0]
0 выполнять v := T[v,X[T[v,2]]];
3. F := T[v,2].
5.11.4. Вычисление значения булевой функции
по синтаксическому дереву Вычислить значение булевой функции по синтаксическому дереву можно с помощью рекурсивной функции Вычислить, в которую передается вершина, являющаяся корнем дерева.
288 Алгоритм функции Вычислить вершина) следующий если в вершине записан аргумент функции, то значение функции равно значению аргумента если в вершине записана операция отрицания, то значение функции равно значению выражения
)
(сын
Вычислить
; если в вершине записана операция конъюнкции, то значение функции равно значению выражения Вычислить левый сын) ˄ Вычислить правый сын если в вершине записана операция дизъюнкции, то значение функции равно значению выражения Вычислить левый сын) ˅ Вычислить правый сын
289 Практическое занятие 5.1 Полностью определенные булевы функции Цель занятия изучить способы задания булевых функций, методы их минимизации и программной реализации. Задания 1. Представить булеву функцию табл. 5.31), где i — номер варианта, совершенной дизъюнктивной нормальной формой, совершенной конъюнктивной нормальной формой и полиномом Жегалкина. 2. Получить сокращенную ДНФ функции методом Квайна — Мак- Класки. 3. Получить минимальную ДНФ функции fi, используя матрицу Квайна. 4. Выполнить скобочную минимизацию минимальной ДНФ функции fi5. Построить бинарный граф функции fi6. Написать программу, вычисляющую значение функции fi на заданном наборе аргументов по минимальной ДНФ. 7. Написать программу, вычисляющую значение функции fi на заданном наборе аргументов по бинарному графу. 8. Используя программу п, написать программу, строящую таблицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 5.31). 9. Используя программу п, написать программу, строящую таблицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 5.31). Практическое занятие 5.2 Частично определенные булевы функции Цель занятия изучить методы минимизации чистично определенных булевых функций. Задания 1. Получить минимальную ДНФ чистично определенной булевой функции табл. 5.20), где i — номер варианта, различными способами. 2. Написать программу, строящую таблицу истинности функции Результат работы программы сравнить с заданием (табл. 5.12).
290 Таблица 5.20 Таблица истинности полностью определенных булевых функций
x
1
x
2
x
3
x
4
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
f
13
f
14
f
15 0
0 0
0 0
1 1
1 0
0 0
1 1
0 1
0 0
0 1
0 0
0 1
1 0
0 0
1 1
1 0
0 1
0 1
1 1
0 0
0 1
0 1
0 1
0 1
0 1
0 1
1 0
1 1
1 0
0 0
1 1
0 1
1 0
1 0
0 1
1 1
0 0
0 1
1 0
1 0
0 0
0 1
0 1
0 1
1 0
1 0
0 1
0 0
0 1
0 1
0 1
1 1
0 1
0 1
0 1
1 0
1 0
0 0
1 1
0 0
0 0
0 1
1 1
1 0
1 0
0 0
1 0
0 1
1 1
1 0
0 1
1 1
1 0
0 0
1 1
1 0
0 1
0 0
0 1
1 1
0 0
1 1
0 0
1 0
0 0
1 1
1 0
0 1
1 1
0 1
0 0
0 1
1 0
1 1
1 0
1 1
0 1
0 0
1 0
1 1
0 0
1 1
1 0
0 1
0 1
1 0
1 1
1 0
0 1
1 0
0 1
0 0
0 1
1 0
0 1
1 0
0 1
1 0
1 0
0 1
1 1
0 1
0 0
1 0
1 1
0 1
0 1
1 0
0 0
1 0
1 0
0 1
0 1
0 1
1 1
0 0
1 0
0 0
1 1
0 1
0 1
0 0
1 1
1 1
1 1
0 1
1 1
1 0
1 0
1 0
1 0
0 1
1 Таблица 5.21 Таблица истинности частично определенных булевых функций
x
1
x
2
x
3
x
4
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
f
13
f
14
f
15 0
0 0
0 0
0 0
1 0
1 1
0 1
0 0
0 1
1 0
0 0
0 1
1 1
1 0
1 0
0 1
0 1
1 1
0 0
1 0
0 1
0 1
-
1 0
-
0 0
1
-
1
-
1
-
0
-
0 0
1 1
-
0
-
-
0
-
-
0 1
-
0
-
1
-
0 0
1 0
0
-
-
1 1
0 1
0 0
-
1 1
-
-
-
0 0
1 0
1 0
1
-
1
-
1
-
0 1
-
-
0 1
1
-
0 1
1 0
-
-
-
-
0 1
0
-
1
-
-
-
1
-
-
0 1
1 1
-
1 0
1 1
0
-
-
0
-
1 0
0
-
1 1
0 0
0 1
-
-
0
-
0
-
1 1
-
1 1
1 0
-
1 0
0 1
-
1 0
1
-
1 1
-
0 0
-
0 1
-
0 1
0 1
0 0
-
-
1
-
-
1 0
1 0
0
-
-
1 0
1 0
1 1
-
1
-
-
1 0
-
0 1
-
-
0 0
1 1
1 1
0 0
0 0
-
0
-
0
-
0
-
-
-
0 1
1
-
1 1
0 1
1
-
-
0 1
-
-
0
-
-
-
0 1
-
1 1
1 1
0
-
-
0
-
1 1
-
1 0
-
1 0
-
0 1
1 1
1 1
-
1
-
0 0
1
-
1 1
0
-
0 1
0 0
291 Практическое занятие 5.3 Минимизация систем полностью определенных булевых функций Цель занятия научиться минимизировать системы полностью определенных булевых функций, закрепить навыки минимизации полностью определенных булевых функций.
Задания В табл. 5.20 (см. выше) представлено множество {
f
1
, f
2
,…, f
15
} полностью определенных булевых функций. В табл. 5.22 каждому варианту поставлена в соответствие система булевых функций, представляющая собой подмножество множества {f
1
, f
2
,…, f
15
} (см. табл. 5.20).
1. Минимизировать систему полностью определенных булевых функций в соответствии с вариантом задания (см. табл. 5.22).
2. Получить систему минимальных ДНФ булевых функций и сравнить с результатом п. Таблица 5.22 Варианты заданий Вариант Система булевых функций
1
f
1
, f
2
, f
3
, f
4 2
f
1
, f
3
, f
4
, f
5 3
f
4
, f
5
, f
6
, f
7 4
f
2
, f
3
, f
5
, f
6 5
f
5
, f
6
, f
7
, f
8 6
f
1
, f
2
, f
6
, f
7 7
f
1
, f
4
, f
5
, f
9 8
f
3
, f
4
, f
8
, f
10 9
f
5
, f
7
, f
9
, f
10 10
f
8
, f
9
, f
10
, f
11 11
f
10
, f
11
, f
12
, f
14 12
f
11
, f
12
, f
13
, f
15 13
f
7
, f
8
, f
13
, f
14 14
f
4
, f
6
, f
10
, f
13 15
f
2
, f
4
, f
11
, f
14 16
f
3
, f
5
, f
9
, f
13 17
f
5
, f
6
, f
8
, f
15 18
f
5
, f
8
, f
11
, f
15 19
f
6
, f
7
, f
10
, f
12 20
f
7
, f
9
, f
13
, f
14
292 Практическое занятие 5.4 Вычисление систем булевых функций Цель занятия научиться минимизировать системы частично определенных булевых функций, строить бинарные графы систем булевых функций и использовать их для вычисления значений функций системы. Задания В табл. 5.21 (см. выше) представлено множество {
f
1
, f
2
,…, f
15
} частично определенных булевых функций. В табл. 5.22 (см. выше) каждому варианту поставлена в соответствие система булевых функций, представляющая собой подмножество множества {f
1
, f
2
,…, f
15
} см. табл. 5.21).
1. Минимизировать систему частично определенных булевых функций в соответствии с вариантом задания (см. табл. 5.22).
2. Построить бинарный граф системы булевых функций.
3. Написать программу, вычисляющую значение системы булевых функций на заданном наборе аргументов по бинарному графу. Заключительные вершины бинарного графа системы булевых функций дополнительно пронумеруем натуральными числами от 1 до k, где k — количество заключительных вершин, и построим таблицу, которая каждой заключительной вершине поставит в соответствие набор значений функций системы. Такую таблицу можно представить двумерным массивом F, в котором элемент F
ij
содержит значение функции f
j
, записанной в заключительной вершине с дополнительным номером i. В основной же таблице в строке, соответствующей заключительной вершине с дополнительным номером i, во втором столбце запишем i. Алгоритм вычисления значения системы булевых функций на заданном наборе аргументов по бинарному графу отличается от алгоритма вычисления значения одной функции тем, что при достижении заключительной вершины (после выхода из цикла) выводятся значения всех функций системы из массива F с использованием дополнительной метки заключительной вершины.
4. Используя программу п, написать программу, строящую таблицу истинности системы булевых функций. Результат работы программы сравнить с заданием (табл. 5.21).
293 Контрольные вопросы и задания
1. Дайте определение булевой функции.
2. Приведите примеры различных таблиц истинности, задающих одну и туже булеву функцию.
3. Какая булева функция называется элементарной Сколько их
4. Что называется функционально полным набором булевых функций. Что называется операцией суперпозиции и суперпозицией функций. Дайте определение классу булевых функций, функционально замкнутого по операции суперпозиции.
7. Дайте определение свойствам булевых функций. Определите свойства заданной булевой функции.
8. Сформулируйте необходимые и достаточные условия функциональной полноты системы булевых функций. Определите, обладает ли функциональной полнотой заданная система функций
9. Дайте определение конституенты единицы и конституенты нуля.
10. Что представляет собой СДНФ, СКНФ, СПНФ?
11. Что называется элементарной конъюнкцией, элементарной дизъюнкцией Что представляет собой ДНФ и КНФ? Чем они отличаются от
СДНФ и СКНФ.
12. Что называется полиномом Жегалкина? Представьте полиномом
Жегалкина булеву функцию, заданную таблицей истинности.
13. Запишите основные законы булевой алгебры. Запишите и докажите истинность правил склеивания, поглощения и вычеркивания.
14. Что такое дизъюнктивное разложение Шеннона? Выполните разложение Шеннона заданной булевой функции по различным аргументам. Что называется импликантой булевой функции Какая импли- канта называется простой
16. Дайте определение сокращенной ДНФ. Получите сокращенную
ДНФ булевой функции, заданной таблицей истинности, различными методами.
17. Дайте определение тупиковой и минимальной ДНФ булевой функции.
18. Что представляет собой матрица Квайна, ядро Квайна?
19. Что такое конъюнктивное представление матрицы Квайна? Как его использовать для получения всех тупиковых ДНФ?
20. Выполните скобочную минимизацию заданной минимальной
ДНФ булевой функции.
294 21. Какая булева функция называется частично определенной
22. Что называется простой импликантой частично определенной булевой функции Как найти все простые импликанты частично определенной булевой функции
23. Какая система ДНФ булевых функций называется минимальной
24. Что называется простой импликантой системы булевых функций. Модифицируйте метод Квайна — Мак-Класки для получения всех простых импликант системы булевых функций.
26. Как строится импликантная матрица Квайна для системы булевых функций
27. Какие аргументы системы частично определенных булевых функций называются фиктивными Каких найти
28. Что называется простой импликантой системы частично определенных булевых функций Как найти все простые импликанты системы частично определенных булевых функций
29. Приведите пример бинарного графа булевой функции. Запишите эту функцию в ДНФ.
30. Постройте различные бинарные графы одной и той же булевой функции.
31. Сколько условных вершин может быть в бинарном графе булевой функции Какова может быть глубина бинарного графа
32. Приведите пример бинарного графа системы булевых функций. Запишите эти функции в ДНФ.
33. Постройте различные бинарные графы одной и той же системы булевых функций.
34. Сколько условных и заключительных вершин может быть в бинарном графе системы булевых функций
35. Какова может быть глубина бинарного графа системы булевых функций
36. Напишите программы для вычисления значения булевой функции по таблице истинности при различных способах ее хранения.
37. Опишите алгоритм вычисления значения булевой функции по
ДНФ.
38. Напишите различные программы для вычисления значения булевой функции по заданному бинарному графу.
39. Разработайте способ хранения и алгоритм вычисления системы булевых функций по таблице истинности.
40. Разработайте способ хранения и алгоритм вычисления системы булевых функций по минимальной системе ДНФ булевых функций.
295 Заключение В данном пособии рассмотрены вопросы, соответствующие содержанию дисциплины «Дискретная математика для студентов, обучающихся по направлениям 09.03.01 Информатика и вычислительная техника и 09.03.04 Программная инженерия. В целом же, дискретная математика представляет собой обширную область знаний, которая значительно превосходит содержание одноименной дисциплины. Например, в пособии не рассмотрены вопросы, касающиеся кодирования информации, логических исчислений, теории алгоритмов, алгебраических структур, формальных языков и грамматик, теории автоматов, сетей Петри и др. Ответы на эти вопросы можно получить при изучении смежных дисциплин или обратившись к специальной литературе.
296 Библиографический список
1. Асанов, М Дискретная математика графы, матроиды, алгоритмы /
М.О. Асанов, В.А. Баранский, В.В. Расин. — Ижевск НИЦ Регулярная и хаотическая динамика, 2001. — 288 с.
2. Белоусов, АИ Дискретная математика учеб. для вузов / АИ. Бе- лоусов, С.Б. Ткачев, под ред. В.С. Зарубина, А.П. Крищенко. — е изд, стер. — М Изд-во МГТУ им. Н.Э. Баумана, 2004. — 744 с. Сер. Математика в техническом университете Вып. ХIХ).
3. Горбатов, В.А. Фундаментальные основы дискретной математики. Информационная математика / В.А. Горбатов.— М Физмат- лит, 2000. — 544 с.
4. Иванов, Б.Н. Дискретная математика. Алгоритмы и программы учеб. пособие / Б.Н. Иванов. — М Лаборатория Базовых Знаний,
2003. — 288 с.
5. Поздняков, С.Н. Дискретная математика учебник для студ. вузов /
С.Н. Поздняков, СВ. Рыбин. — М. : Издательский центр Академия с.
6. Прилуцкий, М.Х. Дискретная математика. Методические пособия для студентов факультета ВМК, специальности 351400 Прикладная информатика».Часть 1 Н. Новгород.Нижег.гос.ун-т, 2007, с.
7. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. — М Мир, 1978. — 429 с.
8. Кузнецов, ОП. Дискретная математика для инженера ОП. Кузнецов, ГМ. Адельсон-Вельский. — е изд, перераб. и доп — М
Энергоатомиздат, 1988. – с.
9. Кузнецов, ОП Дискретная математика для инженера / ОП. Кузнецов е изд, перераб. и доп. — СПб.: Лань, 2004. — 400 сил (Учебники для вузов. Специальная литература.
10. Липский, В Комбинаторика для программистов / В. Липский. — М Мир, 1988. — 201 с.
11. Муромцев, В.В. Проектирование полнопереборных алгоритмов учеб. пособие В.В. Муромцев. — Белгород Изд-во БелГТАСМ,
2001. — 67 с.
12. Новиков, ФА Дискретная математика для программистов учеб. для вузов / ФА. Новиков. — е изд. — СПб.: Питер, 2008. —
384 сил (Серия Учебник для вузов.
13. Прикладная теория цифровых автоматов / КГ. Самофалов,
А.М. Романкевич, В.Н. Валуйский и др. — Киев Вища школа,
1987. — 357 с.
14. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Дэо. — М Мир, 1980. — 476 с.
297 15. Рязанов, Ю.Д. Булевы функции. Способы задания и реализация учеб. пособие / Ю.Д. Рязанов. — Белгород Изд-во БТИСМ,
1993. — 124 с.
16. Рязанов, Ю.Д. Множества и комбинаторные объекты учеб. пособие Ю.Д. Рязанов — Белгород Изд-во БГТУ, 2008. — 99 с.
17. Рязанов, Ю.Д. Быстрый алгоритм решения теоретико- множественных уравнений / Ю.Д. Рязанов // Научное творчество
XXI века Материалы IV Всероссийской научно-практической конференции с международным участием. Приложение к журналу "В мире научных открытий. — Красноярск, 2011. — Вып. 2, с. 78 — 79.
18. Рязанов, Ю.Д. Интуитивные и формальные методы доказательства теоретико-множественных тождеств Ю.Д. Рязанов // Наука в решении региональных проблем сб. науч. трудов с международным участием. — Пермь Березниковский филиал Пермского национального исследовательского политехнического университета,
2012. — Вып. 8., с. 26 — 31.
19. Рязанов, Ю.Д. Генератор заданий для изучения преобразования теоретико-множественных выражений в нормальные формы Кантора Ю.Д. Рязанов, А.В. Штырь // Инновационные технологии в производстве, науке и образовании. Сборник трудов II Международной научно-практической конференции. Часть 2. — Махачкала
Изд-во ООО «Риасофт»», 2012., с. 293 — 297.
20. Седжвик, Р Фундаментальные алгоритмы на C++. Ч. 5: Алгоритмы на графах перс англ / Р. Седжвик. — СПб.: ООО «Диа-
СофтЮП», 2002. — 496 с.
21. Хаггарти, Р Дискретная математика для программистов / Р. Хаг- гарти. — М Техносфера, 2005. — 400 с.
22. Шапорев, С.Д. Дискретная математика курс лекций и практических занятий / С.Д. Шапорев. — СПб.: БХВ-Петербург, 2007. —
400 с.
23. Яблонский, СВ Введение в дискретную математику учеб. пособие для вузов / под ред. В.А. Садовничего. – е изд, стер. – М
Высш. шк, 2003. – 384 с.
24. Литература по дискретной математике — Не решается алгебра / высшая математика ?.. ПОМОЖЕМ URL: http://www.diary.ru/eek/ p49631731.htm# (дата обращения 15.09.2015)
Учебное издание
Рязанов Юрий Дмитриевич ДИСКРЕТНАЯ МАТЕМАТИКА Учебное пособие Редактор В.И. Пустовая Подписано в печать 24.02.16 Формат х. Усл.печ.л. 17,2. Уч.-изд.л. 18,5. Тираж 500 экз. Заказ Цена Отпечатано в Белгородском государственном технологическом университете им. В.Г. Шухова
308012, г. Белгород, ул. Костюкова, 46
|
Скачать 4.33 Mb.