Учебно-методический комплекс дисциплины математическая логика Основная образовательная программа

РАЗДЕЛ II.Методические указания по изучению дисциплины (или ее разделов) и контрольные задания для студентов заочной формы обучения.

РАЗДЕЛ III.Содержательный компонент теоретического материала.

• 
  Высказывания и операции над ними.
  
• 
  Понятие высказывания.
  
• 
  Основные логические операции.
  
• 
  Свойства логических операций.
  
• 
  Формулы алгебры высказываний.
  
• 
  Тавтологии алгебры высказываний.
  
• 
  Классы формул алгебры логики.
  

• 
  Булевы функции одного и двух аргументов.
  
• 
  Свойства булевых функций.
  
• 
  Связь между высказываниями и булевыми функциями.
  
• 
  Понятие нормальных форм.
  
• 
  Теорема о разложении в Д(К)НФ (с доказательством).
  
• 
  Понятие совершенных НФ.
  
• 
  Теорема о единственности разложения в нормальную форму (с доказательством).
  
• 
  Понятие тупиковых НФ.
  
• 
  Понятие минимальных НФ.
  
• 
  Методы минимизации булевых функций.
  
• 
  Применение булевых функций к релейно-контактным схемам.
  

• 
  Понятие систем булевых функций.
  
• 
  Понятие замыкания системы булевых функций.
  
• 
  Свойства замыкания.
  
• 
  Понятие полноты систем булевых функций. Примеры полных систем.
  
• 
  Важнейшие замкнутые классы. Понятие предполных классов.
  
• 
  Лемма о несамодвойственной функции (с доказательством).
  
• 
  Лемма о немонотонной функции (с доказательством).
  
• 
  Лемма о нелинейной функции (с доказательством).
  
• 
  Теорема (Поста) о функциональной полноте с доказательством.
  
• 
  Следствия из теоремы Поста.
  

• 
  Понятие предиката.
  
• 
  Области истинности предикатов.
  
• 
  Классификация предикатов.
  
• 
  Логические операции над предикатами.
  

• 
  Понятие кванторных операций: существования, всеобщности, единственности, численный, ограниченные.
  
• 
  Формулы логики предикатов.
  
• 
  Классификация ФЛП.
  
• 
  Тавтологии.
  
• 
  Равносильные преобразования формул.
  

• 
  Выводимость и доказуемость формул в исчислении предикатов.
  
• 
  Клаузальная форма.
  
• 
  Приведение предикатных формул к клаузальной форме.
  
• 
  Метод резолюций в логике предикатов.
  
• 
  Понятие предварённой нормальной формы.
  
• 
  Понятие предклаузальной нормальной формы.
  
• 
  Понятие общезначимости.
  
• 
  Проблема разрешимости для общезначимости. Неразрешимость её в общем случае.
  
• 
  Применение языка логики предикатов для записи математических предложений, определений, построение отрицаний предложений.
  

• 
  Определение формального исчисления. Аксиоматика и формулы исчисления высказываний.
  
• 
  Исчисление высказываний генценовского типа.
  
• 
  Понятие секвенции и эквивалентность формул. Нормальные формы и семантика исчисления секвенций.
  
• 
  Исчисление высказываний генценовского типа.
  
• 
  Алгоритмы проверки общезначимости и выполнимости: алгоритм Квайна, алгоритм редукции, метод резолюций в исчислении высказываний, (с теоремой о полноте метода резолюций), метод резолюций для хорновских дизъюнктов.
  
• 
  Исследования системы аксиом исчисления высказываний; их непротиворечивость и полнота.
  

• 
  Определение логики предикатов (логики первого порядка). Алфавит, аксиоматика и формулы исчисления предикатов сигнатуры .
  
• 
  Секвенциальное исчисление предикатов сигнатуры . Непротиворечивость ИПС^.
  
• 
  Пренексная (предклазуальная нормальная форма).
  
• 
  Теорема Куратовского-Цорна. Теорема Гёделя о неполноте. Теормема Мальцева о компактности.
  
• 
  Исчисление предикатов гильбертовского типа. Теорема дедукции.
  
• 
  Теорема Гёделя о полноте исчисления предикатов.
  
• 
  Теорема Гёделя о неполноте.
  

• 
  Предикативное доказательство теорем.
  
• 
  Эрбрановские интерпретации. Теорема Эрбрана об H-интерпретациях.
  
• 
  Задача интерпретации.
  
• 
  Скулемизация алгебраических систем и метод резолюций в логике предикатов.
  
• 
  Логические программы.
  

• 
  Элементарная эквивалентность. Теоремы Лёвенгейма-Скулема. Элементарные теории.
  
• 
  Аксиоматический метод в математике. Формальные аксиоматические теории.
  
• 
  Типы. Основные классы моделей. Теорема Воота.
  
• 
  Вывод, язык, метаязык, теоремы, метатеоремы формальной аксиоматической теории.
  
• 
  Примеры аксиоматических теорий (натуральных чисел Пеано, евклидовой геометрии Гильберта и Вейля, теории множеств, теории групп).
  
• 
  Непротиворечивые, полные и выполнимые системы формул.
  
• 
  Интерпретация и модели аксиоматической теории. Свойства аксиоматических теорий (непротиворечивость, полнота, категоричность, разрешимость). Теоремы Лося-Воота, Рыль-Нардзевского, Морли. Болдвина-Еримбетова-Лахлана.
  

• 
  Теорема Генцена об устранении сечения.
  
• 
  Формальная арифметика: система аксиом, арифметические функции и отношения, арифметизация, гёделевы номера, теорема о неразрешимости, формулы и интерпретации, теорема Тарского, система Робинсона.
  
• 
  Теорема Гёделя о неполноте. Вторая теорема Гёделя. Определение истинности. Выразимость. Элиминация кванторов. Арифметика Пресбургера. Теорема Тарского-Зайденберга. Игра Эренфойхта. Понижение мощности. Программа Гильберта обоснования математики. Нестандартный анализ. Теоремы Лёвенгейма-Скулема.
  

• 
  Теория поиска логического вывода (теорема Эрбрана, метод метапеременных, глобальная обработка информации).
  
• 
  Автоматический поиск вывода. Теорема Мальцева о компактности и ее приложения.
  
• 
  Строение математических теорем. Методы доказательства теорем.
  
• 
  Применение исчисления предикатов для записи математических утверждений и для автоматического доказательства теорем.
  
• 
  Понятие сложности вывода и переход к табличным исчислениям. Индексные методы Бродского.
  
• 
  Естественный вывод в развитии искусственного интеллекта. Логические основания ИИ.
  
• 
  Выбор исчислений для автоматического поиска вывода.
  
• 
  Автоматизированные решения логических задач.
  
• 
  Фантоматы.
  

• 
  Тезис Гильберта.
  
• 
  Пропозициональные логики: интуиционистские логики. Принцип противоречия.
  
• 
  Пропозициональные логики: понятие о многозначных логиках. Счётнозначные и континуумзначная логика.
  
• 
  Пропозициональные логики: логики Лукасевича.
  
• 
  Пропозициональные логики: нечёткие (вероятностные) логики и их применение в конструировании процессоров. Релейные схемы в нечёткой логике.
  

• 
  Пропозициональные логики: модальные логики (алетические, деонтические, эпистемические). Исчисление Брауэра. Правило Гёделя. Аксиома Баркан. Исчисление Фейса-фон Вригта.
  
• 
  Означивание. Семантика Крипке. Теоремка о непротиворечивости формальных исчислений.
  
• 
  Пропозициональные логики: ВременнЫе (темпоральные) логики: Прайора, Леммона, фон Вригта.
  

• 
  Предикатные логики: многосортные логики первого порядка. Слабая логика второго порядка. Бесконечные логики. Логика с новыми кванторами. Теорема Линдстрёма.
  
• 
  Предикатные временнЫе логики и их приложения к программированию. Схема программы с памятью.
  
• 
  Алгоритмические логики. Алгоритимическая логика Хоара. Правила верификации.