1432

Другое название переключательной функции ИЛИ (дизъюнкция) – логическое сложение, ПФ И (конъюнкция) – логическое умножение, а ПФ f6 (сумма по mod2) – исключающее ИЛИ. В инженерной практике нашли наибольшее применение логические элементы (ЛЭ), реализующие следующие ПФ: f1 (И, AND), f7 (ИЛИ, OR), f6 (исключающее ИЛИ, XOR), функции Пирса f8 (И–НЕ, NAND) и Шеффера f14 (ИЛИ–НЕ, NOR), а также вырожденные функции – инверсия f10, f12 (НЕ, NOT) и повторение f3, f5 аргументов. Остальные ПФ (в том числе и любая ПФ из указанных) могут быть получены посредством суперпозиции из нескольких (или даже одной) базисных ПФ, как будет показано далее.

На рис. 8.1 показаны условные графические обозначения (УГО) основных логических элементов: повторителя, инвертора (НЕ), И, ИЛИ, И–НЕ, ИЛИ–НЕ, суммы по модулю 2 (исключающее ИЛИ).

Рис. 8.1

71

8.3. Способызаданияпереключательныхфункций

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

совершенных конъюнктивных и дизъюнктивных нормальных форм.

Введем следующие определения.

Конъюнкция называется элементарной (ЭК), если она содержит любое количество попарно различных между собой переменных со знаками отрицания или без них, например ЭК x1x 2 , x1x3 x4 .

Дизъюнкция называется элементарной (ЭД), если она содержит любое количество попарно различных между собой переменных со знаками отрицания или без них, например ЭД x1 x2 , x1 x3 x4 .

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция

элементарных конъюнкций. y = x1x2 x2x3 x1x2x3.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция

элементарных дизъюнкций. y = (x1 x2 x3)(x1 x2)

Преобразование ДНФ КНФ совершается по правилам, изложенным выше (п. 8.2).

Пример. Преобразуйте ДНФ в КНФ. Используя дистрибутивный закон и закон отрицания, получим

x1x 2 x1x 3 = ( x1x 2 x1 ) ( x1x 2 x 3 ) =

= ( x1 x1 ) ( x1 x 2 ) ( x1 x 3 ) ( x 2 x 3 ) = ( x1 x 2 ) ( x1 x 3 ) ( x 2 x 3 ) .

73

Для определения совершенных нормальных форм (СДНФ и СКНФ) введем следующие понятия.

Конституентой единицы (Ki, КЕ) называется ЭК n аргументов, принимающая значение 1 лишь на одном наборе.

Конституентой нуля (Mi, КН) называется ЭД n аргументов, равная 0 лишь на одном наборе.

Общее число Ki и Mi, определенных на всех наборах, равно 2n (для ПФ n аргументов).

m

Совершенной ДНФ называется дизъюнкция всех КЕ этой функции. U Ki i

k

Совершенной КНФназывается конъюнкция всех КН этой функции I M j . j

Согласно этим определениям из таблицы истинности (табл. 8.2) для функ-

цииy1(x2, x1, x0), имеемСДНФy1 = K1 K2 K4 K5 K7, СКНФy1 = M0M3M6.

Сформулируем правило записи Кi и Mi.

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

Для записи КН правило обратное: аргумент записывается в КН в прямой форме, если на данном наборе его значение равно 0, и в инверсной форме, если его значение на наборе равно 1.

Тогда СДНФ y1 = x 2 x 1x0 x 2 x1x0 x 2 x1x0 x 2 x1x0 x 2 x1x0 ,

СКНФ y1 = ( x 2 x 1 x0 ) ( x 2 x1 x0 ) ( x 2 x1 x0 ) .

Переход от СДНФ к СКНФ (и обратно) может быть совершен по формальным правилам.

1. Запишите новую СДНФ (СКНФ) из КЕ (КН), не входящих в исходную, функциюнапример изтабл. 8.2 следует, что y*1 = x 2 x1x0 x 2 x1x0 x 2 x1x0 .

2.В новой СДНФ (СКНФ) операцию ИЛИ замените на И, а операцию И –

на ИЛИ, т.е. y**1 = (x2 x1 x0 )(x2 x1 x0 )(x2 x1 x0 ) .

3.Инвертируйте аргументы для завершения преобразования:

y***1 = (x2 x1 x0 )(x2 x1 x0 )(x2 x1 x0 ) = y1.

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

74

8.4. Функциональнополныенаборы (базисы) переключательных функций

Система ПФ {y1, ..., yN} называется функционально полной (или бази-

сом), если любая ПФ из системы может быть определена суперпозицией функций {y1, ..., yN}.

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

Функционально полной является система функций И, ИЛИ, НЕ, но она не минимальна. Функция штрих Шеффера (И – НЕ) или стрелка Пирса (ИЛИ – НЕ) образуют минимальный базис. Возникает вопрос: что для переключательной функции считать минимальным представлением.

Примеры функционально-полных наборов

8.5. Минимизацияпереключательных функций

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

Основная задача проектирования логических схем (ЛС) и структур – реализация ПФ в заданном базисе при наименьшем числе логических элементов (корпусов ИМС и т.д.).

Известны аналитические методы: Квайна, Мак-Класки, Рота и др. В инженерной практике более распространен формальный метод минимизации с

помощью диаграмм Вейча (карт Карно). Диаграмма Вейча (ДВ) представля-

ет собой квадратную или прямоугольную таблицу с числом клеток 2n (n – число переменных) – по количеству всех конституент функции.

Если минимизация идет в ДНФ, то диаграмма Вейча заполняется единицами (конституентами 1), если в КНФ, то ДВ заполняется нулями (конституентами 0). Таким образом, ДВ представляет собой иную форму записи таблицы истинности.

75

5.Преобразуйте ДНФ в КНФ: x x yz, x yz, xy xz, x y z x y z .

6.Преобразуйте КНФ в ДНФ: (x y)(x y z ), (x z)(x y z )( x y z ).

10.Преобразуйте СДНФ в СКНФ (аналитически и с помощью диаграмм Вейча): xyz xyz , xy z xyz x yz , xyz x yz , xyz xyz .

11.Преобразуйте СКНФ в СДНФ (аналитически и с помощью диа-

грамм Вейча): (x y z)(x y z)(x y z) ,

(x y z)(x y z )(x y z), (x y z )(x y z ) .

12.Постройте таблицы Ki и Mi для n=2, 3, 4.

13.Покажите функциональную полноту базисов И, НЕ; ИЛИ, НЕ; И – НЕ; ИЛИ – НЕ.

14.Найдите МДНФ и МКНФ и оцените их сложность:

(x1 x1x2x3)(x1x2 x1x3 x2x3); (x1x2 x1x3 x1x3)(x1x2 x1x3 x1x2x3); x1x3 x1x3 (x1x3 x1x2x3 x1x2x3); (x1 x3)(x1x2 x3); x1x2x3 (x1x3 x2x3).

8.8. Ссылки наиспользуемуюлитературу

[20; 29 – 32].

78

9. КОМБИНАЦИОННЫЕ УСТРОЙСТВА

9.1. Общиеположения

Комбинационное цифровое устройство (КЦУ) – это преобразователь

дискретной информации X в Y, причем входному двоичному слову X в данный момент времени однозначно и независимо от предыдущего состояния соответствует выходное слово Х в тот же момент времени. У КЦУ нет «памяти» о предыстории процесса. ЦУ с «памятью» называют автоматами. Они будут рассмотрены далее.

Элементарные КЦУ – логические элементы И, ИЛИ, НЕ, И – НЕ, ИЛИ – НЕ, И – ИЛИ – НЕ и т. п. Более сложные КЦУ состоят из элементарных и удовлетворяют двум условиям:

-входыпоследующихЛЭсвязанысвыходамипредыдущих(рис. 9.1, а);

-отсутствуют обратные связи с выходов последующих ЛЭ на входы предыдущих (замкнутые пути для сигналов) (рис. 9.1, б).

Рис. 9.1

Для КЦУ характерен принцип дуальности (следует из правила де Моргана). Если в КЦУ1, реализующей ПФ f(x1x2...xn), заменить И на ИЛИ, ИЛИ на И, проинвертировать входы xi, то полученная КЦУ2 реализует

f (x1x2...xn ) .

9.2. Базовыеинтегральныесхемы иихосновныепараметры

Логические интегральные схемы (ИС), выпускаемые промышленностью, представлены широкой номенклатурой интегральных серий на основе биполярных и полевых транзисторов.

79

Серии ИМС отличаются по целому ряду параметров в зависимости от технологий их изготовления (ТТЛ, ТТЛШ, ЭСЛ, КМОП, n-МОП, p-МОП

идр.).

Кчислу типовых параметров ИМС относят:

1) коэффициент разветвления по выходу Кразв(N) – число входов одно-

типных ИС, которые одновременно могут быть подключены к выходу данной ИС (нагрузочная способность ИМС);