МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Метасимволика и.В. И и.П.
Г- множество посылок (гипотез). Обычно Г записывают в виде Г=А1, А2,…, Аn (Г читается как “гамма”)
Ф – теорема; Аi – метаформула; R(J) – множество правил вывода в исчислении;
| - символ отношения дедуктивного вывода.
Пример. Запись Г|Ф ( из гипотез Г дедуктивно выводима формула Ф) означает А1, А2,…, Аn |Ф, или А1, А2,…, Аn
Ф
Пример. Запись |А означает, что А доказуема.
Пример. Запись А1, А2,…, Аn | означает, что множество посылок противоречива.
Пример. |=, 1 |= 2, 1 | 2 – метавысказывания.
Замечание. Специфика отношений |= и | в том, что в отличие от логических связок (отношений отрицания, конъюнкции, дизъюнкции) они реализуются не на денотатах высказываний, а на пропозициональных формулах.
Yandex.RTB R-A-252273-3Содержание
- Математическая логика
- Парадигмы формальной логики.
- Предмет, цель, задачи и содержание читаемого курса лекций.
- Место читаемого курса о законах и формах правильного мышления.
- Концептуальный базис математической логики.
- Построение математической логики.
- Классическая логика высказываний.
- Язык классической логики предикатов (я.Л.П.).
- Примеры:
- Алгебра логики предикатов.
- Пояснения:
- Квантификация предикатов.
- Эквивалентные преобразования кванторных формул.
- Классические логические исчисления.
- Цель классических и.В. И и.П.
- Метасимволика и.В. И и.П.
- Построение логических исчислений.
- Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.
- Основные требования к алгоритмам.
- Основная терминология теории алгоритмов.
- Основные теоремы теории алгоритмов.
- Параметры алгоритма.
- Основная гипотеза теории алгоритмов.
- Алгоритмические (формальные математические) модели.
- Блок-схемы алгоритмов.
- Машина Тьюринга. Машина Тьюринга т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.
- 1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
- Формальное определение машины Тьюринга.
- Основной тезис Тьюринга.
- Нормальные алгорифмы (алгоритмы).
- Рекурсивные функции.
- Примитивно-рекурсивные функции.
- Оператор минимизации (- орератор).
- Основной тезис Черча.
- Алгоритмически неразрешимые проблемы.