Читать онлайн «Введение в математическую логику: конспект лекций»

московский государственный университет имени М. В. ЛОМОНОСОВА Механико-математический факультет Конспект лекций О. Б. Лунанова по курсу "Введение в математическую логику" Москва 2007 УДК 510. 6: 510. 7: 519. 7 ББК 22 Конспект лекций О. Б. Лупанова по курсу "Введение в математическую логику "/Отв. ред. А. Б. Угольников. М. : Изд-во ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова, 2007. 192 с. Учебное пособие составлено на основе конспектов лекций академика РАН О. Б. Лупанова по курсу "Введение в математическую логику", прочитанных им на первом курсе механико- математического факультета МГУ им. М. В. Ломоносова в 1982- 2006 гг. В пособии рассматриваются следующие вопросы: функции алгебры логики, функции многозначной логики, исчисление высказываний, логика и исчисление предикатов, логические сети, конечные автоматы, алгоритмы и вычислимые функции. Для студентов и аспирантов. Ответственный редактор: Александр Борисович Угольников © Лупанов О. Б. , 2007 содерж:ание Предисловие 7 Функции алгебры логики Лекция К^ 1. Булевы функции. Задание функций таблицами. Существенные и несущественные неременные. Равенство функций. Формулы. Реализация функций формулами. Элементарные функции. Эквивалентность формул. Примеры эквивалентных формул. Теорема о разлож:ении функции но множ:еству неременных. Совершенная дизъюнктивная нормальная форма 9 Лекция Ж^ 2. Полные системы. Достаточное условие полноты. Примеры полных систем. Полиномы Жегалкина. Представление функций полиномами. Замыкание системы функций. Замкнутые классы. Линейные функции. Лемма о нелинейной функции. Классы То и Ti. Самодвойственные функции. Лемма о несамодвойственной функции 19 Лекция J{^?>. Монотонные функции. Лемма о немонотонной функции. Теорема о функциональной полноте. Предпол- ные классы. Теорема о предполных классах в Р2. Формулировки основных теорем Э. Поста. Лемма о сохранении функциями существенной зависимости от переменных . . 26 Функции /с-значной логики Лекция Ж^ 4. Функции многозначной логики. Основные понятия. Элементарные функции. Полные системы. Примеры полных систем. Замкнутые классы. Предполные классы. Алгоритм распознавания полноты конечных систем функций в P/j. 33 Лекция J{^ 5. Существенные функции. Лемма о трех наборах. Лемма о квадрате. Теорема Слупецкого. Теорема Яблонского 41 Лекция Ж^ 6. Функции Шеффера. Критерий шефферовости функций. Особенности функций fc-значной логики, fc ^ 3. Представление функций полиномами. Пример замкнутого класса, не имеющего базиса. Пример замкнутого класса со счетным базисом. Мощность семейства замкнутых классов. Классы сохранения множ:еств функций и их свойства. Теорема Кузнецова о функциональной полноте 50 Логические схемы Лекция Ж^7. Графы. Основные понятия. Правильная геометрическая реализация в трехмерном пространстве. Деревья. Ориентированные графы. Лемма о нумерации вер- П1ИН. Схемы из функциональных элементов. Реализация функций схемами. Реализация системы конъюнкций. Функция L{n). Простейгаие методы синтеза. Теорема Шеннона 58 Лекция J{^ 8.