Основы анализа и синтеза комбинационных логических устройств (стр. 5 из 14)

;

,

.

В рассмотренном примере двум клеткам первого объединения соответствуют минтермы, имеющие две общие переменные

.

Поэтому дизъюнкция этих минтермов равна этим двум общим переменным:

.

Четырем клеткам второго объединения соответствуют минтермы имеющие одну общую переменную

:

Дизъюнкция этих минтермов также равна общей переменной

.

Чем больше клеток входит в объединение, тем меньше переменных входит в соответствующий конъюнктивный член, т.е. проще МДНФ.

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

Необъединенные клетки считывают в виде записанных в них минтермов.

Число конъюнктивных членов в МДНФ равно сумме объединений и необъединенных клеток.

Пример 1.7. Логическая функция задана табл.1.8

Таблица 1.8

Таблица истинности

x1	x2	f
0	0	1
0	1	1
1	0	0
1	1	1

Найти СДНФ этой функции, и провести минимизацию с помощью карты Карно.

Решение: 1. Находят минтермы:

x1	x2	mi	f
0	0		1
0	1		1
1	0		0
1	1		1

2. Логическая функция в форме СДНФ:

.

3. Карта Карно логической функции (рис.1.6)

x1x2	0	1
0	1
1	1	1

Рис.1.6 Карта Карно логической функции

4. Получают МДНФ функции

.

Пример 1.8. Минимизировать с помощью карты Карно (рис.1.7) логическую функцию, заданную в форме СДНФ:

x1x2x3	00	01	11	10
0	1
1	1	1	1

Рис.1.7 Карта Карно

Решение: МДНФ функции:

.

Пример 1.9. Минимизировать с помощью карты Карно (рис.1.8) заданную в форме СДНФ логическую функцию:

.

x1x2x3	00	01	11	10
0	1	1	1	1
1	1	1

Рис.1.8 Карта Карно:

Решение: МДНФ функции:

1.7 Аналитические методы минимизации логических функций

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

Алгоритм получения МДНФ логической функции:

1. Логическая функция представляется в СДНФ. Причем, если она задана таблицей истинности, то представляют путем записи “по единицам”; если она задана алгебраической произвольной дизъюнктивной форме - путем применения операций развертывания, формул Де Моргана и др.

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

3. Находят минимальные дизъюнктивные нормальные формы по импликантной матрице.

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

Клетки импликантной матрицы, образованные пересечением строк с импликантами и столбцов с поглощательными ими членами СДНФ, отмечают крестиками [5].

МДНФ находят как дизъюнкцию минимального числа импликант, которые совместно накрывают крестиками все колонки импликантной матрицы.

Пример 1.10. Минимизировать логическую функцию:

Решение: 1. Функция задана в алгебраической форме, применяя операции развертывания

получают СДНФ, содержащую шесть членов:

2. Операции склеивания проводят в следующем порядке:

1) выполняются все возможные склеивания 1-ого члена с остальными;

2) выполняются все возможные склеивания 2-ого члена с остальными, кроме 1-ого;

3) выполняются все возможные склеивания 3-ого члена с остальными, кроме 1-ого и второго и т.д.

Склеиваться могут только те члены, у которых число переменных с отрицаниями отличается на единицу. Результаты склеивания и поглощения:

Звездочками отмечают те члены СДНФ, которые поглощаются произведениями, образовавшимися после склеивания.

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

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

3. Строят для заданной функции импликантную матрицу (табл.1.9)

Таблица 1.9

Импликантная матрица

Простые	Члены СДНФ
импликанты(минтермы)
	1	2	3	4	5	6
	X	X
	X	X
	X	X
	X	X
	X	X

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