Программа курса математическая логика для студентов 1-2 курсов



Скачать 59.92 Kb.
страница1/2
Дата30.07.2018
Размер59.92 Kb.
ТипПрограмма курса
  1   2

Программа курса

МАТЕМАТИЧЕСКАЯ ЛОГИКА

для студентов 1-2 курсов

Механико-математического факультета

Новосибирского государственного университета


I. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
1. Секвенциальное исчисление высказываний. Вывод в исчислении. Теорема о подстановке.

2. Таблицы истинности. Теорема о корректности для исчисления ИС.

3. Допустимые правила вывода. Примеры.

4. Синтаксическая эквивалентность формул логики высказываний. Теоремы о замене. Вывод основных эквивалентностей.

5. Конъюнктивные и дизъюнктивные нормальные формы.

6. Теорема о полноте исчисления ИС.

7. Совершенные нормальные формы.

8. Функционально полные системы связок.


II. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
1. Операции над множествами. Теоретико-множественные тождества.

2. Упорядоченная пара. Декартово произведение множеств. Отношения и функции.

3. Отношения эквивалентности, предпорядка, частичного и линейного порядков.

4. Основные свойства вполне упорядоченных множеств. Теорема о сравнении вполне упорядоченных множеств.

5. Аксиома выбора, лемма Цорна, теорема Цермело.

6. Сравнение множеств по мощности. Теоремы Кантора-Бернштейна и Кантора. Теорема о трихотомии.

7. Сумма и произведение бесконечных кардинальных чисел. Мощность множества слов в бесконечном алфавите.
III. ЯЗЫК ИСЧИСЛЕНИЯ ПРЕДИКАТОВ И ЕГО СЕМАНТИКА
1. Предикаты и функции. Алгебраические системы данной сигнатуры.

2. Термы и атомарные формулы. Формулы первого порядка.

3. Определение истинности формул на алгебраической системе. Тождественная истинность и выполнимость.

4. Семантическая эквивалентность формул. Предваренная нормальная форма.


IV. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
1. Аксиомы и правила вывода секвенциального исчисления предикатов. Вывод в исчислении.

2. Допустимые правила. Леммы о подстановке.

3. Тождественная истинность доказуемых секвенций.

4. Непротиворечивые множества формул и их свойства.

5. Полные множества формул. Лемма Линденбаума.

6. Теорема о существовании модели.

7. Теорема Геделя о полноте исчисления предикатов.

8. Исчисление предикатов с равенством. Теорема о существовании модели. Теорема о полноте.

9. Теорема Мальцева о компактности. Теорема о расширении. Теорема Левенгейма-Скулема.

10. Теорема Эрбрана.

11. Исчисления гильбертовского типа. Теорема о дедукции для исчисления высказываний ИВ.

12. Вывод в исчислениях предикатов ИП и ИПР. Теорема о дедукции. Сведение ИПР к ИП.

13. Эквивалентность секвенциального и гильбертовского исчислений.

14. Сильная теорема о полноте для ИП и ИПР.

15. Аксиоматизируемые классы. Критерий конечной аксиоматизируемости.
V. АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ
1. Понятие алгоритма. Машина Тьюринга.

2. Функции, вычислимые на машинах Тьюринга.

3. Операторы суперпозиции, примитивной рекурсии и минимизации. Частично-рекурсивные функции.

4. Нумерация пар и кортежей натуральных чисел. Функция Геделя.

5. Нумерация машин Тьюринга.

6. Равнообъемность класса частично-рекурсивных функций и класса вычислимых функций. Тезис Черча.

7. Существование универсальной частично рекурсивной функции. Теорема о нормальной форме Клини

8. Рекурсивные и рекурсивно перечислимые множества. Теорема Поста.

9. Существование нерекурсивного, рекурсивно перечислимого множества.

10. Теорема о графике и ее следствия.

11. Основная теорема о рекурсивно перечислимых множествах.

12. m-сводимость. Существование m-универсального множества.


VI. ТЕОРЕМА ГЕДЕЛЯ О НЕПОЛНОТЕ АРИФМЕТИКИ


  1. Геделевская нумерация и ее свойства.

2. Рекурсивная перечислимость множества теорем ИПР

3. Формальная теория арифметики.

4. Представимость рекурсивных функций.

5. Теорема Геделя о неразрешимости арифметики.

6. Теорема Черча о неразрешимости исчисления предикатов.

7. Рекурсивно аксиоматизируемые, полные и разрешимые теории.

8. Теорема Геделя о неполноте арифметики.
ЛИТЕРАТУРА


  1. Ю.Л.Ершов, Е.А.Палютин. Математическая логика.

  2. И.А.Лавров, Л.Л.Максимова. Задачи по теории множеств, математической логике и теории алгоритмов.

  3. А.И.Мальцев. Алгоритмы и рекурсивные функции.

Профессор, д.ф.-м.н. Л.Л.Максимова


МАТЕМАТИЧЕСКАЯ ЛОГИКА

11 курс (третий семестр)

Вопросы по курсу





  1. Поделитесь с Вашими друзьями:
  1   2


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница