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

Для построения формализованной аксиоматической теории исчисления нужно:

1. Задать алфавит этой теории (т.е. конечную или счётную последовательность символов, в которых будет записана эта теория).

2. Среди всех слов в теории выделить формулы, т.е. слова которые будут являться формулами.

3. Среди формул выделить аксиомы, т.е. такие формулы из которых может быть построена вся теория. Они должны соответствовать тавтологиям в алгебре высказываний.

4. Определить правила получения новых формул из аксиом, т.е. правила вывода или правила доказательства теорем.

Опр. Выводом (доказательством) формулы F из совокупности формул Г={Г1,Г2,…..,Гk} называется последовательность формул В1,В2,……Вn, в которых:

1. Последняя формула совпадает с выводимой формула Вn=F.

2. Каждая формула этой совокупности является либо аксиомой, либо одна из формул совокупности Г, либо получена из предыдущих с помощью правила вывода(Вi).

Алфавит исчисления высказываний состоит из символов трех категорий:

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

Переменные высказывания будем называть элементарными формулами.

Приведем примеры формул исчисления высказываний.

Переменные высказывания являются формулами согласно п.1 определения формулы. Но тогда слова являются формулами согласно      п.2 определения. По этой же причине будут формулами слова:

Очевидно, не являются формулами слова: поскольку одни из них не взяты в скобки, в других скобка лишь одна,…

Одновременно с понятием формулы вводится понятие подформулы или части формулы.

1. Подформулой элементарной формулы является она сама.

1. Если формула имеет вид, то ее подформулами являются: она сама, формула А и все подформулы формулы А.

2. Если формула имеет вид (А*В)(здесь и в дальнейшем под символом * будем понимать любой из трех символов), то ее подформулами являются: она сама, формулы А и В и все подформулы формул А и В.

Таким образом, по мере “погружения вглубь структуры формулы” мы выделяем подформулы все большей глубины.

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

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

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

Из формулы x, x–›y можно отделить или выводима формула y (x,x–›y|-y)

Утверждение1.

Для любой формулы F исчисления высказываний формула |-(F–›F) (является теоремой, т.е. она доказуема, выводима из аксиом.

Утверждение2.

Если формула F является теоремой, то для любой формулы G, формула |-G–›F тоже является теоремой.

Теорема дедукции.

Следствие из теоремы дедукции.

1 Следствие: Формула G выводима из совокупности гипотез Г1,Г2,…..,Гk тогда и только тогда, когда из совокупности гипотез Г1,Г2,…..,Гk-1 выводима формула Гk –› G

2 Следствие: Формула G выводима из совокупности гипотез Г1,Г2,…..,Гk тогда и только тогда, когда (Г1 –›(Г2 –›….. –›(Гk-1 –›(Гk)….).

 

Законы логики.

 

1.  правило силлогизма (цепного заключения) (А®В), (В®С) |-А®С

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

1) (А®(B®С))®(A®С)

2) А®(В®С)=u, т.к. В®С=u

3) А®С

Итак, А®В, В®С|-А®С. Очевидно, т.к. А®С выводимо из А®В и В®С, то |= (А®В)(В®С)®(А®С) и |=(А®В) ® ((В®С)®(А®С))

2. Правило перестановки посылок (А®(B®С)) |-(В–›(A®С))

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

1) А®(B®С гипотеза

2) А гипотеза

3) В гипотеза

4) Из 2,1 МР В –› С

5) Из 3,4 МР С

3.    Правило введения двойного отрицания А |- ⌐⌐А

4. Правило (А –›В) |-(⌐⌐А –›⌐⌐В)

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

1) А–›В гипотеза.

2) ⌐⌐А гипотеза.

3) Правило снятия двойного отрицания.

4) 2,3 МР А.

5) 4,1 МР В.

6) Правило введения двойного отрицания.

7) 5,6 МР ⌐⌐В

5. Второй закон контрапозиции А–›В|-(⌐В–›⌐А).

6. Первый закон контрапозиции ⌐В–›⌐А|-В–›А

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

1) ⌐В–›⌐А гипотеза

2) В гипотеза

3) А3. Y=A, X=B (⌐В–›⌐А) –›((⌐А–›В) –›А)

4) 1,3 МР (⌐А–›В) –›А

5) А1. X=B Y=⌐A (B–›(⌐A–›B)

6) 2,5 ⌐A–›B

7) 6,4 МР А

7. Первый закон противоречия  А,⌐А|-В (|-А–›(⌐А–›В))

8. Второй закон противоречия ⌐А–›В, А–› В |- В

9. Закон отрицания импликации А, ⌐В |- (⌐(А–›В))   (|-А–›(⌐В–›(⌐(А–› В))))

Полнота исчисления высказываний.

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

Теорема1. Всякая теорема исчисления высказываний является тавтологией.

(если |- A, то |=A), (если А является теоремой, то она тождественно истинная).

Теорема2. Любая тождественно истинная формула алгебры высказываний является теоремой исчисления высказываний. Если |=А’, то |-A

Теорема3. Исчисление гипотез является полным.

Непротиворечивость ИВ.

Непротиворечивость ИВ.

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

1) ИВ противоречиво, если формула А выводима в немИВ непротиворечиво, если оно не является противоречивым.

 

Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений.

Разрешимость ИВ.

ИВ разрешима, если существует алгоритм, позволяющий устанавливать тождественную истинность формул.

Независимость системы аксиом.

Опр. Система аксиом S (S' подмножество S) называется независимой, если в S' существует аксиома не выводимая из аксиом S\S'.

Опр. Система аксиом называется независимой, если любая её подсистема независима.

Опр. Моделью системы аксиом называется алгебра, состоящая из не пустого множества М и системы логических связок Ω.

Где М-множество истинностных значений формул данного исчисления. (М,Ω), Ω-система логических связок.

Лемма:

Подсистема S' системы S является независимой, если существует модель этой системы в которой:

1) В системе S' существует аксиома принимающая невыделенное значение;

2) Каждая из аксиом системы S\S' принимает одинаковые выделенные значения;

3) Правила отделения, применимое к выделенным формулам даёт выделенную формулу.

Теорема 1. A1 является независимой от A2,A3

Теорема 2. А2 является независимой от А1,А3.

Теорема 3. A3 является независимой от A1,A2.

Алгебра предикатов.