Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста

ОГЛАВЛЕНИЕ

Введение......................... 7

ЧАСТЬ ПЕРВАЯ

Глава I. Основные понятия алгебры логики..... 10

§ 1. Определение функции. Элементарные функции.. 10

§ 2. Определение формулы и суперпозиции..... 12

§ 3. Теорема о разложении............. 15

§ 4. Теорема о компонентах функции........ 17

§ 5. Определение замкнутого класса. Базис и порядок

замкнутого класса............... 18

§ 6. Принцип двойственности............ 20

Глава II. Самодвойственные, монотонные и линейные

функции алгебры логики.......... 22

§ 1. Самодвойственность. Класс D3, его базис. Лемма

о несамодвойственной функции......... 22

§ 2. Монотонность. Класс Аи его базис. Лемма о немонотонной функции. Сокращенная дизъюнктивная

нормальная форма............... 25

§ 3. Класс D2, его базис.............. 31

§ 4. Линейность. Теорема Жегалкина. Леммы о нелинейных функциях................ 34

Глава ill. Типы оснований замкнутых классов.... 39

§ 1. Типы оснований. Свойства (А2) и (а2). Леммы

о классах, содержащих функцию х у...... 39

§ 2. Лемма о соотношении свойств (Л2), (а2), самодвойственности и монотонности......... 43

§ 3. Класс С,, его базис............... 45

§ 4. Классы С2 и С3, их базисы........... 46

§ 5. Классы самодвойственных а-функций...... 48

Глава IV. Некоторые специальные замкнутые классы 51

§ 1. Свойства {А»), {Ах), {а»), (а00)........ 51

§ 2. Класс Ff, его базис. Лемма об (а)-системах, содержащих класс Ff.............. 54

§ 3. Класс F™, его базис. Лемма об (се, у)-системах,

содержащих класс F^............. 56

§ 4. Классы Ff и Ff, их базисы. Лемма об ((^-системах, содержащих класс Ff. Лемма об (а, у)-си-

стемах, содержащих класс Ff......... 58

§ 5. Лемма о порядках классов Ff, Ff, Ff, Ff... 60

§ 6. Лемма о классах, удовлетворяющих условию (А2)

и не удовлетворяющих условию (_4Й+1)..... 61

§ 7. Классы г7^, их базисы............. 64

§ 8. Классы F%, их базисы............. 65

§ 9. Классы F% и F^, их базисы........... 66

§ 10. Лемма о порядках классов F^, F%, Ff, F$... 69

ЧАСТЬ ВТОРАЯ

Глава I. Описание замкнутых классов в С,..... 70

§ 1. Замкнутые классы О,, Я/,.......... 70

§ 2. Замкнутые классы линейных функций...... 73

§ 3. (6)-, (у)-, (В, у)-системы............ 75

§ 4. (а, В, у)-системы................ 76

§ 5. (а, р, у, 6)-системы............... 76

§ 6. (а)-системы (первая часть)........... 77

§ 7. (а, 6)-системы................. 79

§ 8. (а, 6)- и (а, у)-системы (первая часть)..... 80

§ 9. (а)-системы (вторая часть)........... 81

§ 10. (а, 6)- и (о, у)-системы (вторая часть)..... 86

§ 11. Основные теоремы Поста о замкнутых классах

алгебры логики................. 90

Глава II. Построение диаграммы включений замкнутых классов................. 92

§ 1. (о)-системы.................. 92

§ 2. (а, В)- и (а, у)-системы............ 97

§ 3. (о, 6)-системы................. 99

§ 4. (а, В, у)-системы................ 99

§ 5. Построение полной диаграммы включений. Некоторые следствия из полной диаграммы включений 101

Сводная таблица замкнутых классов........... 104

Литература........................ 113

Обозначения....................... 116

Предметный указатель.................. 118