Arkhitektura_EVM_uchebnoe_posobie

Логическая функция от n аргументов обращающаяся в 0 при единственном наборе переменных и в 1 при остальных 2n-1 наборах называется конституан-

той 0.

Конъюнкцией n аргументов называется функция типа конституанты 1, которая обращается в 1, если все аргументы равны 1.

Дизъюнкцией n аргументов называется функция типа конституанты 0, которая обращается в 0, если все аргументы равны 0.

Для n=2 конъюнкция называется «логическим И», а дизъюнкция называет-

ся «логическим ИЛИ». При n=1 функция называется «отрицанием» или «логи-

ческим НЕ» и по определению является и конституантой 1 и конституантой 0. При записи операция «конъюнкция» обозначается как « » или « », опера-

ция «дизъюнкция» – « » или «+», операция «отрицание» – « ».

В табл. 2.3 приведена таблица значений для функций «конъюнкция» и «дизъюнкция».

Таблица 2.3

Значения функций «конъюнкция» и «дизъюнкция»

x1	x2	x1 x2	x1 x2
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

В табл. 2.4 приведена таблица значений для функции «отрицание».

Таблица 2.4

Значения функции «отрицание»

x
		x
0		1
1		0

Если логическая функция задана таблично, то про переходе к выражению с использованием логических операций «И», «ИЛИ», «НЕ» можно применить следующий прием: для строк функции, соответствующих 1, записать конъюнкцию типа конституанты 1, причем если в наборе аргумент равен 1, то используется его «прямая» запись, если 0 – его отрицание. Аргументы объединяют знаком «И», а все возможные наборы конъюнкций объединяют операцией «ИЛИ». Получившееся выражение называют дизъюнктивной формой записи логической функции.

Наоборот, если строкам, соответствующим 0, поставить в соответствие набор типа конституанты 0, причем если в наборе аргумент равен 0, то используется его прямая запись, если 1 – его отрицание, и полученные наборы дизъюнкций объединить операцией «И», то получим конъюнктивную форму записи логической функции.

50

Пример 2.21. Пусть логическая функция задана таблично

x1	x2	x3	F(x1, x1, x3)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Тогда можно записать дизъюнктивную и конъюнктивную форму записи данной логической функции.

Дизъюнктивная

F(x

, x

, x

) =

x

x

x

x

2

3

x

1

2

x

3

1

x

2

x

3

1

x

2

3

форма

1

F(x1 , x2 , x3 ) = (x1 x2 x3 ) (x1 x2

)

Конъюнктивная

x3

форма

(x1

)

x2

x3

) (x1

x2

x3 ) (x1

x2

x3

Из определения вышеприведенных функций «И», «ИЛИ», «НЕ» можно установить целый ряд простейших свойств:

x 1 =1

x x =1 x 0 = x

x x = x

x 0 = 0 x 1 = x

x x = 0 x x = x

x x ... x = x x x ... x = x

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

коммутативный (переместительный)

x1 x2 = x2 x1 x1 x2 = x2 x1

ассоциативный (сочетательный)

(x1 x2 ) x3 = (x1 x3 ) x2 = x1 (x2 x3 )

(x1 x2 ) x3 = (x1 x3 ) x2 = x1 (x2 x3 )

дистрибутивный (распределительный)

x1 (x2 x3 ) = x1 x2 x1 x3 x1 x2 x3 = (x1 x2 ) (x1 x3 )

закон поглощения

x1 x1 x3 = x1 x1 (x1 x2 ) = x1

51

закон склеивания

x1 x2 x1

x2

= x1

(x1 x2 ) (x1

x2

) = x1

Fx Fx

= F

(x F) (x F) = F

закон свёртки

x

F) = xF

xF = x F

x(x

Правило де Моргана

x1 x2

=

x1

x2

x1 x2

=

x1

x2

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

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

Очень полезной функцией является функция сложения по модулю 2 (исключающее ИЛИ), которая представляется следующим образом:

x1 x2 = x1 x2 x1 x2 = (x1 x2 ) (x1 x2 )

В табл. 2.5 приведена таблица значений для функции «исключающее ИЛИ».

Таблица 2.5

Значения функции «исключающее ИЛИ»

x1	x2	x1 x2
0	0	0
0	1	1
1	0	1
1	1	0

Для этой функции справедливы следующие аксиомы: x x = 0;

x x x = x; x x =1; x 1 = x ; x 0 = x

На основании рассмотренных аксиом и свойств элементарных логических функций можно, например, вывести правила представления функций И, ИЛИ, НЕ через функцию сложения по модулю 2 и наоборот:

x= x 1

x1 x2 = x1 x2 (x1 x2 )

x1 x1 = (x1 x2 ) (x1 x2 )

Используя данные зависимости, можно преобразовывать исходные выражения в более простые (минимизировать их).

52

Пример 2.22. Минимизировать логическую функцию (см. пример 2.20)

F(x1 , x2 , x3 ) = (x1 x2 x3 ) (x1 x2 x3 ) (x1 x2 x3 ) (x1 x2 x3 )(x1 x2 x3 )

1) (x1 x2 x3 ) (x1 x2 x3 ) = (x1 x2 ) (x1 x2 ) x3 (x1 x2 )x3 (x1 x2 ) x3 x3 = (x1 x2 ) (x1 x2 ) (x3 x3 ) 0 =

=x1 x2 ;

2)(x1 x2 x3 ) (x1 x2 x3 ) = x1 x2 ;

3) (x1 x2 ) (x1 x2 ) = x1 x1 x2 x1 x2 x1 x2 x2 = x1 x2 x1 x2 ;

4) (x1 x2 x3 ) (x1 x2 x1 x2 ) = x1 x1 x2 x1 x2 x2 x1 x2 x3

x1 x1 x2 x1 x2 x2 x1 x2 x3 = x1 x2 x3 x1 x2 x1 x2

x1 x2 x3 = x1 x2 x3 x1 x2 (1 x3 ) = x1 x2 x3 x1 x2 .

Значит F(x1 , x2 , x3 ) = x1 x2 x3 x1 x2 .

2.4.2. Минимизация логических функций

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

Использование карт Карно обеспечивает более компактное и наглядное изложение материала. При этом выполняемые операции принято описывать в других терминах. Множества или переменные X и Y называют входными величинами (входными переменными). Логическая операция определяет значение выходной величины (функции). На карте Карно входные величины обозначены сверху и слева. Карта состоит из нескольких клеток. Клетки карты Карно нумеруются так, чтобы та или иная комбинация входных переменных была определена однозначно.

Рассмотрим заполнение карты Карно для функции от трех переменных. Пусть функция F(x1, x2, x3) задана таблично (табл. 2.6).

Тогда для этой функции карта Карно будет иметь вид, представленный на рис. 2.3.

53

										Таблица 2.6
x1				x2				x3		F(x1, x1, x3)
0				0			0			F(0, 0, 0)
0				0			1			F(0, 0, 1)
0				1			0			F(0, 1, 0)
0				1			1			F(0, 1, 1)
1				0			0			F(1, 0, 0)
1				0			1			F(1, 0, 1)
1				1			0			F(1, 1, 0)
1				1			1			F(1, 1, 1)
							x2x3
				00	01			11	10
	x1	0		F(0, 0, 0)	F(0, 0, 1)			F(0, 1, 1)	F(0, 1, 0)
		1		F(1, 0, 0)	F(1, 0, 0)			F(1, 1, 1)	F(1, 1, 0)

Рис. 2.3. Карта Карно для функции от трех переменных

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

				x3x4
		00	01		11	10
	00	F(0, 0, 0, 0)	F(0, 0, 0, 1)		F(0, 0, 1, 1)	F(0, 0, 1, 0)
x1 x2	01	F(0, 1, 0, 0)	F(0, 1, 0, 1)		F(0, 1, 1, 1)	F(0, 1, 1, 0)
	11	F(1, 1, 0, 0)	F(1, 1, 0, 1)		F(1, 1, 1, 1)	F(1, 1, 1, 0)
	10	F(1, 0, 0, 0)	F(1, 0, 0, 1)		F(1, 0, 1, 1)	F(1, 0, 1, 0)

Рис. 2.4. Карта Карно для функции от четырех переменных

Для функции от четырех переменных работа по минимизации с помощью карты Карно состоит в следующем.

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

Если имеется один столбец или одна строка заполненная единицами, или имеется квадрат из 4-х клеток заполненных единицами, то им соответствует конъюнкция двух переменных с отрицанием или без него.

Если имеются две соседние клетки заполненные единицами, то им соответствует конъюнкции 3-х переменных с отрицанием или без него.

54

Отдельно стоящей клетке с единицей соответствует конъюнкция 4-х переменных с отрицанием или без него.

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

Пример 2.23. Пусть логическая функция задана таблично

x1	x2	x3	x4	F(x1, x1, x3, x4)
0	0	0	0	1
0	0	1	0	0
0	1	0	0	1
0	1	1	0	1
1	0	0	0	1
1	0	1	0	0
1	1	0	0	1
1	1	1	0	1
0	0	0	1	1
0	0	1	1	0
0	1	0	1	0
0	1	1	1	0
1	0	0	1	1
1	0	1	1	1
1	1	0	1	0
1	1	1	1	0

	Построим карту Карно для данной функции
						x3x4
			00		01		11			10
		00	1		0		1			1
x1	x2	01	1		0		1			1
		11	1		1		0			0
		10	1		0		0			0

Тогда	F(x1 , x2 , x3 , x4 ) =			x3		x4			x1	x3 x1 x2	x3	.
Пример 2.24. Пусть логическая функция задана таблично (см. примеры 2.20,
2.21)
x1	x2	x3	F(x1, x1, x3)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Построим карту Карно для данной функции

55

				x2x3
		00	01		11	10
x1	0	0	0		0	1
	1	1	1		0	0

Тогда F(x1 , x2 , x3 ) = x1 x2 x1 x2 x3 .

2.4.3. Цифровые схемы

Цифровые схемы могут конструироваться из небольшого числа простых элементов путем сочетания этих элементов в различных комбинациях.

Цифровая схема – это схема, в которой есть только два логических значения. Обычно сигнал от 0 до 1 В представляет одно значение (например, 0), а сигнал от 2 до 5 В – другое значение (например, 1). Напряжение за пределами указанных величин недопустимо. Крошечные электронные устройства, которые называются вентилями, могут вычислять различные функции от этих двузначных сигналов. Эти вентили формируют основу аппаратного обеспечения, на которой строятся все цифровые компьютеры.

Кратко рассмотрим основной принцип работы вентилей. Вся современная цифровая логика основывается на том, что транзистор может работать как очень быстрый бинарный переключатель. На рис. 2.5, а изображен биполярный транзистор, встроенный в простую схему. Транзистор имеет три соединения с внешним миром; коллектор, базу и эмиттер. Если входное напряжение Vin ниже определенного критического значения, транзистор выключается и действует как очень большое сопротивление. Это приводит к выходному сигналу Vout, близкому к Vcc (напряжению, подаваемому извне), обычно +5 В для данного типа транзистора. Если Vin превышает критическое значение, транзистор включается и действует как провод, вызывая заземление сигнала Vout (по соглашению 0 В).

Рис. 2.5.Транзисторный инвертор (вентиль «НЕ») (а); вентиль «И-НЕ» (б); вентиль «ИЛИ-НЕ» (в)

56

Важно отметить, что если напряжение Vin низкое, то Vout высокое, и наоборот. Эта схема, таким образом, является инвертором, превращающим логический 0 в логическую 1 и логическую 1 в логический 0. Резистор (ломаная линия) нужен для ограничения количество тока, проходящего через транзистор, чтобы транзистор не сгорел. На переключение с одного состояния на другое обычно требуется несколько наносекунд.

На рис. 2.5, б два транзистора соединены последовательно. Если и напряжение V1, и напряжение V2 высокое, то оба транзистора будут служить проводниками и снижать Vout. Если одно из входных напряжений низкое, то соответствующий транзистор будет выключаться, и напряжение на выходе будет высоким. Другими словами, Vout будет низким тогда и только тогда, когда и напряжение V1, и напряжение V2 высокое.

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

Эти три схемы образуют три простейших вентиля, их называются вентилями «НЕ», «И-НЕ» и «ИЛИ-НЕ». Вентили «НЕ» часто называют инверторами. Если принять, что высокое напряжение (Vcc) – это логическая 1, а низкое напряжение («земля») – логический 0, то можно выразить значение на выходе как функцию от входных значений. Значки, которые используются для изображения этих трех типов вентилей, а также вентилей «И» и «ИЛИ», показаны на рис. 2.6, а-в. На этих рисунках А и В – это входные сигналы, а X – выходной сигнал. Каждая строка таблицы определяет выходной сигнал для различных комбинаций входных сигналов.

	НЕ		И-НЕ		ИЛИ-НЕ		И		ИЛИ	Исключающее ИЛИ
A	X	A	X	A	X	A	X	A	X	A	X
		B		B		B		B		B

Рис. 2.6. Значки для изображения 6 основных вентилей.

Шесть вентилей, изображенных на рис. 2.6, составляют основу цифрового логического уровня построения ЭВМ.

Пример 2.24. Необходимо создать цифровую схему, реализующую однораз-

рядный двоичный сумматор, имеющего два входа (a и b), вход переноса из преды-

дущего разряда k и два выхода S и Р и выполняющего операцию сложения с учетом переноса. S = f1(а, b, k) – значение цифры суммы в данном разряде; P = f2(а, b, k) – цифра переноса в следующий (старший) разряд.

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

57

a	b	k	S	P
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

С помощью карт Карно минимизируем функции, приведенные в таблице.

Карта Карно для функции S = f1(а, b, k) имеет следующий вид:

				bk
		00	01		11	10
a	0	0	1		0	1
	1	1	0		1	0

Поэтому S = a b k a b k a b k a b k = b (a k a k) b (a k a k) .

Пусть F = (a k a k) = a k , тогда F = a k a k , это легко можно проверить с

помощью законов булевой алгебры. Отсюда

S = b F b F = b F = b (a k) .

Карта Карно для функции P = f2(а, b, k) имеет следующий вид:

				bk
		00	01		11		10
a	0	0	0		1		0
	1	0	1		1		1

Поэтому P = a k b k a b.

Цифровая схема, реализующая сумматор и использующая основные вентили, изображенные на рис. 2.6, приведена на рис. 2.7.

Рис. 2.7. Цифровая схема сумматора

58

Вопросы к главе 2

1.Что называют системой счисления?

2.От чего зависит в позиционной системе счисления вес цифры?

3.В какой системе счисления выполняются все арифметические действия при переводе из системы счисления N в систему счисления P делением?

4.В какой системе счисления выполняются все арифметические действия при переводе из системы счисления N в систему счисления P рекуррентным методом (умножением)?

5.Каким может получиться результат при переводе дробного числа из одной системы счисления в другую?

6.Что такое обратный код положительного числа?

7.Что необходимо для выравнивания разрядов при выполнении арифметических операций?

8.Каким может получиться результат при сложении двоичных чисел фиксированной разрядности?

9.Чему равно максимальное десятичное число, которое можно представить n-разрядным двоичным числом?

10.Что называют дизъюнктивной формой?

11.Что называют конъюнктивной формой?

12.Приведите таблицы задания функций «И», «ИЛИ», «НЕ».

59