arx011010_ch2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ (ТГПУ)

А.П. Клишин

”Архитектура компьютера”

Часть 2

Учебное пособие

Томск - 2009

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ (ТГПУ)

А.П. Клишин

”Архитектура компьютера”

Часть 2

Учебное пособие

Томск - 2009

1

Содержание

1. Логические основы ЭВМ…………………………………………………………………..	4
1.1. Основные сведения из алгебры логики…………………………………………………	4
1.2. Логические функции двух переменных…………………………………………………	5

1.3.Аналитические формы представления логических функций…………………………. 7

1.4.Разложение функций алгебры логики по к переменным. СДНФ и СКНФ…….…….. 11

1.5.Тавтологии и противоречия. Проблема разрешимости в алгебре логики……………. 15

1.6.Основные схемы доказательств…………………………………………………………. 18

1.7.Суперпозиция функций алгебры логики………………………………………………... 18

1.8. Преобразованиеиминимизациялогическихвыражений……………………….…………… 19

1.9.Элементы и узлы компьютерной схемотехники……………………………………….. 20

1.10.Общая характеристика элементов и узлов ЭВМ………..……………….……………. 22

1.11.Логические элементы………..………………………………………………….………. 25 2. Базовые функциональные элементы ЭВМ. Двоичные логические элементы…………. 27

13

13

16

16

18

19

19

37

39

43

49

49

54

54

55

63

67

68

68

71

73

74

76

77

80

81

91

96

98

100 Словарь терминов…………………………………………………………………………….. 106 Литература…………………………………………………………………………………….. 118

Логические основы ЭВМ

1.1. Основные сведения из алгебры логики

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

Если высказывание истинно, то считают, что его значение равно единице; если высказывание ложно, то считают, что его значение равно нулю. Таким образом, значения высказываний можно рассматривать как переменную величину, принимающую только два дискретных значения: 0 или 1. Это приводит к полному соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления.

Высказывание - это предложение, о котором можно говорить истинно оно или ложно. В дальнейшем под высказыванием мы будем понимать переменную, принимающую два значения: 1 (истина) или 0 (ложь). Такие высказывания будем называть элементарными переменными высказываниями и обозначать малыми латинскими буквами: x,y,z и т.д.

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

1) Одноместная операция отрицание.

Отрицанием высказывания x называется высказывание (обозначениеx ), принимающее значение 1, если x=0 и 0, если x=1.

2) Операция конъюнкция.

Конъюнкцией высказываний x и y называется высказывание (обозначение x&y), принимающее значение 1, если x=y=1и значение 0 во всех остальных случаях.

3) Операция дизъюнкция.

Дизъюнкцией высказываний x и y (обозначение xVy), называется высказывание, принимающее значение 0, если x=y=0 и значение 1 во всех остальных случаях.

Алгеброй логики называется пара множеств B=( P({0,1}), {&,V, }), где P({0,1}) - основное (несущее) множество - булеан множества {0,1}, а {&,V, } - сигнатура (множество операций) алгебры.

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

3

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

В каждом конкретном случае количество входных переменных будет различным. В простейшем случае это одна переменная х, принимающая значение 0 или 1. В общем случае таких переменных может быть n, т.е. х1, х2..... хn. Так как каждая переменная х, при этом равна 0 или 1, то для n переменных образуется множество разнообразных сочетаний или наборов входных переменных.

В алгебре логики строго доказывается, что для n переменных

количество различных наборов равно 2n. Так, для одной переменной х существует только два набора: <0> или < 1 >, так как 21 = 2; для двух переменных х1, х2 − четыре различных набора: <0,0>, <0,1 >, < 1,0>, < 1,1 >,

так как 22 = 4; для трех переменных х1, х2, х3 – восемь различных наборов, так как 23 = 8, и т.д.

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

число различных логических функций от n аргументов равно 22n . Например, для n = 1,2,3 и т.д. их будет соответственно 4,16, 256 ит.д.

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

дизъюнкции и конъюнкции.

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

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

x
		x
0		1
1		0

Очевидным является следующее свойство операции отрицания x = x .

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

Дизъюнкцией двух высказываний х и у называется логическая операция, в результате которой образуется логическая функция F, истинная в том случае, если хотя бы одно из высказываний х или у истинно. В соответствии с этим определением таблица истинности для дизъюнкции имеет вид:

4

					F
	x		y
	0		0		0
	0		1		1
	1		0		1
Дизъюнкция	1		1		1
	обозначается	знаком V, который			читается как ИЛИ, т.е.
Р = xVy..
Часто данную операцию называют операцией логического сложения. В
общем случае эта операция			может быть	определена для любого числа

n

аргументов: x1Vx2Vx3Vx4Vx5 ... =V xi .

i=1

Конъюнкцией, или логическим умножением двух высказываний х и у называется логическая функция Р, истинная только в том случае, когда истинны одновременно х и y. Таблица истинности для конъюнкции имеет вид:

x	y	P
0	0	0
0	1	0
1	0	0
1	1	1

Конъюнкция обозначается знаком &, который читается как И. В общем случае операция конъюнкции может быть определена для любого числа

			n
аргументов: х1&х2&х3 &... =			&xi .
			i=1
Для дизъюнкции, конъюнкции и отрицания справедливы следующие
логические выражения:
хV0 = х			х&0 = 0
хV1 = 1			х&1 = х
хVх = х			х&х=х
хV		=1	х&		=0
	x			x

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

1. Переместительный закон:

• для дизъюнкции x1Vx2 = x2Vx1 ;

•для конъюнкции х1& х2= х2& х1.

2.Сочетательный закон:

•для дизъюнкции (x1Vx2 )Vx3 = x1V (x2Vx3 ) ;

•для конъюнкции (х1& х2)& х3 = х1 & (х2 & х3).

5

3.Распределительный закон:

•для дизъюнкции (х1 V х2) & х3 =х1 & х3V х2 & х3;

•для конъюнкции (х1 & х2)V х3 =(х1V х3) & (х2 V х3);

4.Закон общей инверсии (формула де Моргана):

• для дизъюнкции x1 V x2 = x1 & x2 ;

• для конъюнкции x1 & x2 = x1 V x2 );

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

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

х1	х2	x1Vx2					х1& х2						x							&						V
				x V x					x & x							x			x		x	2			x		x	2
				1	2				1	2		1			2			1						1
0	0	0			1		0			1		1			1			1						1
0	1	1			0		0			1		1			0			0						1
1	0	1			0		0			1		0			1			0						1
1	1	1			0		1			0		0			0			0						0

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

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

x1Vx2 Vx3 Vx4 V... = x1 & x2 & x3 & x4 & ...; x1 & x2 & x3 & x4 ... = x1 V x2V x3V x4 ...

Аналогично верно и для для распределительного закона.

Из распределительного закона для дизъюнкции и конъюнкции вытекают такназываемые

•формулысклеивания:

(x1 & x2 )V (x1 & x2 ) = x1 ; (x1 V x2 )&(x1 V x2 ) = x1

•формулыпоглощения:

x1 V (x1 & x2 ) = x1 ; x1 &(x1 Vx2 ) = x1 ;

x1 V (x1 & x2 ) = x1V x2 ; x1 &(x1 V x2 ) = x1 & x2 .

6

В их справедливости можно убедиться, составив необходимые таблицы истинности.

Для удобства записей выражений в алгебре логике в дальнейшем мы будем придерживаться следующих правил:

-если над некоторым выражением стоит отрицание, то это выражение мы не будем заключать в скобки;

-знак & мы будем иногда опускать (как знак операции пересечения в алгебре множеств);

-будем считать, что знак & “сильнее”, чем знаки дизъюнкции, сложения по модулю 2, эквивалентности, импликации, стрелки Пирса и штриха Шеффера, тем самым мы будем где это возможно, опускать скобки;

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

1.2. Логические функции двух переменных

Как уже известно, для двух логических переменных х и у существует четыре различных набора: <0,0>, <0,1>, <1,0>, <1,1>. На этих наборах переменных (аргументов) может быть задано 16 различных логических функций f(х, у), так как 24 = 16. В табл. 6.1 приведены значения всех этих функций для каждого из четырех наборов двух аргументов.

									Функции							Таблица 1
Аргу-
менты
x	y	f	f1	f2	f3	f4	f5	f6	f7	f8		f9	f10	f11	f12		f13	f14		f15
0	0	0	1	0	1	0	1	0	1	0		1	0	1	0		1	0		1
0	1	0	0	1	1	0	0	1	1	0		0	1	1	0		0	1		1
1	0	0	0	0	0	1	1	1	1	0		0	0	0	1		1	1		1
1	1	0	0	0	0	0	0	0	0	1		1	1	1	1		1	1		1

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

1.f14(x,y) − дизъюнкция (логическое сложение, операция ИЛИ) переменных х и у, принимающая значение 0, когда оба аргумента х и у одновременно равны 0; во всех остальных случаях она равна 1. Иными словами, функция дизъюнкции равна mах(х, у).

2.f1(x,y) − отрицание дизъюнкции (операция ИЛИ-НЕ). Данная функция обращается в единицу только в том случае, если аргументы х и у одновременно равны нулю; во всех остальных случаях она равна 0. Часто в

литературе функцию xV y называют также операцией Пирса, по фамилии

математика, исследовавшего ее свойства.

3. f8(x,y) − конъюнкция (логическое умножение, операция И) переменных х & у, принимающая значение 1, когда оба аргумента х и у одновременно равны 1; во

7

всех остальных случаях функция равна 0. Иными словами, функция конъюнкции равна min(х, у).

4. f7(x,y) − отрицание		конъюнкции (операция	И-НЕ). Данная	функция
x & y	обращается в нуль	только в том случае,	когда аргументы	х и у

одновременно равны 1; в единицу − во всех остальных случаях. Часто эта функция называется также операцией Шеффера.

5.f9(x,y) − эквивалентность или равнозначность переменных х и у. Данная функция обращается в единицу, если совпадают значения аргументов; в остальных случаях она равна нулю. Обозначается эквивалентность знаком ~, которыйчитаетсякак«равнозначно».

6.f6(x,y) − отрицание эквивалентности или неравнозначности переменных x и y.

Запись x ~ y читается как «х неравнозчно y“. Можно убедиться, что значения

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

7.f11(x,y) −импликацияотхку, котораяобращаетсявнультольковтомслучае, еслих= 1, ау= 0; востальныхслучаяхфункцияимпликации от х к у равна единице. Данная функция обозначается х→ уичитаетсякак«еслих, тоу».

8.f4(x,y) − отрицание импликации от х к у, т.е. x→y . Данную функцию можно

рассматривать как функцию запрета со стороны переменной у. Это означает, что функция x→y обращается в нуль, если переменная у равна единице; в остальных

случаяхонаповторяетпеременнуюх.

9. f13(x,y) − импликация от у к х, которая обращается в нуль только в том случае, если у = 1, а х = 0; в остальных случаях функция импликации от у к х равна единице. Данная функция обозначается y → x ичитаетсякак«еслиу, тох».

10. f2(x,y) −отрицаниеимпликацииотукх.т.е. y →x . Даннуюфункциюможно рассматриватькакфункциюзапретасостороныпеременнойх. Этоозначает, что функция y →x обращаетсявнуль, еслипеременнаяхравнаединице; востальных случаяхонаповторяетпеременнуюу.

11.f12(x,y) −функция, повторяющаязначенияпеременнойх, т.е. f12(x, y) = x.

12.f3(x,y) −функцияотрицанияпеременнойх, т.е. f3(x,y) = x .

13.f10(x,y) −функция, повторяющая значения переменной у, т.е. f10(x, y) =

у.

14. f5(x,y) −функция отрицания переменной у, т.е. f5(x,y) = y .

15 f0(x,y) −функция, тождественно равная нулю, т.е f0(x,y)= 0.

16. f15(x,y) −функция, тождественно равная единице, т.е f10(x, y) = 1.

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

Табличное представление логических функций является весьма наглядным, однако при большом числе n переменных (аргументов) становится очень громоздким и практически необозримым. Если для n = 2 число различных логических функций равно 16, то для n = 3 это число возрастает до 256.

8

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

Широкое распространение получили так называемые нормальные формы представления логических функций. В их основе лежат понятия элементарных дизъюнкций и конъюнкций.

Элементарная дизъюнкция представляет собой дизъюнкцию конечного

числа переменных и их отрицаний (инверсий), например, x1V x2 , x1V x2 , x1V x2 , и др. Конъюнкция элементарных дизъюнкций называется

конъюнктивной нормальной формой (КНФ), например,

FКНФ=( xV y )&( x V y ).

Элементарная конъюнкция представляет собой конъюнкцию конечного числа переменных и их отрицаний (инверсий), например,

x1 & x2 , x1 &x2 , x1 &x2 , и др.

Обозначим xα =x, если α =1 и xα = x , если α =0. Тогда

Κ = xαi1 i1 & xαi2 i 2 & ...& xαin i n - элементарная конъюнкция,

= xαi1V xαi 2V		...V xαi n - элементарная дизъюнкция.
i1	i2	in

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

РДНФ= x &y V x &y .

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

Для того, чтобы построить по данной формуле алгебры логики равносильную ей ДНФ или КНФ необходимо перейти в сигнатуру алгебры логики (выразить все операции через дизъюнкцию, конъюнкцию и отрицание), воспользоваться законом де Моргана для того, чтобы отрицания стояли лишь над элементарными переменными высказываниями, раскрыть скобки (для построения ДНФ) или воспользоваться дистрибутивным законом (для построения КНФ).

Одну и ту же логическую функцию можно представить различными ДНФ и КНФ. Однозначность представления логических функций возможна при записи их в совершенных нормальных формах.

Дизъюнктивная совершенная нормальная форма (ДСНФ) образуется дизъюнкцией так называемых конституент 1 или минтермов. При этом минтермы представляют собой элементарные конъюнкции переменных на тех наборах, на которых функция равна 1. Те переменные, которые в данном наборе равны 0, записываются в минтерме с отрицанием (инверсией), а которые равны 1, − без отрицания (инверсии).

9