Учебное пособие посвящено изложению основ математической логики и
теории алгоритмов. основу пособия составляют конспекты лекций,
которые читались студентам вторго курса отделения компьютерных наук
Омского гос. универститета в 2002 г.
Для студентов специальностей 075200 - "Компьютерная безопасность" и по специальности 220100 - "Вычислительные машины, комплексы, системы и сети".
Содержание разделов:
Логика.
Классическая логика.
Логика высказываний.
Высказывания.
Основные законы логики.
Логический парадокс Рассела.
Алгебра (логика) высказываний.
Релейно-контактные схемы.
Равносильные формулы.
Алгебра Буля.
Истинные и общезначимые формулы.
Проблема разрешимости.
Логическое следствие.
Силлогизмы.
Логика предикатов.
Предикаты и формулы.
Интерпретации.
Истинность и выполнимость формул. Модели, общезначимость, логическое следствие.
Готлоб Фреге.
Сколемовские функции.
и сколемизация формул.
Метод резолюций.
Метод резолюций в логике высказываний.
Метод резолюций в логике предикатов.
Формальные теории (исчисления).
Определение формальной теории, или исчисления.
Доказательство. Непротиворечивость теории. Полнота теории.
Исчисление высказываний.
Язык и правила вывода исчисления высказываний.
Пример доказательства теоремы.
Полнота и непротиворечивость исчисления высказываний.
Исчисление предикатов.
Язык и правила вывода исчисления предикатов.
Полнота и непротиворечивость исчисления предикатов.
Формальная арифметика.
Эгалитарные теории.
Язык и правила вывода формальной арифметики.
Непротиворечивость формальной арифметики. Теорема Генцена.
Теорема Геделя о неполноте.
Курт Гёдель.
Автоматический вывод теорем.
С. Ю. Маслов.
Логическое программирование.
Логическая программа.
Языки логического программирования.
Неклассические логики.
Интуиционистская логика.
Нечеткая логика.
Нечеткие подмножества.
Операции над нечеткими подмножествами.
Свойства множества нечетких подмножеств.
Нечеткая логика высказываний.
Нечеткие релейно-контактные схемы.
Модальные логики.
Типы модальности.
Исчисления 1 и Т (Фейса-фон Вригта).
Исчисления S4, S5 и исчисление Врауэра.
Означивание формул.
Семантика Крипке.
Другие интерпретации модальных знаков.
Георг фон Вригт.
Временные логики.
Временная логика Прайора.
Временная логика Леммона.
Временная логика фон Вригта.
Приложение временных логик к программированию.
Временная логика Пнуели.
Алгоритмические логики.
Принципы построения алгоритмической логики.
Чарльз Хоар.
Алгоритмическая логика Хоара.
Алгоритмы.
Алгоритмы.
Понятие алгоритма и вычислимой функции.
Рекурсивные функции.
Примитивно рекурсивные функции.
Частично рекурсивные функции.
Тезис Чёрча.
Машина Тьюринга-Поста.
Вычисления функций на машине Тьюринга-Поста.
Примеры вычислений.
Тезис Тьюринга.
Универсальная машина Тьюринга-Поста.
Алан Тьюринг.
Эмиль Пост.
Эффективные алгоритмы.
Алгоритмически неразрешимые проблемы.
Сложность алгоритмов.
Понятие о сложности алгоритмов.
Классы задач Р и NP.
Класс задач Р.
Класс задач NP.
Недетерминированная машина Тьюринга.
О понятии сложности.
Три типа сложности.
Четыре категории чисел по Колмогорову.
Тезис Колмогорова.
А. Н. Колмогоров.
Алгоритмы реальности.
Генератор виртуальной реальности.
Принцип Тьюринга.
Логически возможные среды Кантгоуту.
Для студентов специальностей 075200 - "Компьютерная безопасность" и по специальности 220100 - "Вычислительные машины, комплексы, системы и сети".
Содержание разделов:
Логика.
Классическая логика.
Логика высказываний.
Высказывания.
Основные законы логики.
Логический парадокс Рассела.
Алгебра (логика) высказываний.
Релейно-контактные схемы.
Равносильные формулы.
Алгебра Буля.
Истинные и общезначимые формулы.
Проблема разрешимости.
Логическое следствие.
Силлогизмы.
Логика предикатов.
Предикаты и формулы.
Интерпретации.
Истинность и выполнимость формул. Модели, общезначимость, логическое следствие.
Готлоб Фреге.
Сколемовские функции.
и сколемизация формул.
Метод резолюций.
Метод резолюций в логике высказываний.
Метод резолюций в логике предикатов.
Формальные теории (исчисления).
Определение формальной теории, или исчисления.
Доказательство. Непротиворечивость теории. Полнота теории.
Исчисление высказываний.
Язык и правила вывода исчисления высказываний.
Пример доказательства теоремы.
Полнота и непротиворечивость исчисления высказываний.
Исчисление предикатов.
Язык и правила вывода исчисления предикатов.
Полнота и непротиворечивость исчисления предикатов.
Формальная арифметика.
Эгалитарные теории.
Язык и правила вывода формальной арифметики.
Непротиворечивость формальной арифметики. Теорема Генцена.
Теорема Геделя о неполноте.
Курт Гёдель.
Автоматический вывод теорем.
С. Ю. Маслов.
Логическое программирование.
Логическая программа.
Языки логического программирования.
Неклассические логики.
Интуиционистская логика.
Нечеткая логика.
Нечеткие подмножества.
Операции над нечеткими подмножествами.
Свойства множества нечетких подмножеств.
Нечеткая логика высказываний.
Нечеткие релейно-контактные схемы.
Модальные логики.
Типы модальности.
Исчисления 1 и Т (Фейса-фон Вригта).
Исчисления S4, S5 и исчисление Врауэра.
Означивание формул.
Семантика Крипке.
Другие интерпретации модальных знаков.
Георг фон Вригт.
Временные логики.
Временная логика Прайора.
Временная логика Леммона.
Временная логика фон Вригта.
Приложение временных логик к программированию.
Временная логика Пнуели.
Алгоритмические логики.
Принципы построения алгоритмической логики.
Чарльз Хоар.
Алгоритмическая логика Хоара.
Алгоритмы.
Алгоритмы.
Понятие алгоритма и вычислимой функции.
Рекурсивные функции.
Примитивно рекурсивные функции.
Частично рекурсивные функции.
Тезис Чёрча.
Машина Тьюринга-Поста.
Вычисления функций на машине Тьюринга-Поста.
Примеры вычислений.
Тезис Тьюринга.
Универсальная машина Тьюринга-Поста.
Алан Тьюринг.
Эмиль Пост.
Эффективные алгоритмы.
Алгоритмически неразрешимые проблемы.
Сложность алгоритмов.
Понятие о сложности алгоритмов.
Классы задач Р и NP.
Класс задач Р.
Класс задач NP.
Недетерминированная машина Тьюринга.
О понятии сложности.
Три типа сложности.
Четыре категории чисел по Колмогорову.
Тезис Колмогорова.
А. Н. Колмогоров.
Алгоритмы реальности.
Генератор виртуальной реальности.
Принцип Тьюринга.
Логически возможные среды Кантгоуту.