Логические основы построения компьютера

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

Выполним фрагмент алгоритма перевода целого десятичного числа в двоичную систему счисления: «Последовательно выпол­нять деление числа и получаемых целых частных на 2 до тех пор, пока не получим частное меньше 2».

Компьютер, который автоматически выполняет, операции пе­ревода, должен уметь делать выбор:

«Да» — закончить работу «Нет» — продолжить деление

«Полученное целое частное меньше 2?»

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

«Есть переизбыток?» «Да» «Нет»

Алгебра логики

Алгебра логики появилась в середине XIX в. в трудах англий­ского математика Джорджа Буля. Он пытался решать традицион­ные логические задачи алгебраическими методами.

Логическое высказывание — это любое повествовательное предло­жение, в отношении которого можно однозначно сказать, истинно оно или ложно. Например, предложение «6 — четное число» следует считать высказыванием, так как оно истинное; предложение «Рим — столица Франции» — тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим выс­казыванием.

Высказываниями не являются, например, предложения: «Сту­дент 204 группы», «Здравствуйте!», «В колледже более 1000 уча­щихся», «Хороший студент», — так как невозможно судить об их истинности или ложности (или нужны дополнительные сведения, чтобы предложение стало высказыванием, например: «Петров — хороший студент» или «в колледже № 15 г. Самары более 1000 учащихся»).

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным.

Заметим, что зачастую трудно установить истинность высказы­вания. Например, высказывание «Площадь поверхности Индий­ского океана равна 75 млн км²» в одной ситуации можно посчи­тать ложным, а в другой — истинным (ложным — так как указан­ное значение неточное и вообще не является постоянным; истин­ным — если рассматривать его как некоторое приближение, прием­лемое на практике).

Употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если, то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые. Такие слова и слово­сочетания называются логическими связками.

Высказывания, образованные из других высказываний с по­мощью логических связок, называются составными. Высказыва­ния, не являющиеся составными, называются элементарными. Например, из элементарных высказываний «Иванов — студент», «Иванов — отличник» при помощи связки и можно получитьсоставное высказывание «Иванов — студент и отличник».

Чтобы обращаться к логическим высказываниям, им назнача­ют имена. Пусть через А обозначено высказывание «Иван поедет летом на море», а через В — высказывание «Иван летом отправится в горы». Тогда составное высказывание «Иван летом побывает и на море, и в горах» можно записать кратко: «А И В». Здесь И — логическая связка; А, В — логические переменные, которые могут принимать только два значения: «истина» и «ложь», обознача­емые соответственно 1 и 0.

В алгебре высказывания обозначаются именами логических пе­ременных, которые могут принимать лишь два значения: «исти­на» (1) и «ложь» (0).

Рассмотрим операции, которые можно производить с логиче­скими высказываниями.

Операция отрицания. Операция, выражаемая словом НЕ, назы­вается отрицанием, или инверсией, и обозначается чертой над высказыванием. Высказывание А истинно, когда А ложно, и лож­но, когда А истинно. Например: «Луна — спутник Земли» (А); «Луна — не спутник Земли» (А).

Пусть А = «Два умножить на два равно четырем» — истинное высказывание, тогда высказывание, образованное с помощью опе­рации логического отрицания — «Два умножить на два не равно четырем», — ложное высказывание.

Образуем высказывание F, являющееся логическим отрицани­ем А:

F = A.

Истинность такого высказывания задается таблицей истинно­сти функции логического отрицания (табл. 2.6).

Таблица 2.6 Таблица истинности функции логического отрицания

А	F

 

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

Операция, выражаемая связкой И, на­зывается соединением, или конъюнкцией, или логическим ум­ножением, и обозначается знаком «&» (может обозначаться зна­ком «л» или «•»). Высказывание F = А&В истинно только тогда, когда оба высказывания А и В истинны. Например, высказывание «10 делится на 2 И 5 больше 3» истинно, а высказывания «10 делится на 2 И 5 не больше 3», «10 не делится на 2 И 5 больше 3», «10 не делится на 2 И 5 не больше 3» ложны.

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

Таблица 2.7

Таблица истинности функции логического умножения

 

А	В	F

Рассмотрим, например, составное высказывание «2 • 2 = 4 И 3 *3 = 10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0). По табл. 2.7 определяем, что логиче­ская функция принимает значение «ложь» (F = 0), т.е. данное со­ставное высказывание ложно.

Операция дизъюнкции. Операция, выражаемая связкой ИЛИ, называется разделением, или дизъюнкцией (от лат. disjunctio — разделение), или логическим сложением, и обозначается знаком «v» (или «+»). Высказывание F = A v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание «10 не делится на 2 ИЛИ 5 не больше 3» ложно, а высказывания «10 делится на 2 ИЛИ 5 больше 3», «10 делится на 2 ИЛИ 5 не больше 3», «10 не делится на 2 ИЛИ 5 больше 3» истинны.

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

Таблица 2.8

Таблица истинности функции логического сложения

 

А	в	F

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

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере следующих высказыва­ний: «Данный четырехугольник — квадрат» (А) и «Около данного четырехугольника можно описать окружность» (В). Рассмотрим составное высказывание F = А-»В, под которым понимается: «Если данный четырехугольник — квадрат; то около него можно опи­сать окружность».

Существуют три варианта, когда высказывание А-*В истинно:

1) А истинно и В истинно, т.е. данный четырехугольник — квадрат и около него можно описать окружность;

2) А ложно и В истинно, т. е. данный четырехугольник не явля­ется квадратом, но около него можно описать окружность (разу­меется, это справедливо не для всякого четырехугольника);

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

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

Функцию F можно определить, используя таблицу истинности (табл. 2.9): F = A^B

Таблица 2.9

Таблица истинности логической функции импликации

 

А	в	F

Операция логического следования несколько отличается от обычного понимания слова «следует». Если первое высказывание (предпосылка) ложно, то независимо от истинности или ложно­сти второго высказывания (вывода) составное высказывание истин­но. Из неверной предпосылки может следовать что угодно.

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

Докажем методом сравнения таблиц истинности, что операция импликации А-> В равносильна логическому выражению A v В (табл. 2.10).

Таблица 2.10

Таблица истинности логического выражения A v В

 

А	в	А	A vB
			I

 

Табл. 2.10 полностью совпадает с табл. 2.9.

Операция эквиваленции. Операция равенства, выражаемая связ­ками «тогда и только тогда», «необходимо и достаточно», «...рав­носильно...», называется эквиваленцией, или двойной имплика­цией, и обозначается знаками «<-»» или «~». Высказывание А <-> В истинно тогда и только тогда, когда значения А и В совпадают. Например, истинны высказывания: «24 делится на 6 тогда и толь­ко тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3» — и ложны высказывания: «24 де­лится на 6 тогда и только тогда, когда 24 делится на 5», «21 делит­ся на 6 тогда и только тогда, когда 21 делится на 3».

Высказывания А и В, образующие составное высказывание F = А<-»В, могут быть совершенно не связаны по содержанию.

Составное высказывание F = А<-> В имеет таблицу истинности (табл. 2.11).

Таблица 2.11

Таблица истинности составного высказывания А<->В

 

А	в	F

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

Эквивалентность можно выразить через следующие логические функции:

F=AoB = (AvB)&(BvA).

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились счи­тать, что сначала выполняется операция отрицания (НЕ), затем — конъюнкции (И), затем дизъюнкции (ИЛИ) и в последнюю оче­редь — импликации. Такая последовательность называется при­оритетом операций.

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

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

1. Закон двойного отрицания:

А = А.

Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

• для логического сложения

A v В = В v А;

• для логического умножения

А&В=В&А

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания. В обычной алгебре a + b = b + a;a-b = b-a.

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

• для логического сложения

(A v В) v С = A v (В v С);

• для логического умножения

(А&В)&С = А&(В&С).

При одинаковых знаках скобки можно ставить произвольно или опускать.

В обычной алгебре (а + Ь) + с = а + (Ь + с) = а + b + с;

(а • Ь) ■ с = а • (Ь • с) = а • b • с.

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

• для логического сложения

(A v В) & С = (А&С) v (B&C);

• для логического умножения
(А&В) v С = (A v C)&(B v С).

Данный закон определяет правило выноса общего высказыва­ния за скобку.

В обычной алгебре справедлив распределительный закон толь­ко для сложения: (а + Ь) • с = а • с + b • с.

5. Закон общей инверсии (законы де Моргана):

• для логического сложения

AvB = A&B;

• для логического умножения

A&B = AvB.

6. Закон идемпотентности (от лат. idem — тот же самый + potens —сильный (дословно — равносильный)):

• для логического сложения

AvA = A

• для логического умножения

А&А = А.

Закон означает отсутствие показателей степени.

7. Закон исключения констант:

• для логического сложения

Avl = l;AvO = A;

• для логического умножения

А&1 = А; А&0 = 0.

8. Закон противоречия:

А&А=0.

Невозможно, чтобы противоречащие высказывания были од­новременно истинными.

9. Закон исключения третьего:

AvA = l.

Из двух противоречащих высказываний об одном и том же пред­мете одно всегда истинно, а второе — ложно; третьего не дано.

10. Закон поглощения:

• для логического сложения:

A v (A&B) = А;

• для логического умножения

А&(А v В) = А.

11. Закон исключения (склеивания):

• для логического сложения

(A&B)v(A&B) = B;

• для логического умножения

(AvB)&(AvB) = B.

12. Закон контрапозиции (правило перевертывания):

(А*+В) = (ВвА).

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

Пример 1. Найдите X, если XvAvXvA=B.

Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

(Х&А) v (Х&А).

Согласно распределительному закону для логического сложе­ния

X&(AvA).

Согласно закону исключения третьего и закона исключения констант

Х&1 = X. Полученную левую часть приравняем правой:

Х = В.

Окончательно получим: X = В.

Пример 2. Упростите логическое выражение (AvBvC)&

&А v В v С. Правильность упрощения проверьте с помощью таб­лиц истинности для исходного и полученного логических выра­жений.

Согласно закону общей инверсии для логического сложения (первому закону де Моргана) и закону двойного отрицания

(A v В v C)&A v В v С = (A v В v С)&(А&В&С).

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

(A v В v С)&(А&В&С) = (А&А) v (В&А) v (С&А) v (A&B) v v (B&B) v (C&B) v (А&С) v (В&С) v (С&С).

Согласно закону противоречия»

(А&А) = 0; (С&С) = 0.

Согласно закону идемпотентности

(В&В) = В.

Подставляем значения и, используя переместительный (ком­мутативный) закон и группируя слагаемые, получаем:

О v (A&B) v (A&B) v В v (C&B) v (C&B) v (C&A) v (A&C) v 0.

Согласно закону исключения (склеивания)

(A&B) v (А&В) = В; (C&B) v (C&B) = В.

Подставляем значения и получаем:

OvBvBvBv (C&A) v (A&C) v 0.

Согласно закону исключения констант для логического сложе­ния и закону идемпотентности

0vBv0vBvB = B.

Подставляем значения и получаем:

Bv(C&A)v(A&C).

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

(C&A) v (А&С) = (С v А) & (С v С) & (A v A) & (A v С). Согласно закону исключения третьего

(CvC) = l;(AvA) = l. Подставляем значения и окончательно получаем:

В&А&С.

Решение логических задач способствует развитию абстрактно­го мышления, тренирует память и развивает логику.

2.2.3. Логические основы устройства компьютера

Математический аппарат алгебры логики очень удобен для опи­сания того, как функционируют аппаратные средства компьюте­ра, поскольку основной системой счисления в компьютере явля­ется двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: 1 (true) и 0 (false).

Из этого следует два вывода:

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

• на этапе конструирования аппаратных средств алгебра логи­ки позволяет значительно упростить логические функции, опи­сывающие функционирование схем компьютера, и, следователь­но, уменьшить число элементарных логических элементов, из де­сятков тысяч которых состоят основные узлы компьютера.

Логический элемент компьютера — это часть электронной логи­ческой схемы, которая реализует элементарную логическую функ­цию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и др. (называемые также вентилями), а также триггер. С помощью этих схем можно реали­зовать любую логическую функцию, описывающую работу уст­ройств компьютера. Обычно у вентилей бывает от двух до восьми входов и один или два выхода. Чтобы представить два логических состояния 1 и 0 в вентилях, соответствующие им входные и вы­ходные сигналы имеют один из двух установленных уровней на­пряжения. Например: 5 и О В.

Высокий уровень обычно соответствует значению «истина» (1), а низкий — значению «ложь» (0).

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

Работу логических элементов описывают с помощью таблиц истинности (аналогично таблицам истинности функций).

Рассмотрим структурные схемы логических элементов компь­ютера и их таблицы истинности (табл. 2.12).

• схема И реализует конъюнкцию двух или более логических значений. На выходе схемы И будет 1 тогда и только тогда, когда на всех входах будут 1. Когда хотя бы на одном входе будет 0, на выходе также будет 0;

• схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном из выходов схемы или будет 1, на ее выходе тоже будет 1;

• схема НЕ (инвертор) реализует операцию отрицания. Связь Между входом х этой схемы и выходом z можно записать соотно­шением z= х. Если на входе схемы 0, то на выходе 1. Когда на Входе 1, то на выходе 0;

• схема И—НЕ состоит из элемента И и инвертора и осуществ­ляет отрицание результата схемы И. Связь между выходом z и выхо­дами х и у схемы записывают следующим образом: z = х & у;

• Таблица 2.12

Структурные схемы логических элементов компьютера и их таблицы истинности

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Условное обозначение	Структурная схема	Таблица истинности
И
X Y				X	У	х&у
&	X&Y
ИЛИ
				X	У	xvy
X_ Y		XvY
НЕ
Х_		() X		X	X
И-НЕ
				X	У	х&у
X Y	& <
X&Y
ИЛИ-НЕ
				X	У	xvy
X Y	1 (
XvY

• схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора и _оСуществляет отрицание результата схемы ИЛИ. Связь между вы­ходом z и входами х и у схемы записывают следующим образом: _z = xVy.

Триггер

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

Триггер можно построить их двух логических элементов ИЛИ и двух элементов НЕ (рис. 2.3, а). Им соответствует таблица истин­ности (табл. 2.13).

Самый распространенный тип триггера — RS -триггер (от англ. set — установка + reset — сброс). Он имеет два симметричных вхо­да R и S и два симметричных выхода Q и Q. На каждый из двух выходов могут подаваться входные сигналы в виде импульсов (на­личие импульса на входе будем считать единицей, а его отсут­ствие — нулем). В обычном состоянии на входы R и S триггера подан сигнал 0 и триггер хранит 0. Для записи 1 на вход S (устано­вочный) подается сигнал 1. Последовательно рассмотрев прохож­дение сигнала по схеме, видно, что триггер переходит в СОСТОЯ­ВШИ"

Рис. 2.3. Схема триггера: а — на элементах ИЛИ и НЕ; б — на элементах ИЛИ-НЕ

Таблица 2.13 Таблица истинности

 

S	R	Q	Q
		Запрещено
		Хранение бита

ние «1» и будет устойчиво находиться в нем и после того, как сигнал на входе S исчезнет. Триггер запомнил 1, т.е. с выхода триггера Q можно считать 1.

Для того чтобы сбросить информацию и подготовиться к при­ему новой, подается сигнал 1 на вход R (сброс), после чего триггер возвращается к исходному (нулевому) состоянию. Если на входы R и S подана логическая 1, то состояние Q и Q не меняется, подача на оба входа логического 0 может привести к неординарному ре­зультату, и поэтому эта комбинация входных сигналов запрещена.

На рис. 2.3, б показана реализация триггера с помощью венти­лей ИЛИ-НЕ.

2.2.5. Сумматор двоичных чисел

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

При сложении двоичных чисел образуется сумма в текущем разряде; при этом возможен перенос единицы в старший разряд. Обозначим слагаемые — А, В, перенос — Р и сумму — S.

Таблица 2.14

Таблица сложения одноразрядных двоичных чисел

 

Слагаемые	Перенос	Сумма
А	В	Р	S

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

Р = А&В,

где Р — перенос; А и В — множители.

Для определения суммы можно применить следующее выраже­ние:

S = (AvB)&(A&B).

Построим таблицу истинности для данного логического выра­жения и убедимся в правильности нашего предположения (табл. 2.15).

Таблица 2.15

Таблица истинности функции F = (A v В) & (А & В)

 

А	В	AvB	А&В	А&В	(AvB)&(A&B)

Рис. 2.4. Схема полусумматора двоичных чисел

На основе полученных логических выражений можно постро­ить схему полусумматора на базовых логических элементах.

По логической формуле переноса легко определить, что для по­лучения переноса необходимо использовать логический элемент И.

Анализ логической формулы для суммы показывает, что на выходе должен стоять элемент логического умножения И, кото­рый имеет два входа. На один из входов подается результат логи­ческого сложения исходных величин A v В, т. е. на него должен подаваться сигнал с элемента логического сложения ИЛИ.

На второй вход требуется подать результат инвертированного логического умножения исходных сигналов А&В, т.е. на второй вход подается сигнал с элемента НЕ, на вход которого поступает сигнал с элемента логического умножения И (рис. 2.4).

Данная схема называется полусумматором, так как реализует суммирование одноразрядных двоичных чисел без учета переноса из младшего разряда.

 

 

Контрольные вопросы

1. Связано ли появление алгебры логики с разработкой персонально­го компьютера?

2. Назовите основные логические операции.»

3. Приведите примеры предложений, которые не являются логиче­ским высказыванием.

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

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

6. Назовите приоритеты логических операций.

7. Сформулируйте отрицание следующих высказываний: «2 > 5»;
«10 < 7»; «а = 2».

8 Изобразите в декартовой системе координат области (|х| < 1) и

9. Определите истинность составного высказывания «(А & В) & (С v D)»,
состоящего из простых высказываний: А = «Принтер — устройство выво­
да информации», В = «Процессор — устройство хранения информации»,
С = «Монитор — устройство вывода информации», D = «Клавиатура —
устройство обработки информации».

10.Докажите, используя таблицы истинности, что операция эквива­лентности равносильна логическим выражениям А <-» В = (А & В) v (А & В) и A<->B = (AvB)&(AvB).

11.Докажите, используя таблицы истинности, что логические выра­жения A v В и А & В равносильны.

12.Какие логические функции двух аргументов имеют свои названия?

13.Какое существует число логических функций трех аргументов?

14.Упростите следующие логические выражения:

(AvA)&B; A&(AvB)&(BvB).

15. Приведите примеры из повседневной жизни:

если (не а и не Ь), то (с или d); (а или Ь) тогда и только тогда, когда (с или не d).

16.Проследите на логической схеме триггера, что происходит при поступлении сигнала 1 на вход R.

17.Какое число базовых логических элементов необходимо для хране­ния 512 Мбайт информации?