Классические логические исчисления.

Понятие “исчисление” является экспликацией интуитивных понятий “вывод”, “доказательство”, “оперирование”, “вычисление”.

В математической логике исчисление является частным случаем формальных (дедуктивных) систем F.S. вида <L, D>, задаваемое правилами синтаксиса (образования) языковых выражений и правилами построения выводов (дедуцирования). В том случае, если в исчислении не выделяют аксиомы, то говорят о натуральных исчислениях.

Ниже будем изучать классические исчисления высказываний (И.В.) и предикатов (И.П.) как гомоморфные отображения (модели) логики высказываний и логики предикатов.

Цель классических и.В. И и.П.

Целью И.В. и И.П. является описание кланов всех общезначимых (тождественно-истинных) формул (часто называемых тавтологиями, или законами).

Метасимволика и.В. И и.П.

Г- множество посылок (гипотез). Обычно Г записывают в виде Г=А₁, А₂,…, А_n (Г читается как “гамма”)

Ф – теорема; А_i – метаформула; R(J) – множество правил вывода в исчислении;

| - символ отношения дедуктивного вывода.

Пример. Запись Г|Ф ( из гипотез Г дедуктивно выводима формула Ф) означает А₁, А₂,…, А_n |Ф, или А₁, А₂,…, А_n

Ф

Пример. Запись |А означает, что А доказуема.

Пример. Запись А₁, А₂,…, А_n | означает, что множество посылок противоречива.

Пример. |=, ₁ |= ₂, ₁ | ₂ – метавысказывания.

Замечание. Специфика отношений |= и | в том, что в отличие от логических связок (отношений отрицания, конъюнкции, дизъюнкции) они реализуются не на денотатах высказываний, а на пропозициональных формулах.

Построение логических исчислений.

Построение (задание) исчислений качественно отличаются видом аксиоматики – конечным или бесконечным множеством аксиом.

Аксиома – формула объектного языка, в рамках которого строится исчисление. Система аксиом – конечное множество аксиом. Бесконечное множество аксиом задается перечислением конечного множества схем аксиом. Схема аксиом – выражение метаязыка, представляющее бесконечное множество формул определенной структуры.

КЛАССИЧЕСКОЕ И.В.

Ниже рассмотрим различные И.В., отличающиеся аксиоматикой. Задание классического И.В. в Я.Л.В. будем осуществлять с привлечением схем аксиом и одного вывода.

a) I₁ A

I₂ (AB)((A)

I₃ (AB) ((A(BC)) (AC

I₄ (AB)

I₅ (AB)B

I₆ A (B (AB))

I₇ A (AB)

I₈ B (AB)

I₉ (AC) ((BC) ((AB)C))

I₁₀ 

Правило вывода для этой аксиоматики – правило модус-поненс (Modus ponens, m.p.), часто называемого правилом отделения:

ТЕОРИЯ АЛГОРИТМОВ.

Вводные положения.

Теория алгоритмов- раздел математической логики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения.

Основное понятие этой теории – алгоритм – в интуитивном (наивном) понимании существует в математике довольно давно, а точные математические понятия, которые в том или ином смысле формализуют интуитивное понятие алгоритма, предложены только в середине 30-х годов 20-го века. Необходимость такой формализации была обусловлена как вопросами обоснования математики, так и вопросами доказательства алгоритмической разрешимости и неразрешимости тех или иных задач. Очевидно, что в математике доказываемый объект должен быть точно определен.

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

Замечание:

Абстрактная дескриптивная теория алгоритмов не учит строить конкретные алгоритмы. Этим занимается прикладная метрическая (количественная) теория алгоритмов. В отличие от абстрактной теории алгоритмов прикладная теория рассматривает не только детерминированные, но также вероятностные (стохастические) и эвристические алгоритмы. В последнем случае, кроме детерминированных или статически заданных правил, алгоритм включает также содержательные указания о целесообразном направлении процесса.

Предмет и содержание читаемого курса.

Предметом изучения в читаемом курсе являются формальные уточнения интуитивного понятия «алгоритм» с различных точек зрения: арифметизации, нормализации и построения абстрактной машины. Целью читаемой дисциплины студентам специальности 2201 является усвоение необходимости формулировать алгоритмические проблемы как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождение такого алгоритма в случае, если он существует.

Содержанием курса являются следующие вопросы:

• языки операндов и алгоритмические языки;

• рекурсивные функции как математический вариант уточнения понятия вычислимой арифметической функции;

• машины Тьюринга как математический эквивалент для общего интуитивного представления об алгоритме;

• нормальный алгоритм Маркова;

• сложность алгоритма.