Алгоритмы и вычислимость

Содержание дисциплины

Начальные сведения

1. Множества

1. Понятие множества

2. Подмножества

3. Пересечение и объединение множеств

4. Разность множеств. Дополнение множества

5. Свойства операций над множествами

6. Диаграммы Эйлера – Венна

7. Прямое произведение множеств

2. Отображения и соответствия

1. Понятие отображения

2. Специальные виды отображений

3. Операции

4. Характеристические функции

5. Соответствия

6. Композиция соответствий

3. Отношения

1. Понятие отношения

2. Свойства бинарных отношений

3.Отношения эквивалентности

4. Натуральные числа

1. Натуральный ряд

2. Метод математической индукции

Логика высказываний

1.1. Высказывания и операции над ними

1.2. Формулы логики высказываний

1.3. Равносильность формул

1.4. Принцип двойственности

1.5. Тождественно истинные формулы

1.6. Система натурального вывода

1.7. Принцип резолюций

Логика предикатов

2.1. Понятие предиката

2.2. Логические операции над предикатами

2.3. Кванторы

2.4. Формулы логики предикатов и логические законы

2.5. Выполнимые формулы и проблема разрешения

2.6. Логика предикатов и математическая практика

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

3.1. Формализация в математике

3.2. Исчисление высказываний

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

3.4. Теории первого порядка. Формальная

арифметика

Алгоритмы и вычислимость

4.1. Мощность множества

4.2. Счетные множества

4.3. Диагональный метод Кантора

4.4. Уточнение понятия алгоритма

4.5. Рекурсивные функции

4.6. Вычислимость и разрешимость