Если F(y1, y2, …, ym ) и fi (x1, x2, …, xn ) – формулы алгебры логики, то (F| yi fi )(x1, x2, …, xn ) также является формулой.

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

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

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

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

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

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

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

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

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

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

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

x1	x2	x1®x2				x1x2			x1	x2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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-куб.

4) Нахождение существенных импликант.

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

5) Вычеркивание доминируемых строк.

Если в j -ой строке имеются все пометки i -ой строки и может быть, еще некоторые, то j -я строка доминирует над i -ой, и i -ую строку можно исключить из дальнейшего рассмотрения. Из таблицы вычеркиваются все доминируемые строки (с меньшим числом пометок – в частности, строки без пометок).

6) Вычеркивание столбцов.

Если в m -ом столбце таблицы имеются все пометки k -го столбца и может быть, еще некоторые, то m -ый столбец доминирует над k -ым и m -ый столбец можно исключить из дальнейшего рассмотрения (т.е. вычеркивается столбец с большим числом пометок, в отличие от строки).

7) Этапы 4–6 повторяются до тех пор, пока это возможно. Полученная после таких преобразований таблица называется циклической.

8) Выбор минимального покрытия в циклической таблице.

Используется процедура ветвления:

а) выбирают столбец с минимальным количеством пометок (таких столбцов может быть несколько);

б) используя эти столбцы, выбирают из строк, содержащих пометки в выбранном столбце, ту, которая содержит максимальное количество пометок, и включают ее в минимальную ДНФ (в ответ). Если таких строк несколько, то берется любая.

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

В результате описанных преобразований таблицы будет получена минимальная ДНФ.

Пример 4.15 Найдем минимальную ДНФ для функции = .
1) Выпишем все наборы, на которых функция принимает значение 1 (т.е. 0-кубы функции): 0000, 0011, 0100, 0110, 0111, 1001, 1110, 1111. Разобьем наборы на группы по количеству единиц. Первая группа состоит из наборов, не содержащих единиц: {0000}; вторая – из наборов, содержащих одну единицу: {0100}, третья – две единицы: {0011, 0110, 1001}, четвертая – три {0111, 1110}, пятая – четыре {1111}. Выполним все возможные склеивания между наборами соседних групп, помечая участвующие в склеивании наборы: Результаты склеивания – 1-кубы 0x00, 01x0, 0x11, 011x, x110, x111, 111x. Импликанта 1001 – простая. Разобьем все полученные в результате склеивания импликанты по положению x на группы: 1-я группа: ; 2-я: ; 3-я: ; 4-я: .
Произведем все возможные склеивания внутри каждой группы, помечая наборы, участвующие в склеивании.
Результат склеивания – импликанта, соответствующая x11x, и набор простых импликант, соответствующих 0x00, 0x11, 01x0. Дальнейшее склеивание осуществить нельзя, поэтому x11x соответствует простой импликанте. Можно переходить к составлению импликантной таблицы.

Импликанты, соответствующие 0x00, 0x11, 1001, x11x – существенные, поэтому они обязательно входят в минимальную ДНФ. Удалим строки и столбцы для этих импликант из таблицы. Вычеркнутся все столбцы, следовательно, на этом процесс поиска минимальной ДНФ закончен.

Минимальная ДНФ имеет следующий вид:

Можно построить карту Карно и проверить полученный результат.

4.4.3 Минимизация частично определенных функций

Для минимизации неполностью определенных функций вводят в рассмотрение две дополнительных функции: j₀(x₁,x₂,...,x_n)=0 и j₁(x₁,x₂,...,x_n)=1 на всех наборах, на которых функция f не определена, и j₀(x₁,x₂,...,x_n)=j₁(x₁,x₂,...,x_n)=f там, где f определена. Для построения минимальной ДНФ нужно выбрать наименьшее покрытие 0-кубов функции j₀ простыми импликантами функции j₁.

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

Пример 4.16 Рассмотрим функцию , заданную Т.И.

Дополним ее функциями j₀ и j₁. Нужно найти сокращенную ДНФ для j₁, а затем все покрытия 0-кубов j₀.
Выпишем наборы, на которых функция j₁ принимает значение 1: 0000, 0001, 0010, 0100, 0110, 0111, 1000, 1001, 1011, 1101, 1110, 1111. Разобьем наборы на группы по количеству единиц. K⁰₀={0000}; K⁰₁={0001,0010,0100,1000}; K⁰₂={0110,1001}; K⁰₃={0111,1011,1101,1110}, K⁰₄={1111}. Выполним все возможные склеивания между наборами соседних групп, помечая участвующие в склеивании наборы: Результаты склеивания – 1-кубы 000x, 00x0, 0x00, x000, x001, 01x0, 100x, 011x, x110, 10x1, 1x01, x111, 1x11, 11x1, 111x. Разобьем все полученные в результате склеивания импликанты по положению x на группы:
K¹₁= ; K¹₂= ; K¹₃= ; K¹₄= .
Произведем все возможные склеивания внутри каждой группы, помечая наборы, участвующие в склеивании. Получим: x00x, x11x, 1xx1, 0xx0, 1xx1, x00x, x11x. После устранения дубликатов получим: x00x, x11x, 1xx1, 0xx0.
Результат склеивания – простая импликанта – 1-куб, соответствующая 0x00, и набор 2-кубов импликант, соответствующих x00x, x11x, 1xx1, 0xx0. Дальнейшее склеивание осуществить нельзя Þ это простые импликанты. Можно переходить к составлению импликантной таблицы, столбцы которой – 0-кубы функции j₀.

0x00	v
x00x	v		v
x11x		v		v
1xx1			v
0xx0	v	v

Импликанта x11x – существенная для 1110, вычеркиваем столбец 1110 и строку x11x, а также столбец 0110, который она покрывает, при этом импликанту x11x включаем в ответ. Больше существенных импликант нет, а строка x00x доминирует над всеми остальными Þ доминируемые строки вычеркиваем, а импликанту x00x выписываем в ответ. В итоге в ответ вошли импликанты x11x и x00x, т.е. функция имеет вид f = x₂×x₃ Ú `x<sub>2</sub>×`x₃. Проверка: Построенная карта Карно подтверждает полученный результат. Для включения в покрытия всех единиц, используя при необходимости символы d и выбирая покрытия наибольшей размерности, достаточно покрытий x11x и x00x. Остальные символы d, не вошедшие в эти покрытия, заменяются нулями.

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

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

1. Что является импликантой функции? В чем отличие простой импликанты?

2. Что соответствует импликанте (простой импликанте) на карте Карно?

3. Что такое сокращенная ДНФ?

4. Каков алгоритм нахождения сокращенной ДНФ?

5. Как можно получить минимальную ДНФ с помощью карт Карно?

6. Что позволяет найти метод Квайна-Мак-Класки? Каковы основные этапы этого метода? Что является результатом каждого из этапов?

7. Что такое 0-кубы? 1-кубы?

8. Что представляет операция склеивания? Какие наборы возможно склеить?

9. Как строится импликантная таблица? Что является ее строками, а что – столбцами? Какие строки и какие столбцы удаляются при упрощении импликантной таблицы?

10. В чем состоит процедура ветвления?

11. Единственна ли минимальная ДНФ?

12. Что такое частично определенная функция?

13. Чем отличается минимизация частично определенной функции?