Читать онлайн «Функции алгебры логики и классы Поста»

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ОСНОВАНИЯ МАТЕМАТИКИ ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1966  ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ И КЛАССЫ ПОСТА С. В. ЯБЛОНСКИЙ Г. П. ГАВРИЛОВ В. Б. КУДРЯВЦЕВ ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1966  517. 1 Я 14 УДК 512. 8+164 2-2-3 116-66  ОГЛАВЛЕНИЕ Введение 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 Глава III. Типы оснований замкнутых классов. ... 39 § 1. Типы оснований. Свойства (А2) и (а2). Леммы о классах, содержащих функцию х • у 39 § 2. Лемма о соотношении свойств (А2), (а2), само- двойственности и монотонности 43 § 3. Класс С4, его базис 45 § 4. Классы С2 и Сз> их базисы 46 § 5. Классы самодвойственных а-функций 48 Глава IV. Некоторые специальные замкнутые классы 51 § 1. Свойства <А**>. {А00), {а»), {а*>) 51 § 2. Класс F5°, его базис. Лемма об (а)-системах, содержащих класс Ff 54  б ОГЛАВЛЕНИЕ § 3. Класс F™, его базис. Лемма об (а, у)-системах, содержащих класс Fg° 56 § 4. Классы Fq* и F2°, их базисы. Лемма об (^-системах, содержащих класс F*j?. Лемма об (а, у)-си- стемах, содержащих класс F^ 58 § 5. Лемма о порядках классов F£°, F^t FF\'f ... 60 § 6. Лемма о классах, удовлетворяющих условию (А2) и не удовлетворяющих условию (/Р11'1) 61 § 7. Классы F£, их базисы 64 § 8. Классы /^, их базисы 65 § 9. Классы и F^, их базисы 66 § 10. Лемма о порядках классов /^, Ftf, Fjf, Fg ... 69 ЧАСТЬ ВТОРАЯ Глава I. Описание замкнутых классов в С! 70 § 1. Замкнутые классы О/, Я/, S/ 70 § 2. Замкнутые классы линейных функций 73 § 3. (Р)-, (у)-, (Р, у)-системы 75 § 4. (а, р, у)-системы 76 § 5. (а, р, у, 6)-системы 76 § 6. (а)-системы (первая часть) 77 § 7. (а, 6)-системы 79 § 8. (а, Р)- и (а, у)-системы (первая часть) 80 § 9. (а)-системы (вторая часть) 81 § 10. (а, Р)- и (а, у)-системы (вторая часть) 86 § 11. Основные теоремы Поста о замкнутых классах алгебры логики 90 Глава II. Построение диаграммы включений замкнутых классов 92 § 1. (а)-системы 92 § 2. (а, р)- и (а, у)-системы 97 § 3. (а, 6)-системы 99 § 4. (а, р, у)-системы 99 § 5. Построение полной диаграммы включений. Некоторые следствия из полной диаграммы включений 101 Сводная таблица замкнутых классов 104 Литература 113 Обозначения 116 Предметный указатель 118  ВВЕДЕНИЕ В 1921 году появилось сообщение о крупном исследовании в области алгебры логики, выполненном известным американским математиком Э.