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

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

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

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

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

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 является усвоение необходимости формулировать алгоритмические проблемы как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождение такого алгоритма в случае, если он существует.

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

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

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

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

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

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