Формальные теории



Скачать 53.16 Kb.
Дата07.11.2012
Размер53.16 Kb.
ТипДокументы
ФОРМАЛЬНЫЕ ТЕОРИИ

проф. Н.К. Верещагин

1 год

1. Языки первого порядка.

1. Понятие языка первого порядка. Термы, формулы, замкнутые формулы.

2. Понятие интерпретации языка первого порядка.

3. Язык формальной арифметики. Выразимость в этом языке любого разрешимого отношения. β-функция Гёделя.

4. Нумерация арифметических термов и формул. Теорема Тарского о невыразимости в языке формальной арифметики множества номеров истинных арифметических формул.
2. Исчисление высказываний.

5. Аксиомы и правила вывода исчисления высказываний. Теорема корректности исчисления высказываний.

6. Лемма о дедукции для исчисления высказываний. Другие производные правила вывода: правило сведения к противоречию, правило разбора случаев. Выводимость законов де Моргана и законов контрапозиции.

7. Теорема о полноте исчисления высказываний.

3. Исчисление предикатов.

8. Аксиомы и правила вывода исчисления предикатов. Теорема корректности исчисления предикатов.

9. Лемма о дедукции для исчисления предикатов. Лемма о свежих константах.

10. Теорема о полноте исчисления предикатов: формула выводима из множества замкнутых формул тогда и только тогда, когда она истинна во всех моделях этого множества.

11. Аксиомы равенства и теорема о полноте исчисления предикатов с аксиомами равенства.

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

12. Аксиоматизация различных фрагментов арифметики: (1) множества формул сигнатуры истинных в стандартной интерпретации, (2) множества формул сигнатуры истинных в стандартной интерпретации, (3) множества формул сигнатуры истинных в стандартной интерпретации.

13. Аксиомы формальной арифметики Пеано (PA). Теорема Гёделя о неполноте PA.

14. Выводы в PA основных свойств натуральных чисел. Формульное определение отношения ''быть меньше'' и вывод его свойств.

15. Вывод в PA принципа полной математической индукции и принципа наименьшего числа.

16. Принцип свёртывания и его вывод в PA.

17. Следствия принципа свёртывания: (1) для любых конечных последовательностей существует последовательность, равная конкатенации этих последовательностей, (2) возможность рекурсивных определений.

18. Понятие финитного доказательства и тезис о том, что любое финитное доказательство можно провести в рамках PA. Доказательство в PA основной теоремы арифметики.

19. Формула непротиворечивости PA и её невыводимость в PA (вторая теорема Гёделя о неполноте).

20. Теоремы Бернайса. Принцип отражения.
Короткое доказательство второй теоремы Гёделя о неполноте на основе теорем Бернайса и принципа отражения.

5. Аксиоматическая теория множеств.

21. Аксиомы теории множеств Цермело-Френкеля. Доказательство существования объединения, пересечения, разности двух множеств.

22. Определение упорядоченной пары по Куратовскому. Доказательство основного свойства упорядоченной пары. Определение понятия произвольной функции. Доказательство существования декартова произведения двух множеств.

23. Понятие транзитивного множества. Ординалы. Элемент ординала – ординал. Сравнение ординалов. Если имеется ординал с некоторым свойством, то есть и минимальный ординал с этим свойством.

24. Теорема о сравнимости любых двух ординалов.

25. Теорема о том, что для любого множества ординалов существует ординал, больший всех элементов этого множества.

26. Предельные и непредельные ординалы. Натуральные числа. Существование множества натуральных чисел. Определение арифметических операций. Доказательство аксиом Пеано.

27. Принцип трансфинитной индукции.

28. Определения по трансфинитной рекурсии. Теорема о существовании и единственности функции, задаваемой данным рекурсивным правилом.

29. Теорема об изоморфности любого вполне упорядоченного множества некоторому ординалу.

30. Аксиома выбора. Теория множеств с аксиомой выбора ZFC. Доказательство теоремы Цермело в ZFC.

31. Равномощные множества. Кардиналы (мощности). Определение мощности данного множества как кардинала, равномощного этому множеству (в ZFC). Доказательство того, что все натуральные числа и множество натуральных чисел являются кардиналами. Определение конечных и счётных множеств.

32. Мощность подмножества не превосходит мощности множества (доказательство этого факта в ZFC). Доказательство теоремы Кантора-Бернштейна в ZFC.

33. Формула, устанавливающая взаимно-однозначное соответствие между парами ординалов и ординалами. Теорема о том, что декартов квадрат любого бесконечного кардинала равномощен этому кардиналу.

6. Конструктивные множества.

34. Определение класса конструктивных множеств L. Определение порядка конструктивного множества.

35. Лемма о том, что если все элементы множества конструктивны, то множество может быть расширено до конструктивного.

36. Лемма о конструктивности множества кортежей, элементы которых принадлежат данному конструктивному множеству и обладают в L данным свойством.

37. Теорема о том, что в классе конструктивных множеств истинны все аксиомы ZF, кроме аксиомы бесконечности.

38. Конструктивность всех ординалов. Теорема о том, что в классе конструктивных множеств истинна аксиома бесконечности.

39. Абсолютность формулы ''x есть конструктивное множество с номером ''. Аксиома конструктивности V=L и её истинность в классе конструктивных множеств.

40. Истинность аксиомы выбора в классе конструктивных множеств.

41. Гипотеза континуума и её истинность классе конструктивных множеств.

7. Задачи.

Кроме знания указанных теоретических вопросов, необходимо уметь решать следующие задачи:

1. Вывести в исчислении высказываний формулу.

2. Вывести в исчислении высказываний формулу.

3. Вывести в исчислении предикатов формулу

4. Докажите, что для каждого натурального числа n в PA выводима формула , где обозначает (n раз).

5. Докажите, что для любых натуральных чисел m, n в PA выводимы формулы и .

6. Докажите, что аксиома существования неупорядоченной пары и аксиома существования пустого множества следуют из остальных аксиом ZF.

7. Докажите (в ZF), что для любой функции f существуют её область определения и множество значений.

8. Докажите (в ZF), что если для всех существует единственное y, для которого (где некоторая формула), то существует функция, всюду определённая на z, сопоставляющая каждому x такое y.

9. Докажите, что формула ''x есть функция'' абсолютна.

10. Пусть формула получена из формулы языка ZF, релятивизацией всех кванторов к конструктивному множеству B (квантор заменяется на , а квантор – на ). Докажите, что формула абсолютна.

11. Определим множество , где произвольный ординал, трансфинитной рекурсией: есть множество всех подмножеств множества . Докажите, что для каждого множества x найдётся ординал , для которого .
Литература

1. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. М., МЦНМО, 1999.

2. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. М., МЦНМО, 2000.

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

4. Шенфилд Дж. Математическая логика. М., Наука, 1975.

5. Конспекты:http://lpcs.math.msu.ru/˜ver/formal-theories

Похожие:

Формальные теории iconПрограмма курса «Числовые системы»
Формальные и неформальные аксиоматические теории. Схема построения неформальной аксиоматической теории. Интерпретация и модель аксиоматической...
Формальные теории icon1 формальные теории 1 Основные положения
Мы рассмотрели две логических системы: алгебру высказываний и логику предикатов. Это было содержательное рассмотрение. Попытаемся...
Формальные теории iconМетоды представления знаний Формальные языки и формальные системы
Естественный язык: достоинства (и они же недостатки): неполнота, избыточность, неоднозначность
Формальные теории iconРабочая программа дисциплины теория автоматов и формальных языков направление подготовки
Уметь: строить формальные грамматики, деревья вывода, распознающие автоматы; анализировать формальные языки
Формальные теории iconЛекция 4 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Формальные теории iconЛекция 3 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Формальные теории icon4. Введение в формальные (аксиоматические) системы 1 Формальные модели
Принципы построения формальных теорий. Аксиоматические системы, формальный вывод
Формальные теории iconФормальные модели программных агентов в задаче семантического индексирования документов
В работе рассматриваются формальные модели делиберативных агентов, т е агентов базирующихся на базируется на принципах и методах...
Формальные теории iconПрограмма дисциплины «Формальные модели в лингвистике»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 035800....
Формальные теории iconСоставляющие формальной системы. Язык формальной теории. Синтаксис формального языка, отношение между формулой и подформулой, сложные и атомарные формулы
Формальные системы (ФС) – это совокупность чисто абстрактных объектов, не связанных с внешним миром, в котором представлены правила...
Разместите кнопку на своём сайте:
ru.convdocs.org


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