Полнота исчисления предикатов

 

Рассмотрим полноту исчисления предикатов.

Определение:

Множество Т называется полным если для любой формулы исчисления предикатов существует вывод этой формулы из Т, либо существует вывод отрицания этой формулы

Т.е. для "Е ∈ ИП существует вывод Т ⊢ Е или Т ⊢ Е

Теорема о выполнимости:

Всякое непротиворечивое множество выполнимо

Г – непротиворечиво => Г – выполнимо

Рассмотри вспомогательную Лемму для доказательства теоремы.

Для любого непротиворечивого множества S существует более полное непротиворечивое множество включающее в себя множество S т.е. S c T где Т – полное множество

Пусть существует множество S и множество φ S при этом S φ причем если φ добавить в S, то – непротиворечиво

Рассмотрим иерархию множеств

S c c …

Процесс включения будет продолжаться пока не получится некоторое максимальное непротиворечивое множество включающее S. Его получим т.к. множество всех формул больше чем любое множество непротиворечивых формул.

- даст уже противоречивое множество, где "f и f

Т.е. существует формула, Ψ для которой существует , f ⊢ Ψ и , f ⊢ Ψ одновременно

По правилу введения отрицания можем записать что ⊢ f, а это означает что максимальное непротиворечивое множество является полным т.е.

Полное т.е. f зато существует. ⊢ f

 

Теорема

Всякое непротиворечивое множество выполнимо, следовательно, существует такая интерпретация, при которой все формулы множества истинны.

 

I: <M, >, где М – объектное множество, δ – множество отношений, <M, > - модель

М = {x₁,…,x_n,y₁,…,y_n}

 

Pⁿ(x₁,…,x_n)^(I)=

 

Р Т – полное, непротиворечивое множество

 

Доказать, что на модели <M, >: А^(I)= И T A

 

Доказательство:

(По индукции)

1) База индукции

А = Pⁿ(x₁,…,x_n) – по определению ;

2) Шаг индукции

1. А = А₁

2. А = А₁ А₂

3. А = А₁ & А₂

4. А = А₁ А₂

5. А = А₁ А₂

6. A = x A₁

7. A = x A₁

 

Докажем, что если для формул A₁, А₂ выполняется:

А₁^(I)= И, А₂^(I)= И Т ⊢ А₁, Т ⊢ А₂

То для формулы А выполняется:

А^(I)= И T ⊢ A

 

1. А = А₁

Необходимость

Докажем, что для А = А₁ теорема выполняется.

А^(I)= И А₁^(I)= Л Т ⊢ А₁ T ⊢ А

 

Достаточность

T ⊢ А т.к. Т – полное, непротиворечивое множество, то: Т ⊢ А₁ Т ⊬ А₁ А₁=Л А=А₁=И

 

3. А = А₁ & А₂

Необходимость

А^(I)= И А₁=И и А₂=И Т⊢ А₁ и Т ⊢ А₂ //по правилу введения И// Т ⊢ А₁ & А₂ T ⊢ А

 

Достаточность

(от противного)

Т ⊢ А₁ & А₂. Пусть А₁ & А₂ = А = Л

Т.к. Т ⊢ А₁ & А₂ // по правилу удаления И// А₁ & А₂ →А₁ //modus ponens// А₁ Т ⊢ А₁ ; Т ⊢ А₂

А₁ = Л или А₂ = Л Т ⊬ А₁ или Т ⊢ А₂

Противоречие! А^(I) = А₁^(I) & А₂^(I) = И

 

 

В рассматриваемой интерпретации для любого значения предиката значение формулы истинно, если А^(I)=И Т ⊢ А

Поскольку S T для f S T ⊢ f. Если выводятся все f S - истинны: f^(I) = И множество S – выполнимо.

Теорема (о полноте)

Любая общезначимая формула доказуема.

|= E ⊢E

 

Доказательство:

Е^I=И Е^I = Л {E} – невыполнимо. По теореме о выполнимости {E} – противоречиво существует формула ψ для которой E ⊢ ψ; E ⊢ ψ //по правилу введения НЕ// ⊢E (формула Е – доказуема) ч.т.д.

 

Другие теоремы

 

Теорема (о непротиворечивости)

Любое выполнимое множество формул является непротиворечивым.

Ф – выполнимо Ф – непротиворечиво

 

Доказательство:

(от противного)

Пусть Ф – выполнимо, но противоречиво найдется формула ψ, для которой можно вывести противоречие.

Ф ⊢ (ψ & ψ) существует некая конечная последовательность формул , , …, ψ & ψ Ф¹=Ф { ,…, } ⊢ ψ & ψ //по теореме о дедукции// ⊢ ( …( (ψ & ψ)…)

 

Но т.к. любая доказуемая формула является общезначимой //по теореме о полноте//

( …( (ψ & ψ)…) //по теореме импликации и следования// … ψ & ψ

(связаны отношением следования)

Т.к. (ψ & ψ)^I=Л => (Ф¹) =Л – невыполнимо Ф – невыполнимо. Противоречие! Ф – выполнимо и непротиворечиво.

 

 

Теорема Мальцева (теорема компактности)

Если множество выполнимо, то выполнимо любое его конечное подмножество.

Ф – выполнимо S – выполнимо, S Ф и S – конечно.

 

Необходимость: Доказательство опустим.

 

Достаточность:

Предположим, что все S- выполнимы, а Ф – невыполнимы Ф – противоречиво (по теореме о выполнимости) найдется такая формула ψ, для которой Ф ⊢ ψ & ψ (вывод всегда конечен) S Ф, S – конечно, S ⊢ ψ & ψ S является противоречивым. Противоречие! Ф – выполнимо.

 

 

Теорема (об адекватности)

Если формула ϕ следует из множества формул Ф, то формула ϕ выводится из Ф.

Ф Ф ⊢

 

Необходимость:

Ф { } – невыполнимо противоречиво найдется такая формула ψ, что можно вывести и ψ и ψ т.е. Ф, ψ ⊢ ψ и Ф, ψ ⊢ ψ Ф ⊢

 

Достаточность:

Уже доказывали (теорема 1) Ф ⊢ Ф

Семантический и синтаксический подходы эквивалентны как в исчислении предикатов, так и в исчислении высказываний.

 

 

Алгоритмические модели

Понятие алгоритма

Алгоритм – последовательность действий приводящая к получению определенного результата из исходных данных за конечное число действий.

Такое определение алгоритма является интуитивным понятием.

Алгоритмические проблемы:

1. Алгоритмическая разрешимость. Имеет ли данная задача алгоритм решения?

2. Наибыстрейший алгоритм решения. Определение нижней границы сложности решения.

В рамках интуитивного определения алгоритма нельзя разрешить данные алгоритмические проблемы, поэтому рассмотрим, что именно в интуитивном понятии алгоритма нуждается в уточнении.

1. Что такое данные (алгоритмический объект)

2. Память. Способ хранения и представления данных

3. Элементарное действие, команда

4. Последовательность порождения операций, шагов

5. Что есть результат

6. Способ реализации

Однозначного определения данных понятий для алгоритма не было найдено. Таким образом алгоритм есть фундаментальное интуитивно ясное, но неопределяемое понятие. Поэтому в теории алгоритмов принят подход, основанный на конкретной алгоритмической модели.

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

Классы моделей:

1. Класс как описание некоторого технического устройства: машина Тьюринга, машина прямого доступа, машина Поста.

2. Описание алгоритма как некоторого класса функций с определенными способами их образования: частично рекурсивные функции(исторически первая формализация понятия алгоритма).

3. Набор правил по преобразованию слов: алгорифм Маркова.

 

Машины Тьюринга