Мат. логика

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

Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

;

;

;

;

;

;

;

;

;

;

.

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

(Modus ponens)

Теорема корректности исчисления высказываний |-E => |=E утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

22. Лемма о выводимости.

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

х1, х2, …, хn – набор переменных, содержащий все переменные, входящие в формулу А.

α1, α2,…, αn – произвольный фиксированный набор этих переменных. Обозначим через

,

где

Тогда:

1)Если R α1, α2,…, αn(A) = 1, то Н├ А

2)Если R α1, α2,…, αn(A) = 0, то Н├

Доказательство: Доказательство леммы проведем по индукции (индукция по построению формул)

1)Пусть А = xi

А) Если R α1, α2,…, αn(хi) = αi = 1, то очевидно, что xi├ xi

├ xi

├ A H├ A

Б) Если R α1, α2,…, αn(хi) = αi = 0, то очевидно, что

├

├

├

Н├

2)Предположим теперь, что формула А имеет один из четырех видов:

1)В1В2

2)В1 + В2

3)В1 → В2

4)

идля формул В1, В2 лемма справедлива.

Рассмотрим каждый из четырех случаев:

1)Пусть A = B1B2

А) Если R α1, α2,…, αn(B1B2) = 1, то это означает, что

R α1, α2,…, αn(B1) = 1

R α1, α2,…, αn(B2) = 1

Это означает, что Н├ В1

Н├ В2 Отсюда, по правилу введения конъюнкции

Н├ В1В2 Н├ А

Б) R α1, α2,…, αn(B1B2) = 0 R α1, α2,…, αn(B1) = 0, либо

R α1, α2,…, αn(B2) = 0

Предположим, что R α1, α2,…, αn (B1) = 0

Н├ (1)

Воспользуемся аксиомой II1 и выполним подстановку

Получим:├ В1В2 → В1

Н├

2)Пусть А = В1 + В2

А) Если R α1, α2,…, αn (B1+B2) = 1, то либо R α1, α2,…, αn (B1) = 1, либо R α1, α2,…, αn (B2) = 1

Пусть R α1, α2,…, αn (B1) = 1

Тогда по предположению Н├ В1 (3) Воспользуемся аксиомой III1

├ В1 → В1 + В2 (4)

По ПЗ (3, 4) получим: Н├ В1 + В2, т.е. Н├ А

Б) Если R α1, α2,…, αn (B1+B2) = 0, то

R α1, α2,…, αn (B1) = R α1, α2,…, αn (B2) = 0

Отсюда следует, что Н├ , Н├ Тогда по правилу введения конъюнкции

Из формул (5) и (6) по ПЗ(5, 6) имеем Н├

Н├

3)Пусть А = В1 → В2

А) Если R α1, α2,…, αn(B1→B2) = 1, то либо

R α1, α2,…, αn(B1) = 0, либо

R α1, α2,…, αn(B2) = 1

Доказательство основано на некоторых интерпретациях переменных и логических операций исчисления. Допускается, что переменные в аксиомах могут принимать два значения: 1(И) и 0(Л). Все логические операции, кроме одной, определяются так же, как и в алгебре высказываний. Одну же из логических операций специально определяют так, чтобы та аксиома, в которую эта операция входит и независимость которой доказывается, не являлась общезначимой.

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

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

В качестве примера докажем независимость аксиомы II1: х*y = y

Все аксиомы групп I, III и IV общезначимы, т.к. в них операция конъюнкции не входит, а остальные операции определены как в алгебре высказываний.

Аксиомы II2 и II3 в данной интерпретации принимают вид: y→y и ((z→x) → (z→y))

Легко проверить, что они общезначимы.

А вот аксиома II1 в этой интерпретации принимает вид: y→x , которая не общезначима, т.к. при y=1, х=0 принимает значение 0.

По аналогичной схеме доказывается независимость остальных аксиом группы II, III и IV. Несколько сложнее доказывается независимость аксиом группы I.

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

Применим к (8) правило подстановки посылок и получим:

├

Из (7) и (9) по правилу заключения получим: H├ B1 → B2, т.е. H├ А

А) Если R α1, α2,…, αn(B1) = 1, то

H├ B2

Из аксиомы I1 получим:

├ B2 → (B1 → B2)

Тогда по правилу заключения имеем:

H├ B1 → B2, т.е. H├ А

Б) Если Rα1, α2,…, αn(B1 → В2) = 1, то Если R α1, α2,…, αn(B1) = 1, а R α1, α2,…, αn(B2) = 0. Отсюда по

предположению следует, что

H├ B1 (10)

H├ (┐В2) (11)

Воспользуемся доказуемой формулой:

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

к доказуемой формуле

├ А → А

Из (12) по правилу перестановки посылок получаем

├ B1 → ((B1 → B2) → B2) (13)

Из (10) и (13) по ПЗ получим

Н├ ((B1 → B2) → B2) (14)

Из (14) по правилу контрпозиции имеем

Из (11) и (15) по ПЗ получаем

23. Теорема Поста (о полноте исчисления высказываний).

Каждая тождественно истинная формула алгебры высказывания доказуема в ИВ, т.е. ╞ Е => ├ Е,

где Е – произвольная формула логики высказывания.

Впервые эту теорему доказал американский математик Эмиль Пост в 1921 году. Потом она много раз переоткрывалась и передоказывалась. Другое называние – теорема о полноте исчисления высказываний.

Доказательство. Пусть А – тождественно истинная формула в АВ, а х1, х2, …, хn – перечень всех переменных, входящих в формулу А.

Возьмем (α1, α2,…, αn) – произвольный набор значений переменных х х1, х2, …, хn ,

Т.к. А≡1, то R α1, α2,…, αn(А) = 1

Отсюда с учетом предыдущей доказанной леммы имеем: Нn├А (1), где

Так как всего различных наборов (α1, α2,…, αn) 2n , то соотношение (1) справедливо в 2n случаях.

ивыполним подстановку

,тогда получим

Из (8) по правилу контрпозиции следует: ├ Используя оба правила снятия двойного отрицания, получаем:

Пусть теперь у - некоторая доказуемая формула, тогда из формул ├ у и (9) по правилу заключения

├А

Отсюда по правилу введения дизъюнкции имеем

├А

Но формула

доказуема, поэтому Ø├А, а это означает, что формула А доказуема. ├А

Объединяя две последние теоремы, мы можем записать теорему Поста:

╞Е ├Е

Произвольная формула Е является общезначимой в АВ тогда и только тогда, когда она доказуема в ИВ.

24.Проблемы аксиоматического исчисления высказываний: непротиворечивость, полнота, разрешимость, независимость.

Всякая аксиоматическая теория для своего обоснования требует рассмотрения четырех проблем:

1.проблема непротиворечивости

2.проблема полноты

3.проблема разрешимости

4.проблема независимости

Непротиворечивость теории L

Определение. Формальная аксиоматическая теория называется непротиворечивой, если ни для какой формулы А формулы А и ┐А не являются обе доказуемыми в ней.

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

Метатеорема. Теория L непротиворечива.

Доказательство: Допустим, что теория L противоречива. Тогда, согласно определению, существует формула А, такая, что ├ А и ├ ┐А

Это означает, что ╞ А и ╞ ┐А, что невозможно.

Полнота теории L

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

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

Метатеорема. Теория L полна относительно общезначимости.

Разрешимость теории L

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

Метатеорема: Теория L разрешима.

Доказательство. Разрешающий алгоритм для теории L состоит в построении истинностей таблицы заданной формулы E, что всегда можно сделать за конечное число шагов. Далее, если столбец значений формулы Е состоит из одних И, то формула Е общезначима и доказуема. Если же указанный столбец содержит не только И, то формула Е необщезначима, а значит и недоказуема.

Независимость аксиом теории L

Определение. Аксиома Х системы Г называется независимой, если она не является теоремой в формальной аксиоматической теории, описываемой системой аксиом Г \ {х}. Если каждая аксиома системы аксиом Г независима, то система аксиом Г называется независимой.

Метатеорема. Система аксиом теории L независима.

1, для _ х М , при _ которых _ P x 0 P x 0, в _ противном _ случае

I M \ I P = I P

P

Импликацией двух предикатов называется новый предикат:

0, для _ х М , при _ которых _ P x 1,Q x 0

P x Q x

1, в _ противном _ случае

P x Q x P(x) Q x

Множество истинности:

I P Q I P IQ I P IQ

Кванторные операции

1.Квантор общности.

Пусть Р(х) – некоторый одноместный предикат, определенный на М.

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

- это высказывание не зависит от х. Читается: Для всякого х Р(х) – истинно.

2.Квантор существования.

- высказывание, которое истинно, если существует элемент х из М для которого Р(х) – истинно, и ложно в противном случае.

В общем случае изменение порядка следования кванторов меняет смысл высказывания, а значит, и его логическое значение. Рассмотрим одноместный предикат Р(х), определенный на множестве М,

Кванторные операции можно рассматривать как обобщение конъюнкций и дизъюнкций на случай бесконечных областей.