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

70

П я т ы й ш а г . Получаем следующее частное:

11. 10111. 00.011 = 11,10111 - 2 ‘ 011= — 101,11 = -------

54

Вопросы и задачи для самопроверки

1. Для чего в ЦЕШ применяют двоично-десятичные системы записи чисел?

з

2.Запишите числа 99, 137, — в двоичной и восьмеричной системе счисле­ ния.

3.Переведите двоичные числа 1101,0, 1101, 1111, 011 в десятичную систему счисления.

4.Как определить знак числа в случае использования модифицированного кода при переполнении?

5.Чем отличаются правила образования обратного и дополнительного ко­ дов?

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

7.Для чего в цифровых вычислительных машинах применяют двоичноде­ сятичные системы записи чисел?

8.Почему для записи.программы используется восьмеричная система счис­ ления?

9.Запишите числа 139, 251, 4/5 в двоичной и восьмеричной системах счис­ ления.

10.Переведите двоичные числа 10101,0,1011, 1101,011 в десятичную систему счисления.

11.Переведите восьмеричные числа 71, ИЗ, 267 в десятичную систему счис­

ную часть переведите с точностью до З- 5 .

14.Переведите десятичное число х 10= 211,335 в двоичную систему. Дробную часть переведите с точностью до 2~5.

15.Чем отличаются позиционные системы счисления от непозиционных?

16.Запишите десятичные числа в двоичной системе счисления в прямом, обратном и дополнительном кодах:

17.Для чего в ЦВМ используются обратные и дополнительные коды?

18.Чем отличаются правила образования обратного и дополнительного кода?

19.Для чего в ЦВМ применяются модифицированные коды?

20.Как определить знак числа в случае использования модифицированного кода при переполнении?

21. Какому числу соответствует [х]доп = s — 1,00 . . . 0? s — запись числа

вs-ичной системе.

22.Переведите число [х]доп = 3,40223 в обычную запись.

23.Для каких чисел дополнительный и обратный коды числа совпадают

с самим числом (х не предполагается удовлетворяющим условию \х\ < 1)?

24.В каком модифицированном коде необходимо сложить два числа, если

[*]“„ = 11 .0 0 1 , Ы “р = и д и ?

71

ЧАСТЬ II

ЛОГИЧЕСКИЕ ОСНОВЫ ЦВМ

Глава четвертая

М АТЕМ АТИЧЕС КАЯ ЛОГИКА

Логика — наука о формах и законах мышления. Математиче­ ская логика описывает результаты применения математических методов к проблемам формальной логики.

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

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

§ 1. ПРОСТЫЕ И СЛОЖНЫЕ ВЫСКАЗЫВАНИЯ

Под высказыванием понимают всякое утверждение, относительно которого можно судить о его истинности или ложности, например: Мир — материален, снег — белый, 7 — четное число. Здесь первые два высказывания истинны, а третье — ложно. Из определения высказывания вытекает, что любое высказывание может быть ис­ тинным или ложным. Одновременно истинным и ложным высказы­ вание быть не может.

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

Примеры высказываний, являющихся объектами булевой ал­ гебры:

А — «за понедельником всегда следует воскресенье». F — «семью три — двадцать один»,

В— «лебедь — хищная птица»,

С— «С. Михалков — советский писатель».

логических связей формальной логики.

73

В — 1. Высказывания оцениваются лишь по их истинности или ложности, без учета их конкретного содержания. Высказывания называют эквивалентными, если они имеют одинаковые значения истинности. Эквивалентность двух высказываний обозначают зна­ ком равенства. Запись А — В означает, что истинность высказыва­ ний А и В одинакова. Переменную величину, принимающую зна­ чение 0 или 1, называют переменной Буля, или двоичной перемен­ ной.

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

§ 2 . н е к о т о р ы е понятая и ОПРЕДЕЛЕНИЯ БУЛЕВОЙ АЛГЕБРЫ

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

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

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

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

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

74

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

Булевой, или переключательной, функцией (функцией двузнач­ ной алгебры логики) f (х 0, х 1г . . . , хп) называют функцию, кото­ рая, как и ее я аргументов, может принимать лишь два значения — О или 1. Таким образом, можно определять булевы функции как двоичные функции двоичных аргументов. Функция, зависящая от я аргументов, называется я-местной и является полностью за­ данной, если указаны ее значения для всех булевых наборов значе­ ний аргументов.

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

Одним из распространенных способов задания булевой функции

данным набором в двоичной системе счисления (т. е. десятичный эквивалент десятичного представления числа), называется номером этого набора.

Областью определения переключательной функции от я аргу­

ментов является совокупность 2п булевых наборов. Булева функ­ ция от 2 аргументов является полностью определенной, если ука­ заны ее значения для каждого из 4 возможных наборов (22 = 4); функция от 3 аргументов полностью задана, если указаны 8 ее зна­ чений (23 = 8).

Отсюда совокупность значений какой-либо функции я пере­ менных можно рассматривать как запись 2п разрядного двоичного числа; так как имеется 22п различных 2п разрядных двоичных чисел,

75

то количество различных переключательных функций от п пере­

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

(табл. 4-2).

Втабл. 4-1 был приведен пример задания полностью определен­ ной трехместной булевой функции. Если значение функции не оп­ ределено хотя бы на одном наборе значений аргументов, то говорят, что функция задана (определена) не полностью, что она является частичной булевой функцией, а ее таблица соответствия — непол­ ной. Табл. 4-3 является неполной таблицей соответствия, ибо бу­ лева функция не определена на наборах (010) и (101), что обозна­ чено символом Ф.

Если частичная булева функция описывает работу какой-то

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

Условные состояния дают возможность соответствующим обра­ зом распределить функцию. Положив по тем или иным соображе­ ниям Ф = 0 или Ф = 1, тем самым распределим функцию, т. е. превратим ее из частной в полностью определенную.

Таблица соответствия дает возможность получить формулу функции. Формула — это другой способ задания функции. Выра­ жения вида:

78

или

являются формулами. Вместо формы записи формулы (4.2), часто

применяют следующую: хгх0 -f х 2х3. При этом учитывают следую­ щий порядок выполнения операций: 1) операция инверсии; 2) опе­ рация конъюнкции; 3) операция дизъюнкции. Такой очередности необходимо придерживаться в формулах, представленных с по­ мощью операций конъюнкции, дизъюнкции и инверсии.

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

[ ( О - М )^ !] V (1_AJ) = 1. 1

1

1

§ 3. ЛОГИЧЕСКИЕ СВЯЗИ

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

Логическое отрицание

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

79

0 = 1 = 0 ,

T = o = i.

Логический элемент, реализующий отрицание (инверсию), назы­ вается элементом «не» или инвертором (рис. 10). '

Логическое произведение (конъюнкция)

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

Конъюнкция обозначается символом Д, - , &, х .

Л Д В = Л Х В = Л - В = Л & В .

Читается эта запись как «А и В», а сами знаки — «и». Таблица ис­

подставляя в различные комбинации значение Л и В (0 и 1).

4 x 0 = 0,

А х 1 = Л,

Лх Л = Л,

Лх А = 0.

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

ется «и» — схема совпадения, или вентиль. Условно логический элемент обозначается (рис. 11).

8 0