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

Для большей наглядности рассмотрим множество N6. Для этого необходимо построить таблицы умножения и сложения. Множество N6 достаточно велико для того, чтобы изучать свойства основной структуры. Можно подумать, что для этой цели более уместным является множество N2, однако это не так. Начнем со сложения.

Операция сложения имеет единицу, которая обычно обозначается символом 0, однако 0 N6. Поэтому будем использовать множество Z6 = {0, 1, 2, 3, 4, 5}, которое более удобно. Очевидно, что Z6~N6. Поэтому можно работать с Z6, не теряя никаких свойств. Таким образом, мы можем построить соответствующую табл. 1.1.

Таблица 1.1

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

Так как операция коммутативна, то таблица должна быть симметричной. Труднее отстоит дело с ассоциативностью. Если мы хотим, чтобы операция была ассоциативной, и требуем, как обычно, существование обратных элементов по сложению, то любой элемент должен входить ровно один раз в каждую строку и каждый столбец. Объясним это высказывание.

Если а + b = а + с, то

- а+(а + b)=- а + (а + с),

(-а + а)+ b = ( -а + а) + c,

0 + b = 0 + c,

b=с.

Рассмотрим теперь операцию, определенную в табл. 1.2.

Таблица. 1.2

A	0 0 1 2 3 4 5 B	0 0 1 2 3 4 5 C	0 0 1 2 3 4 5
0 1 2 3 4 5	0 1 2 3 4 5 0 1 2 0 4 5 3 1 2 0 1 5 3 4 2 3 5 4 0 2 1 3 4 3 5 1 0 2 4 5 4 3 2 1 0 5	0 1 2 3 4 5 0 1 1 2 3 4 5 1 2 2 2 3 4 5 2 3 3 3 3 4 5 3 4 4 4 4 4 5 4 5 5 5 5 5 5 5	0 1 2 3 4 5 1 5 3 4 2 0 2 3 1 5 0 4 3 4 5 0 1 2 4 2 0 1 5 3 5 0 4 2 3 1

Из трех возможностей для операции сложения на Z6 только C удовлетворяет всем условиям, что выглядит несколько необычно. Операция А не коммутативна, а в В нарушен критерий «едининственности результата». Как же построить соответствующую операцию, удовлетворяющую всем обсуждаемым выше свойствам? Из дальнейшего изложения будет видно, что наиболее трудно обеспечить выполнение свойства ассоциативности. В предложенной ниже процедуре мы используем ассоциативность как основной шаг построения, и, следовательно, это свойство будет выполняться автоматически.

Шаг 1. Число 0 является единицей для операции сложения. Поэтому получаем табл. 1.3.

Таблица 1.3

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

Шаг 2. Определим следующую строку таблицы, удовлетворяющую условию «единственности результата». Чтобы подчеркнуть используемую технику, специально выберем результат, который отличается от привычного. Возьмем

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

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

Таблица 1.4

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

Шаг 3. Заполним другие клетки таблицы, используя ассоциативность. Проследим подробно за каждой деталью:

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

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

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

2 + 5=(2 + 1)+3 = 0 + 3 = 3.

Здесь мы использовали соотношение 2+1 = 0 и 0 + х= х. Далее

3 + 3=(1 + 1) + 3 = 1 + (1 + 3)=1 + 5 = 4 и т. д.

Таким образом, на основе значений 1+х получаем таблицу для операции + (табл. 1.5).

Таблица 1.5

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

При выполнении процесса надо учитывать дополнительные ограничения на шаге 2. Значения в нулевой строке должны выбираться так, чтобы они «продолжали» все Z6. Например, начиная с 1 (как мы делали), получаем

1 + 1 = 3, 3+1 = 5, 5+1 = 4, 4+1 = 2, 2 + 1 = 0, 0+1 = 1.

Следовательно, прибавляя только 1, можно получить все Z6.

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

х = 0*х = х*0, у = 0 + у = у + 0,

поэтому

х*у =х*(0 + у) = (х* 0) + (х* у) = х + (х*у),

а значит, х= 0. Поэтому 0 не является единицей для умножения.

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

Таблица 1.6

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

Однако в этом случае мы не должны тредовать выполнения критерия «единственности результата». (В обычной арифметике не существует целого числа, которое при умножении на 2 давало бы 1! Поэтому в конечном множестве могут быть повторения.)

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

Заметим, что 1+1= 3. Поэтому из предположения дистрибутивности получаем, что

3*0-(1 + 1)*0=(1*0) + (1*0)=0 + 0=0,

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

3*3 = (1*3) + (1*3)=3 + 3 = 4,

3*4 = (1*4) + (1*4)=4 + 4=3,

3*5=(1*5) + (1*5)=5 + 5 = 0.

Теперь 3 + 3 = 4, 3+1 = 5, 1 + 4 = 2 и 1 + 2 = 0. Действуя как и ранее, получаем следующую операцию (табл. 1.7).

Т а б л и ц я 1.7

*	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 1 4 3 5 0 3 4 4 3 0 0 4 3 3 4 0 0 5 5 0 0 5

Следовательно, начиная с почти произвольного выбора строки в таблице, не содержащей 1 по сложению, и накладывая ряд простых ограничений, мы приходим к приемлемой арифметической системе. Теперь достаточно установить, что полученная система не находится в противоречии с высказанными ранее соображениями, т. е., что 1+1 действительно существует. Короче говоря, если в нормальной (бесконечной) арифметике а+b=c и с Z6, то хотелось бы, чтобы и в нашей арифметике ответ был с. Следовательно, мы пришли к выбору

+	0 0 1 2 3 4 5
1	1 2 3 4 5 ?

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

Таблица 1.8

+	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 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

Она определяет так называемую арифметику по модулю (основанию) 6. (Эта арифметика работает точно так же, как и обычная целочисленная арифметика, за исключением того, что все целые числа заменяют на остатки от деления их на 6.)

1.3. «Большая» конечная арифметика

Мы уже построили арифметику для Z6. Возникает вопрос: как можно расширить эту систему, чтобы иметь возможность считать после 5? Для этого достаточно иметь множество п-значных чисел (наборов из п элементов из Z6) с арифметикой над Z6. Чтобы проиллюстрировать это, рассмотрим упорядоченную тройку из Z6, т. е. элементы множества Z6×Z6×Z6. Если Z6 упорядочено обычным способом, т. е. 0<1<2<3<4<5, тогда определим порядок на Z6×Z6×Z6 по правилу

(a, b,c)< (x, y, z),

если а<х или а = х и b <y или а= х, b=у и c< z.

В этом случае элементы Z36 = Z6×Z6×Z6 будут упорядочены следующим образом:

(0,0,0), (0,0, 1), .... (0,0, 5),

(0,1,0),..., (0,1,5),

………………………………

(0,5,0),......., (0,5,5),

(1,0,0),..., (1,0,5),

(5,5,0),..., (5,5,5).

Таким образом, существует 63 = 216 различных троек. Поэтому нужно уметь делать арифметические вычисления над Z36 в пределах от 0 до 215. В приведенном выше упорядочивании элементов из Z36

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

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