Глава 4 Алгебра логики (стр. 4 )

Схема Булева операция

x1x2

`x1

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

Пример 4.11  Пусть задана контактная схема. Упростить ее до пяти контактов.
Составим булеву функцию для исходной схемы и упростим ее. . По упрощенной формуле составим схему:

4.3.1  Контрольные вопросы

1.  Что такое контактная схема?

2.  Какая логическая операция соответствует последовательному соединению контактов? А параллельному соединению?

3.  Как можно построить булеву функцию по контактной схеме?

4.  Какие алгоритмы булевой алгебры можно использовать для упрощения контактной схемы?

4.4  Минимизация булевых функций

Минимальная ДНФ – это такая ДНФ функции, которая содержит наименьшее количество вхождений переменных по сравнению с остальными.

Элементарная конъюнкция называется импликантой функции , если она равна 0 на тех наборах, на которых f обращается в 0. Простой импликантой называется импликанта, в которой отбрасывание любой буквы ведет к получению элементарной конъюнкции, которая не является импликантой (т. е. никакая часть простой импликанты сама импликантой не является). Каждая импликанта соответствует покрытию на карте Карно, а простая импликанта – покрытию наибольшей размерности.

Пример 4.12  1) . – импликанта, причем простая; – импликанта, но не простая, т. к. удаление x3 снова дает импликанту (которая является простой).
2) Найдем импликанты и простые импликанты для функции . Всего имеется 8 элементарных конъюнкций с переменными x1, x2. Приведем их таблицы истинности.

x1	x2	x1®x2				x1x2			x1	x2
0	0	1	1	0	0	0	1	1	0	0
0	1	1	0	1	0	0	1	0	0	1
1	0	0	0	0	1	0	0	1	1	0
1	1	1	0	0	0	1	0	0	1	1

Из таблицы истинности заключаем, что , , x1x2, , x2 являются импликантами функции f. Из них простыми являются и x2.

Дизъюнкция всех простых импликант функции называется сокращенной ДНФ. Сокращенная ДНФ функции единственна.

Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет значения функции.

Если из сокращенной ДНФ удалить все лишние дизъюнктивные члены, и удаление любого из оставшихся приведет к изменению значения функции, то такая форма называется тупиковой ДНФ. Та из всех тупиковых ДНФ, которая имеет наименьшее число вхождений переменных, является минимальной ДНФ.

Минимальных ДНФ может быть несколько.

Процесс нахождения минимальной ДНФ из СДНФ можно разбить на следующие этапы:

1)  нахождение сокращенной ДНФ (она единственна);

2)  нахождение всех тупиковых ДНФ (их м. б. несколько);

3)  выбор из всех тупиковых минимальной ДНФ (их тоже м. б. несколько).

Известны аналитические и графические способы построения минимальной ДНФ. Графический способ использует представление на картах Карно.

4.4.1  Применение карт Карно

Этот метод используется для формул с малым числом переменных.

Покрытие, состоящее из двух клеток, соответствует произведению всех переменных кроме одной, значением которой отличаются эти клетки. Покрытие из четырех клеток соответствует произведению, в котором отсутствуют две переменные и т. д.

Для построения минимальной ДНФ следуют двум правилам:

1.  Выбирают покрытия наибольшего размера, содержащие клетки, которые не могут быть ни в каком другом покрытии.

2.  Для оставшихся клеток выбирают покрытие наибольшей размерности.

Пример 4.13  Найдем минимальную ДНФ для функции
=. Выпишем двоичные номера всех 0-кубов: 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1111. Построим карту Карно и покроем все единицы на карте Карно покрытиями наибольшего размера. Порядок построения минимальной ДНФ будет таким:
1) Выбираем покрытие наибольшего размера для ячейки, соответствующей x1x2x3x4. Это импликанта x3x4.
2) Выбираем покрытие для ячейки – импликанта . 3) Выбираем покрытие для ячейки – импликанта . Непокрытых ячеек не осталось Þ минимальная ДНФ имеет вид .

4.4.2  Метод Квайна-Мак-Класки

Будем предполагать, что функция представлена в СДНФ. Метод Квайна-Мак-Класки позволяет получить минимальную ДНФ независимо от количества аргументов. На первом этапе выполняется построение сокращенной ДНФ (т. е. поиск всех простых импликант), на втором – получение из нее минимальной ДНФ.

Этап 1. Нахождение сокращенной ДНФ.

1)  Каждому дизъюнктивному члену ставим в соответствие двоичный набор. Полученное множество 0-кубов обозначим K0 и разобьем его на группы по количеству единиц, обозначив группу с i единицами через K0i.

2)  Нахождение простых импликант.
а) Применяем операцию склеивания к 0-кубам из соседних подмножеств, которые различаются одной переменной: . Склеивание возможно только между элементами соседних групп (только они могут различаться ровно одной переменной). Элементы, участвующие в склеивании, помечаем. Результат склеивания – набор 1-кубов (импликант) и, возможно, простые импликанты, которые остались не помеченными. Для 1-кубов на месте отсутствующей переменной будем писать знак x.
б) Разбиваем 1-кубы на подмножества по расположению x и производим склеивание внутри каждого подмножества (принцип тот же – склеиваются 1-кубы, отличающиеся ровно одной переменной). Склеенные 1-кубы помечаем, результат склеивания – 2-кубы. Неотмеченные 1-кубы – простые импликанты.
в) Аналогично склеиваем 2-кубы, 3-кубы и т. п., пока это возможно. По окончании процесса все оставшиеся непомеченными элементы являются простыми импликантами, т. е. получена сокращенная ДНФ.

Пример 4.14  Результат склеивания наборов 0110 и 1110 – набор x110, который соответствует импликанте . Результат склеивания 1-кубов x110 и x100 – 2-куб x1x0, который соответствует импликанте .

Этап 2. Нахождение минимальной ДНФ.

3) Построение импликантной таблицы.

По найденным на предыдущем этапе простым импликантам составляем импликантную таблицу, заголовки строк которой – простые импликанты, заголовки столбцов – 0-кубы из исходной СДНФ. В таблице помечаем пересечение строки и столбца, если импликанта покрывает 0-куб.