Глава 1 Введение в конечную алгебру и логику
1.1. Исходные понятия и определения
Множество и соответствие (3). Способы задания соответствий на конечных множествах (8). Отношения (10). Операции (13). Задание отношений и операций на конечных множествах (13).
1.2.Свойства алгебраических операций
Алгебры как множества с заданными операциями (17). Свойства унарных операций (23). Свойства бинарных операций (24). Взаимные свойства операций разной арности (25). Изоморфизм, изотопия, изотонность (26).
1.3.Классификация унарных алгебр
Алгебры с одной унарной операцией (36). Метод построения графов для унарных алгебр (36). Конечные моногенные алгебры (37). Орбиты (38). Представление унарных операций на конечных множествах {подстановки и перестановку (40). Метод образования сложной функции (44). Степенные алгебры, порождаемые подстановками и перестановками (44). Классификация степенных алгебр (46).
1.4.Классификация алгебр с одной бинарной операцией
Группоиды, полугруппы, квазигруппы, группы (48). Примеры групп (52). Классификация- группоидов (53). Таблица Кэли для группоида (54). Тест на ассоциативность (56). Изотопия группоидов (57). Полурешетки (57). Модулярные бинарные операции (59). Прямая сумма (прямое произведение) группоидов (60). Циклические и примарные группы (61). Полугруппа подстановок (преобразований) и группа перестановок (63). Системы образующих конечной группы (66).
1.5. Классификация дистрибутивных алгебр с парой бинарных операций
Кольца, тела, поля (68). Булевы кольца (70). Прямое произведение {прямая сумма) булевых колец (71).Булсаы алгебры как кольца и решетки (72).Иные аксиоматики булевой алгебры (77). Решетки как частично упорядоченные множества (78). Дьоичная булева алгебра {алгебра логики) (79). Булева алгебра множеств (82). Классы накрытия, покрытия и разбиения (87).
1.6. Поля Галуа и их основные свойства
Определение конечного поля с помощью четырех операций (92). Понятие о векторных пространствах (95). Трактовка поля Галуа GF(pr) как векторного пространства над простым полем GF{p) (99). Линейная зависимость векторов, базис и размерность конечного векторного пространства (100). Трактовка поля Галуа GF(pr) как расширения простого поля GF(p) (100). Основные, способы представления элементов полей Галуа (102). Операции сдвига компонент вектора и умножения полинома на переменную х (104). Генерация элементов поля Галуа GF(2r) (105). Основные операции над элементами полей CF(2r) (107).
1.7. Понятие о недистрибутивных алгебрах с парой бинарных операций
Вводные замечания (111). Определение недистрибутивных алгебр с парой бинарных операций (112). Некоторые обобщепш иедистрибутиипых алгебр (118).
Глава 2:Алгебра отношении
2.1. Свойства и классификация бинарных отношений
Свойства бинарных отношений (трихотомичность, связность, рефлексивность, симметричность, транзитивность) (123). Классификация бинарных отношений по трем признакам: рефлексивность, симметричность и транзитивность (128).
2.2. Отношения эквивалентности и толерантности
Одинаковость (эквивалентность) и сходство (толерантность) (129). Классы и "предклассы" эквивалентности и толерантности (131). Графы и матрицы отношений толерантности и эквивалентности, заданных с помощью соответствий (133). Фактор-множество, смежные классы и фактор-группа (135). Отношение "быть эталонам" (137).
2.3. Отношения порядка
Классификация транзитивных бинарных отношений (139). Отношение порядка и его разновидности (139). Число упорядочений конечного множества (141). Минимаксные порядки (144).
2.4. Специальные виды отношений
Отношения, задаваемые перестановками (147). Кватернарные (четверичные) отношения на элементарной абелевой группе конечного поля (149). Центральные тотально симметричные и тотально рефлексивные отношения (158). Регулярные отношения эквивалентности и их прообразы (165).
2.5. Функции и операции над отношениями
Теоретико-множественные операции над отношениями (166). Специальные операции над отношениями (170).
2.6. Инвариантность свойств отношений
Понятие об инвариантности свойств отношений (172). Инвариантность свойств отношения эквивалентности (174). Инвариантность свойств отношения толерантности (175). Инвариантность свойств отношения порядка (175). Понятие о теории Галуа (177). Функции, сохраняющие отношения [полиморфизмы и их инварианты) (178).
Глава 3. Дискретные и непрерывные алгебры логики
3.1. Непрерывные алгебры логики
Обобщенная булева алгебра с зеркальным отрицанием (187). Основные логико-алгебраические тождества (189). Решетки над линейно упорядоченным множеством (191).
3.2.Конечнозначные алгебры логики
Понятие о дискретных и конечнозиачных алгебрах логики (192). Функции конечнозначной алгебры логики (192). Существенные и несущественные переменные {аргументы) (193).Элементарные многозначные функции (194). Операция суперпозиции многозначных логических функций (197).
3.3.Четыре основные проблемы в многозначной алгебре логики
Общие сведения о функциональной полноте, регулярных формах, оптимизации, и декомпозиции схем\формул (202). Замкнутые и максимальные классы многозначных функций,понятие о функциональной полноте и базисе (204). Понятие о функциональной полноте в непрерывной алгебре логики (207). Функциональная полнота полиномиальных представлений (207). Понятие о регулярных формах в конечнозначной алгебре логики (215). Понятие о минимизации логических выражений (224).
3.4.Необходимые и достаточные условия функциональной полноты в конечнозначной алгебре логики
Шесть семейств многозначных логических функций, образующих максимальные (предполные) классы (226). Теорема о функциональной полноте в конечнозначной алгебре логики (226). Минимаксно монотонные функции (227). Равномерно самодвойственные функции (227). Линейные и квазилинейные функции (228).
3.5.Число максимальных классов и тисов многозначных логических функций
Полиморфизмы, соответствующие отношению р1 минимаксного порядка (230). Полиморфизмы, соответствующие равномерно циклическому отношению pi (230). Полиморфизмы, соответствующие кватернарному отношению р3 на элементарной абелевой группе поля Галуа GF{jf) (231). Полиморфизмы, соответствующие неполному и нетривиальному отношению эквивалентности р4 (232). Полиморфизмы, соответствующие неполному тотально центральному отношению р5 (232). Полиморфизмы, соответствующие отношению р6, являющемуся прообразом регулярного отношения эквивалентности (232). Сводная таблица числа максимальных классов и их типов (233).
3.6. Примеры исследования систем функций на полноту
Принадлежность основных двоичных функций к максимальным классам (234). Принадлежность основных троичных функций к максимальным классам (237). Примеры троичных функций, сохраняющих отношения pi,.. .,ps (239). Другое определение троичных функций, сохраняющих разбиение и бинарное отношение с одним центром (242). Принадлежность троичных функций одной переменной к максимальным классам (244). Критерии функциональной полноты в многозначной алгебре логики (244).
Глава 4. Логические уравнения
4.1. Введение
Классификация логических уравнений и неравенств (252). Приведение неоднородного логического уравнения к равносильному однородному уравнению (255). Агрегация системы однородных логических уравнении в одни равносильное уравнение (256). Основные свойства операций транспортами и агрегации (257).
4.2. Двоичные логические уравнения
Числовое двоичное логическое уравнение с одним неизвестным. (259). Буквенное двоичное логическое уравнение с одним неизвестным (260). Система нескольких двоичных логических уравнений с одним неизвестным -(264). Двоичные логические уравнения с несколькими неизвестными (266).
4.3. Троичные логические уравнения
Числовые троичные логические уравнения с одним неизвестным (269). Буквенное троичное логическое уравнение с одним неизвестным (270). Системы троичных логических уравнений (275).
4.4. Понятие о решении конечно-значных логических уравнений
ОСНОВНОЙ МЕТОД РЕШЕНИЯ (276).
4.5. Уравнения и неравенства в бесконечно-значной (непрерывной) алгебре логики
Основной метод решения (284). Решение логичестсиг уравнений и неравенств непрерывной логики (286). Логические уравнения с характеристическими функциями (289). Решение конечнозначных логических уравнений путем сведения их к уравнениям непрерывной алгебры логики (290).
4.6. Использование логических уравнений в теории цифровых многозначных схем
Анализ многозначных схем с обратными связями (292). Синтез многозначных триггерных последовательностных схем (293). Регулярные аналитические представления функций мнффозначной логики (304).
Глава 5. Регулярные аналитические представления многозначных логических функций в недистрибутивных алгебрах
5.1. Обобщенные регулярные формы
Постановка задачи (314). Малоуровнеяые регулярные формы (315). Сведение задачи о регулярных представлениях функций многозначной логики к задаче о разрешимости системы многозначных уравнений (318).
5.2. Аналитические представлекня многозначных функций в недистрибутивных алгебрах-изобиноидах
"Диагональная" система (базис) (320). "Треугольная" система {базис) (324).
5.3. Квазиполиномиальные представления многозначных функций в недистрибутивных биноидо- и ринго- подобных алгебрах
Постановка задачи (326). Реализация ''диагонального" базиса (квазиполином в интерполяционной форме Лагранжа) (327). Реализация "треугольного" базиса (квазиполином в интерполяционной форме Ньютона) (329). Реализация недистрибутивных логико-арифметических базисов (332).
Список литературы