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

Для связи импликации справедливо соотношение

которое легко проверяется по таблице истинности. Запишем выра­ жение (4.9) для отрицаний высказываний А и В:

Знак «->» обладает свойством коммутативности

Из (4.9) и (4.11) получаем новую эквивалентность:

А -> В = В -> А.

Если обе импликации А — В и В -> А истинны, то это значит, что не может быть одновременно А истинным, а В ложным, а также В — истинным, а Л — ложным. Поэтому высказывание

(Л В)-(В -> Л) = 1

означает, что Л и В имеют одинаковые значения истинности. Отсюда следует:

Из определения эквивалентности (—) вытекают следующие оче­ видные соотношения:

Л ~ В = В ~ Л,

(4.13)

Л ~ В = А ~ В.

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

А- В = А + В,

(4.14)

ХТ~В = Т И

или, что то же самое,

А - В = А + В ,

(4.15)

А + В = Х 1Т .

Анализируя получение эквивалентности, приходим к выводу что в алгебре логики можно заменять одни связи другими и обхо' диться совсем без некоторых простых связей, заменяя их сложными высказыванйями, и наоборот. Таким образом, из (4.12) следует, что связь «~» можно заменить связями «->-» и «•», а из (4.9, 4.15) сле­ дует, что «-^» и «+» можно заменить связями «—», «•».

91

Покажем, что для выражения сложных высказываний доста­

точно связей «—» и «+». Согласно (4.9) А -> В = А- В, но так как

А - В = А -'\г В, поэтому А - В = А + В ---■=А + Б, тогда

Из (4.16) и (4.15) вытекает, что связи «Д», «->» можно заменить

«+», «—»•

Таким же образом можно показать, что для образования слож­ ных высказываний достаточно применить связи «-*-», «—», поскольку согласно (4.15) связь «Д» можно заменять связями «V, + » и «—», а затем, согласно (4.17), заменять связь «+» на «->» и «—». При по­ мощи указанного способа замены связей можно образовать новые эквивалентности:

Выражение (4.18) следует из выражения (4.12), в котором связь «-г-» согласно (4.16) заменена на «+» и «—» и вытекает непосредст­ венно из определения связи «~». Как уже отмечалось, любую ло­ гическую связь можно заменить посредством связи Шеффера. Объединение простых высказываний составляет сложные высказы­ вания, например:

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

§ 6. ПРИМЕНЕНИЕ ОСНОВНЫХ ЗАКОНОВ БУЛЕВОЙ АЛГЕБРЫ ПРИ ПОИСКЕ ПРОСТОГО ВАРИАНТА ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ

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

92

Любое сложное высказывание путем эквивалентных преобразо­ ваний можно привести к так называемой совершенной нормальной форме (СНФ), которой называется выражение, состоящее из конъюнкции дизъюнкций или дизъюнкции конъюнкций.

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

При преобразовании сложных выражений в более простые не­ обходимо учитывать:

1. Со знаком «Д» и «\/» можно оперировать как в классиче­ ской алгебре, пользуясь законами (2, 7, 8).

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

а) исключают операции «->» и «~»; б) избавляются от общего отрицания, достигают того, чтобы

отрицание «—» оказалось над простыми высказываниями (исполь­ зовать правило де Моргана).

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

Пример 2. Покажем, что рассмотренная нами электрическая схема, реализующая логическую операцию импликации, может иметь более простую форму и схему, чем Tas которую мы получили (рис. 14). Для этого к формуле, представленной в виде комбинации операций логического отрицания, суммы и умножения, применимы некоторые из перечисленных правил.

Итак, исходная формула для импликации была такой:

Л = А -* Б = А - Б + А - Б + А - Б .

Применим правило (7) и вынесем во втором и третьем слагаемом общий член А за скобки: ~

АБ = А - Б + А ( Б + Б),

проще.

Продолжим упрощение. Воспользуемся формулой закона (7а) и внесем слагаемое в скобку. Получим: А Б -- {А + А)-(А + Б).'

93

Проверим полученную сумму при всех значениях Л и £ и убе­ димся, что и более простая формула дает прежнее отношение им­ пликации.

Электрическая схема, которая реализует упрощенную формулу, отношения импликации, также значительно упрощается (рис. 23).

Обозначим данное выражение буквор Л

Л = (*->• y ) A ( y ^ z ) / \ x - z .

Используем формулу (4.16), тогда имеем

Л = (x\/y)A(y\/z)/\x\Jz .

По правилу (9) избавляемся от общего знака отрицания, заме­ няя операцию логического произведения операцией суммы

A = (x\/y)\/(y\/z)\Jx\/z.

Теперь используем правило (9) и получаем A = x - y \ J y - z \ J

V x\Jz.

Следуя правилу (7), имеем;

Л = x - y\ J y-z\J x\Jz = (x-y)\J x\/(y-z)\J z.

Используя правило (7a), получим

Л = (xVx) ■(x\/y)\J(y\/z) -(z\/z) = (х\/ у) V (УVz) = x\J у У y\Jz =

= { y\ Jy) \/ x\fz = \\/x\Jz .

Тогда вся сумма по правилу (5) равна 1. Итак, окончательно:

Л = 1 \Jx\Jz= 1.

94

Таким образом, чисто формально проверено, что то заключение, которое имеет выражение (4.21), будет истинное — «1».

Упражнение.

Упростить логические выражения

1. х - > у 7 (х~у).

2.(х V у Л г) V ж А у.

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

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

докажем их справедливость с помощью законов (1— 12) 1. x\Jxy = x\ly.

Д о к а з а т е л ь с т в о : на основании (9, 11, 3) получим

х\ / х - у = (х у х ) ■(хv у) = i(x v у) = х М у .

2.x{x\Jy) = x- y.

Д о к а з а т е л ь с т в о : на основании (1, 11, 9) имеем

X(х Vу) = х ■XVху —ОVху = X■у,.

3.(x\Jy){x\Jz) = x-z\Jxy.

До к а з а т е л ь с т в о : с учетом (1, 11, 8, 7) получим

(x\Jy) (.x\Jz) = ( х\/y) x\ l {x\ l y) z — xx\Jyx\Jxz\jyz =

| = О \J xz-\-xy-\-yz = xz\J х у \/ yz = xz\J xy\J yz(x\J x) —

=xz\/ xy\j yzx\] yzx = xz\J xzy\J xy\j xyz =

=xz (1 V У) V ХУ(1V z) = xz V xy.

§7. АЛГЕБРА ЖЕГАЛКИНА

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

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

95

мы будем понимать произвольные булевы функции (обычные двоич­ ные переменные). Порядок выполнения операций в данной алгебре следующий: 1) выполнение операций в скобках; 2) операция умно­ жения; 3) операция сложения. Ниже будут установлены тождест­ венные соотношения в рассматриваемой алгебре.

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

геброй. Множество булевых функций рассматриваемых вместе с операциями умножения и сложения (по mod 2), называют алгеброй Жегалкина. В этой алгебре порядок выполнения операций анало­ гичен обычной алгебре (умножение, сложение). Нашей задачей является установление тождественных соотношений, имеющих ме­ сто в двух алгебрах.

Основные тождества алгебры Жегалкина

В алгебре Жегалкина оперируют с операциями

«-[-»—сложение по mod 2;

«•» — конъюнкция.

Установим основные тождества данной алгебры. Для сложения по mod 2, как и для умножения, имеют место законы коммутатив­ ности и ассоциативности:

Имеет силу дистрибутивный закон для умножения по отноше­ нию к сложению:

Закон сложения по отношению к умножению не имеет силы. Для операции с константами устанавливаются следующие тож­

дества :

Рассмотрим взаимосвязь между булевой алгеброй и алгеброй Жегалкина, для чего введем объединенную алгебру, использую­ щую операции отрицания, дизъюнкции, умножения и сложения

96

no mod 2. Подстановкой различных возможных наборов значений переменных устанавливаются следующие тождества:

По теории де Моргана:

x \ / y = x - y = ( x + l ) - ( y + l ) + l = x- y + y + x + l + l = Х + У + Х'У.

Рассмотрим примеры преобразования выражений булевой ал­ гебры в равные им выражения алгебры Жегалкина, а также при­

гебры Жегалкина и упростить полученное после преобразования выражение.

§ 8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ

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

тельных функций (табл. 4.2), которые в переключательной алгебре можно трактовать как элементарные операторы. Указанным опера­ торам могут быть поставлены в соответствие элементарные опе­ рации математической логики.

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

0) = 0. Поскольку на одном из наборов значения функций фикси­ рованы, произвольными остаются (в случае п переменных) лишь

зывается линейной, если ее возможно представить в виде канониче­

ление самодвойственных функций будет следующее.

Булева функция называется самодвойственной, если на любых двух противоположных наборах она принимает противоположные значения (0 и 1).

Самодвойственная функция в случае табличного способа зада­ ния функций будет иметь вид таблицы 4-14.

98

Из таблицы 4-14 видно, что при расположении набора в естест­ венном порядке противоположные друг другу наборы помещаются симметрично относительно середины этого расположения.

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

-fin

тов равно | Примеры:

1. /(%!, X2)= * lV * 2 , /*(*!, X2)==X1\/^2 = ^lA^2=^lA^2-

2. f2(x) = x, /* ( x)=J (x) = x = x.

функции (х, х г х г). Приведем определения для суперпозиции лю­ бого числа функции данного класса:

1)суперпозиция любого числа булевых функций, сохраняющих кон­ станту «О», является также функцией,сохраняющей константу «О»;

2)суперпозиция любого числа булевых функций, сохраняющих

константу «1», является функцией, сохраняющей константу «1»;

3)суперпозиция любого числа линейных булевых функций пред­ ставляет собою снова линейную функцию',

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

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

Свойства элементарных функций указаны в таблице 4-15.

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

Введенное определение легко распространяется на произволь­ ные булевы функции. При установлении необходимых и достаточ­ ных условий функциональной полноты большую роль играют пять классов булевых функций. Используя пять классов булевых функ­ ций в работе «Синтез цифровых автоматов», В. М. Глушков рас-

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

Теорема гласит: Для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала по крайней мере одну функцию: 1) не сохраняющую константу «О», 2 ) не сохра­ няющую константу «1», 3) несамодвойственную, 4 )немонотонную, 5) нелинейную.

Доказательство необходимости описываемых в этой теореме свойств системой булевых функций вытекает из определений 1—5, а также из того, что тривиальные функции f (хг...........хп) -- xt при­ надлежат каждому (i — 1, . . . , п) из пяти классов булевых функ­ ций. Целью теоремы является построение в виде суперпозиций функ­ ции системы s и переменных (хг, . . . , хп) любой заданной булевой функции f (х1г . . . , хп) этих переменных.

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

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

100