Цифровые устройства. Логические функции и их минимизация

План лекции
Логические функции
Способы задания функций
Пример перехода от таблицы к СДНФ
Карты Карно
Минимизация с помощью карт Карно
Минимизация частично определенных функций

Логические функции
Логической (двоичной, переключательной) функцией
Y = f (Xn-1, Xn- 2 ,...Xi , X0)
называется двоичная переменная Y, значения которой зависят от значений других двоичных переменных, называемых аргументами.
Если функция Y зависит от n аргументов, то полное число возможных двоичных наборов аргументов
p = 2^n .
Если логическая функция определена на всех наборах, то она называется полностью определенной.

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

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

Способы задания логических функций
1. Табличный
2. Алгебраический, например дизъюнктивная нормальная форма (ДНФ) - логическая сумма элементарных логических произведений:
F (A, B, C) = AB + AC
3. Числовой (под знаком суммы перечисляются номера наборов, на которых функция равна «1»)
F = Σ (1,2)

Правило перехода от таблицы к совершенной ДНФ
Для каждого набора, на котором функция равна единице, записывается элементарное произведение всех аргументов.
Причём если аргумент в этом наборе принимает значение 0, то пишется его отрицание.
Затем производится логическое сложение полученных элементарных произведений.
Примечание: совершенная ДНФ (СДНФ) содержит все переменные или их отрицания, например:
_ _ _
F (A, B, C) = АВС + АВС +АВС

Пример перехода от таблицы к СДНФ
Переход от табличного представления булевой функции к алгебраическому.
_ _
F (A, B) = АВ + АВ = А В

Построение комбинационной схемы
На основе полученной структурной формулы построим комбинационную схему, состоящую из логических элементов И, ИЛИ, НЕ.

Логический элемент «НЕ»
Отрицание (Операция «НЕ») Х-ка передачи и быстродействие
6 элементов «НЕ»
(К155ЛН1)
http://myrepititor.ru/electronics/82-Osnovnye_xarakteristiki_i_parametry_logicheskix_eleme.html

Логические элементы «2И» и «2ИЛИ»

Схема на логических элементах
Выводы 7 DD1-DD3 – общ.
Выводы 14 DD1-DD3 – +5В.

Представление функций картой Карно
Карта Карно представляет собой прямоугольник, разбитый на квадраты (ячейки), число которых равно общему числу наборов для данной функции
n-переменных, т.е. p = 2^n.
Для функции n = 3 и число ячеек равно 8. Следовательно, соответствует определенному набору, причем, если на этом наборе функция равна 1, то в ячейке проставляется 1, а если - 0, - то ставится 0.

Карты Карно
Карта Карно четырех переменных.

Правила применения закона склеивания
1. Если единицами заполнены две соседние строки или два соседних столбца, либо две строки или два столбца, расположенные по краям карты, то соответствующие восемь слагаемых четвертого ранга можно заменить слагаемым первого ранга (ранг — число переменных, входящих в слагаемое).

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

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

Пример применения карты Карно
Дана функция
F (A, B, C, D) = Σ (0, 3, 4, 5, 7, 8, 10, 11, 14, 15).
В виде структурной формулы она выглядит следующим образом:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
F = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD +
_ _ _ _
+ ABCD + ABCD + ABCD + ABCD.

Пример применения карты Карно
Нанесем эту функцию на карту Карно и, произведя все возможные склеивания, получим функцию
_ _ _ _ _
F = AC + CD + BCD + ABC,

Пример применения карты Карно
На карте Карно при нанесении на нее функции F остаются заполненные нулями квадраты, относящиеся к наборам, на которых функция
F = 0.
Логическая сумма слагаемых, соответствующая этим наборам, равна отрицанию функции F.
Иногда вместо группирования единиц целесообразно произвести группирование нулей.
В результате получается минимальная форма для F.

Пример применения карты Карно
Например, дана функция
F (A, B, C, D) = Σ (1,3,4,5,9,11,12-15),
которая представлена на карте Карно.
При группировании нулей получается
_ _ _ _
F = BD + ABC.

Пример минимизации
Минимизировать функцию четырех переменных путем склеивания минитермов.
_ _ _ _
F = BD + CD

Пример минимизации с факультативными условиями
Функция с обязательными и факультативными условиями записывается следующим образом:
F = Σоб (0, 2, 4, 6, 8) + Σф (10, 11, 12, 13, 14, 15).
После упрощения структурной формулы строят комбинационную логическую схему на базе логических элементов И, ИЛИ, НЕ.

Пример минимизации частично определенных функций
В таблице значения функции для номеров наборов 5, 6 и 7 не определены.
Карта Карно заданной функции

Пример минимизации частично определенных функций
При минимизации частично определенных функций производят произвольное задание значений функции на запрещенных наборах для получения наиболее простой минимальной ДНФ функции.
Значение функции до минимизации
Минимальная ДНФ

Задача
Построить схему на логических элементах
Задана булева функция
Задание:
1. Построить схему на логических элементах
НЕ, И, ИЛИ.
2. Выбрать серию ИС ТТЛ.
3. Проставить цоколевку.
4. Определить таблицу состояний.
5. Представить функцию числовым способом.

Список использованных источников и литературы
1. Нарышкин А.К. Цифровые устройства и микропроцессоры: учеб. пособие для радиотехн. специальностей вузов / А. К. Нарышкин. - М. : Академия, 2006. - 317 с.
2. Пухальский Г.И., Новосильцева Т.Я. Проектирование дискретных устройств для интегральных микросхем: Справочник. - М.: Радио и связь, 1990. - 304 с.
3. Пухальский Г.И., Новосельцева Т.Я. Проектирование цифровых устройств: Учеб. пособие. – СПб.: Изд-во «Лань», 2012. – 896 с.
4. Одинец А.И. Цифровые устройства. Конспект лекций. – Омск: ОмГТУ, 2009.-64 с.
5. Открытые источники Internet