Савельвев А.Я. Основы информатики

Подождите немного. Документ загружается.

2 7 Системы функций алгебры логики

Теорема Поста-Яблонского. Для того чтобы система ФАЛ

была полной, необходимо и достаточно, чтобы она содерж:ала хотя

бы одну функцию:

не сохраняющую нуль,

не сохраняющую единицу,

не являющуюся линейной,

не являющуюся монотонной,

не являющуюся самодвойственной.

В таблице 2.15 представлены свойства функции двух переменных .

К базису относится система функций И, ИЛИ, НЕ (базис I), свойства

которых были изучены Дж. Булем. Поэтому алгебра высказываний, постро-

енная на основе этих функций, названа булевой алгеброй. Базисами явля-

ются такясе системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (ба-

зис 3), состоящие из функции Шеффера (базис 4) и функции Пирса (Вебба)

(базис 5). Это перечисление показывает, что базисы могут быть избыточ-

ными (базис I) и минимальными (базисы 4 и 5).

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

систему ФЛЛ в неполную.

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

выбору не только базиса, но и формы наиболее экономного представления

этих функций.

Ьазис И. ИЛИ. HR является избыточной системой, так как возможно

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

де Моргана, можно удалить либо функцию И, заменив ее на функции ИЛИ

и MR, либо функциЮ'ИЛИ, заменяв ее на функции И и НЕ.

1хли сравнить в смысле минимальности различные формы представле-

ний ФЛЛ, станег ясно, что нормальные формы экономичнее совершенных

нормальных (|)орм. Но, с другой стороны, нормальные формы не дают од-

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

Минимальная форма представления ФАЛ — форма представления

ФАЛ, которая содержит минимальное количество термов и переменных в

термах (т. е. минимальная форма не допускает никаких упрощений).

Например, функция /(х|,

^2,...,

х„) = х,

•¥

Xj является минимальной

формой и, наоборот, функция х, +х,Х2 может быть упрощена, если к этому

выражению применить распределительный закон, т.е. х^

х^Х2

(х^-^

)( \-| ( V, ) - V,

X, .

Ф>11кги1н /q и /,^ не принадлежат ни одному из указанных классов.

томат как основной элемент информационных систем

Следовательно, упрощение сложных логических выражений может

быть осуществлено по основным законам

аксиомам, изложенным выше.

Пример 2.9. Упростить функцию /(А, В, С)

АВ

ВС•*-

ВС

АВ в базисе 1.

Решение. Сначала примем правило (2.23), а затем упростим функцию.

/{A.B.C)=^AB+BC+BCiA

ABiC*C)=AB+BC+ABC+ABC*ABC+ABC =

' АВ(\

С)+ВС(\

А)+АС{В+В)=АВ

ВС

АС.

Ответ: /(А. В. С)= АВ

ВС

АС .

Пример 2.10. Упростить функцию f{A,B,C.D)=AB

Ci^ ACD

BCD в базисе I

Решение. Нетрудно доказать, что х

ху

у, Используя также теорем)

де Моргана, получим х

ху.

Тогда C+ACD

AD: C

BCD~C+BD.

Следовательно. /(А. B.C. D) = АВ+С+ AD+BD= АВ

D(A

В)

АВ + DAB +

+С=АЪ+С+О.

Ответ: /(А. B.C. D)= АВ+С

D .

Задание для самоконтроля

Составить таблицу истинности для заданных функций:

a)/i(jr,,j<j.,,) = v(1.2,3,5);

6)/j(:,„jc,,;,,) = V(l.2,3,S,6,7);

я) /M-'i-h)' V(l.3.8, 9,10, 11,12,14);

Доказать тождественность функций:

а) АС + ВС

АС

ВС .

б) (А

ВХА+С)^ АС+АВ.

в) АВ+ВС

АС

АВ

ВС+АС .

Найти минимальную форму для функций, заданных в примере 1.

Найти СДНФ и СКИФ для следующих функций:

а) М"!'

>'i,':,)

= x,+ х.,х, + xfyx, + х,х,;

б)

/2(.tr,-«2.-'))

= ^l + »2:

в) Mx,.Xj.X,)

(,X,X2+X,.X,)&X,X2

•

ПРЕДСТАВЛЕНИЕ ЧИСЛОВОЙ ИНФОРМАЦИИ

В ИНФОРМАЦИОННЫХ СИСТЕМАХ

3.1.

Выбор системы счисления для представления

числовой информации

Информация во внешнем по отношению к ЭВМ мире представляется в

непрерывном или дискретном виде. Внутри ЭВМ информация всегда пред-

ставляется в виде чисел, записанных в той или ииой системе счисления.

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

также с помощью чисел. Вопрос о выборе системы счисления для цифрово-

го автомата — один из важнейших вопросов проектирования как алгорит-

мов функционирования отдельных устройств, так и расчета технических

харашеристик Ttoio автомата [II, 12].

Система счисления — совокупиость приемов и правил для записи чи-

сел цифровыми знаками или символами. Наиболее известна десятичная

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

О, I, ..., 9. Способов записи чисел цифровыми знаками существует бесчис-

ленное множесгво. Лйбая предназначенная для практического применения

система счисления должна обеспечивать:

возможносгь представления любого числа в рассматриваемом диапа-

зоне величии;

единственность представления (каждой комбинации символов должна

COOI

ветствовать одна и только одна величина);

просгогу оперирования числами.

Все системы представления чисел делят иа позиционные и непозицион-

иые.

Самьп"! простой способ записи чисел может быть описан выражением

где А,, — запись числа /I в системе счисления D; Д — символы системы,

образующие базу £) =

{

Ц, Д ,...,£>,).

Но этому принципу построены иепозиционные системы счисления.

S- Представление числовой информации в информационных системах

Непозиционная система счисления — система, для которой значение

символа не зависит от его положения в числе.

Принципы построения таких, систем не сложиы. Для их образования

иС1юльзуют в основном операции сложения и вычитания. Например, систе-

ма с одним символом (палочкой) встречалась у многих народов. Для изо-

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

чек, равное данному числу. Эта система неэффективна, так как запись

числа получается длинной. Другим примером непозиционной системы

счисления является римская система, использующая набор следующих

символов: (, X, V, L, С, D, М и т. д. В этой системе существует отиюнение

от правила независимости значения цифры от положения в 4HCjre. В числах

LX и XL символ X принимает два различных значения: +10 — в первом

случае и -10 — во втором.

В общем случае системы счисления можно построить по следующему

принципу:

Ад =0,8^+0282+...

а„В„,

(3.1)

где Ag —запись числа/< в системе счисления с основанием В,; п, —циф-

ра (символ) системы счисления с основанием В/, В, — база, или 0С1ГОванне

системы.

Если предположить, что В, = д', то с учетом (3.1)

B,=q,B,.,.

(3.2)

Позиционная система счисления — система, удовлетворяющая равен-

ству (3.2).

Естественная позиционная система счисления имеет место, если </ --

целое положительное число.

В гюзициониой системе счисления значение цифры определяется ее

положением в числе: один и тот же знак принимает различное значение.

Например, в десятичном числе 222 первая цифра справа означает две еди-

ницы, соседняя с ней — два десятка, а левая — две сотни.

Любая позиционная система счисления характеризуется основанием.

Основание {базис) q естественной позиционной системе^ счисления — коли-

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

системе. Возможно бесчисленное множество позиционных систем, так как,

приняв за основание любое число, можно образовать новую систему. Напри-

мер,

запись числа в шестнадцатеричной системе может проводиться с рюмо-

щью следующих знаков (цифр): О, 1, ..., 9, А, В, С, Д Е, F (вместо А, ..., F

можно записать любые другие символы, например, Т,

2,...,

5 ).

3 I выбор системы счисления для представления числовой информации

Для позиционной системы счисления справедливо равенство

2".?'. (3-3)

или

/1,^

=а„|/"+... + 0|(/'+aj(/''+а_|(/''+.,, + а_„17~'', где А^ —произволь-

ное число, записанное в системе счисления с основанием q; « + I, m — ко-

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

11а прапике ис[10льзу10т сокращенную запись чисел:

А^

а„а^_У

...й|Й5а_| .-.a_„,.

В восьмеричной системе счисления числа изображают с помощью цифр

0. I,..., 7. Например, I24,537g =

1-8^2-8'+

4-8°+5-8"' +3-8"Ч 7•8"^

В двоичной системе счисления используют цифры О, 1. Например,

1001,1 lOlj =Ь2Ч0-2Ч0-2' +l-2°+l-2"'+l-2'^+0-2~4l-2"V

1У\я записи чисел в троичной системе берут цифры О, 1,2. Например,

2122,

=2-3'4 ЬЗ'+2-3' +2-3°.

В заблицеЗ.) приведены эквиваленты десятичных цифр в различных

системах счисления.

/(ссяти'шан rinfjipa

9 = 2

0000

0001

0010

ООП

0100

0101

оно

0111

1000

1001

Т а6 л и ца 3.1

Зквиваленты в других системах счисления

?=3

000

001

002

010

011

012

020

021

022

100

?-5

9 = 8

q = \b

Для любой 1ЮЗИЦИОННОЙ системы счисления справедливо, что основа-

ние изображается символом 10 в своей системе, т. е. любое число можно

записать в виде

Л,,

=о„10" +... + 0, •10'+а„-10°+а_|-10'' +... + «_,

•10~'

(3.4)

S. представление числовой информации в информационных

В ЭВМ используют в основном позиционные системы счисления. В

дальнейшем для простоты изложения будем употреблять термин «система

счисления», имея в виду позиционные системы.

Вес разряда р^, числа в позиционной системе счисления выражается

соотношением

Р,=я'1я'=ч',

OS)

где / — номер разряда при отсчете справа налево.

Если разряд имеет вес р, = 10*, то следующий старший разряд будет

иметь вес р,^, =10 ^', а соседний младший разряд — вес д_, - 10*"' . [акая

взаимосвязь разрядов приводит к необходимости передачи информации

между ними.

Если в даином разряде накопилось значение единиц, равное или боль-

шее q, то должна происходить передача единицы в соседний старший раз-

ряд. При сложении такие передачи информации называют переносами, а

при вычитании — заемами. Передача переносов или заемов происходит

последовательно от разряда к разряду.

Длина числа (ДЧ) — количество позиций (или разрядов) в записи чис-

ла [14]. В техническом аспекте длина числа интерпретируется как длина

разрядной сетки (ДРС).

Для разных систем счисления характерна разная длина разрядной сет-

ки,

необходимая для записи одного и того же числа. Например,

96 = 120j =10120з =

lOOOOOj. Здесь одно и то же число, записанное в раз-

ных базисах, имеет разную длину разряД1ЮЙ сетки. Чем меньше основание

системы, тем больше длина числа.

Если длина разрядной сетки задана, то это ограничивает максимальное

(или минимальное) по абсолютному значению число, которое может бьпь

записано.

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

например п. Тогда

А^

,„„ =q" -i; /!,„,„= Нч"

•

Диапазон представления (ДП) чисел в заданной системе счисления —

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

ным числами, представленными длиной разрядной сетки:

Л„„„>ДПг4™,п-

0-6)

Правильный выбор системы счисления — важный практический во-

прос,

поскольку от его решения зависят такие технические характеристики

проектируемой ЭВМ, как скорость вычислений, объем памяти, сложность

3 I Выбор системы счисления для представления числовой

иифо1

ftoifuu

алгоритмов выполнения арифметических операций. При вы iope системы

счисления для ЭВМ необходимо учитывать следующее:

основание системы счисления определяет количество у< гойчивых со-

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

изображения разрядов числа;

длина числа существенно зависит от основания системы i числения;

система счисления должна обеспечить простые алгоритм"*! выполнения

арифметических и логических операций.

Десятичная система, столь привычная в повседневной >к-'|зни, не явля-

ется наилучшей с точки зрения ее технической реализации в-ЭВМ. Извест-

ные в настоящее время элементы, обладающие десятью устойчивыми со-

стояниями (элементы на основе сегнетокерамики, декатроиы.и др.), имеют

невысокую скорость переключения, а следовательно, не мог т обеспечить

соответствующее быстродействие машины.

ПодавлягонЕсе большинство компонентов электронных,..схем, приме-

няемых для построения ВМ, — двухпозиционные. С этой то',<и зрения для

ЭВМ наиболее подходит двоичная система счисления. Но рг^диоиальио ли

использование этой системы с точки зрения затрат оборудо? шия? Для от-

вета на это

вопрос введем !юказатель экономичности систем,

С — произ-

ведение осЕЮвания системы на длину разрядной сетки, выбранную для за-

писи чисел в этой системе:

qN, (3.7)

где q — основание системы счисления; Л^— количество разрг 10в.

Вели принять, что каждый разряд числа представлен не i дним элемен-

том с f/ устойчивыми состояниями, а q элементами, каждь'й из которых

имеет одно устойчивое состояние, то показатель экономи-'иости укажет

ycjTOBHoe KojHi4ecTBo оборудования, которое необходимо')затратить на

прелс'тавление чисел в этой системе.

Максимальное число, которое можно изобразить в cncTefie с основани-

ем q,

Л.п.х=9''-"- (3-8)

Из (3.8) можно найти требуемую длину разрядной сетки:)

(3.9)

Го1

да для любой системы счисления С = 9log,(/l,„„ +Ь.

Представим, что величина ^ принимает любые значени; | (целочислен-

ные и дробные), т. е. является непрерывной величиной. 3i ) необходимо

3 Представление числовой информации в информационных системах

для того, чтобы рассматривать величину С как функцию от величины q.

Данное допущение не является строгим, однако позволяет получить инте-

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

элемент с одним устойчивым состоянием, то для сравнения двух систем

счисления можно ввести относительный показатель экономичности

/='

?1о8,(Л....х +')Д2Ь82{Л,„„ +1)]. (3.10)

ПОЗВОЛЯЮЩИЙ сравнить любую систему счисления с двоичной.

Если функция F непрерывна, то, как видно из приведенного ниже со-

отношения, она имеет минимум.

....

F „ .

... 2

1,(Ю0

0.946

1.000

1.148

1,333

1.303

На рис. 3.1 представлена зависимость ве-

личины F

от

основания системы счисления q.

Нижняя точка графика соответствует мини-

муму функции F, определяемому из условия

dFjdq = О, что соответствует значению

q = е . Следовательно, с точки зрения мини-

мальных затрат условного оборудования,

наиболее экономичной является система

счисления с основанием, равг{ым е » 2,72 .

Используя (3.10), можно доказать, что

троичная система счисления 3KoiioMH4Fiee

двоичной. В подавляющем большинстве

ЭВМ ис1юльзуют двоичную систему счисления, однако для ЭВМ это связа-

но с преодолением дополнительных трудностей, возникающих при перево-

де входной информации в двоичную систему счисления и двоичной ин-

формации в выходную информацию.

Рис.

3.1.

Зависимость относи-

icjibiKUo Е1оказа|еля эконо-

мичное

и 01 основания

сисгсмы счисления

3.2. Перевод числовой информации

нз одной позиционной системы в другую

в процессе преобразования информации в цифровом автомате возни-

каег необходимость перевода чисел из одной позиционной системы счис-

ления в другую. Это обусловлено тем, что в качестве внутреннего алфавита

наиболее целесообразно использовать двоичный алфавит с символами

и Г.

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

VI!

в Ф, Бэкон, который использовал символы 0. I.

3 2 Ih'peeoc) числовой информации из одной позиционной системы в другую

Рассмотрим задачу перевода чисел в общей постановке.

В соогветствин с (3.3) числа в разных системах счисления можно пред-

ставить слелуюншм образом:

•\^1."Я\-ЪЬ^ц{=Л^^.

(3.11)

В общем виде задачу перевода числа из системы счисления

осиоваии-

см

f/,

в сисюму счисления

основанием q^ можно представить как задачу

определения коэффициентов Ь, нового ряда, изображающего число в систе-

ме с основанием с/,. Реижть эту задачу можно подбором коэффициентов

Ь,.

Основная груд1юе1ь при этом заключается

выборе максимальной степени,

которая еще содержится

числе

А^^

Все действия должны выполняться по

правилам

-арифметики, т. е. по правилам исходной системы счисления.

После нахождения максимальной степени основания проверяют «вхо-

ж;1ерте»

за/шниое чиcJЮ всех степеней нового основания, меньших мак-

cHMaJH^nor о. Каждая из отмеченных степеней может «входить» в ряд не бо-

лее

Ц; I раз, гак как

для любого коэффициента ряда накладывается

о1

рамичепне:

()<a,<q^-\;^<b,<q2-\. (3.12)

Пример З.Г. Ucpcnecin леся1ич11()е число

= 96

троичную систему счисления

!'СИ! erf и с 46 = 0 3' +

3' +0-ЗЧ|-ЗЧ23'+0-3'' = 10120,

Ответ А. =10120

Рассмотренный

примере 3.1 прием может быть использован только

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

приме1гя101 следующие методы.

Перевод целых чисел делением

на

основание q^ новой системы

счисления. 1Делое число

в системе с основанием q^ записывается в виде

[[ерепнсав это выражение по схеме Горнера, получим

Л.

=(--№?2+Vi)?2+---)?2+^i)?2+^o- (3.13)

ьиеипрем при •записи десятичных чисел индекс опускается.

Представление числовой информации

информационных системах

Правую часть выражения (3.13) разделим

на

величину основания

</,. В

результате определим первый остаток

йц и

целую часть

(•••((bi,qi+b^^^)q-,

+...)q, +*,).

Разделив целую часть

на qj,

найдем вюрой

остаток

й|.

Повторяя процесс деления

раз,

получим последнее целое

частное

6,,

которое,

по

условию, меньше основания системы

^2 "

является

старшей цифрой числа, представленного

системе

основанием

q,.

Пример 3.2. Перевести десятичное число

.^ = 98

в двоичную систему счисления

(t^, - 2 )

Решение.

6„=0

Ответ

/1,

=1100010.

= 0

1=6,

л,

А]

Пример

3.3.

Перевести лноичное число

Aj =

1101001

десятичную CMCteNfy счисления

{е/з

= 10 ).

Основание

е/^

изображается в двоичной системе чквивалеитом

е/,

-1010,

1101001

1010

001100

1010

[1010

1010

0000

=0001

0000

6„=0101

Ответ:

на

основании та6лицы3.1 можно записать: 6|,=0i0l2=5;

б,

=0000,

=0;

*2 =000lj

=1: А

105.

Этот

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

Перевод правильных дробен умножением

на

основапне

новой

системы счисления. Пусть исходное число, записанное

системе счисле-

ния

основанием

q,,

имеет

вид

Л,

="-i4t' +••• + ''-n,чГ•

Toгm

новой системе

основанием

q^ это

число будет изображено

как

О,

Ь_,,

..., й,, или