Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

Как было показано выше, физическими аналогами •символов двоичного алфавита 0 и 1 в логических схемах ЦВМ являются два хорошо различимых значения напря­ жения, тока, электрического сопротивления или магнит­ ной индукции и т. п. в зависимости от физической приро­ ды применяемых схемных элементов. Связи между вход­ ными и выходными сигналами в комбинационных схе­ мах аналитически описываются булевыми функциями.

Любая булевая функция может быть задана табли­ цей ее значений в зависимости от значений аргументов. Булевы функции одной и двух переменных, их условные обозначения и наименования приведены в табл. 3-4 и 3-5 соответственно.

Читатель легко может проверить справедливость со­ отношений, устанавливающих связь между функциями «штрих Шеффера» и «стрелка Пирса» и функциями конъюнкции, дизъюнкции и отрицания:

fl4 (х, У) = х/у = ху; /8 (х, у) = X ; у = х у у . (3-9)

Некоторые из приведенных в табл. 3-5 функций мо­ гут быть распространены на число независимых пере­ менных больше двух. Например, можно рассматривать булевы функции

f(x1,x 2,...,xn) = x1x2...xn-

f(x1,x2,...,xn)= xl x y . . x n = x&2...xn.

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

Например, приведенная в табл. 3-5 функция f і3 мо­ жет быть получена из функции f ц путем перенумерации (переименования) аргументов. Функция «штрих Шеффе­ ра» может быть получена из функции отрицания f (х) =

= х путем подстановки вместо аргумента х другой бу­ левой функции — К О Н Ъ Ю Н К Ц И И Х \ Х 2.

122

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

/(1, !,•••, 1) = 1; 3) самодвойственной функцией, если справедливо

f(x1, x 2,...,xn)==f(x1,x2,...,xny,

4) монотонной функцией, если при

где cti — постоянные: 0 или 1.

Примерами функций, обладающих свойствами 1 и 2, являются функции f і(х, у ) = х у и f7(x, у ) = х V У, так как

123

то она является функционально полной.

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

(ß ) j f 7( * ,?/) = х\/у\

1 f із (х) = •*:

и

(С) (Л (X, У) =--ху\

If 12(X) = X .

В системе (В) отсутствующую конъюнкцию можно получить, используя дизъюнкцию отрицаний согласно формуле де Моргана

В системе (С) дизъюнкцию получают, используя отри­ цания и конъюнкцию согласно выражению

В справедливости этих формул нетрудно убедиться их непосредственной проверкой.

124

Функционально полной будет также система, состоя­ щая из одной-единственной булевой функции «штрих Шеффера»:

(D)/і4 (х, у) = X у — ху.

Всистеме (D) инверсию, дизъюнкцию и конъюнкцию получают, используя соотношения:

X = х/х;

х Ѵ У = (хІх)І(у:у); ху = (х/у):'(х;у).

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

(E)fH(x,y) = X Іу=ху~у.

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

3-4. Т Е Х Н И Ч Е С К И Е А Н А Л О Г И Б У Л Е В Ы Х Ф У Н К Ц И Й . Э Л Е М Е Н Т А Р Н Ы Е А В Т О М А Т Ы

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

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

Элементарные логические операции над двоичными переменными реализуются элементарными электронны­ ми схемами, которые называются электронными логиче­ скими элементами или просто логическими элементами. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции.

Рассмотрим принципиальные электрические схемы некоторых логических элементов.

Логическая функция ИЛИ (дизъюнкция) f(x !,х2 хп) = х1Ѵ х 2Ѵ ...Ѵ х п

реализуется простейшей диодной схемой, показанной на

125

рис. 3-5. Такая схема имеет несколько названий: логи­ ческий элемент ИЛИ, клапан ИЛИ, схема сборки. Здесь аргументы, равные 1, представляются положительными электрическими сигналами высокого уровня (единичные сигналы), а аргументы, равные 0, представляются элек­

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

Примером комбинационной схемы И, реализующей функцию И (конъюнкцию)

f(x 1, x 2,...,xn) = x lx2...xn,

является схема, показанная на рис. 3-6, которая отлича­ ется от схемы ИЛИ направлением включения диодов. Схема И называется также «схемой совпадения» или «клапаном И». Если хотя бы на одном из входов такой

126

Эти же схемы являются соответственно схемами И и ИЛИ для входных сигналов, логическое соответствие ко­ торых изменено на обратное, т. е. высокий уровень на­ пряжения соответствует сигналу логический 0, а низкий уровень напряжения — сигналу логическая 1. Действи­ тельно, в этом случае схема на рис. 3-6 выполняет логи­ ческую операцию ИЛИ, потому что когда на всех вхо­ дах сигнал 0 (высокий уровень напряжения), то на выходе схемы тоже сигнал 0, так как все дио­ ды закрыты и на выходе высокий уровень напря­ жения; если на любом из входов появится сигнал 1 (низкий уровень напря­ жения), то на выходе схе­ мы будет сигнал 1, так как один из входных дио­ дов открыт, ток протекает на вход схемы и на выход

поступает низкий уровень напряжения.

На рис. 3-7 представлена схема инвертора, который реализует логическую функцию НЕ (отрицание):

f(x) =х.

Если на вход инвертора подан положительный еди­ ничный сигнал, то транзистор открыт и находится в ре­ жиме насыщения. На выход схемы НЕ поступает сигнал логический 0, близкий к потенциалу эмиттера транзисто­ ра. Если на вход схемы НЕ подается нулевой сигнал, то транзистор закрыт отрицательным смещением от источ­ ника Еб и на выходе схемы будет сигнал 1, близкий к потенциалу коллекторного источника питания.

При проектировании функциональных схем ЦВМ ло­ гические элементы обозначают прямоугольником, в ко­ торых стоят знаки & (конъюнкции) или 1 (дизъюнк­ ции). Инверсия переменной (отрицание, НЕ) обознача­ ется кружком со стороны выхода схемы. Рекомендуется линии связи подводить к вертикальным сторонам прямо­ угольников: входы — слева, выходы — справа.

127

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

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

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

На рис. 3-8 в качестве примера приведена функцио­ нальная схема некоторого устройства, составленного из логических элементов, обозначенных символами в соот­ ветствии с выполняемой ими логической операцией. Пунктиром на рис. 3-8 обозначены конструктивные мо­ дули. Модуль Ml выполняет функцию 2И—ИЛИ—НЕ, модуль М2 выполняет функцию 2 (И—И ЛИ —НЕ). По­ нятие логического элемента и конструктивного модуля ЦВМ нетождественны, так как конструктивный модуль (ячейка) может содержать не один, а несколько логиче­ ских элементов, иметь более одного выхода, иметь спе­ циальные выводы, позволяющие производить перекоммутацию входов и, таким образом, реализовать в одном

128