Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

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

.pdf

Скачиваний:

Добавлен:

23.10.2023

Размер:

6.44 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 179 10 11 12 13 14 15 16 17 > Следующая >>>

Конъюнкция	обладает	свойством	к о м м у т а т и в н о с т и и
а с с о ц и а т и в н о с т и , т.		е. значения переключательной функции
не изменяются	от перемены мест аргументов функции и от изме
нения последовательности		выполнения	операций формул (4.3)
и (4.4).

Логическая сумма высказываний (дизъюнкция)

Дизъюнкцией высказываний называется такая логическая связь (сложное высказывание), которая истинна всегда, если истинно хотя бы одно из простых высказываний, составляющих дизъюнк

цию, и ложна лишь тогда, когда
ложны все простые высказыва		А 0 ---------	1	Z^A v8
ния.		В0------		Z^A v8
ния.	зна	В0------		----0
Дизъюнкция обозначается	зна	С 0---------		Увых
ком «V» или «+» и читается	как
«или» А V В = А + В.Таблица 4-6
истинности дизъюнкции имеет вид:			Рис.	12
		Т а б л и ц а	4-6
А	в	А \'В
0	0	0
0	1	1
1	0	1
1	1	1

Из определения дизъюнкции и таблицы истинности вытекает справедливость следующих соотношений:

Л + 0 = Л, Л + 1 = 1,

Л + Л = Л, Л + Л = 1.

Дизъюнкция подчиняется переместительному и сочетательному законам (т. е. обладает свойством коммутативности и ассоциатив ности):

Л\! В = В V Л,

лV (В V С)= (А V в) V С.

Логический элемент, реализующий дизъюнкцию, называется «или» (собирательная схема) и обозначается как на рис. 12.

Равнозначность двух высказываний

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

З а к а з № 2437

Равнозначность обозначается символом «—» например А ~ В читается как «Л равнозначно В». Пользуясь определением, соста вим таблицу истинности этой связи (табл. 4-7).

			Т а б л и ц а	4-7
	А	В	А ~ В
	0	0	1
	0	1	0
	1	0	0
	1	1	1
Из таблицы истинности непосредственно вытекает следующее
соотношение:	А ~ 1 = А .		Л ~ 0 = Л.
Отрицание равнозначности (сумма по модулю 2)
О т р и ц а н и е м		р а в н о з н а ч н о с т и		называется пе

реключательная функция, которая принимает значение, равное 1, тогда, когда з н а ч е н и я аргументов различные. Обозначается символом А — В или зн ак о м ь ; отрицание равнозначности может

Рис. 14

быть получено из р а в н о з н а ч н о с т и путем применения к ней

операции	инверсии
		А — В = Ат=^В или ( Л@В);
читается	«Л неравнозначно В».		Таблицей включений является
табл. 4-8.		Т а б л и ц а 4-8	Обозначение неравнознач
		Т а б л и ц а 4-8	Обозначение неравнознач
А	в	2— А ^ В	ности показано на рис. 13. Из
А	в	2— А ^ В	таблицы истинности вытекают
			следующие соотношения:
0	0	0	А ~ В = В ~ А ,
0	1	1	А ~ В = В ~ А ,
0	1	1	А ~
1	0	1	А ~	1 = Л,
1	1	0	Л ~ 0	= Л.
			Л ~ 0	= Л.

Путем непосредственной проверки по приведенной таблице ис тинности легко убедиться в справедливости зависимости

	Л ~ В = ( Л ~ В ) ~ 1.
В самом деле, 1 —	1	= 1;
( 1 ~ 1 ) ~ 1 =	1	или 1 ~ 0 = = 0 и ( 1 ~ 0 ) ~ 1 = 0 .

Равнозначность может быть реализована простейшей контактной

	схемой (рис. 14; табл. 4-9).
Т а б л и ц а 4-9	Условие — нажато А, В = 1,
________________________________	отжато А, В = 0.

Вход	А =	1	В =	1	Выход
					+ Е	(1)
				г =
Вход	А = 0		В = 0		Выход
					+ В	(1)
				2 =
Вход	А =	0	В =	1	Выход
						(0)
				г = 0
Вход	А =	1	в =	о	Выход
					г =	0

Импликация двух высказываний

Импликацией двух вы сказываний называется та кое сложное высказыва ние, которое ложно в том случае, когда А истинно, а В ложно.

	Т а б л и ц а 4-10
А	в	А^В
0	0	1
0	1	1
1	0	0
1	1	1

Импликация двух высказываний обозначается, например, А --> В; читается как «если А, то В». Импликация не имеет смысла связей между причиной и следствием, т. е. из истинности А не сле дует обязательная истинность В. Наоборот, для истинности импли кации достаточно ложности А.

Пользуясь определением, составим таблицу истинности импли кации 4-10.

Несовместимость двух высказываний (связь Шеффера)

Связью Шеффера называется такое сложное высказывание, ко

торое л о ж н о		в том и только в том случае, когда оба составляю
щих	высказывания			и с т и н н ы .	Связь	Шеффера	обозначается
А!В	и читается		как «Л не
совместно В».						Т а б л и ц а 4-11
Пользуясь		определением,

составим таблицу			истинности		А	в	А/С
4-11.
		связь Шеффе
Логическая					0	0	1
ра играет важную роль в тео
рии ЭЦВМ и в теории логи					0	1	1
					1	0	1
ческих схем.		Все		другие
					1	1	0
логические связи			могут быть

6 *

выражены через связь Шеффера, а схема, реализующая связь Шеффера, является универсальным функциональным элементом, при помощи которого могут быть построены любые функциональ ные схемы счетных и управляющих блоков машины. Это универ сальная операция, которая реализуется схемой «И — НЕ».

К	универсальной операции относится стрелка Пирса, А \| В
(Л ±	В). Эта операция реализуется схемой «ИЛИ — НЕ».

Эти операции универсальны потому, что любая из трех опера ций «И», «ИЛИ», «НЕ» может быть получена с помощью «И—НЕ»

и«ИЛИ—НЕ».

1.а-а — а

2. (a-b)-(a-b) = (a-b) = a-b по закону полноты

3. (a-a)-(b-b) — a-b = A ^ b —a ^ b по правилу де Моргана.

Логический элемент, выполняющий функцию «И—НЕ» или, «ИЛИ—НЕ», может выполнить новые элементарные функции «И», «ИЛИ», «НЕ».

§ 4. ОСНОВНЫЕ ЗАКОНЫ БУЛЕВОЙ АЛГЕБРЫ

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

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

переменную, являющуюся функцией других переменных:
х0 = (а ~ Ь)	с, x1 = ( a / \ c ) ~ ( d ^ « ) ,	(4.5)
x2 = q ^ e ,	xs = f \ J q .

Здесь х 0, х г, х 2, х3 рассматриваются как булевы функции аргу ментов а, Ь, с, d, е, /, q. Подставляя эти функции в уравнение вместо х 0, x lt х 2, х3, получим формулу

{[(а Д с ) ~ (d <- е)] -+ (a?^b) - с)) ~ [ ( q ~ ё) V (/ V Ф А !)•

(4-6)

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

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

казательствами теорем, а рассмотрением наглядных дискретных контактных схем.

1.	Двойное отрицание
_		Двойное отрицание равносильно ут-
_	А	верждению:
А =	А	«Контакт не	замкнут» — значит				он замк
		нут. Или: если		1	==_0,	а 0 = 1.	Таким об
		разом 1 = 0	=	1;	0 =	1 = 0.

	2. Переместительный (коммутативный) закон
а) А / \ Б = Б / \ А
А - Б -		Б - А	Если, например, поменять в последо
			вательной цепи контакты местами, то все
			равно ток потечет лишь тогда, когда на
б)	А +	Б = Б 4- А	жаты обе кнопки. По этой же причине
			очевидно, что ток потечет по цепи при усло
А	V Б = Б ]/ А		вии, когда нажата хотя бы одна из кнопок.

3.	Закон	повторения (тавтологии)
а) А + А = А
А V А == А		Две	параллельно		включенные кнопки
		при их общем нажатии ведут себя точно
		так же,	как одна кнопка,			т. е. (рис. 14, б,
		в; схема б равноценна схеме в).
		Примечание. На всех рисунках для простоты
		одной и	той же буквой обозначены и кнопка
		и все связанные с ней контактные перемычки.
		Отливается		только тип	связи— утверждение,
		или отрицание, что проявляется в том, прижи
		мается ли контактная перемычка к контактам
б) А Л А — А		при нажатии ее кнопки или отходит от них.
		Последовательная цепь из двух кнопок,
		нажимаемых		и отпускаемых		одновременно, ве-

А -А =	А			дет себя так же, как цепь из одной кнопки (схема
				рис. 15, а. равноценна схеме рис. 15,	б).
4.	Законы нулевого			множества
а) А +		0	— А	Это логическая константа,	например,
А V		0	= А	навсегда разомкнутый (скажем, сломанный)

					контакт, независимый			элемент системы
					в состоянии «О». Тогда неважно, стоит он
					параллельно		А или	нет, на	результате
					это не скажется, и лампочка будет гореть
					или не гореть лишь в зависимости от со
	А -0 =				стояния контактной перемычки А (рис. 16,о)
б)	А -0 =		0		Это значит, что если в последовательной
					цепи есть постоянный разрыв «О», то неза-
	Л Д	0 =		0	висимо от нажатия или ненажатия кон
					такта	А ток	в цепи не течет (рис. 16, б).
	5. Законы				универсального	множества
а)	А +	1	=	1	Это тоже логическая константа, напри
	Л V	1	=	1	мер,	такой	контакт,	который	постоянно
								6)

			)Л=А	Л*1		I ЛшО
			)Л=А			I ЛшО
		Рис.	17	Рис. 18
			замкнут,	т. е. независимый элемент си
			стемы в состоянии «1». Тогда ток по цепи
			через этот контакт будет течь постоянно,
			независимо от состояния контактов пере
			мычки Л	(рис. 17, а).
б) Л • 1	=	Л	Если	в последовательной	цепи	один
Л Д	1	= Л	контакт	постоянно замкнут, то	ток	в ней

зависит только от положения другого кон такта (рис. 17, б).

6. Законы дополнительности

а) Л + А = 1 Л V А = 1

б) А - А == О

Л Д Л = О

Если всякий раз при размыкании од

ного параллельного контакта второй за мыкается, то цепь всегда остается замкну той (рис. 18, а).

Если при размыкании одного последо

вательного контакта второй размыкается, то цепь всегда остается разомкнутой

(рис. 18, б).

7. Распределительные (дистрибутивные) законы

а) А ■(Б + В) = А Б ф-

+АВ

АМ Б У В) = ЛД

ЛБ У А Л В

б) В + (АБ) = (В +

+А ) • (В + Б)

ВУ ( А - В ) = ( В У А ) Х

Х( В У Б )

Конъюнкции относительно дизъюнкции (умножение относительно сложения). Это правило раскрытия скобок, как в обыч ной алгебре. Справедливость этого прави ла легко проверить на сравнении схем рис. 19, а, б. В логических формулах можно как раскрывать скобки, так и вы носить одинаковые члены за скобки.

Дизъюнкция относительно конъюнкции (сложение относительно умножения). Рас смотренное правило (7а) внешне совпадает с обычным правилом раскрытия скобок,

а)

б)

( А . Б ) + В = ( А + В ) Х

Х( Б + В)

{А ^ Б ) у В = ( А у В ) / \

Л(Б У В)

	а)		б)	в
В	о А	- А	А
В	о А	О С
		О С
		- 4	Б

Ч /

В I _______ _

! Л=В+АБ

Рис. 20

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

Данное правило не имеет прямой ана логии с обычной количественной алгеброй. На контактной схеме правильность этого закона очевидна: если мы замыкаем па раллельным контактом «В» некоторую по следовательную цепь А-В, то подключе ние параллельно контактов к каждому из последовательных дает такой же резуль тат, т. е. (рис. 20, а, б) схема б равноценна схеме а.

8. Сочетательные (ассоциативные) законы

а) (А - Б ) - В= А -(Б-В)	Этим	законам соответствуют схемы
(А / \ Б ) / \ В ~ А /\	рис. 21,	а, б.

Л (£ Д В )

б) (А + Б ) + В = А +

+ (Б + В)

(Ау Б ) У В — А +

+ ( БУВ )

U.J	■ОА О-	А
	-о Б о -
	-°S	В

б)

15 о—о В

А о— о 5 о— о 5 о -..-> •

					Рис.	21
	9.	Закон де Моргана
	А - В = А + В			Это правило можно выразить так: если
а)	А - В = А + В			имеется произведение и над ним стоит об
	A f\ B = A y B			щее отрицание, то можно заменить знак
				произведения на знак суммы (конъюнк
				цию	на	дизъюнкцию),			если	отрицание
				«разорвать», поставить его отдельно над
				каждым членом суммы. Физический смысл
				этого правила очевиден. Например, если
				цепь имеет два последовательных контакта
				и проводит ток лишь когда нажаты кнопки
				А и Б (т.		е. когда и А		и Б — 1), то цепь
				не проводцт ток, когда не нажата либо
				одна (т. е. А), либо другая (т. е. Б) кнопка,
				либо они обе вместе (т. е.					и А и Б).
б)	А +	Б = А ■Б		Смысл этого варианта правила де Мор- .
А У Б = А Д Б				гана такой же, как и «а».
А У Б = А Д Б				Правило де Моргана («а» и «б») читается:
				«отрицание конъюнкции есть дизъюнкция
				отрицаний»; «отрицание дизъюнкции есть
				конъюнкция отрицаний».
	Справедливость вышерассмотренных						законов		легко установить
с	помощью		таблиц	соответствия двухместных булевых функций,
определяя			значения	правых	и левых		частей	законов		(1 — 8) на
всех наборах значений аргументов.
	Убедимся таким способом в справедливости одного									из законов
( 12).

х У х —- 1,

так как при х — О

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).

Для доказательства их справедливости достаточно убедиться в том, что на всех возможных наборах значений аргументов значе ния левых и правых частей этих тождеств совпадают. Однако до кажем их справедливость с помощью законов (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

= Ы +

+ 0-1 + 0-0 = 1 -г 0 + 0 = 1.

Для

А =

Б =

</7 — < / 7 - > Б = 0 - 1 + 0 1 - ( - 0 - 1

;- =0Д +

+ Ы + 1-0 ■= 0 +

1 +

0 = 1.

Для

А =

Б =

/1 - Б

0-0

-= 0-0 +

+ 1-0 + Ы == 0 т 0 4- 1 = 1.

§5. ЗАМЕНЯЕМОСТИ ОСНОВНЫХ СВЯЗЕЙ

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

Используя законы	(1—9)	и эквивалентности	логических свя
зей можно получить	целый	ряд эквивалентных	(взаимозаменяе

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

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 179 10 11 12 13 14 15 16 17 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ