В.А. Успенский - Программа экзамена по дискретной математике

Программа экзамена по математической логикеЛектор — В. А. УспенскийII семестр, 2004 г.1. Экзаменационные билеты1. Бинарные отношения. Отношения эквивалентности, предпорядка, нестрого и строгого (частичного) порядка. Построение нестрогого порядка по предпорядку факторизацией.2. Частично и линейно упорядоченные множества. Плотные множества. Понятие изоморфии упорядоченных множеств. Сечения упорядоченных множеств, аксиома Дедекинда. Изоморфное вложение счетноголинейно упорядоченного множества в (Q, <).3.

Высказывание и его истинностное значение. Основные логические операции и таблицы истинности дляних. Построение формулы по ее истинностной таблице.4. Формулы языка логики высказываний. Истинностное значение формулы. Таблица истинности формулы.Тавтологии.5. Эквивалентность (равносильность) формул логики высказываний. Законы логики высказываний в форме равносильностей. Выражение одних логических операций через другие. Приведение формул логикивысказываний к нормальным формам (ДНФ и КНФ).6. Язык упорядоченных множеств. Интерпретация формулы на данном упорядоченном множестве. Истинность и равносильность формул на данном упорядоченном множестве. Запись (формулами) аксиом порядка (строгого и нестрого), линейного порядка, плотного порядка.7.

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

Понятие разрешимой теории. Разрешимость элементарной теории плотных линейно упорядоченных множеств без первого и последнего элемента.11. Язык логики предикатов: алфавит, термы, формулы, элементарные формулы. Запись утверждения о бесконечности множества изменения индивидных переменных с помощью функциональной переменной.12.

Язык логики предикатов: алфавит, термы, формулы, элементарные формулы. Формульная запись аксиомыДедекинда.13. Язык логики предикатов: алфавит, термы, формулы, элементарные формулы. Запись аксиом группы,кольца, поля.14. Понятие математической структуры. Сигнатура. Языки данной сигнатуры.

Интерпретация сигнатуры.Способы выражения законов предикатной логики (общезначимые формулы и равносильности, справедливые при каждой интерпретации), их взаимосвязь. Выразимость предиката равенства с помощью предикатной переменной (формула Лейбница).15. Модели данной системы аксиом. Следствия системы аксиом. Построение формулы, класс всех моделейкоторой состоит из всех множеств, имеющих мощность а) не менее n; б) не более n; в) ровно n. Записьутверждения о конечности множества изменения переменных с помощью функциональной переменной.16. Совместные и локально совместные системы аксиом.

Теорема компактности для элементарных языков (бездоказательства). Невозможность распространения её на случай неэлементарных языков.17. Язык арифметики. Стандартная интерпретация. Запись аксиомы математической индукции. АксиомыПеано и единственность их модели с точностью до изоморфии.18. Арифметические множества. Арифметичность объединения, пересечения, разности, прямого произведенияи проекции арифметических множеств.119. Основные понятия теории алгоритмов. Конструктивные объекты. Множество возможных исходных данных алгоритма. Пошаговый характер выполнения алгоритма. Возможные варианты развития процессаприменения алгоритма к исходным данным. Область применимости алгоритма. Функция, вычисляемаяданным алгоритмом.20.

Разрешимые множества. Разрешимость объединения, пересечения и дополнения разрешимых множеств.21. Вычислимые последовательности. Перечислимые множества. Перечислимость N2 . Перечислимость объединения и пересечения двух перечислимых множеств.22. Вычислимые последовательности. Перечислимые множества.

Перечислимость прямого произведения ипроекции перечислимых множеств.23. Разрешимые и перечислимые множества. Перечислимость области определения каждой вычислимой функции.24. Разрешимые и перечислимые множества. Теорема Чёрча – Поста (критерий разрешимости).25. Представление перечислимого множества в виде области определения вычислимой функции. Полуразрешимые множества. Полуразрешимость перечислимых множеств.26. Перечислимость области определения и области значений вычислимой функции. Перечислимость полуразрешимых множеств.27. Теорема о графике вычислимой функции.28.

Машины Тьюринга. Вычисление словарных функций на машинах Тьюринга. Теорема о возможности чистого вычисления словарной функции. Тезис Тьюринга.29. Машины Тьюринга. Теорема о вычислимость по Тьюрингу композиции функций.30. Машина Тьюринга.

Кодирование программ посредством слов в алфавите программ. Существование универсальной машины Тьюринга.31. Универсальные функции. Построение вычислимой универсальной функции для класса Com(N, N).32. Главные универсальные функции. Главность вычислимой универсальной функции, построенной по нумерации машин Тьюринга.33. Пример вычислимой функции, не продолжаемой до тотальной вычислимой функции. Существованиенеразрешимого перечислимого множества.34. Проблема остановки, ее алгоритмическая неразрешимость.35. Задача распознавания свойств вычислимых функций по их программам. Теорема Райса.36.

Задача распознавания истинности замкнутых арифметических формул, ее алгоритмическая неразрешимость.37. Отрицательное решение 10-й проблемы Гильберта.38. Теорема Тарского.22. Подробная программа курсаЭта программа наиболее соответствует курсу 2003 г.2.1. Предварительные понятияИмена и их денотаты.

Смысл знака равенства. Десятичная (двoичнaя, римская и т. п.) запись числа как имячисла; число как денотат своей записи. Как образуются имена русских слов, имена множеств и имена функций;лямбда-обозначения.Переменные и их области изменения (они же области значений). Сорта переменных. Именные формы (т.е.имена, зависящие от параметра). Свободные и связанные вхождения переменных. Явные и фиктивные переменные. Параметры именной формы.Множества, их элементы и подмножества. Знаки принадлежности «∈» и включения «⊂». Бинарные (они жедвуместные) операции над множествами: объединение, пересечение, разность. Объединение и пересечение произвольного множества множеств. Мощность множества.

Характеристическая функция множества относительноего надмножества. Разбиение множества.Функции из одного множества в другое, многоместные функции из одного множества в другое, их области определения, области значений и графики. Тотальные функции. Понятие одноместной, двуместной и т.д.операции на данном множестве. Композиция функций.Неупорядоченные пары, упорядоченные пары (или просто пары).

Кортежи. Прямое (или декартово) произведение двух или нескольких множеств; проекция на данные оси.Свойства, их области осмысленности и области истинности (объёмы).Отношения, их области осмысленности и области истинности (они же объёмы, они же графики).Виды отношений: рефлексивные, симметричные, транзитивные; эквивалентности. Инверсия, или обращение,отношения.Теорема о разбиении множества на классы эквивалентности (они же смежные классы).Отношения частичного порядка (называемые также просто отношениями порядка), строгие и нестрогие.Отношения линейного порядка, строгие и нестрогие.Частично упорядоченные множества (называемые также упорядоченными множествами).

Линейно упорядоченные множества. Наибольший, или первый, и наименьший, или последний, элементы. Максимальные иминимальные элементы. Плотные множества. Вполне упорядоченные множества.Сечения упорядоченных множеств и их виды: скачки, щели, дедекиндовы сечения. Аксиома Дедекинда длядействительных чисел.Предпорядок и индуцированная эквивалентность. Фактормножество и его упорядочение. Изоморфизм одного упорядоченного множества на другое. Понятие изоморфии упорядоченных множеств. Примеры изоморфныхи неизоморфных множеств.Алфавит, слово в данном алфавите, его длина. Пустое слово. Графическое равенство слов. Чем графическоеравенство отличается от обычного равенства? Конечные и бесконечные алфавиты.

Кортеж слов как слово врасширенном алфавите; текст как слово. Вхождение слова (в частности, буквы) в другое слово.Словарное пространство как множество всех слов в конечном алфавите, его лексикографическое и иныеупорядочения. Биекции между словарными пространствами. Словарные множества и словарные функции. Погружение прямого произведения двух словарных пространств в новое словарное пространство.Высказывания и их истинностные значения. Употребление знака «|=» для обозначения истинности высказывания. Равносильные высказывания и знак равносильности «≡».

Операции над высказываниями: отрицание,конъюнкция, дизъюнкция, импликация.Высказывательные формы. Свободные и связанные вхождения переменных. Явные и фиктивные переменные. Параметры высказывательной формы. Равносильность высказывательных форм.Знак «!» осмысленности выражения и знак «≃» условного равенства.2.2.

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

Равносильность формул.Тавтологии. Законы логики высказываний в форме тавтологий. Знак для обозначения тавтологий.Существование алгоритма для распознавания тавтологий.Законы логики в форме равносильностей: закон снятия двойного отрицания; законы ассоциативности, коммутативности и дистрибутивности; законы де Моргана.3Выражение одних логических операций через другие. Невыразимость отрицания через конъюнкцию, дизъюнкцию и импликацию.Безымпликативные формулы. Нормальные формулы.