Книга написана двумя американскими учеными, один из которых— Гаррет Биркгоф — известен широтой своих научных интересов, простирающихся от абстрактной алгебры до гидродинамики, а другой — Томас Барти — является директором вычислительной лаборатории Гарвардского университета. На русском языке выходила «Теория структур» Биркгофа, два издания его знаменитой «Гидродинамики», а также совместная с Э. Сарантонелло монография по теории струй.
Книга восполняет существенный пробел в нашей учебной литературе. В отличие от других математических дисциплин, по которым имеются превосходные руководства, специально ориентированные на приложения, по алгебре таких книг до сих пор не было. Это связано с тем, что алгебра (за исключением теории уравнений) приобрела черты прикладной науки лишь за последние десятилетия.
В книге излагаются те идеи и методы современной алгебры, которые нашли широкие применения в таких областях, как теория автоматов и вычислительных машин, передача сообщений и кодирование, языки программирования и математическая лингвистика. Она будет полезна тем, кто работает в этих областях, а также математикам всех специальностей, занимающимся прикладными вопросами.
Особый интерес она представляет для студентов университетов и высших технических учебных заведений, связанных с прикладной математикой.
ПРЕДИСЛОВИЕ
Термин «современная алгебра» принято относить к теории таких алгебраических систем (групп, колец, булевых алгебр и т. д.), элементы которых, вообще говоря, не являются числами, Напротив, «классическая» алгебра занимается в основном алгебраическими уравнениями или системами уравнений, в которых символы обозначают вещественные или комплексные числа. За последние сорок лет «современная» алгебра постепенно вытеснила «классическую» в программах американских университетов. Прошедшее двадцатилетие было отмечено бурным развитием новых отраслей техники. К ним относятся электронные вычислительные машины, средства передачи, хранения и переработки информации, системы обнаружения типа радара и сонара. Работа в каждой из этих отраслей требует довольно глубокого знания современной алгебры. Изучение последней, таким образом,стало необходимым для специалистов по прикладной математике, инженеров и всех исследователей, которые занимаются перечисленными вопросами и пользуются ЭВМ.
В этой книге мы попытались изложить те идеи и методы современной алгебры, которые оказались наиболее полезными в этих областях. Хотя в тексте неизбежно некоторое разделение между математическими принципами и их приложениями, мы старались добиться единства в изложении фундаментальных идей и основанных на них алгоритмов.
Книга начинается с обсуждения и иллюстрации примерами понятий множества, функции, математической индукции, бинарного отношения и графа. Рассматриваются также булевы алгебры, моноиды, морфизмы и другие основные алгебраические понятия. Все это занимает первые две главы.
В следующей, третьей главе вводятся понятия автомата и машины Тьюринга. Описаны также способы представления этих объектов и методика уменьшения числа состояний при синтезе конечных автоматов. Глава 4 вводит читателя в синтаксис и семантику языка программирования АЛГОЛ.
ОГЛАВЛЕНИЕ
Предисловие.................. „ . . "....... 5
Глава 1. Множества и функции................... 9
1.1. Множества и подмножества ............... 9
1.2. Булевы алгебры..................... 11
.3. Функции........................ 16
.4. Обратные функции ................... 20
.5. Функции из S в S ................... 22
.6. Суммы, произведения и степени............. 25,
.7. Аксиомы Пеано..................... 29
1.8. Финитная индукция................... 31
*1.9. Принцип Дирихле; алгоритм деления........... 35
Глава 2. Бинарные отношения и графы............... 39
2.1. Введение........................ 39
2.2. Матрицы отношений................... 41
2.3. Алгебра отношений ................... 42
2.4. Частичное упорядочение................. 46
2.5. Разбиения и отношения эквивалентности......... 51
2.6. Классы вычетов и морфизм ............... 54
2.7. Циклические унарные алгебры.............. 58
2.8. Ориентированные графы................. 61
2.9. Графы .......'.................. 65
*2.10. Ориентированные графы, II............... 67
Глава 3. Конечные автоматы..................... 73
3.1. Введение........................ 73
3.2. Двоичные элементы и состояния........•..... 74
3.3. Конечные автоматы................... 75
3.4. Покрытие и эквивалентность............... 80
3.5. Эквивалентные состояния..............'. . 84
3.6. Процедура минимизации................. 87
*3.7. Машины Тьюринга.................... 93
3.8. Неполностью описанные автоматы . ,.......... 98
*3.9. Отношения между состояниями и процедура минимизации . 100
Глава 4. Языки программирования ................. 110
4.1. Введение........................ ПО
4.2. Арифметические выражения............... 114
4.3. Идентификаторы и операторы присваивания ....... 117
4.4. Массивы........................ 120
4.5. Операторы цикла.................... 123
398 ОГЛАВЛЕНИЕ
4.6. Блочные структуры в АЛГОЛе............. 126
4.7. Грамматика АЛГОЛа.................. 128
4.8. Вычисление арифметических выражений . . •...... 133
*4.9. Трансляция арифметических выражений ......... 136
Глава 5. Булевы алгебры...................... 139
5.1. Введение . . . . .................... 139
5.2. Порядок ........................ 143
5.3. Булевы многочлены................... 146
5.4. Диаграммы вентильных схем............... 150
5.5. Связи с логикой..................... 154
5.6. Логические возможности АЛГОЛа ............ 155
5.7. Приложения к булевым алгебрам ........'. . . . 159
5.8. Булевы подалгебры................... 162
5.9. Дизъюнктивная нормальная форма............ 164
*5.10. Прямые произведения и морфизмы............ 167
Глава 6. Оптимизация и проектирование вычислительных машин ... 170
6.1. Введение........................ 170
6.2. Оптимизация...................... 170
6.3. Оптимизация с помощью вычислительной машины .... 174
6.4. Логическое проектирование............... 179
6.5. Элементы НЕ-И и НЕ-ИЛИ ............ . . . 184
6.6. Проблема минимизации................. 186
6.7. Перечисление простых импликантов ........... 189
6.8. Союз.......................... 195
6.9. Триггеры........................ 197
6.10. Проектирование последовательностных машин....... 198
Глава 7. Моноиды и группы.................... 204
7.1. Бинарные алгебры................... 204
7.2. Циклические моноиды; подмоноиды............ 206
7.3. Группы.......................... 209
7.4. Морфизмы; прямые произведения............ 213
7.5. Примеры групп; аксиомы................ 216
7.6. Подгруппы....................... 219
7.7. Абелевы группы..................... 223
7.8. Действия групп на множествах ............. 225
7.9. Перестановки...................... 227
7.10. Теорема Лагранжа ................... 229
7.11. Нормальные подгруппы......... ........ 231
Глава 8. Двоичные групповые коды . ................ 236
8.1. Введение........................ 236
8.2. Кодирование и декодирование.............. 238
8.3. Блочные коды ..................... 242
8.4. Методика матричного кодирования ............ 245
8.5. Групповые коды .................... 247
8.6. Таблицы декодирования................. 248
8.7. Коды Хэмминга..................... 253
Глава 9. Решетки......................... 258
9.1. Решетки и частично упорядоченные множества...... 258
9.2. Решетки как частично упорядоченные множества..... 260
9.3. Решетки и полурешетки ................ . 264
9.4. Подрешетки и прямые произведения............ 265
9.5. Дистрибутивные решетки................ 268
ОГЛАВЛЕНИЕ 399
I '.
9.6. Модулярные и геометрические решетки .......... 271
*9.7. Булевы решетки.................... 275
•9.8. Морфизмы и идеалы................... 276
' t *9.§. Конечные булевы алгебры................ 277
, Глава 10. Кольца и идеалы..................... 281
10.1. Введение........................ 281
10.2. Области целостности и поля............... 283
*10.3. Поля частных..................... . 287
10.4. Подкольца ........................ 289
10.5. Морфизмы колец................... . 292
' 10.6. Прямые суммы..................... 293
10.7. Идеалы и факторкольца................. 296
10.8. Делимость ....................... 300
10.9. Евклидовы области .........'.......... 301
*10.10. Области с однозначным разложением........... 304
•10.11. Простые и максимальные идеалы ............ 307
*10.12. Гауссов метод исключения................ 308
" Глава 11. Полиномиальные кольца и полиномиальные коды ..... 311
11.1. Кольцо /?•[*]...................... 311
11.2. Полиномиальные кольца над полями........... 314
11.3. Полиномиальные коды.................. 316
11.4. Преимущества полиномиальных кодов.......... 318
11.5. Регистры сдвига .................... 320
11.6. Теорема об однозначном разложении для многочленов . . 322 . 11.7. Комплексные корни из единицы............. 323
*11.8. Полиномиальные функции . . . ;............ 325
•11.9^ Формальные производные................ 327
Глава 12. Конечные поля.......1............. . 329
12.1. Расширения полей.................... 329
12.2. Простые расширения .................. 332
•12.3. Вычисления в R[x]/(m(x))................ 333
12.4. Теорема существования................. 336
12.5. Конечные поля..................... 337
12.6. Вычисления в Of (2я).................. 339
12.7. Коды Боуза —Чоудхури — Хоккенгема.......... 340
12.8. Свойства наименьшего расстояния............ 342
•12.9. Поля разложения.................... 344
•12.10. Изоморфизм полей разложений '............. 346
Глава 13. Рекуррентные последовательности............. 349
13.1. Радар и системы связи ...--:............. 349
13.2. Разностные коды.................... 350
13.3. Разностные уравнения.................. 353
13.4. Формальные степенные ряды............... 355
13.5. Приложение к разностным кодам............ 358
13.6. Рекуррентные последовательности ............ 359
13.7. Периоды последовательностей, связанных с взаимно простыми многочленами ;..................* . 361
13.8. Последовательности с максимальным периодом...... 363
13.9. Автокорреляционная функция.............. 364
•13.10. Теорема об автокорреляции ............... 366
•13.11. Формальные ряды Лорана'................ 367
Глава 14. Вычислимость.......*.............. . 369
400 ОГЛАВЛЕНИЕ
14.1. Арифметика кардинальных чисел ............ 369
14.2. Счетная бесконечность.................. 371
14.3. Мощность континуума.................. 372
14.4. Вычислимость по Тьюрингу............... 376
14.5. Вычислимость по Тьюрингу и практическая вычислимость 377
14.6. Математическая лингвистика............... 378
14.7. Автоматные грамматики................. 381,
14.8. Синтаксис; магазинные акцепторы............ 384
*14.9. Рекурсивные функции.................. 387
"14.10. Невычислимость и проблемы тождества слов....... 388
/
Предметный указатель.................. 391
Цена: 300руб.
