книги из ГПНТБ / Сарингулян, Э. В. Арифметические и логические основы цифровых машин учеб. пособие

Пример. Найти сокращенную дизъюнктивную нормальную фо.рму логической функции

/ ( « , й, с, cl) : abc d V abc d У a b с d V a b с d.

Выполним операции склеивания:

первого члена со вторым по переменной a(bcd)_, первого члена с четвертым по переменной b(acd), второго члена с третьим по переменной b (acd), третьего члена с четвертым по переменной a{bcd). Затем проведем операции поглощения

f(a, b, с, d) — b c d y a c d y a c d y bed .

Полученное выражение позволяет провести еще раз опера­ ции склеивания:

первого члена с четвертым по переменной b(cd), второго члена с третьим по переменной a (erf). В результате имеем:

f(a, b, с, d) = be d\/а с d У ас d \ / b с d\/с d \ / cd-

Произведение cd поглощает первый, второй, третий и чет­ вертый члены, после чего сокращенная дизъюнктивная нор­ мальная форма имеет вид:

f(a, b, с, d) — cd.

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

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

70

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

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

1) логическая функция представляется в СКНФ в соответ­ ствии с последовательностью преобразований, рассмотренных на стр. 65;

2) выполняются все возможные операции склеивания и поглощения для конъюнктивной формы соответственно фор­ мулам

врезультате будет получена сокращенная КНФ;

3)определяется минимальная КНФ по таблице минимиза­ ции, которая строится по значениям конституент нуля СКНФ и по членам сокращенной КНФ. Выбирается наименьшее коли­ чество членов, перекрывающих отметками все столбцы табли­ цы и объединяющихся затем в логическое произведение.

Пример. Найти минимальную конъюнктивную нормальную форму для функции f(a , Ь, с) = (а \/Ь\/с) {а\/b y с) (а\/ Ь\/с),

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

Выполним операции склеивания:

первого члена со вторым по переменной с, первого члена с третьим ;по .переменной Ь:

f{a, b, с) — (а V Ь)(а у b \/ c){a\/b у с) ( а у с) (а\/ Ь\/ с).

Проведем операции поглощения:

(а \/ Ь) (а\/Ь\/с) (ауЬ\/с)(а\/с) (а \/ b V с) — (аУ b) (а V с).

Полученные члены между собой не склеиваются, поэтому сокращенная КНФ имеет вид:

/(a , b, с) = ( а у Ь) (а. У с).

Для отыскания минимальной формы строим таблицу мини­ мизации.

73

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

Плоскостная диаграмма представляет собой таблицу СДНФ заданной логической функции, разбитую на квадраты, каждому из которых соответствует определенный набор пере­ менных. Конституенты единицы функции п переменных распо­ лагаются в квадратах, число которых в плоскостной диаграм­ ме равно 2п. Склеивающиеся конституенты, обеспечивающие понижение ранга общей конъюнкции на единицу, для функции двух переменный располагаются в соседних квадратах диа­ граммы. Общая конъюнкция включает переменные, одинако­ вые для исходных конституант. Для функции двух переменных две соседние 'конституенты заменяются одной буквой; для функции трех переменных две соседние конъюнкции выра­ жаются произведением двух переменных, а четыре единицы — одной буквой. Для логической функции четырех переменных диаграмма разбита на 16 квадратов. В этом случае одной бук­ ве соответствует восемь соседних конституент единицы, конъ­ юнкции двух переменных — четыре единицы, конъюнкции трех переменных — две единицы.

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

74

Если функция задана в совершенной конъюнктивной нор­ мальной форме, то оклеивание реализуется по конституантам нуля, аналогично рассмотренному варианту задания функции в СДНФ. Рассмотрим примеры.

Пример. Найти минимальную дизъюнктивную нормальную форму функции /( а , b) — ab V ab \/ ab.

Т а б л и ц а 3.7

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

На диаграмме конституанты ab и ab можно склеить по переменной Ь, конетитуенты аЪ и сГЬ—-по а. Получим

f(a, b) — а V Ь.

Пример. Найти минимальную дизъюнктивную нормальную

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

f(a, b, с) = be V a c V ab;

f(a, b, c) = a b V a c V b c .

75

§ 3.3. Некоторые схемы основных логических элементов

Переключательные функции в цифровых машинах реали­ зуются логическим'!! схемами, выполненным!]! на электронных лампах, полупроводниковых элементах, магнитных двухпози­ ционных сердечниках и других физических элементах.

В зависимости от представления двоичных цифр выходны­ ми сигналами логических схем последние делятся на статиче­ ские, импульсные и фазовые. В статических схемах коды 1 и О преимущественно изображаются различными уровнями на­ пряжения, при импульсных выходах коду 1 соответствует обычно наличие импульса иди серии импульсов, а коду 0*—от­ сутствие таковых. В цифровых машинах статические и им­ пульсные схемы чаще всего 'используются совместно. В фазо­ вых схемах применяется фазовое кодирование двоичных цифр.

Логические функции ИЛИ, И надежно и достаточно просто реализуются с помощью схем на диодах. На рис. 3.7 показана логическая схема ИЛИ на три входа, принимающих код 1 в ви­ де положительного и код 0 в виде нулевого потенциалов.

-W-

X

Рис. 3.7

При подаче хотя бы на один из входов кода 1 через соот­ ветствующий диод и нагрузку R потечет ток. Падение напря­ жения на сопротивлении R эквивалентно выходному сигналу р —.1. При пулевых сигналах на всех входах р = 0.

Вариант выполнения схемы И с двумя входами на диодах приведен на рис. 3.8. Если на один из входов подан код 0, про­ текающий по сопротивлению R, ток вызывает падение напря­ жения, устанавливая на выходе потенциал, близкий к нулю, что эквивалентно р = 0. И только в том случае, если на оба вхо­

И

Рис. 3,8

77

Поскольку диоды являются пассивными элементами, то в диодных логических цепях происходит затухание передавае­ мых сигналов. Поэтому неооходимьш оказывается устанавли­ вать в логические схемы активные элементы, например, тран­ зисторные усилители (рис. 3.9).

P - x .v jc w x ,

Рис. 3 9

Но транзисторы могут использоваться в логических схемах не только как усилители, но и как элементы, реализующие ло­ гические функции. На рис. 3.10, а показана схема ИЛИ—НЕ па два входа. При параллельном включении транзисторов 7\ и Т2, имеющих общее коллекторное сопротивление RK, с подачей кодов 1, задаваемых низкими уровнями, на выходе бу­

дет снят сигнал р—л\\/х2,представленный высоким уровнем,

принятым за код 0(/7=1 \ 1=0). Если на оба входа поступа­ ют сигналы высокого уровня, что соответствует коду 0, то транзисторы закрыты и с выхода снимается сигнал низкого

уровня, кодирующий двоичную цифру 1 (p = 0 V 0 = l).

1 х,

в х о д

Схема II— НЕ (рис. 3. 10, б) выполнена на транзисторах Т\ и Гг, включенных последовательно и имеющих общее сопро­ тивление в коллекторной цени RK. Д!воич1Ные цифры кодируют­ ся аналогично рассмотренной схеме ИЛИ— НЕ. Коллекторный ток через сопротивление протекает® случае, если на оба входа

зависимость р= х\-х2. Элементы ИЛИ— НЕ, И— НЕ являются функционально полными, на базе которых может быть реали­ зована любая логическая функция.

Одним из широко применяемых элементов для построения логических схем является магнитный сердечник (феррит), об­ ладающий характеристикой в виде прямоугольной петли ги­ стерезиса. Действие его основано на свойстве сохранять одно из двух устойчивых состояний, соответствующих положитель­ ной (+ ДЧ) и отрицательной ( -Вч) остаточной магнитной ин­ дукции.

Эти устойчивые состояния используются для представления кода I и кода 0 (обычно -+-5,, соответствует коду 1, —В,,—ко­ ду 0). Для построения логических схем ферритовые сердечни­ ки с прямоугольной петлей гистерезиса применяются в сочета­ нии с полупроводниковыми элементами. Диоды и транзисторы обеспечивают однонаправленный поток сигналов в цепях связи логических схем, а полупроводниковые триоды — также и их усиление. По принципу работы схемы с ферритовыми сердеч­ никами являются токовыми. Ферритовые сердечники в соче­ тании с диодами образуют феррит-диодные ячейки. Основны­ ми обмотками сердечника в феррит-диодных ячейках являют­ ся обмотки записи, считывания и выходная (рис. 3.11, а).

Обмотка записи предназначена для записи кода 1, обмотка считывания — для стирания кода 1. Выходная обмотка обеспе­ чивает передачу сигнала па последующий каскад схемы. На­ чало обмоток обозначено точкой. При подаче импульса записи

79