Теоремы об общезначимых формулах в исчислении высказываний и в исчислении предикатов.

Теоремами исчисления высказываний являются тождетвенно истинные формулы и только они:

-тавтология.

Док-во

1.(->) Аксиомы любой системы являются тавтологией. Правило заключения сохраняет тавтологичность => теоремы исчисления высказываний это тавтология.

2.(< -) Пусть формула А-тавтология, тогда в любой интерапритации (по лемме), таким образом имеется различных выводимостей: среди них есть 2 различающиеся по значению А'n принадлежит либо либо : и по теореме дедукции отсюда имеем и по теореме 3е выполняется следующее применяем 2 раза правило MP, получаем . Повторить весь процесс ещё n-1 раз докажем выводимость => A выводимо из не нулевого множества гипотез => А теорема.

Теорема об общезначимых формулах

– теоремами ИП являются общезначимые формулы и только они.

Док-во:

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

2) Доказал впервые Гёдель. Оно сложнее и не приводится в этом курсе.

Опр. Две формулы F и G эквивалентны, если F G

Из теоремы об общезначимых формулах ИП следует, что между соотношениями ЛП и формальными эквивалентностями в ИП имеются аналогичные соответствия.

F G .

11. Примитивно рекурсивные функции: базовые функции и элементарные операции. Примеры примитивно рекурсивных функций.

Базовые фукции.

Простые одношаговые рекурсивные функции называются базовыми.

1)Нуль функция 0(х)=0

2)Функция тождества(проектирующая функция, функция введения фиктивных переменных) , где , если

3)Функция следования(прибавление единицы)

*эта функция позволяет по числу построить сколь угодно большой начальный отрезок множества натуральных чисел

Элементарные операции.

Операции, с помощью которых можно получить из базовых функций рекурсивные называются элементарными.

1) Операция суперпозиции

Говорят, что n-местная функция получена с помощью операторов суперпозиции из m-местной функции и n-местных функций , …, , если …, )

2) Операция примитивной рекурсии

Говорят, что n+1-местная функция получена из n-местной и n+2- местной с помощью операции примитивной рекурсии если ее значения можно вычислить по формуле:

При n=0 схема примитивной рекурсии имеет вид

Будем говорить что функция получена из функции с помощью итераций

если:

Примеры:

1) Базовые функции

2) 0( – ПРФ, так как 0( =0( (, …, ), т.е. получаем из базовых функций 0(x) и

3) f(x)=x+n т.к. f(x)=x

4) – ПРФ т.к. ее можно получить из функций тождества и следования с помощью оператора примитивной рекурсии.

(

5) – ПРФ т.к. ее можно получить из 0 и сложения с помощью оператора примитивной рекурсии.

6) Поскольку ПРФ должны быть определены на всем N, то вместо обычной разности в теории рекурсивной функции вводят арифмитическую или усеченную разность:

x-y (всюду ниже в этом билете над минусом ставится точка)

x-y=

функция x-1

7) Cигнум

sgn(x)=

sgn(x, y)= => sgn(x, y)=sgn(x-y)

К этим двум функциям можно ввести дополнительные: