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

................................................................

(0, 5, 5) непосредственно предшествует (1, 0, 0).

Следовательно, хотелось бы, чтобы выполнялось соотношение

(0, 0, 5)+1=(0, 1,0).

Однако до сих пор не было представления 1 в Z36. И хотя это соотношение выглядит естественным, мы должны заботится о том, чтобы не использовать ни одного не определенного понятия. Для облегчения описания представим Z36 как А2×A1×A0 и рассмотрим сумму (а2, а1 а0) и (b2, b1, b0). Покомпонентное сложение дает (а2+b2, a1+b1, a0+b0), где сложение осуществляется в Z6, и пока, как кажется, этого достаточно.

Пример.1. Рассмотрим соотношение

(0, 1,3)+ (4, 2, 1) = (4, 3, 4),

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

0, 1, 3

+

4, 2, 1

= 4, 3, 4

Однако

1, 2, 5 и 0, 0, 5

+ +

2, 3, 1 0, 0, 1 (=1?)

=3, 5, 0 =0, 0, 0 (=0?).

В результате операции сложение множество А0 переходит в себя. Однако для того чтобы сумма достаточно больших чисел (таких, как 5+1) могла бы выйти за пределы А0, нам необходимо производить некоторые действия в А1 и также, возможно, в А2. (Это иллюстрируется табл. 1.9).

Таблица 1.9

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

Возьмем любые два числа а и b с Z6. Тогда их сумма (в Z) составляет

6*(а + сb) + (а + sb).

Пример 2. 4 плюс 4 дает 6*(1) + (2) = 8 в Z.

Таблица дает «обычную» сумму двух элементов из Z6, в то время как таблица показывает, когда необходим «переход» в следующее множество Z6, и содержит только нули и единицы. Значения в ограничены, так как если

0 ≤ х <п и 0≤у<п,

то

0≤х≤х + у<х + п<п + п = 2п (и п = 6 в Z6). ,

В действительности можно получить лучшую оценку, поскольку

0≤х≤п-1 и 0≤у≤п-1,

и, следовательно,

0 ≤ х + у≤ 2п-2<2п - 1.

Возвращаясь к сложению (а2, а1, а0) и (b2, b1, b0) и обозначая ответ через (d2, d1, d0), получим -

d0 = a0 +sb0,

x0 = a0 +cb0,

d1=а1+ sb1+ sx0,

x1 = если а1 + cb1 = 1 тогда 1,

иначе (а1+ sb1)+cх0,

d2 = а2 + sb1+ sx1,

x2= если а2 + sb2=1 тогда 1,

иначе (а2 + sb2) + cx1.

Поскольку 0 ≤ аi + bi < 2n — 1 и xi= 0 или xi= 1, то переносимий

результат из aі + bi + xi-1 никогда не может быть больше 1.

Заметим, что в наших определениях числа (0, 0, 0) и (0, 0, 1) в Z36 действуют, как 0 и 1 в новой арифметике. Кроме этого, если х2=5, то результат сложения может оказаться слишком большим для Z36. В этом случае говорят, что состоялось «переполнение». Этот случай мы обсудим более подробно в п.1.4, а до конца этого пункта возможность переполнения будем игнорировать,

Аналогично можно использовать операции *р и *с (таблицы произведения и переноса), заданные в табл. 1.10 для того, чтобы производить умножение над Z36, однако мы не будем этим заниматься.

Таблица 1.10

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

До сих пор мы рассматривали только символы, которые имеют вид положительных чисел. Конечно, с символами 0, 1, 2, ... можно обращаться «естественным» образом, и, следовательно, их можно интерпретировать как неотрицательные числа. Арифметика над Z36 оперирует с числами от 0 = (0, 0, 0) до 215 = (5, 5, 5), которые были получены из последовательности (от 0 до 5) в Z6. Если взять множество {—3, —2, —1, 0, 1, 2} вместо Z6, то получим систему, которая содержит отрицательные числа, но ведет себя странным образом.

Если мы возьмем два множества Z6 и множество {—3, —2, —1, 0, 1, 2}, которое назовем Z—6, и образуем множество Z—6×Z6×Z6, то можно построить арифметику с числами от —108 до 107. На самом деле арифметика является той же самой, за исключением того, что значение 3, 4 и 5 в А2 сейчас интерпретируются як —3, —2, —1 соответственно. Поэтому, например, (-2, 4, 2) исчисляется в Z как

(-2*36) + (4*6)+2 = -46.

Биекция между двумя системами, определенная следующим образом:

3-3,

4-2,

5-1,

х х в других случаях,

может быть применена в любой момент при условии, что результат вычислений не имеет цифр 3, 4 или 5 в А2. Мы выбираем обозначения из соображения удобства, не вводя ограничений на случаи, когда можно применять биекцию или обратное отображение. На этом этапе мы советуем игнорировать любые очевидные противоречия, которые относятся к переполнению А2. Этот случай будет подробно рассмотрено в следующих пунктах на более простом примере. Отметим, что новая система «переходит» от положительных чисел к отрицательным. Например,

(В Z это дает 107 + 1 = -108!)

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

(5,5, 5) + (0, 0, 1) = (0,0,0)

((5, 5, 5) эквивалентно (-1, 5, 5)), а вторая - вид

(а2, а1, а0) + (b2, b2,b0) =(5,5, 5).

Они имеют место тогда и только тогда, когда

a2 + b2 = 5, а1 + b1 = 5, а0 + b0 = 5.

Таким образом, чтобы вычислить обратное по сложению число к (a2, a1, а0), мы должны сначала найти число (b2, b1, b0), которое называют дополнением по 5, и затем прибавить 1=(0, 0, 1). Это даст дополнение до 6. Проиллюстрируем этот процесс на следующем примере.

Пример 3. Найдем обратные элементы к (-3, 4, 1) и (3, 4, 1).

Из 3, 4, 1

получаем 2, 1, 4 (дополнение к 5)

+ 1

2, 1, 5 (дополнение к 6)

Проверим результат 3, 4, 1

+

2, 1, 5

= 0, 0, 0

Поэтому - (-3, 4, 1) = (2, 1, 5).

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

Пример 4. Вычислим (1, 3, 4) -(2, 1, 5).

Берем 2, 1, 5

получаем 3, 4, 0 (дополнение к 5)

результат 3, 4, 1 (дополнение к 6)

прибавим (1, 3, 4) (1, 3, 4)

5, 1, 5=(-1, 1, 5).

Проверяя вычисление над Z, получаем 58—83=—25. Конечно, причиной образования так называемых дополнений к 5 и 6 является тот факт, что мы проводим вычисления над N6 (или Z6).

В общем случае, если вычисление производится в Nm, мы должны использовать дополнение к m—1 и m соответственно.

Надо подчеркнуть, что в вычислениях на ЭВМ мы обычно имеем дело с Znm для некоторых фиксированных m и п и очень редко — с множеством Z. Таким образом, совокупность имеющихся в нашем распоряжении чисел всегда ограничена, и, хотя границы могут быть очень большими, мы не должны забывать о том, что они существуют. Риск тем более велик по той причине, что в записи обычно опускают комы и все нули, которые стоят слева от первой ненулевой цифры за исключением числа (0, 0, 0). Следовательно (1, 3, 4) запишется как 134, (0, 0, 6) как 6 и (0, 0, 0) как 0.

1.4. Двоичная арифметика

Из уже построенных арифметик над Zпm и Zп-m легко выделить основы двоичной арифметики. Существуют две так называемые двоичные арифметики. Первая — это знаковая и модульная форма, которая определена на {—, +}×Zп2, т. е. Zп2 (определенное в предыдущем пункте) с добавленным знаком, который расширяет элементы Zп2. Знак обычно кодируют в бинарной форме: 0 для «+» и 1 для «-».

Вторая арифметика (двоичная арифметика дополнений) — это Zп-2 с элементами {0, 1} во всех п позициях. Этот вид двоичной арифметики используется в большинстве компьютеров. Поэтому ограничим наши рассмотрения Zп-2. Чтобы сделать обсуждение более конкретным, рассмотрим Z5-2 , элементы которого лежат в пределах от 10 000 (=-16) до 01 111 (=+15) (т. е. содержит 32=25 разных чисел). Число —1 представляется в Z5-2 как 11 111. Поэтому легко найти двоичное дополнение. Для этого надо слегка изменить все двоичные цифры, которые називаоть битами, чтобы получить дополнение к 1, а затем прибавить 1, чтобы получить дополнение к 2.