1.4 Основные соотношения и законы алгебры логики.

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

1. сложение;

2. умножение;

3. вычитание.

X1	0	1	0	1
X2	0	0	1	1
F	0	1	1	1

X1	0	1	0	1
X2	0	0	1	1
F	0	0	0	1

X	0	1
F	1	0

Основные тождества алгебры логики выглядят следующим образом:

0+0=0 0 ·0=0

0+1=1 0·1=0

1+1=1 1·1=1

1. Переместительный закон:

X+Y=Y+X

X·Y=Y·X

2. Сочетательный закон:

X+(Y+Z)=(X+Y)+Z

X·(Y·Z)=(X·Y)·Z

3. Распределительный закон:

Z·(X+Y)=ZX+ZY

(Z+X)·(Z+Y)=Z+(X·Y)

4. Закон двойственности:

(правило де’Моргана)

5. Правило поглощения:

6.Правило склеивания:

7.Полезные тождества:

Пример.

используем тождество

1.

2.

3.

5. Упрощение структурных формул на основе карт Карно.

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

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

Для функции с небольшим числом переменных (до 5-6) наиболее употребительным методом минимизации является метод карт Карно.

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

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

Карта Карно для двух переменных.

Значения переменных обозначаются с внешней стороны карты посредством двоичных цифр «0» или «1». В самих клетках для соответствующих наборов переменных записываются значения логической функции «0» или «1» (по таблице истинности).

Карта Карно для функций трех и четырех переменных имеет следующий вид:

В клетках соответствующих единичным наборам таблицы истинности записывается «1», а в клетках соответствующих нулевым наборам записывается нуль.

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

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

При объединении клеток карты следует помнить следующие основные правила:

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

2. Клетки могут объединяться по две, по четыре, по восемь.

3. Одна и таже клетка может входить в несколько групп.

4. Минимизированная структурная формула записывается на основе наименьшей совокупности групп, которая захватывает все либо единичные (для СДНФ), либо нулевые (для СКНФ) клетки.

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

Пример 1.

Пусть имеется логическая функция F двух переменных X₁ и X₂. таблица истинности которой имеет вид:

Х1	0	1	0	1
Х2	0	0	1	1
F	0	1	0	1

Составим карту Карно:

(*)

Для группы из двух объединенных клеток 01; 11 используется обозначение Х₁, что соответствует операции склеивания (*).

Пример 2.

Предположим что логическая функция от трех переменных описывается следующей таблицей истинности:

Х1	0	1	0	1	0	1	0	1
Х2	0	0	1	1	0	0	1	1
Х3	0	0	0	0	1	1	1	1
F	0	1	0	1	0	1	0	1

Карта Карно для трех переменных имеет вид:

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

Пример 3.

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

При составлении структурной формулы по условному обозначению группы, слагаемые СДНФ получаются следующим образом:

1. Вместо единицы обозначения группы записываются соответствующие переменные.

2. Вместо нулей в обозначении группы записываются инверсии соответствующих переменных.

3. Знаки Х пропускаются.

0 Х1 1 Х 0 1 1 Х 1 Х 0 1 Х 0 0

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

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

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

Пример.

Пусть функция задана таблицей истинности.

Составим карту Карно для 5-ти переменных.

При минимизации функции необходимо помнить следующие правила:

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

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

3. Комбинации клеток, содержащих единицы и (или ), соответствуют два слагаемых минимизированной формы.

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

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

Минимизация функции шести переменных с использованием карты Карно из 16 клеток основывается на представлении исходной функции в следующем виде:

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