Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 18
Текст из файла (страница 18)
На самом деле (как будет видно из последующих глав) наиболее общеизвестная алгебра может быть построена из относительно небольшого набора основных правил. Сейчас мы продемонстрируем, как из элементарных предположений можно извлечь некоторые простые следствия; большинство примеров дано в виде упражнений. Пример 6.6. Пусть 9 — операция на множестве А и существует единица по отношению к ®, Тогда единичный элемепт единствен. Доказательство. Предполонгнм, что х и р — едв.
пицы по отношению к ®, т. е. х9а=а9х=а, р9а=а9у=а для всех ааиА. Тогда х=х®у, так как у — единица, и х9р р, поскольку х — единица. Следовательно, х у. г" П р и и е р 6.7. Пусть 9 — ассоциативная операция на мншкестве А и е — единица по отношению к 9. Тогда если хюА и х имеет обратный, то обратный элемент единствен по отношению к 9. Доказательство. Допустим, что х' и х" обратные элементы к х, так что х®х' = х'®х е и х®х = х" ®х=е. Тогда х' х'9е х'®(х9х")=(х'®х)®х" е9х" = х'. Х У п р а ж н е к п е 3.6.
1. Рассмотреть указанные ниже аопределенияз 9. Решить, правильно или нет каждое из иих определяет бинарную операцию, н если так, то является ли операция коммутативной. Найти, если это возможно, единицу з обратный элемент к х. Предполагаются выполненными обычные свойства арифметики: 112 а) х 9 у = х — у на М; б) х®у = (хау) — 1 на 2; в) х ® у шах(х, у) на Х; г) х® у — Уха + у' на (х: 0(х,х~ К); д) х(9 у х~у на (х: 0(х„хан К).
2. Определим операцию у на множестве (а, Ь, е), как указано ниже. Проверить, что у ассоциативна и коммутативна и найти единичный элемент. а Ь с Ь с а а Ь а а а Ь 3. Предполагая обычные свойства операций +, —, а и ! на К, доказать, что операция ф, определенная на ($, а ( следующим образом: аФЬ вЂ” —, (ааь) + 1 а+Ь 1 ассоциативна. Обосновать ответ, У к а з а н и е: не следует особо обращать внимание на область определения. 4.
Пусть Š— ассоциативная операция на множестве А с единицей е такая, что каждый элемент а ш А обратны и обратный обозначается через а'. Показать, что (а ® Ь)' = Ь' ® а'. 5. Покааать, что если ®- ассоциативная операция на множества А с единицей е такая, что а®а — е для каждого аж А, то ® коммутативна. 6. Пусть ® — ассоциативная операция на множестве А такая, что для любых а, Ь |и А, если а®Ь = ЬЕ а, то а ° й. Показать, что каждый элемент А идемпотентен по отношению к Е. Что можно сказать про Е, еслк операция имеет единицуг 8 д кт, г. вава ГЛАВА 4 ОСНОВНЫЕ ПОНЯТИЯ АРИФМЕТИКИ Итак, мы определили операции и описали некоторые их свойства.
Теперь посмотрим, что можно сделать с совокупностью операций, заданных на множестве. Множество с заданными па нем операциями называют алгебраической структурой. Некоторые пз наиболее часто встречающихся алгебраических структур будут рассмотрены позднее. Прежде чем приступить к их рассмотрению, посмотрим на арифметику с неформальной точки зрения.
В большинстве случаев мы будем опускать формальные определения, делая ударения ка чследствия из правил», даже в тех случаях, когда это приводит к необычным способам использования известных символов, которые обычно попользуются для представления десятичных чисел. й 1. «Малая» конечная арифметика Арифметику можно рассматривать как множество с двумя операциями, действующими подобно сложению и умножению. Ее мол<но изучать многимп способами. Чтобы уяснить требования арифметической системы, примем конструктивное приближение и рассмотрим целые числа (О, 1, 2, ...) просто как символы.
В дальнейшем будем рассматривать только конечную арифметику, в которой используется лишь конечное множество чисел; вначале это множество будет небольшим. Подразумевается, что если А г1, то требуется т различных символов, при атом никакие комбинации символов не разрешаются. Если используются только десятичные числа, то и < 10. Поскольку все множества данного размера бпектпвны, то можно рассматривать только множества М . Для большей наглядности рассмотрим множество Хв. Для этого необходимо построить таблицы умнон'ения и сложения.
Множество Хз достаточно велико для того, чтобы изучать свойства основной структуры, Можно цо- 114 думать, что для этой цели более уместным является множество (Ч», однако это не так. Начнем со сложения. Операция сложения ил«ест единицу, которая обычно обозначается символом О, однако ОФ М». Поэтому будем использовать множество Х«- (О, 1, 2, 3, 4, 51, которое более удобно. Очевидно, что Х«(»«.
Поэтому можно работать с Х«, пе теряя никаких свойств. Таким образом, к настоящему моменту мы имеем соответствующую табл. 4А. Табзпиа 4,1 О 1 2 3 4 5 О 1 2 3 4 5 1 2 3 5 Так как операция коммутатпвпа, то таблица должна быть симметричной. Труднее обстоит дело с ассоциа- тивностью. Если мы хотим, чтобы операция была ассо- циативной, и требуем, как обычно, существовапия обрат- ных зле»щагов по сложению, то любой элемент должен входить ровдо один раз в каждую строку и каждый стол- бец.
Поясним это высказынапие, Если а+ Ь = а+ с, то а+(а+ Ь) = — а+(а+ с), ( — а+а)+ Ь =( — а+а)+с, О+Ь=О+с, Ь с. Рассмотрим теперь операцию, определенную в табл. 4.2. Из трех во»мол постой для операции сложения иа Х«только С' удовлетворяет всем условиям, что выглядит несколько необычно. Операция А ие коммутативиа, а в В иарушои кро герай «едипствеппости результата». Как н,"е построить соответствующую операцию, удовлетворяющую всем обсуи«даемым выше свойствам7 Иа дальнейшего изложения будет видно, что наиболее трудно обеспечить выиолпение свойства ассоциативности. В предложепиой ниже процедуре мы используем ассо- 8« 115 циативность как основной шаг построения, и, следовательно, это свойство будет выполняться автоматически.
Шаг 1. Число 0 является единицей для операции сложения. Поэтому получаем табл. 4.3. Таблица 42 О 1 2 3 4 5 С О 1 2 3 4 5 А О 1 2 3 4 5 8 О 1 2 3 4 5 О 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 О 1 2 3 4 5 1 5 3 4 2 О 2 3 1 5 О 4 3 4 5 О 1 2 4 2 О 1 5 3 5 О 4 2 3 1 О 1 2 3 4 5 О 1 2 О 4 5 3 1 2 О 1 5 3 4 2 3 5 4 О 2 1 3 4 3 5 1 О 2 4 5 4 3 2 1 О 5 Таблица 4.3 О 1 2 3 4 5 3 О 5 2 Так как операция должна быть коммутативпой, запол- ним соответствующий столбец табл.
4.4. Шаз 3. Заполним другие клетки таблицы, используя ассоциативность, Проследим подробно за каждой де- талью: 2+ 2 2+(1+ 4) =(2+ 1)+ 4 О+ 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. 115 Шаа 2. Определим следующую строку таблицы, удовлетворяющую условию «единственности результата».
Чтобы подчеркнуть используемую технику, специально выберем результат, который отличается от привычного. Возьмем + ~ О 1 2 3 4 5 Здесь мы использовали соотношения 2+1=0 и О+х х. Далее 3+3 (1+1)+3 1+(1+3) 1+5 4 и т. д. Таким образом, на основе значений 1+х получаем таблицу для операции + (табл. 4.5).
Таблица 44 Таблица 45 0 1 2 3 4 5 + 0 1 2 3 4 5 О 1 2 3 4 5 1 3 О 5 2 4 2 О 3 5 4 2 5 4 0 1 2 3 4 5 1 3 О 5 2 4 2 О 4 1 5 3 3 5 1 4 О 2 4 2 5 0 3 1 5 4 3 2 1 О При выполнении процесса надо учитывать дополнительные ограничения ва шаге 2. Значения в нулевой строке должны выбираться так, чтобы ояи «продолясалиа все Х«. Например, начиная с 1 (как мы делали), получаем 1+1 3, 3+1 5, 5+1 — 4, 4+1 2, 2+1=0, О+1 1.
Следовательно, прибавляя только 1, можно получить все Е«. Перейдем теперь к умножению. Сначала заметим, что единипа для операпии умножения долясна отличаться от нуля. В противном случае для любых х и у мы имели бы х=О«х-хаО, у=О+у-у+О, поэтому х «р х а (О+ р) =(х а 0)+(х а у) х+(х а у), а аначит, х О. Поэтому 0 не является единицей для умножения. На самом деле вам требуется число, которое будет порождать Ха. Следовательно, мы могли бы определить аналогичным образом операцию умножения на основе частичной табл. 4.6. Однако э этом случае мы нв должны настаивать па выполнении критерия «единственности результата». (В обычной арифметике пе существует целого числа, которое при умножении на 2 давало бы 1! Поэтому в конечном множестве могут быть повторения.) 117 Ва>есто того чтобы повторлть процедуру построения таблицы для умножения, вернемся к проблеме связи двух операций — дпстрибутнвности умнов'ения относительно сложения.
Эта проблема связана с ассоциативностью. Расс»>стрип (уже построенную) операци>о сложения. Таблаца 46 Таблица 47 О (>)2)3)4)5 ° О 1 2 3 4 5 О О О О О О О 1 2 3 4 5 О 2 1 4 3 5 О 3 4 4 3 О О 4 3 3 4 О О 5 5 О О 5 О О 1 2 3 4 5 2 3 5 Заметим, что 1+1 3. Поэтому пз предположения ди- стрибутивности получаем, что 3 * 0 =(1+ 1)» 0 (1 «0)+(1 ° 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» б (1» 5)+(1» 5) 3+5 О. 1 ) 1 2 3 4 5 7 Недостающим элементом должен быть О, поскольку б Ф ФЕ», и 0 является единственным элементом Еа, которо- $18 Теперь 3+3=4, 3+1 5, 1+4=2 и 1+2=0. Действуя как и ранее, получаем следующую операцию (табл. 4.7).
Следовательно, начинан с почти произвольного выбора строки в таблице, не содержащей 1 по сложению, и накладывая ряд простых ограничений, мы приходим к приемлемой арифметической системе. Теперь достаточно установить, что полученная система не находитсн в противоречии с высказанными ранее соображенннми, т. е. что 1+ 1 действительно существует, Короче говорл, если в нормальной (бесконечной) арифметике а+5 с и с>и >в 2», то хотелось бы, чтобы и в пашей арпфметпке ответ был с. Следовательно, мы пришли к выбору + ( О 1 2 3 4 5 Таблица 48 + ~ 0 1 2 3 4 5 « 0 1 2 3 3 4 5 0 4 5 0 1 5 0 1 2 0 1 " 3 1 2 3 4 2 3 4 О 0 0 0 О О 0 1 2 3 0 2 4 о 2 0 3 0 3 О 3 0 4 2 О 4 2 О 5 4 3 2 1 0 1 2 1 2 3 2 3 4 3 4 5 4 5 0 5 0 1 У п р а ж н е н и е 4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
