В.А. Успенский - Программа экзамена по дискретной математике (1107941), страница 2
Текст из файла (страница 2)
Дизъюнктивные и конъюнктивные нормальные формулы. Приведение произвольной формулы к нормальному виду, к дизъюнктивному (конъюнктивному) нормальному виду.Операция на множестве {и, л}, выражаемая данной формулой (при данном списке переменных). Существование для любой n-местной операции выражающей формулы.2.3. Язык упорядоченных множествАлфавит языка упорядоченных множеств. Правильно построенные выражения (они же формулы языкаупорядоченных множеств). Атомные формулы.Запись на языке упорядоченных множеств аксиом порядка (строгого и нестрогого), аксиом линейного порядка, аксиом плотного порядка.Свободные и связанные вхождения переменных в формулу.
Подстановка имён вместо свободных вхожденийпеременных.Расширение алфавита языка за счёт введения имён элементов. Смысл кванторов при задании области изменения подкванторной переменной.Интерпретация формулы на данном упорядоченном множестве в виде высказывания или высказывательнойформы. Формулы, тождественно истинные на данном упорядоченном множестве. Равносильность формул наданном упорядоченном множестве.Бескванторные формулы, нормальные бескванторные формулы, дизъюнктивные и конъюнктивные нормальные бескванторные формулы. Приведение бескванторной формулы к нормальному, дизъюнктивному нормальному, конъюнктивному нормальному виду.Переименование связанных переменных и ограничения на такое переименование. Выражение квантора существования через квантор общности и обратное выражение.Возможности выноса квантора наружу за знаки отрицания, конъюнкции, дизъюнкции.Предварённые формулы и приведение формулы к предварённому виду.Ограничения на подстановку одной переменной вместо другой.
Разрешенные, или свободные, подстановки.Теорема о свободной подстановке: B(q/x)(q/y) графически равно B(y/x)(q/y) (здесь B — формула, q — имяили переменная, x и y — переменные, а подстановка y вместо x — свободная).Следствие теоремы о свободной подстановке: ∃x(x = y & B) ≡ B(y/x).Теорема об устранении кванторов для формул, рассматриваемых на плотных линейно упорядоченных множествах без первого и последнего элементов.Понятие элементарной эквивалентности упорядоченных множеств. Элементарная эквивалентность плотныхлинейно упорядоченных множеств без первого и последнего элементов.Понятие разрешимой теории. Разрешимость теории плотных линейно упорядоченных множеств без первогои последнего элементов.Понятия интерпретации языка упорядоченных множеств, системы аксиом в этом языке, модели системыаксиом.2.4.
Языки логики предикатовПонятие s-местного предиката (отношения) на данном множестве. Соответствие между предикатами и подмножествами. Предикатные константы, или имена, и их валентность. Предикатные переменные и их валентность.Понятие s-местной операции на данном множестве. Функциональные константы, или имена, и их валентности. Функциональные переменные и их валентности.Алфавит языка, логики предикатов: запятая, скобки, логические связки, кванторы; индивидные константы(они же индивидные имена), предикатные константы (они же предикатные имена), функциональные константы(они же функциональные имена), индивидные, функциональные и предикатные переменные.Термы, атомные формулы, формулы.
Элементарные формулы. Замыкание всеобщности. Равносильные формулы. Понимание того, что основные равносильности и графические равенства, установленные для языка упорядоченных множеств, справедливы и для любого языка логики предикатов.Записать:••••На языке логики предикатов аксиомы строгого, нестрогого, линейного и плотного порядкаУтверждение о бесконечности множества изменения переменных с помощью функциональной переменной.Аксиому Дедекинда и определение вполне упорядоченного множества.Определение упорядоченного множества, изоморфного натуральному ряду.4• Аксиомы упорядоченного множества, группы, кольца, поля, упорядоченного кольца, упорядоченного поля.• Аксиомы евклидовой геометрии.2.5.
Структуры и сигнатуры, интерпретации и моделиПонятия элементарной математической структуры (в дальнейшем, для краткости, просто структуры) и еёносителя. Упорядоченные множества, группы, кольца, поля, упорядоченные кольца, упорядоченные поля, геометрия, натуральный ряд N, множество действительных чисел R как структуры.Сигнатура данной структуры как множество имён (они же константы), снабженных валентностями. Сигнатуры структур предыдущего абзаца.Понятия изоморфизма и изоморфии структур одинаковой сигнатуры.Язык данной сигнатуры, его алфавит, его термы и его формулы.
Элементарные и неэлементарные языки.Интерпретация сигнатуры (она же интерпретация языка). Какой смысл приобретают формулы при той илииной интерпретации? Выражение I |= F для обозначения того, что формула F истинна (если она закрытая)или тождественно истинна (если она открытая) в интерпретации I. Равносильность формул при данной интерпретации.Общезначимые формулы. Знак «|=» для обозначения общезначимости.Два способа выражения законов предикатной логики: посредством общезначимых формул и посредствомравносильностей, справедливых при любой интерпретации.
Формула Лейбница. Теорема: F1 ≡ F2 тогда и толькотогда, когда общезначима формула (F1 ⇒ F2 ) & (F2 ⇒ F1 ).Система аксиом как произвольное множество закрытых формул рассматриваемой сигнатуры. Модели даннойсистемы аксиом. Построение для каждого натурального n формулы, для которой произвольное множество тогдаи только тогда является носителем какой-нибудь её модели, когда это множество имеет мощность: 1) не менееn; 2) не более n; 3) n; 4) конечную; 5) бесконечную.Понятие следствия системы аксиом.
Запись S |= F того факта, что формула F есть следствие системыаксиом S. Теорема:A1 , . . . , An |= Fтиттк |= (A1 & · · · & An ) ⇒ F .Совместные и локально совместные системы аксиом. Теорема компактности (без доказательства) для элементарных языков и её опровержение для языков неэлементарных.Существование нестандартных моделей системы аксиом арифметики.Элементарная эквивалентность структур. Полные системы аксиом.Понятие независимой аксиомы.2.6.
Язык арифметикиСигнатура языка, термы и формулы. Главная, или стандартная, интерпретация. Арифметические истины.Запись аксиомы математической индукции. Аксиомы Пеано и единственность их модели с точностью доизоморфии.Определение арифметического множества. Арифметичность множества всех чётных чисел, множества всехпростых чисел. Арифметичность трёхмерного множества(a, b, m) | a ≡ b mod m .Существование неарифметических множеств.Арифметичность объединения, пересечения, разности, прямого произведения, проекции арифметическихмножеств.2.7. Алгоритмы, машины Тьюринга и вычислимые функцииОбщее понятие алгоритма; вход и выход алгоритма. Неформальное понятие конструктивного объекта ивозможность представления конструктивных объектов словами в подходящем алфавите.
Область возможныхвходов, или возможных исходных данных, область возможных выходов, или возможных результатов, областьрезультативности. Три варианта протекания алгоритмического процесса. Как избавиться от безрезультатнойостановки.Функция, вычисляемая данным алгоритмом. Понятие вычислимой функции одного или нескольких аргументов.Представление о шаге алгоритма. Сигнализирующее множество алгоритма. Машина Тьюринга (она задаётсяленточным алфавитом, алфавитом внутренних состояний и программой).
Кодирование программ посредствомслов восьмибуквенного алфавита (алфавита программ).5Слабое (или в слабом смысле) и сильное (или в сильном смысле) вычисление функций из X m в X намашине Тьюринга. Понимание того, что, для фиксированных X и m, каждая машина вычисляет в слабомсмысле какую-то функцию из X m в X. Теорема: всякое слабое вычисление может быть заменено сильным (нона другой машине).Понятие функции, вычислимой по Тьюрингу. Существование функций из X m в X, не вычислимых по Тьюрингу.Теорема: если две функции вычислимы по Тьюрингу, то их композиция вычислима по Тьюрингу.Тьюрингова универсальная функция, дающая по слову p в алфавите программ P и по элементу x словарного пространства X, значение функции, вычисляемой в слабом смысле программой p, применённой к x (еслиp не есть программа, то никакого результата, естественно, не возникает).
Теорема: если F — тьюрингова универсальная функция, то для любой вычислимой по Тьюрингу функции g : X 2 → X найдётся такая тотальнаявычислимая функцияh : X → P ∗ , что ∀ k ∈ X λx g(k, x) = λx F h(k), x .Тезис Чёрча в версии Тьюринга.2.8. Разрешимые и перечислимые множестваРазрешимые множества в словарных пространствах. Характеризация разрешимости множества в терминахвычислимости характеристической функции. Примеры разрешимых числовых множеств.
Разрешимость множества программ в словарном пространстве алфавита программ. Разрешимость сигнализирующего множества.Разрешимость объединения, пересечения, разности, прямого произведения разрешимых множеств.Вычислимые последовательности и перечисляемые ими множества. Перечислимые множества. Перечислимость любого конечного множества, любого словарного пространства. Теорема: всякое бесконечное перечислимое множество допускает перечисление без повторений. Существования вычислимой биекции между бесконечными перечислимыми множествами.Перечислимость объединения, пересечения, прямого произведения, проекции перечислимых множеств.Теорема Чёрча – Поста: словарное множество разрешимо тогда и только тогда, когда перечислимо и оносамо, и его дополнение.Теоремы: 1) проекция всякого разрешимого множества перечислима; 2) всякое перечислимое множество является областью определения некоторой вычислимой функции; 3) область определения всякой вычислимой функции является проекцией некоторого разрешимого множества; 4) область значений всякой вычислимой функцииперечислима.Характеризация вычислимости функции в терминах перечислимости её графика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
