Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.07.2024
Просмотров: 98
Скачиваний: 1
7. Распределительные (дистрибутивные) законы
а) А ■(Б + В) = А Б ф-
+АВ
АМ Б У В) = ЛД
ЛБ У А Л В
б) В + (АБ) = (В +
+А ) • (В + Б)
ВУ ( А - В ) = ( В У А ) Х
Х( В У Б )
Конъюнкции относительно дизъюнкции (умножение относительно сложения). Это правило раскрытия скобок, как в обыч ной алгебре. Справедливость этого прави ла легко проверить на сравнении схем рис. 19, а, б. В логических формулах можно как раскрывать скобки, так и вы носить одинаковые члены за скобки.
Дизъюнкция относительно конъюнкции (сложение относительно умножения). Рас смотренное правило (7а) внешне совпадает с обычным правилом раскрытия скобок,
а) |
б) |
( А . Б ) + В = ( А + В ) Х
Х( Б + В)
{А ^ Б ) у В = ( А у В ) / \
Л(Б У В)
|
а) |
|
б) |
в |
В |
о А |
- А |
А |
|
О С |
|
|
||
|
|
|
|
|
|
|
- 4 |
Б |
|
Ч /
ч
В I _______ _
! Л=В+АБ
Рис. 20
или, наоборот, вынесения за скобки оди наковых сомножителей.
Данное правило не имеет прямой ана логии с обычной количественной алгеброй. На контактной схеме правильность этого закона очевидна: если мы замыкаем па раллельным контактом «В» некоторую по следовательную цепь А-В, то подключе ние параллельно контактов к каждому из последовательных дает такой же резуль тат, т. е. (рис. 20, а, б) схема б равноценна схеме а.
8. Сочетательные (ассоциативные) законы
а) (А - Б ) - В= А -(Б-В) |
Этим |
законам соответствуют схемы |
(А / \ Б ) / \ В ~ А /\ |
рис. 21, |
а, б. |
Л (£ Д В )
87
б) (А + Б ) + В = А +
+ (Б + В)
(Ау Б ) У В — А +
+ ( БУВ )
U.J |
■ОА О- |
А |
|
-о Б о - |
|
|
-°S |
В |
б)
15 о—о В
А о— о 5 о— о 5 о -..-> •
|
|
|
|
|
Рис. |
21 |
|
|
|
|
|
9. |
Закон де Моргана |
|
|
|
|
|
|
||
|
А - В = А + В |
Это правило можно выразить так: если |
||||||||
а) |
имеется произведение и над ним стоит об |
|||||||||
|
A f\ B = A y B |
щее отрицание, то можно заменить знак |
||||||||
|
|
|
|
произведения на знак суммы (конъюнк |
||||||
|
|
|
|
цию |
на |
дизъюнкцию), |
|
если |
отрицание |
|
|
|
|
|
«разорвать», поставить его отдельно над |
||||||
|
|
|
|
каждым членом суммы. Физический смысл |
||||||
|
|
|
|
этого правила очевиден. Например, если |
||||||
|
|
|
|
цепь имеет два последовательных контакта |
||||||
|
|
|
|
и проводит ток лишь когда нажаты кнопки |
||||||
|
|
|
|
А и Б (т. |
е. когда и А |
и Б — 1), то цепь |
||||
|
|
|
|
не проводцт ток, когда не нажата либо |
||||||
|
|
|
|
одна (т. е. А), либо другая (т. е. Б) кнопка, |
||||||
|
|
|
|
либо они обе вместе (т. е. |
и А и Б). |
|||||
б) |
А + |
Б = А ■Б |
Смысл этого варианта правила де Мор- . |
|||||||
А У Б = А Д Б |
гана такой же, как и «а». |
|
|
|||||||
Правило де Моргана («а» и «б») читается: |
||||||||||
|
|
|
|
«отрицание конъюнкции есть дизъюнкция |
||||||
|
|
|
|
отрицаний»; «отрицание дизъюнкции есть |
||||||
|
|
|
|
конъюнкция отрицаний». |
|
|
||||
|
Справедливость вышерассмотренных |
законов |
легко установить |
|||||||
с |
помощью |
таблиц |
соответствия двухместных булевых функций, |
|||||||
определяя |
значения |
правых |
и левых |
частей |
законов |
(1 — 8) на |
||||
всех наборах значений аргументов. |
|
|
|
|
||||||
|
Убедимся таким способом в справедливости одного |
из законов |
||||||||
( 12). |
|
|
|
|
|
|
|
|
|
|
х У х —- 1,
88
так как при х — О
0\/0 = 0\/1 — 1 и при х — 1,
1 V T = 1 VO = 1 ;
то справедливость закона доказана.
10. Логическое отношение импликация «если, то . . .». Закономерность этого правила легко установить, если рассмот
рим электрическую схему (рис. 22) и составим таблицу истинности
(табл. 4-12).
Из таблицы истинности видно, что лампочка горит все время за
исключением случая, когда кнопка А нажата, |
а кнопка Б — нет. |
||
11. Закон поглощения (абсорбции) |
|||
*lA(*lV-*a) = *l. x1\J{x1f \ x 2) ^ x 1 |
|||
Xi (ху+ х2) == |
|
х1 + х1-х2 = х1. |
|
|
|
Т а б л и ц а 4-12 |
|
Л |
|
А —>Б |
|
А |
Б |
||
Л |
|||
1 |
1 |
1 |
|
1 |
0 |
0 |
|
0 |
1 |
1 |
|
0 |
0 |
I |
|
12. Закон склеивания (распространения)
(*iА Ха) V (*iА Х9) = |
, (МV *а)A (*iV *а) = |
*1 . |
|
||||||||
Х1 -Х2 + Х1 -Х2 = Х1 , (А Т + |
х 2 ) • ( * ! + х 2 ) = хг. |
|
|
||||||||
Убедимся в справедливости одного из законов склеивания: |
|||||||||||
при at = |
0; |
х3 = |
0; |
00 + |
00 = |
|
00 + |
01 = |
0 + |
0 — 0; |
|
при х г = |
0; |
х2 = |
1; |
01 |
01 |
= |
01 |
г00 = |
0 + |
0 = |
0; |
при х х = |
1; |
х2 |
0; |
10 + |
Ю = |
10 |
-1 1 = |
0 4 - 1 = |
1; |
||
при х г = |
1; |
х 2 = |
1; |
11 + 11 = |
11 4 |
ю = |
1 4 - 0 |
1. |
|||
Можно было бы в этом случае поступить иначе: убедившись в справедливости, получим
Х\ ‘ Х 24 " Xj •Х 2 — Ху (Х2 + Х2) — АТ, 1 = Хх’
что и требовалось доказать.
Необходимо отметить, что законы (1-^12) широко используются при минимизации булевых функций. Приведем несколько примеров для равносильного преобразования формул с использованием за конов (1 — 12).
89
Для доказательства их справедливости достаточно убедиться в том, что на всех возможных наборах значений аргументов значе ния левых и правых частей этих тождеств совпадают. Однако до кажем их справедливость с помощью законов (1 — 12)
х + ху = х + у. |
|
(4.7 |
|
Доказательство: на основании законов |
(1), (4) |
и (7) имеем |
|
х (х + У) = хх + ху = 0 + ху = х у , |
|
||
(x + y) {x+z ) = xz + xy. |
|
(4.8) |
|
Доказательство: с учетом (4), (7), (2), (1) получим |
|
||
(х-\-у) (x + z) = (x + y ) x + ( x + y)z = xx + yx-\-xz + yz = |
|
||
= 0 -f xz -f ху + yz — xz + ху + yz — xz -f ху + yz (х + х) — |
|
||
= xz + ху-\- yzx + yzx = xz -f xzy + xy |
xyz — |
|
|
= XZ (1 + y) -f XJ/(1 +2) = xz + xy. |
|
||
Из табл. 4-12 составим формулу |
импликации Л = А |
Б |
|
и выразим ее через отношение логического отрицания, про
изведения |
и суммы. |
Тогла |
Л — Л |
Б — А - Б J\- А - Б -\- А - Б . |
|||||||
Теперь |
убедимся, что она действительно |
дает результат |
0, |
когда |
|||||||
А = |
1, |
а |
Б ----- 0, а |
в остальных |
случаях |
равна |
1. |
|
|
||
Л |
/1 |
|
Б = 1 0 |
1-0 |
1 -0 |
- 1-0 |
|
0 -0 |
0 • 1 |
0 |
0 |
+0 = 0 .
Для |
А --= |
1 |
и |
Б = |
1; |
Л = А -+ Б = |
1 • 1 |
+ |
1-1 |
+ |
1 • 1 |
= Ы + |
|
+ 0-1 + 0-0 = 1 -г 0 + 0 = 1. |
|
|
|
|
|
|
|||||||
Для |
А = |
0 |
и |
Б = |
1; |
</7 — < / 7 - > Б = 0 - 1 + 0 1 - ( - 0 - 1 |
;- =0Д + |
||||||
+ Ы + 1-0 ■= 0 + |
1 + |
0 = 1. |
|
|
|
|
|
|
|||||
Для |
А = |
0 |
и |
Б = |
0; |
Л |
/1 - Б |
0-0 |
+ |
0-0 |
+ |
0-0 |
-= 0-0 + |
+ 1-0 + Ы == 0 т 0 4- 1 = 1.
§5. ЗАМЕНЯЕМОСТИ ОСНОВНЫХ СВЯЗЕЙ
Спомощью преобразований сложных логических формул можно найти более простые варианты, равноценные с точки зрения связи воздействий с результатами. Однако прежде чем преобразовать логическое выражение необходимо уметь его получать. Исходной информацией для записи зависимости некоторой логической функ ции от заданных аргументов может служить протокол наблюдений за реальным объектом, или, что то же самое, таблица истинности, данной функции.
Используя законы |
(1—9) |
и эквивалентности |
логических свя |
зей можно получить |
целый |
ряд эквивалентных |
(взаимозаменяе |
мых) связей, необходимость применения которых может возник нуть при преобразовании логических формул.
90