2.5. Интерпретация формальных теорий

Интерпретацией формальной теории в область интерпретации М называется функция, которая каждой формуле формальной теории ставит в соответствие некоторое содержательное высказывание относительно объектов множества М. Если соответствующее высказывание истинно, то говорят, что формула выполняется в интерпретацииI.

Интерпретация называется моделью множества формул Г, если все формулы выполняются в данной интерпретации.

Если формула истинна в любой интерпретации, то это тавтология, если формула ложна в любой интерпретации, то это противоречие.

Формальная теория называется семантически непротиворечивой, если ни одна ее теорема не является противоречием.

Модель для формальной теории существует тогда и только тогда, когда она семантически непротиворечива.

Формальная теория формально непротиворечива, если в ней нельзя одновременно вывести формулуFи ее отрицание.

Формальная теория называется полной, если каждому истинному высказыванию модели М соответствует теорема теории.

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

Формальная теория называется разрешимой, если существует алгоритм, который определяет, является ли формула теоремой теории.

2.6. Исчисление высказываний.

Опишем формальную теорию исчисления высказываний.

Исчисление высказываний – это формальная теория £, которой:

1. Алфавит:

• - буквы (A,B,…Z);

• - специальные символы ⌐ → ( ).

2. Формулы:

• любая буква A,B,…Z– формула;

• если А, В – формулы, то (А), (⌐А), (А→ В) – формулы.

3. Аксиомы:

1. А1:

2. А2:

3. А3:

Выражения А1-А3 называются схемами аксиом, т. к. каждая из них порождает бесконечное множество формул. Вместо А, В и С можно подставлять любые формулы.

4. Правило вывода: правило modusponens(m.p.):

AиB- любые формулы. Т. о. множество аксиом теории £ - бесконечно. Множество правил вывода также бесконечно.

2.7. Производные правила вывода

Исчисление высказываний £ достаточно богатая формальная теория, в которой можно вывести многие правила вывода.

Теорема 1.

- закон тождества.

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

1. А1: . Выполним замену {}. Получим:

.

2. А1: . Выполним замену{}. Получим:

.

3. Из 1 и 2 по правилу m.p. получим:

.

4. A1:{A/B}. Получим:.

5. Из 3 и 4 по правилу m.p. получим.

Теорема 2

А- добавление антцедента.

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

1. А - гипотеза

2. А1:

3. Из 1 и 3 по правилу m.p. получаем

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

Если имеется множество общезначимых формул, то из него можно вывести только общезначимые формулы.

2.8. Дедукция

В теории £ импликация тесно связана с выводимостью. Теорема дедукции используется при доказательстве теорем, т. к. дает нам новое правило вывода.

Теорема (дедукции). Если Г – множество формул, А и BГ иA|-_£B, то Г|-А→В.

В частности A|-B, то А→В.

Доказательство. Пусть E₁,E₂,….E_nвыводBиз Г,A.E_n=B. Покажем, что Г|-_£А→E_i,.

Пусть i=1.

Возможны 3 случая.

1) Пусть Е₁– аксиома. Тогда рассмотрим вывод:

1. Е₁

2. А1: . Выполним замену {А/Е1, В/А}. Получим:

3. Из 1 и 2 по правилу m.p. получаем |-_£А→E₁.

2) Пусть Е₁Г. Доказательство аналогично 1).

3) Пусть Е₁А. Тогда по закону тождества (теорема1), следовательно,

Таким образом Г.

Пусть i<k. Рассмотрим выводE_k. Возможны 4 случая:

1) E_k– аксиома.

2) Е₁Г.

3) Е₁А.

4) E_kполучена из формулE_i иE_jпо правилуm.p., причемi,j<kиE_i=E_jE_k.

Для 1), 2), 3) доказательство аналогично доказательству при i=1.

Для 4) случая:

1. (i)

2. (j)

3. А2: . Выполним подстановку {E_i/B,E_k/C}, получим(n)

4. По правилу m.p. из (j) и (n) получаем(n+1)

5. По правилу m.p. из (j) и (n+1) получаем(n+2) ч.т.д.

Таким образом, для любогоk, в том числе приk=n. НоE_n=B.

Схема аксиом A3 теории £ в доказательстве не использовалась, поэтому теорема дедукции имеет место для более широкого класса теорий, чем £.

Следствие 1.Если, тои обратно.

Доказательство. По теореме дедукции, если , то. Пусть Г={0}. Тогда имеем Следствие 1.

Следствие 2.(правило транзитивности).

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

1. Гипотеза .

2. Гипотеза с.

3. Гипотеза А.

4. По правилу m.p. из 1 и 3 получаемB.

5. По правилу m.p. из 2 и 4 получаемC

6. Из 1-5 получаем: если ,- гипотезы Г, то.

7. По теореме дедукции .

Следствие 3.(правило сечения).

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

1. Гипотеза .

2. Гипотеза A.

3. По правилу m.p. из 1 и 2 получим.

4. В – гипотеза.

5. По правилу m.p. из 3 и 4 получим С.

6. Из 1-5 получаем:

7. по теореме дедукции .