Дискретно-непрерывная математика (стр. 6 )

Пример 1.

— (01 011)

10 100

+

1

10 101

(=-24 + 22 + 20 = - ll);

-(10110)

+01 001

1

01 010

(=23+ 21= 10).

Очевидно, что могут возникнуть проблемы, вызванные ограниченностью чисел. Мы не можем их избежать, однако следует знать, когда возможна «ошибка». Форма дополнения делает проверку условия переполнения относительно легкой, использующей только значение старшего значащего бита. (В Z5-2 это бит с номером 24.) Этот бит обозначает знак представляемого числа и называется знаковым битом или знаковым разрядом. Перед тем как проверить, какое значение имеет знаковый бит, напомним, что прибавление 1 к максимальному положительному числу в Zn-m дает максимальное отрицательное число (наибольшее отрицательное число — это отрицательное число, которое отстоит дальше всего от нуля). Другими словами, числа повторяются циклическим образом. В Z5-2 мы имеем ситуацию, которая изображена на рис. 1.3.

Рис. 1.3.

Что же произойдет, если мы сложим два числа х и у, где

— а ≤х < а и — а≤у<а (в Z5-2, a = 16)?

Сумма х + у будет ограничена:

2а ≤ х + у ≤ 2а - 2 < 2а - 1.

Само по себе это неравенство ничего не дает. Поэтому мы рассмотрим три случая;

(I) если — а≤х<0 и — а≤у<0

тогда —2а ≤ х + у < 0;

(II) если 0≤х<а и 0≤у<а

тогда 0≤х + у ≤ 2а - 2 < 2а – l;

(III) если — а≤х<0 и 0≤ у <а

тогда -а ≤ х + у < а.

Вначале заметим, что результат в случае (III) находится в требуемых границах и, следовательно, всегда правильный. Чтобы понять, как могут возникать ошибки в случаях (I) и (П), необходимо вспомнить, что если z Z и —2а≤z<-а, то число z представимо в конечной арифметике числом z', где z'=z+2а и 0≤z'<а. Аналогично, если a≤z<2a— 1, то z представимо z", где z"=z — 2а и —a≤z"<0. Следовательно, ответ будет неправильный, если он в случае (I) положительный или в случае (II) отрицательный.

Чтобы объяснить эти заключения в терминах свойств знакового разряда, рассмотрим различные возможности сложения двух чисел:

а) оба чисела отрицательны;

б) оба чисела положительны;

в) числа имеют различные знаки.

Анализируя эти случаи, видим, что переполнение (ошибка переполнения) встречается тогда и только тогда, когда существует перенос в знаковый разряд или перенос из знакового разряда, но не оба вместе. Для иллюстрации этого рассмотрим несколько примеров в Z5-2. Попытаемся сопоставить эти примеры со случаями (I)-(III) и а) - в), рассмотренными выше.

Пример 2. Напомним, что вычисление проводятся в Z5-2:

Вернемся теперь к умножению и делению. Сначала рассмотрим умножение. Напомним, что в Z (или, более точно, в Zп10 для достаточно большого п) умножение на 10 можно получить «сдвигом» всех цифр на одну позицию влево и записью в 0-й позиции цифры 0. (В Zпm умножение на m также всегда можно осуществить сдвигом влево.)

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

Пример 3. (Вычисление проводятся в Z5-2 .)

0 0 0 11 (3) 111 1 0 (-2)

0 0 110 (*2) 111 0 0 (*2)

0 1 100 (*2=12) 110 0 0 (*2 = -8)

0 0 1 0 1 (5)

0 1 0 1 0 (*2)

1 0 1 0 0 (*2)

0 1 0 0 0 (*2 = 8).

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

Пример 4. (Вычисление проводятся в Z5-2).

3*5 = 3*22 + 3*20(20=1)

(-5)*3 = (-5)*21+ (-5)*20.

Поэтому

0 0 0 1 1 1 1 0 1 1

+ +

0 1 1 0 0 1 0 1 1 0

0 1 1 1 1 1 1 0 0 0 1 .

Точно так же, как умножение производилось сдвигами влево деление на положительные степени числа 2 осуществляется сдвигом вправо. (Деление на другие целые числа должно получаться путем сведения к вычитанию степеней числа 2. Этот процесс мы обсуждать не будем.) Однако специального рассмотрения требуют отрицательные числа. Отметим также, что в общем случае ожидаемый результат (т. е. арифметически ожидаемый результат в R) будет не целым, а дробным.

Пример 5. Попытаемся в Z5-2 вычислить 12/4, (—6)/2 и 7/4 сдвигом на 2, 1 и 2 позиции соответственно. Имеем

0 1 1 0 0 (12) 1 1 0 1 0 (-6),

0 0 0 1 1| 0 0 (3 = 12/4) 0 1 1 0 1|0 (13 ≠-6/2)

0 0 1 1 1 | (7)

0 0 0 0 1 | 1 1 (1≈7/4).

Сдвиг на одну позицию вправо автоматически переводит любое отрицательное число к положительному. В Z5-2 сдвиг переводит —16 к +8. Чтобы исправить это, следует отнять от результата число 16, что даст -8 (т. е. -16/2). То же самое можно получить, устанавливая знаковый разряд равным 1. Следовательно, правильный результат достигается использованием знакового разряда, значение которого равно 0 или 1 (в зависимости от знака числа), для того чтобы заполнить «пропуска», создаваемые в результате сдвига вправо.

Следовательно, (-6)/2 приводит к

11101 = -3.

Действие битов (со значением 1), «выпадающих» из числа в результате сдвига вправо, должно усекать результат. Поэтому 7/4 дает 1. Существует общепринятая практика округлять число (вверх независимо от знака) прибавлением к числу утерянного последнего бита. Это отвечает обычному арифметическому правилу округления, поскольку 1 в первом бите остатка представляет собой 0.5. Следовательно, 7/4 дает 2.

1.5. Логическая арифметика

Строго говоря, булева арифметика оперирует на множествах Z2 и Zп2 и, следовательно, включает только числа 0 и 1. Для того чтобы подчеркнуть такую структуру, начнем с рассмотрения логической арифметики на «относительно большом» множестве Z5. Она дает основу многозначной логики. Отсюда легко получить более простой случай Z2. Возьмем множество Z5 = (0, 1, 2, 3, 4} и операции и , которые определены в табл. 1.11.

Таблица 1.11

	0 0 1 2 3 4		0 0 1 2 3 4
0 1 2 3 4	0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4	0 1 2 3 4	0 0 0 0 0 0 1 1 1 1 0 1 2 2 2 0 1 2 3 3 0 1 2 3 4

Упорядочивая Z5 обычным образом (порядок индуцируется Z и R), видим, что

а b = max {а, b},

a b = min {a, b}.

Обе операции коммутативны и ассоциативны, 0 является единицей для , а 4 является единицей для ; дистрибутивна по отношению к , но не наоборот.

Пример 1. Возьмем множество Zт с естественным порядком элементов. Введем операции и . Рассмотрим шесть возможных случаев упорядочивания трех произвольных элементов а, b, с с Zm:

(I) a≤b≤c;

(II) a≤c≤b;

(III) b≤a≤c;

(IV) b≤c≤a;

(V) c≤a≤b;

(VI) c≤b≤a.

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

a ≤ b тогда и только тогда, когда а b= b.

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

a (b c)= (а b) (а с).

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

(I) a (b c) = a c = a,