Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

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

которое легко проверяется по таблице истинности. Запишем выра­ жение (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 элементарных переключа­