Читать онлайн «Дискретная математика и математические вопросы кибернетики»

i Дискретная математика и математические вопросы кибернетики Дискретная математика и математические вопросы кибернетики Под общей редакцией С. В. ЯБЛОНСКОГО и О. Б. ЛУПАНОВА Том первый т, ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 197 4 518 Д48 УДК 519. 95 Авторы: Ю. Л. ВАСИЛЬЕВ, Ф. Я. ВЕТУХНОВСКИЙ, В. В. ГЛАГОЛЕВ, 10. И. ЖУРАВЛЕВ, В. И. ЛЕВВНШТЕЙН, С. В. ЯБЛОНСКИЙ Дискретная математика и математические вопросы кибернетики, т. I, под общей редакцией С. В. Яблонского и О. В. Лупанова, Главная редакция физико- математической литературы изд-ва «Наука», М. , 1974. Первый том двухтомной монографии, написанной коллективом специалистов но математической кибернетике. Книга может служить учебным пособием для студентов, специализирующихся в области теоретической кибернетики. В первый том входят главы, посвященные функциональным построениям в многозначных логиках, теории дизъюнктивных нормальных форм, теории графов и теории кодирования. Книга будет полезна широкому кругу научных работников — специалистов в других разделах математики, а также инженерам, работающим в области вычислительной техники, автоматики, связи и электроники. ВВЕДЕНИЕ В ТЕОРИЮ ФУНКЦИЙ fe-ЗНАЧНОЙ ЛОГИКИ 9 Глава I. Алгебра логики 9 § 1. Функции алгебры логики 9 § 2. Формулы. Реализация функций формулами 12 § 3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности 17 § 4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма 21 § 5. Полнота и замкнутость 24 § 6. Важнейшие замкнутые классы. Теорема о полноте 28 § 7. Представление о результатах Поста 34 Глава П. fe-значная логика 35 § 8. Функции А-значной логики. Формулы я реализация функций формулами 35 § 9. Примеры полных систем 39 § 10. Распознавание полноты. Теорема А. В. Кузнецова о полноте 42 § 11. Некоторые свойства существенных функций. Теорема Слу- пецкого и ее приложения 46 § 12. Теорема Саломаа 54 § 13. Особенности fc-значных логик 59 Ля тература 65 Раздел 2. АЛГОРИТМЫ ПОСТРОЕНИЯ МИНИМАЛЬНЫХ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ ДЛЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ 67 Глава I. Основные понятия теории дизъюнктивных нормальных форм 67 § 1. Постановка задачи 67 § 2. Геометрическая интерпретация - 69 1* 4 ОГЛАВЛЕНИЕ § 3. Допустимые конъюнкции 70 § 4. Сокращенная д. н. ф 71 § 5. Методы построения сокращенной д. н. ф 74 § 6. Тупиковые д. н. ф 76 § 7. Способы построения тупиковых д. н. ф 77 § 8. Не всюду определенные (частичные) функции алгебры логики S1 Глава П. Локальные алгоритмы упрощения дизъюнктивных нормальных форм ... 83 § 9. Операции над д. н. ф 84 § 10. Алгоритм Квайна 85 § 11. Необходимое и достаточное условие вхождения конъюнкции в д. н. ф. DUt 87 § 12. Л-алгоритм 90 § 13. Кольцевой алгоритм 93 § 14. Отсутствие локального критерия вхождения конъюнкции в д. н. ф. DUh 95 Литература 98 Раздел 3.