ОГЛАВЛЕНИЕ
Предисловие к третьему изданию Предисловие ка второму изданию
б 7
1. Основные понятия и факты, связанные с булевым кубам и булевыми функциями (9). 2. Элементы булева куба. Первичные представления а булевых функциях (15). 3. Формулы. Реализация булевых функций формулами (23). 4. Двойственные функции. Принцип двойственности (31). 5. Фиктивные и существенные переменные. Отождествление переменных у булевых функций (ЗЗ).
3 2. Специальные представления булевых функций .................... 39
1. Разложения булевых функций па переменным. Саверщенные дизьюнктивная и каньюнктивная нармальн е формы (39). 2. Дизьюнктивные и каньюнктивные нормальные формы (47). 3. Палинамы Жегалкина (52).
Глава П1
7с-значные логики
3 1. Представление функций й-значных логик формулами ............. 88
1. Элементарные функции й-значных логик и саатнащения между
ними (88). 2. Разложение функций й-значных логик в первую и
вторую формы (91).
Глава 1
Способы задания и простейшие свойства функций
алгебры логики
3 1. Функции алгебры логики и способы их задания. Операция супер- позиции
Глава П
Замкнутые классы и полнота систем функций
алгебры логики
9 1. Понятия функциональной замкнутости и полноты
3 2. Класс самадвайственных функций
3 3. Класс линейных функций
9 4. Классы функций, сохраняющих константы
9 5. Класс монотонных функций
9 б. Полнота и замкнутые классы
бб
б4 б8 72 75 81
Огваввснвс
3 2. Замкнутые классы и палната в й-значных логиках ...............
1. Некатарые замкнутые классы й-значных логик. Представление функций из Ря палинамами па модулю й 192). 2. Исследование систем функций й-значнай логики на палнату 197).
Глава 1Ч
Ограниченно-детерминированные функции
9 1. Отабражения паследавательнастей ............................... 102
1. Оснавные панятия и факты, связанные с заданием детерминираввнных функций 1102). 2. Типавые примеры 1105). 3. Выявление свайства детерминираваннасти функции. Эквивалентнасть детерминираввнных функций. Остатачные функции 1111). 4. Выявление свайства аграниченнай детерминированности функции. Паражденные и ввтанамные функции. Страение классав эквивалентнасти.
Машнасти некатарых мнажеств атабражений 1119).
3 2. Диаграммы, таблицы, кананические уравнения, схемы ........... 12б
1. Диаграммы Мура, кананические таблицы и кананические уравнения 112б). 2. Операции нац детерминираввнными функциями 1145). 3. Реализация агрвниченна-детерминираввнных функций схемами 1159). 4. Замкнутые классы и палната в мна жестввх детерминираванных и агрвниченна-детерминираввнных функций 1171).
Глава Ч
Элементы теории алгоритмов 3 1. Минины Тьюринга и аперации нац ними. Функции, вычислимые
на машинах Тьюринга 178
1. Прастейшие свайства машин Тьюринга (178). 2. Операции над
мининами Тьюринга 118б). 3. Вычислимые функции 1190).
3 2. Классы вычислимых и рекурсивных функций ................... 195
1. Операции суперпазиции, примитивнай рекурсии и минимизации 1195). 2. Некатарые специальные свайства рекурсивных функций (201).
Глава Ч1
Графы и сети
3 1. Оснавные панятия теарии графав ................................ 203
1. Прастейшие свайства грвфав. Изамарфизм грвфав 1203). 2. Ориентираввнные графы 1210).
3 2. Планарнасть и раскраска графав .................................
9 3. Деревья и сети
1. Карневые деревья 1219). 2. Двухпалюсные сети 1223).
Глава ЪЗ1
Элементы теории кодирования
3 1. Алфавитнае кадиравание. Критерий адназначнасти кадиравания . 230
3 2. Кады с минимальнай избытачнастью .............................. 235
