Компьютерная схемотехника (стр. 2 )

3.5 Принцип двойственности булевой алгебры

Если в выражении F8=АВ конъюнкцию заменить на дизъюнкцию и проинвертировать обе переменные, то результат окажется инверсией прежнего значения функции . Аналогично, если в выражении F14=АВ дизъюнкцию заменить на конъюнкцию и проинвертировать обе переменные, то результат окажется инверсией прежнего значения функции .

Указанные свойства логических функций отражают принцип двойственности булевой алгебры.

3.6 Основные тождества булевой алгебры

А+0=А;А+1=1;

А+А=А;А+=1;

А*0=0;А*1=А;

А*А=А;А*=0;=А.

3.7 Основные законы и теоремы булевой алгебры

3.7.1 Законы

Переместительный (свойство коммутативности): А+В=В+А; А*В=В*А.

Сочетательный (свойство ассоциативности): (А+В)+С=А+(В+С); (А*В)*С=А*(В*С).

Распределительный (свойство дистрибутивности): А*(В+С)=А*В+А*С; А+В*С=(А+В)*(А+С).

3.7.2 Теоремы

Поглощения: А+А*В=А; А*(А+В)=А.

Склеивания:

Де Моргана. Существует две формы записи теоремы де Моргана:

("16") Форма 1:(3.1.1)

Форма 2:(3.1.2)

Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).

Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:

(3.1.3)

Два полезных соотношения:

(3.1.4)

3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений

СДНФ является одной из аналитических форм представления переключательных функций. Булевы выражения простых логических функций можно записать по их словесному описанию. В общем случае для получения аналитической формы (булевого выражения) используют таблицы истинности.

Предположим, логическая функция трех переменных задана таблицей истинности (таблица 3.4).

Таблица 3.4

№набора	С	В	А	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	0

("17") Эта функция имеет четыре конституенты единицы К1, К4, К5 и К6 (коституента единицы – это единичное значение ПФ на одном конкретном наборе. Всего для ПФ трех переменных может быть восемь конституент единицы, если функция принимает единичное значение на всех наборах). Конституента единицы записывается в виде конъюнкции. Для нашего примера ; .

Булево выражение ПФ в СДНФ представляет сумму конституент единицы:

.(3.2)

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

СДНФ называется дизъюнктивной (состоит из суммы конъюнкций), совершенной (все конъюнкции содержат по одному разу каждую переменную в прямом или инверсном виде) и нормальной (двухуровневой) – для ее реализации требуются логические элементы двух видов: конъюнкторы и дизъюнкторы, при этом предполагается, что исходные переменные поступают в прямом и инверсном виде.

3.9 Дизъюнктивная нормальная форма (ДНФ)

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

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

3.10 Совершенная конъюнктивная нормальная форма (СКНФ) записи булевых выражений

Описанная таблицей 3.4 переключательная функция помимо конституент единицы содержит конституенты нуля К0, К2, К3 и К7 (конституента нуля – это нулевое значение ПФ на одном конкретном наборе). Всего для ПФ 3-х переменных может быть восемь конституент нуля, если функция принимает нулевое значение на всех наборах. Конституента нуля записывается в виде дизъюнкции. Для нашего примера (таблица 3.4) это

Булево выражение в СКНФ представляет собой произведение конституент нуля:

.(3.3)

СКНФ называется конъюнктивной (состоит из произведения дизъюнкций), совершенной (все дизъюнкции включают по одному разу каждую переменную в прямом или инверсном виде) и нормальной (двухуровневой) – для ее реализации требуются логические элементы двух видов: конъюнкторы и дизъюнкторы, при этом предполагается, что исходные переменные поступают в прямом или инверсном виде.

Логическая функция имеет единственное булево выражение в СКНФ.

3.11 Конъюнктивная нормальная форма (КНФ)

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

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

3.12 Минимизация логических функций

("18") Минимизацией называют процедуру упрощения аналитического выражения, представляющего переключательную (логическую) функцию, направленную на то, чтобы булево выражение ПФ содержало минимальное количество членов с минимальным числом переменных.

Способы минимизации:

– алгебраический;

– с помощью диаграмм Вейча (карт Карно).

3.12.1 Алгебраический способ минимизации ПФ

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

Пример 1. Исходное булево выражение:

.(3.4)

Применяя теорему склеивания, получим булево выражение

,(3.5)

которое равносильно (эквивалентно) исходному, но значительно проще его.

Пример 2. Исходное булево выражение:

.(3.6)

Используя тождество А=А+А и теорему склеивания получим более простое выражение

.(3.7)

Такие элементарные приемы минимизации удается использовать, если исходное булево выражение содержит малое количество членов с небольшим числом переменных.

Более наглядным и удобным является минимизация с применением диаграмм Вейча (карт Карно).

3.12.2 Минимизация ПФ с использованием диаграмм Вейча (карт Карно)

Диаграммы Вейча (карты Карно) [3, 11, 18] построены так, что их соседние клетки содержат члены исходной ПФ, отличающиеся значением одной переменной: один член содержит эту переменную в прямой форме, а другой – в инверсной. Благодаря этому возникает наглядное представление о различных вариантах склеивания смежных членов.

3.12.2.1 Минимизация ПФ с помощью диаграмм Вейча

("19") Исходным продуктом для применения диаграмм Вейча является представление ПФ таблицей истинности, в которой возможные наборы переменных упорядочены по возрастанию или по убыванию их десятичных эквивалентов (таблица 3.1). Вид диаграмм Вейча зависит от числа переменных минимизируемой ПФ - n и от того, как упорядочены наборы переменных в таблице. Если наборы упорядочены по возрастанию их десятичных эквивалентов, то диаграммы Вейча для n=2,3,4 имеют вид, приведенный на рисунке 3.1.

Рисунок 3.1

Число клеток диаграммы равно количеству наборов переменных

Nкл=Nнаб=2n.(3.8)

Если n=2, то Nкл=22=4; n=3 – Nкл=8, n=4 – Nкл=16.

Каждая клетка соответствует определенному набору переменных и имеет номер, одинаковый с номером набора.

Строки и столбцы диаграммы, помеченные чертой, определяют наборы, в которых переменные принимают единичные значения (входят в прямой форме). Строки и столбцы, не помеченные чертой, соответствуют наборам, в которых те же переменные принимают нулевые значения (входят в инверсной форме). Например, для n=3 (рисунок 3.1) двум левым столбцам соответствует единичное значение переменной В (в входит в прямой форме), а двум правым – нулевое значение (в входит в инверсной форме).

В клетки записываются значения ПФ на соответствующем наборе (нулевое или единичное). Если на каком-то наборе функция не определена, то в клетке диаграммы ставится прочерк.

ПФ считается неопределенной, если:

1) данный набор переменных в реальном логическом устройстве невозможен;

2) значение функции на данном наборе безразлично.

После заполнения диаграммы можно приступить непосредственно к минимизации, которую производят по единицам или нулям.

В первом случае результатом минимизации будет булево выражение в ДНФ, а во втором – в КНФ.

3.12.2.1.1 Общие правила минимизации

Минимизацию можно проводить по единицам (нулям). При этом:

1) Смежные единицы (нули) диаграммы условно охватывают (накрывают) прямоугольными контурами. Каждый контур может содержать 2,4,8,16, ... единиц (нулей).

2) Одним контуром (накрытием) необходимо объединить максимальное количество смежных клеток, содержащих единицы (нули).

3) Необходимо, чтобы каждая единица (нуль) накрывалась хотя бы один раз.

4) Одна и та же единица (нуль) может охватываться несколько раз разными контурами.

("20") 5) Верхняя и нижняя строки диаграммы считаются смежными - их можно представить таковыми, если мысленно свернуть диаграмму в горизонтальный цилиндр.

6) Левый и правый столбцы также считаются смежными - диаграмму можно мысленно свернуть в вертикальный цилиндр.

7) Угловые клетки также считаются смежными - диаграмму можно мысленно свернуть в тор.

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

9) Результатом минимизации является булево выражение в ДНФ (КНФ). Количество конъюнкций в ДНФ (дизъюнкций в КНФ) соответствует числу контуров (накрытий).

10) В каждую конъюнкцию (дизъюнкцию) войдут только те переменные, значение которых в пределах контура не меняется (переменная принимает в накрытии только единичное или нулевое значение (входит только в прямой или инверсной форме)).

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

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

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

На рисунке 3.1 показаны диаграммы Вейча при числе логических переменных n=2,3,4. Для n>4 диаграммы содержатся в [18]. Если наборы переменных исходной таблицы истинности упорядочены по убыванию их десятичных эквивалентов, то следует воспользоваться диаграммами Вейча, приведенными в [5, 6]

3.12.2.1.2 Примеры минимизации ПФ с помощью диаграмм Вейча

Пример 1. Для контроля за возможной деформацией металлической конструкции из-за перегрева в ее различных критических точках установлены четыре термодатчика, обозначенные ТД1, ТД2, ТД3, ТД4. Экспериментальные исследования конструкции показали, что в процессе ее эксплуатации возможны шесть сочетаний сработавших и не сработавших датчиков. При этом деформация конструкции возникала в следующих случаях:

1) сработали ТД4, ТД3 и не сработали ТД2 и ТД1;

2) сработали ТД4, ТД3, ТД2 и ТД1;

3) сработали ТД2 и не сработали ТД4, ТД3 и ТД1;

4) сработали ТД3, ТД2 и ТД1 и не сработал ТД4;

В случаях, когда:

5) сработали ТД4, ТД3, ТД2 и не сработал ТД1;

6) сработали ТД2, ТД1 и не сработали ТД4, ТД3

деформация конструкции не возникала.

("21") Таблица 3.5

№	Состояние датчиков	Деформация конструкции
Сработали	Не сработали
1	ТД4, ТД3	ТД2, ТД1	Возникала
2	ТД4 ... ТД1	―
3	ТД2	ТД4, ТД3, ТД1
4	ТД3, ТД2, ТД1	ТД4
5	ТД4, ТД3, ТД2	ТД1	Не возникала
6	ТД2, ТД1	ТД4, ТД3

По условию эксплуатации конструкции другие сочетания сработавших и не сработавших датчиков невозможны.

("22") Необходимо спроектировать цифровое логическое устройство, включающее сигнал тревоги, если происходит срабатывание термодатчиков в опасном сочетании.

Обозначим цифровые сигналы на выходе термодатчиков логическими переменными: ТД4→D; ТД3→С; ТД2→В; ТД1→А, а логическую функцию, которую должно реализовать устройство контроля – F.

Составим таблицу истинности, отражающую требуемую логическую функцию (таблица 3.6).

Таблица 3.6

	(ТД4)	(ТД3)	(ТД2)	(ТД1)
№ набора	D	C	B	A	F
0	0	0	0	0	-
1	0	0	0	1	-
2	0	0	1	0	1	3)
3	0	0	1	1	0	6)
4	0	1	0	0	-
5	0	1	0	1	-
6	0	1	1	0	-
7	0	1	1	1	1	4)
8	1	0	0	0	-
9	1	0	0	1	-
10	1	0	1	0	-
11	1	0	1	1	-
12	1	1	0	0	1	1)
13	1	1	0	1	-
14	1	1	1	0	0	5)
15	1	1	1	1	1	2)

("23")
Диаграмма Вейча, отражающая данную таблицу, показана на рисунке 3.2.

Рисунок 3.2

Если будем производить минимизацию по единицам, то в клетки, содержащие прочерки проставим дополнительные единицы.

Основные единицы накрываем тремя контурами: 1-й контур (1I) образуют клетки первой и последней строки, 2-й (1II) - клетки 2-го столбца и 3-й (1III) - 4-го столбца.

Итоговое булево выражение минимизированной ПФ имеет вид

.(3.9)

Это выражение должно быть реализовано цифровым логическим устройством, включающим сигнал тревоги.

Рассматриваемую функцию можно минимизировать и по нулевым значениям (нулям). Для этого доопределяем клетки с номерами 1,6,9 и 11 нулями и накрываем два основных нуля двумя прямоугольниками, включающими два и четыре элемента (нуля). Первый прямоугольник (0I) охватывает клетки с номерами 6,14, второй (0II) – 1,3,11 и 9.

Итоговое булево выражение минимизированной ПФ имеет вид

.(3.10)

Оба выражения (3.9) и (3.10) эквивалентны, и применять следует то из них, которое проще реализуется на конкретном наборе логических элементов (базисе). Этот вопрос будет рассмотрен в следующих лекциях.

Пример 2. Необходимо разработать блок приоритетных прерываний от 2-х внешних устройств: ВУ1 и ВУ2. ВУ с меньшим номером соответствует более высокий приоритет. Упрощенная структура проектируемой системы показана на рисунке 3.3.