ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.03.2024
Просмотров: 200
Скачиваний: 3
52
5. БУЛЕВЫ ФУНКЦИИ
Л а б о р а т о р н а я р а б о т а № 5.1
Полностью определенные булевы функции
Цель занятия: изучить способы задания булевых функций, методы их минимизации и программной реализации.
Задания
1.Представить булеву функцию fi (табл. 7), где i — номер варианта, совершенной дизъюнктивной нормальной формой, совершенной конъюнктивной нормальной формой и полиномом Жегалкина.
2.Получить сокращенную ДНФ функции fi методом Квайна — Мак-Класки.
3.Получить минимальную ДНФ функции fi, используя матрицу Квайна.
4.Выполнить скобочную минимизацию минимальной ДНФ функции fi.
5.Построить бинарный граф функции fi.
6.Написать программу, вычисляющую значение функции fi на заданном наборе аргументов по минимальной ДНФ.
7.Написать программу, вычисляющую значение функции fi на заданном наборе аргументов по бинарному графу.
8.Используя программу п.6, написать программу, строящую таб-
лицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 5.7).
9.Используя программу п.7, написать программу, строящую таб-
лицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 5.7).
Л а б о р а т о р н а я р а б о т а № 5.2
Частично определенные булевы функции
Цель занятия: изучить методы минимизации чистично определенных булевых функций.
Задания
1.Получить минимальную ДНФ чистично определенной булевой функции fi (табл. 8), где i — номер варианта, различными способами.
2.Написать программу, строящую таблицу истинности функции fi. Результат работы программы сравнить с заданием (табл. 8).
53
Таблица 7
Таблица истинности полностью определенных булевых функций
x1 |
x2 |
x3 |
x4 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
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 |
Таблица 8
Таблица истинности частично определенных булевых функций
x1 |
x2 |
x3 |
x4 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
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 |
54
Л а б о р а т о р н а я р а б о т а № 5.3
Минимизация систем полностью определенных булевых функций
Цель занятия: научиться минимизировать системы полностью определенных булевых функций, закрепить навыки минимизации полностью определенных булевых функций.
Задания
В табл. 7 (см. выше) представлено множество {f1, f2,…, f15} полностью определенных булевых функций. В табл. 9 каждому варианту поставлена в соответствие система булевых функций, представляющая собой подмножество множества {f1, f2,…, f15} (см. табл. 7).
1.Минимизировать систему полностью определенных булевых функций в соответствии с вариантом задания (см. табл. 9).
2.Получить систему минимальных ДНФ булевых функций и сравнить с результатом п.1.
Таблица 9
|
Варианты заданий |
|
|
Вариант |
Система булевых функций |
1 |
f1, f2, f3, f4 |
2 |
f1, f3, f4, f5 |
3 |
f4, f5, f6, f7 |
4 |
f2, f3, f5, f6 |
5 |
f5, f6, f7, f8 |
6 |
f1, f2, f6, f7 |
7 |
f1, f4, f5, f9 |
8 |
f3, f4, f8, f10 |
9 |
f5, f7, f9, f10 |
10 |
f8, f9, f10, f11 |
11 |
f10, f11, f12, f14 |
12 |
f11, f12, f13, f15 |
13 |
f7, f8, f13, f14 |
14 |
f4, f6, f10, f13 |
15 |
f2, f4, f11, f14 |
16 |
f3, f5, f9, f13 |
17 |
f5, f6, f8, f15 |
18 |
f5, f8, f11, f15 |
19 |
f6, f7, f10, f12 |
20 |
f7, f9, f13, f14 |
55
Л а б о р а т о р н а я р а б о т а № 5.4
Вычисление систем булевых функций
Цель занятия: научиться минимизировать системы частично определенных булевых функций, строить бинарные графы систем булевых функций и использовать их для вычисления значений функций системы.
Задания
В табл. 8 (см. выше) представлено множество {f1, f2,…, f15} частично определенных булевых функций. В табл. 9 (см. выше) каждому варианту поставлена в соответствие система булевых функций, представляющая собой подмножество множества {f1, f2,…, f15} (см. табл. 8).
1.Минимизировать систему частично определенных булевых функций в соответствии с вариантом задания (см. табл. 9).
2.Построить бинарный граф системы булевых функций.
3.Написать программу, вычисляющую значение системы булевых функций на заданном наборе аргументов по бинарному графу.
Заключительные вершины бинарного графа системы булевых функций дополнительно пронумеруем натуральными числами от 1 до k, где k — количество заключительных вершин, и построим таблицу, которая каждой заключительной вершине поставит в соответствие набор значений функций системы. Такую таблицу можно представить двумерным массивом F, в котором элемент Fij содержит значение функции fj, записанной в заключительной вершине с дополнительным номером i. В основной же таблице в строке, соответствующей заключительной вершине с дополнительным номером i, во втором столбце запишем i. Алгоритм вычисления значения системы булевых функций на заданном наборе аргументов по бинарному графу отличается от алгоритма вычисления значения одной функции тем, что при достижении заключительной вершины (после выхода из цикла) выводятся значения всех функций системы из массива F с использованием дополнительной метки заключительной вершины.
4. Используя программу п.3, написать программу, строящую таблицу истинности системы булевых функций. Результат работы программы сравнить с заданием (табл. 8).
56
Контрольные вопросы
1.Дайте определение булевой функции.
2.Приведите примеры различных таблиц истинности, задающих одну и ту же булеву функцию.
3.Какая булева функция называется элементарной? Сколько их?
4.Что называется функционально полным набором булевых функ-
ций?
5.Что называется операцией суперпозиции и суперпозицией функ-
ций?
6.Дайте определение классу булевых функций, функционально замкнутого по операции суперпозиции.
7.Дайте определение свойствам булевых функций. Определите свойства заданной булевой функции.
8.Сформулируйте необходимые и достаточные условия функциональной полноты системы булевых функций. Определите, обладает ли функциональной полнотой заданная система функций?
9.Дайте определение конституенты единицы и конституенты нуля.
10.Что представляет собой СДНФ, СКНФ, СПНФ?
11.Что называется элементарной конъюнкцией, элементарной дизъюнкцией? Что представляет собой ДНФ и КНФ? Чем они отличаются от СДНФ и СКНФ.
12.Что называется полиномом Жегалкина? Представьте полиномом Жегалкина булеву функцию, заданную таблицей истинности.
13.Запишите основные законы булевой алгебры. Запишите и докажите истинность правил склеивания, поглощения и вычеркивания.
14.Что такое дизъюнктивное разложение Шеннона? Выполните разложение Шеннона заданной булевой функции по различным аргументам.
15.Что называется импликантой булевой функции? Какая импликанта называется простой?
16.Дайте определение сокращенной ДНФ. Получите сокращенную ДНФ булевой функции, заданной таблицей истинности, различными методами.
17.Дайте определение тупиковой и минимальной ДНФ булевой функции.
18.Что представляет собой матрица Квайна, ядро Квайна?
19.Что такое конъюнктивное представление матрицы Квайна? Как его использовать для получения всех тупиковых ДНФ?
20.Выполните скобочную минимизацию заданной минимальной ДНФ булевой функции.
21.Какая булева функция называется частично определенной?