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

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

Теорема Поста-Яблонского. Для того чтобы система ФАЛ была полной, необходимо и достаточно, чтобы она содерж:ала хотя

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

Кбазису относится система функций И, ИЛИ, НЕ (базис I), свойства которых были изучены Дж. Булем. Поэтому алгебра высказываний, постро­ енная на основе этих функций, названа булевой алгеброй. Базисами явля­ ются такясе системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (ба­ зис 3), состоящие из функции Шеффера (базис 4) и функции Пирса (Вебба) (базис 5). Это перечисление показывает, что базисы могут быть избыточ­ ными (базис I) и минимальными (базисы 4 и 5).

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

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

Ьазис И. ИЛИ. HR является избыточной системой, так как возможно удаление из него некоторых функций. Например, используя законы де Моргана, можно удалить либо функцию И, заменив ее на функции ИЛИ и MR, либо функциЮ'ИЛИ, заменяв ее на функции И и НЕ.

1хли сравнить в смысле минимальности различные формы представле­ ний ФЛЛ, станег ясно, что нормальные формы экономичнее совершенных нормальных (|)орм. Но, с другой стороны, нормальные формы не дают од­ нозначного представления.

Минимальная форма представления ФАЛ — форма представления ФАЛ, которая содержит минимальное количество термов и переменных в термах (т. е. минимальная форма не допускает никаких упрощений).

Например, функция /(х|, ^2,..., х„) = х, •¥ Xj является минимальной формой и, наоборот, функция х, +х,Х2 может быть упрощена, если к этому выражению применить распределительный закон, т.е. х^ + х^Х2 = (х^-^

+ V, )( \-| ( V, ) - V, 4- X, .

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

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

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

Принципы построения таких, систем не сложиы. Для их образования иС1юльзуют в основном операции сложения и вычитания. Например, систе­ ма с одним символом (палочкой) встречалась у многих народов. Для изо­ бражения какого-то числа в этой системе нужно записать количество пало­ чек, равное данному числу. Эта система неэффективна, так как запись числа получается длинной. Другим примером непозиционной системы счисления является римская система, использующая набор следующих символов: (, X, V, L, С, D, М и т. д. В этой системе существует отиюнение от правила независимости значения цифры от положения в 4HCjre. В числах

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

Позиционная система счисления — система, удовлетворяющая равен­ ству (3.2).

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

В гюзициониой системе счисления значение цифры определяется ее положением в числе: один и тот же знак принимает различное значение. Например, в десятичном числе 222 первая цифра справа означает две еди­ ницы, соседняя с ней — два десятка, а левая — две сотни.

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

Основание {базис) q естественной позиционной системе^ счисления — коли­ чество знаков или символов, используемых для изображения числа в данной системе. Возможно бесчисленное множество позиционных систем, так как, приняв за основание любое число, можно образовать новую систему. Напри­ мер, запись числа в шестнадцатеричной системе может проводиться с рюмощью следующих знаков (цифр): О, 1, ..., 9, А, В, С, Д Е, F (вместо А, ..., F можно записать любые другие символы, например, Т, 2,..., 5 ).

64

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

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

65

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

ВЭВМ используют в основном позиционные системы счисления. В дальнейшем для простоты изложения будем употреблять термин «система счисления», имея в виду позиционные системы.

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

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

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

Длина числа (ДЧ) — количество позиций (или разрядов) в записи чис­ ла [14]. В техническом аспекте длина числа интерпретируется как длина разрядной сетки (ДРС).

Для разных систем счисления характерна разная длина разрядной сет­ ки, необходимая для записи одного и того же числа. Например, 96 = 120j =10120з = 1 lOOOOOj. Здесь одно и то же число, записанное в раз­ ных базисах, имеет разную длину разряД1ЮЙ сетки. Чем меньше основание системы, тем больше длина числа.

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

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

Правильный выбор системы счисления — важный практический во­ прос, поскольку от его решения зависят такие технические характеристики проектируемой ЭВМ, как скорость вычислений, объем памяти, сложность

66

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

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

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

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

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

Десятичная система, столь привычная в повседневной >к-'|зни, не явля­ ется наилучшей с точки зрения ее технической реализации в-ЭВМ. Извест­ ные в настоящее время элементы, обладающие десятью устойчивыми со­ стояниями (элементы на основе сегнетокерамики, декатроиы.и др.), имеют невысокую скорость переключения, а следовательно, не мог т обеспечить соответствующее быстродействие машины.

ПодавлягонЕсе большинство компонентов электронных,..схем, приме­ няемых для построения ВМ, — двухпозиционные. С этой то',<и зрения для ЭВМ наиболее подходит двоичная система счисления. Но рг^диоиальио ли использование этой системы с точки зрения затрат оборудо? шия? Для от­ вета на это г вопрос введем !юказатель экономичности систем, >i С — произ­ ведение осЕЮвания системы на длину разрядной сетки, выбранную для за­

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

Вели принять, что каждый разряд числа представлен не i дним элемен­ том с f/ устойчивыми состояниями, а q элементами, каждь'й из которых имеет одно устойчивое состояние, то показатель экономи-'иости укажет ycjTOBHoe KojHi4ecTBo оборудования, которое необходимо')затратить на прелс'тавление чисел в этой системе.

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

67

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

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

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

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

На рис. 3.1 представлена зависимость ве­ личины F от основания системы счисления q. Нижняя точка графика соответствует мини­ муму функции F, определяемому из условия dFjdq = О, что соответствует значению q = е . Следовательно, с точки зрения мини­ мальных затрат условного оборудования, наиболее экономичной является система счисления с основанием, равг{ым е » 2,72 .

Используя (3.10), можно доказать, что троичная система счисления 3KoiioMH4Fiee двоичной. В подавляющем большинстве

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

3.2. Перевод числовой информации нз одной позиционной системы в другую

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

Первым два символа для кодирования информации применил известный философ X V I ! в Ф, Бэкон, который использовал символы 0. I.

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

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

В соогветствин с (3.3) числа в разных системах счисления можно пред­ ставить слелуюншм образом:

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

В общем виде задачу перевода числа из системы счисления с осиоваиисм f/, в сисюму счисления с основанием q^ можно представить как задачу определения коэффициентов Ь, нового ряда, изображающего число в систе­ ме с основанием с/,. Реижть эту задачу можно подбором коэффициентов Ь,. Основная груд1юе1ь при этом заключается в выборе максимальной степени, которая еще содержится в числе А^^ . Все действия должны выполняться по правилам q^ -арифметики, т. е. по правилам исходной системы счисления.

После нахождения максимальной степени основания проверяют «вхо- ж;1ерте» в за/шниое чиcJЮ всех степеней нового основания, меньших макcHMaJH^nor о. Каждая из отмеченных степеней может «входить» в ряд не бо­ лее Ц; I раз, гак как для любого коэффициента ряда накладывается о1 рамичепне:

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

Пример З.Г. Ucpcnecin леся1ич11()е число /1 = 96 в троичную систему счисления

!'СИ! erf и с 46 = 0 3' + 1 3' + 0 - З Ч | - З Ч 2 3 ' + 0 - 3 ' ' = 10120, .

Ответ А. =10120

Рассмотренный в примере 3.1 прием может быть использован только при ручном переводе. Для реализации машинных алгоритмов перевода приме1гя101 следующие методы.

Перевод целых чисел делением на основание q^ новой системы счисления. 1Делое число А в системе с основанием q^ записывается в виде

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

69