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

ИССЛЕДОВАНИЕ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ

Самостоятельная работа

по дисциплине «Теория дискретных устройств автоматики и телемеханики»

Студент гр. 40-В

А.Ю.Сахарчук

Руководитель –

А.В.Мальцева

Омск 2012

Задание. Провести анализ комбинационной схемы, минимизировать логическую схему и синтезировать устройство в заданных базисах логических элементов.

Исходная схема и данные:

Вариант 48.

Рис.1. Исходная схема для всех вариантов

№ варианта	DD1	DD2	DD3	DD4	DD5	DD6	DD7	DD8
	НЕ	НЕ	И-НЕ	ИЛИ-НЕ	ИЛИ	ИЛИ	И	И-НЕ

Данные из таблицы вариантов:

Анализ исходных данных:

Элементы схемы DD1 и DD2 – инверторы.

Функции других элементов указаны в таблице.

Итак, заданная схема представлена на рис. 2.

Рис.2. Исходная схема для 48 варианта

Решение.

1. Определение функций на выходах всех микросхем без преобразований.

Для наглядности составим таблицу.

Таблица 1

Таблица выходов логических элементов

Логическая схема	Вход	Функция
DD1	b	f1 =`b
DD2	d	f2 =`d
DD3	a, f1	f3 =
DD4	c, f2	f4 =
DD5	b, f2	f5 =
DD6	f3, f4	f6 =
DD7	f3, f5	f7=
DD8	f6, f7	f8=

Теперь необходимо получить зависимости выходов комбинационно­го устройства от его входов.

2. Составление таблицы истинности

Таблица истинности или состояния составляется для четырех переменных a, b, c и d.

Таблица 2

Таблица истинности для 4 переменных

Переменные	Функции выходов элементов схемы
a	b	c	d	f1=`b	f2=`d	f3	f4	f5	f6	f7	f8=Z

3. После составления таблицы истинности целесообразно перейти к совершенной дизъюнктивной нормальной фор­ме (СДНФ) и к совершенной конъюнктивной нормальной форме (СКНФ).

Запись функции Z в СДНФ:

Z =`a`b`c d Ú`a`b c d Ú a`b`c`d Ú a`b`c`d Ú a`b`c d Ú a`b c`d Ú a`b c d. (1)

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

В результате сравнения первого и второго слагаемых получим `a`b`d, первого и четвертого –`b`c`d, второго и третьего –`a`b c, второго и пятого –`b c`d,

третьего и шестого –`b c d, пятого и шестого – a`b c, четвертого и пятого – a`b`d и шестого и седьмого – a c d.

Проводя функции склеивания с минтермами третьего ранга, получим минтермы второго ранга:

`a`b d Ú a`b d =`b d; a`b`c Ú a`b c = a`b;

`b`c d Ú`b c d =`b d; a`b`d Ú a`b d = a`b.

Таким образом, получаем функцию

Z=`b d Ú a`b Ú`b d Ú a`b = a`b Ú`b d. (2)

Запись функции Z в СКНФ.

Из таблицы 1выбираем функции Z, равные 0:

Z = (a Ú b Ú с Ú d) (a Ú b Ú`с Ú d) (a Ú`b Ú с Ú d) (a Ú`b Ú с Ú`d) &

(a Ú`b Ú`с Ú d) (a Ú`b Ú`с Ú`d) (`a Ú`b Ú с Ú d) (`a Ú`b Ú с Ú`d) &

& (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d). (3)

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

Z = (a Ú a b Ú a c Ú a d Ú a b Ú b Ú b с Ú b d Ú a`c Ú b`c Ú 0 Ú`c d Ú a d Ú b d Ú с d Ú Ú d) (a Ú`b Ú с Ú d) (a Ú`b Ú с Ú`d) (a Ú`b Ú`с Ú d) (a Ú`b Ú`с Ú`d) (`a Ú`b Ú с Ú d) (`a Ú`b Ú с Ú`d) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (a Ú a b Ú a d Ú a`b Ú a`b d Ú a c Ú b c Ú c d Ú a d Ú b d Ú d) (a Ú`b Ú с Ú`d) (a Ú`b Ú`с Ú d) (a Ú`b Ú`с Ú`d) (`a Ú`b Ú с Ú d) (`a Ú`b Ú с Ú`d) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (a Ú a b c Ú a d Ú a`b Ú 0 Ú`b d Ú a c Ú b c Ú c d Ú a`d Ú b c`d Ú 0) (a Ú`b Ú`с Ú d) (a Ú`b Ú`с Ú`d) (`a Ú`b Ú с Ú d) (`a Ú`b Ú с Ú`d) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (a Ú a`b d Ú a b c Ú a c d Ú a b c`d Ú a`b Ú`b d Ú 0 Ú`b c d Ú 0 Ú a`c Ú`b`c d Ú 0 Ú 0 Ú 0 Ú a d Ú`b d Ú b c d Ú c d Ú 0) (a Ú`b Ú`с Ú`d) (`a Ú`b Ú с Ú d) (`a Ú`b Ú с Ú`d) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (a Ú a`b d Ú a`b c d Ú a`b`c d Ú a b c d Ú a c d Ú a`b Ú`b d Ú`b c d Ú`b`c d Ú 0

Ú`b c d Ú a`c Ú`b`c d Ú 0 Ú b`c d Ú0 Ú a`b Ú 0 Ú 0 Ú 0 Ú 0 Ú 0) (`a Ú`b Ú с Ú d) (`a Ú`b Ú с Ú`d) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (0 Ú`a`b d Ú`a`b c d Ú`a`b`c d Ú a`b Ú`b d Ú`b c d Ú`b`c d Ú a c Ú`b c d Ú`b c d Ú 0 Ú a d Ú`b d Ú`b c d Ú`b`c d) (`a Ú`b Ú с Ú`d) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (`a`b d Ú`a`b c d Ú`a`b`c d Ú 0 Ú`a`b d Ú`a`b`c d Ú 0 Ú 0 Ú`a`b d Ú`a`b c d Ú`a`b`c d Ú a`b Ú`b d Ú`b c d Ú`b`c d Ú a`b c Ú a`b d Ú`a`b c d Ú`a`b c d Ú 0 Ú a`b c Ú`b c d Ú`b c d Ú 0 Ú a c Ú a c d Ú 0 Ú 0 Ú 0 Ú a`b`d Ú 0 Ú 0 Ú 0 Ú a`b c Ú 0) (`a Ú`b Ú`с Ú d) (`a Ú`b Ú`с Ú`d) = (`a`b d Ú`a`b c d Ú`a`b`c d Ú 0 Ú`a`b d Ú Ú`a`b c d Ú`a`b`c d Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú`a`b d Ú

` a`b c d Ú`a`b`c d Ú a`b Ú`b d Ú`b c d Ú`b`c d Ú a`b c Ú a`b d Ú a`b c Ú a`b c d Ú a`b`d Ú a`b c`d Ú`a`b`c d Ú 0 Ú`a`b`c d Ú a`b`c Ú`b`c d Ú 0 Ú`b`c d Ú 0 Ú a`b`c d Ú 0 Ú 0 Ú a`b`c`d Ú 0 Ú`a`b d Ú`a`b c d Ú`a`b c d Ú a`b d Ú`b d Ú`b c d Ú`b`c d Ú

a`b c d Ú a`b d Ú a c d Ú a c d Ú 0 Ú 0) (`a Ú`b Ú`с Ú`d) = (`a`b d Ú`a `b c d Ú`a `b `c d Ú 0 Ú `a`b d Ú`a `b c d Ú`a`b`c d Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 Ú `a`b d

Ú`a`b c d Ú`a `b`c d Ú a`b Ú`b d Ú`b c d Ú`b`c d Ú a`b c Ú a`b d Ú a`b c d Ú a`b`d Ú a`b c`d Ú a`b`c Ú a`b`c d Ú a`b`c`d Ú a`b c d Ú`a`b`c d Ú 0 Ú`a`b`c d Ú a`b c Ú

`b`c d Ú`b c d Ú`b`c d Ú 0 Ú a`b`c d Ú 0 Ú a`b`c`d Ú 0 Ú a`b c Ú a`b`c d Ú a`b`c`d Ú 0 Ú 0 Ú 0 Ú 0 Ú a`b`d Ú 0Ú 0 Ú a`b c`d Ú 0 Ú 0 Ú a`b`d Ú a`b c`d Ú a`b`c`d Ú 0 Ú a`b`c`d Ú 0) = a`b`d Ú`a`b c d Ú`a`b`c d Ú a`b Ú`b d Ú`b c d Ú`b`c d Ú a`b c Ú

`a`b d Ú a`b c d Ú a`b`d Ú a`b c`d Ú a`b`c Ú a`b`c d Ú a`b`c`d = a`b Ú`b d (4)

Функции (2) и (4) совпадают.

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

4. Проверка полученного результата.

Вернемся к функции Z или f₈, полученной в результате анализа заданной схемы и внесенной в таблицу 1. Перейдем от сложных функций к простым и раскроем скобки. Пользуясь законами и тождествами алгебры логики, получим

Z = f₈ = ; f₆ = f₃ & f₄; f₃ = a Ú f₁; f₁ =`b; f<sub>4</sub> = ; f<sub>2</sub> =`d,

f₃ = a Ú`b, f₄ = .

Запишем структурную формулу для f₆:

f₆ = f₃ & f₄ = (a Ú`b) .

Не преобразовывая это выражение, находим функцию f₇:

Из табл. 1, f₇= . Функция f₃ определена выше, раскрываем функцию f₅.

f₅ = = . Подставляем полученные выражения в формулу для определения f₇.

f₇= = .

f₆ и f₇ определены, теперь получаем выражение для Z или f₈.

Z = f₈ = .

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

1 шаг – применяем формулу де Моргана для дизъюнкции:

Z = f₈ = & ;

2 шаг– применяем формулу де Моргана для конъюнкции:

Z = f₈ = ;

3 шаг– вновь применяем формулу де Моргана для дизъюнкции:

Z = f₈ = ; (–опять проблема с редактором формул!)

4 шаг – выполняем действия со скобками поочередно

Z= =`a b Ú(a c Ú a`d Ú `b c Ú`b`d)(d Ú`b) =`a b Ú (a c dÚ Úa`d d Ú`b c d Ú`b`d d Ú a c`b Ú a`b`d Ú`b`b cÚ`b`b`d) =`a bÚ a c dÚ`b cÚ`b`d. (5)

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

5. Определение минимальной формы с помощью Карт Карно

Строим таблицу для четырех переменных и анализируем функцию (1)

ab   cd
a b	a`b	`a`b	`a b
	c d		1
	c`d
	`c`d
	`c d

Столбцы и строки карты Карно обозначаются в коде Грея. Тогда клетки, которые могут склеиваться, находятся рядом друг с другом.

В результате операций склеивания получим, В результате операции склеивания

Z=`b c Ú`b`d Ú a c d (5)

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

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

Члены сокращенной формы (2, 4) являются просты­ми импликантами.

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

В импликантной таблице ставятся отметки. Если про­стая импликанта является составной частью какой-либо конституенты единицы, то на пересечении строки и столбца ставится условный знак.

Выполняем проверку как для выражения (2), так и (4)

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

Таблица 3

Простые импликанты (5)	Конституенты
`а`b`c`d	`а`b c`d	`a`b c d	a`b`c`d	a`b c`d	a`b c d	a b c d
`b`d	*	*		*	*
`а b
`b c		*	*		*	*
a c d						*	*

Анализируем полученный результат:

импликанты`b`d, `b c и a c d являются существенными: `b`d единственная, входящая в состав конституенты`a`b`c`d, `b c – в состав `a`b c d, a c d – единственная в столбце c конституентой аbcd. Эти три простые импликанты «закрывают» все столбцы. `а b не входит ни в одну конституенту, не является существенной и может быть исключена из дальнейшего рассмотрения.

Таким образом, в выражении (5) следует исключить это слагаемое:

Z =`b`d Ú`а b Ú`b c Ú a c d. Z =`b`d Ú`b d Ú a c d. (6)

7. Построение функциональной схемы устройства по полу­ченной минимальной ДНФ (сравнить с рис. 2).

Для построения удобно воспользоваться вертикальными шинкам a,b,c,d и формировать функциональные элементы в соответствии с выражением (6).

Рис.3. Реализация функции Z в базисе И-ИЛИ-НЕ

8. Запись функции (6) в базисах И-НЕ и ИЛИ-НЕ

8.1. Запись функции Z в базисе И-НЕ

Z =`b`d Ú`b с Ú a c d. Применяем двойное отрицание:

. (7)

Схемная реализация функции в базисе 2И-НЕ, рис.4

8.2. Запись функции Z в базисе ИЛИ-НЕ

Z =`b`d Ú`b с Ú a c d. Двойное отрицание каждого слагаемого и двойное отрицание полученного выражения

. (8)

Схемная реализация функции в базисе 2ИЛИ-НЕ показана на рис.5.

Рис. 4. Реализация функции (7) в базисе 2И-НЕ

Рис.5. Реализация функции (8) в базисе ИЛИ-НЕ

9. Моделирование в среде Electronics Workbench.

После запуска программы Multisim на рабочем поле собрать схему, соответствующую реализации функции в базисе И-НЕ, рис.4.(или другую по заданию преподавателя).Подавая с помощью ключей A, B, C, D значения логических переменных 0 или 1 на входы схемы убедиться в соответствии ее таблице истинности. Для проверки правильности работы схемы лучше подключить ко всем выходам элементов схем логический анализатор, рис.6.

Рис.6. Моделирование схемы, полученной в базисе И-НЕ

Проверку соответствия таблице истинности с помощью ключей вести сложно. Лучше использовать генератор слов, рис.7.

Рис.7. Проверка функционирования схемы в базисе И-НЕ с применением генератора слов и логического анализатора

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

Полученная функция была реализована на элементах И-НЕ, ИЛИ-НЕ, в релейно-контактном исполнении, а также смоделирована на цифровых интегральных микросхемах ТТЛ серии К155 в программной среде Electronics Workbench.

Дата добавления: 2015-10-24