Набебин А.А., Кораблин Ю.П. Математическая логика и теория алгоритмов - файл n1.doc

приобрести
Набебин А.А., Кораблин Ю.П. Математическая логика и теория алгоритмов
скачать (295.1 kb.)
Доступные файлы (2):
n1.doc825kb.16.12.2010 15:32скачать
n2.doc774kb.15.08.2005 17:30скачать

n1.doc

  1   2   3
2. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

2.1. Определение исчисления высказываний

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


p

q

p&q

pq

pq

pq

 p

Л


Л

Л

Л

И

И

И

Л

И

Л

И

И

Л

И

И

Л

Л

И

Л

Л

Л

И

И

И

И

И

И

Л


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

Пусть А(р12,...,рk) - формула алгебры логики, которая построена из пропозициональных переменных р12,...,рk с помощью конъюнкции, дизъюнкции, отрицания, импликации, эквивалентности. Замещая переменные р12,...,рk некоторыми высказываниями, получим новое, которое примет значение "истина" или "ложь" (И или Л). Содержание самих высказываний при этом не существенно; важны только их истинностные значения. Поэтому в формуле A(р12,...,рk) переменные можно сразу замещать знаками И и Л, а затем вычислять истинностное значение получившегося выражения, как это делается в алгебре логики, если считать, что И отождествляется с 1, а Л - с 0. Формула A(р12,...,рk) реализует некоторую функцию алгебры логики от k переменных. Не будем различать и оговаривать их особо в дальнейшем, если о такой функции придется говорить.

Содержательно значения конъюнкции, дизъюнкции, отрицания, эквивалентности понятны. Значения импликации р  q на наборах (1,1) и (1,0) тоже понятны. Несогласие вызывает у слушателей курса логики в первый раз значения функции р  q на наборах (0,0) и (0,1). Выбранную таблицу значений импликации можно пояснить следующими рассуждениями. Функции pq и qp должны быть одинаковыми, ибо если утверждение р  q при некоторых конкретных высказываниях р и q истинно (как прямое утверждение), то высказывание qp тоже истинно (как противоположное утверждение). Например, справедливо необходимое условие сходимости числовых рядов: если ряд сходится, то его общий член стремится к нулю. Справедливо и противоположное утверждение: если общий член ряда не стремится к нулю, то ряд расходится. Из этих же соображений верно и обратное: из истиннос­ти утверждения qp следует истинность утверждения р  q.

Функции pq и qp не могут быть равными, иначе импликация становится эквивалентностью, что невозможно, ибо из того, что р влечет q, вообще говоря, не следует, что q влечет р (пример с тем же необходимым условием сходимости рядов).

Таким образом, импликация р  q определяется следующими условиями:
1) функции pq и qp одинаковы; 2) функции р  q и q  р различны.

Итак, функция р  q на наборе (1,1) равна единице, а на наборе (1,0) - нулю. Такова же и равная ей функция qp. На наборе (0,0) функция qp равна единице; такова же и р  q. Значения импликации q  р на наборах (0,0), (1,0), (1,1) определились. Осталось задать значение р  q на (0,1). Если примем, что
р  q на (0,1) равно 0 (т.е. 0  1 = 0), то q  р на (1,0) тоже равно 0 (т.е. 1  0 = 1). Тогда функции р  q и q  р оказываются равными. Поэтому импликация р  q на (0,1) равна 1.

Построим формально-логическое исчисление, в котором описывают­ся все тождественно истинные формулы алгебры логики и только они.

Алфавит.

1. p,q,r,p1,q1,r1,... - символы пропозициональных переменных.

2. &, V, ,  - логические связки (конъюнкция, дизъюнкция, импликация, отрицание соответственно).

  1. ( , ) - скобка левая, запятая, скобка правая.

Формулы.

1. Отдельно взятый символ пропозициональной переменной есть элементарная формула (атом).

2. Если А и В есть формулы, то выражения (А & В), (А V В), (А  В), (  А) есть формулы.

Примем соглашение об опускании скобок в соответствии со следующим приоритетом связок:  , & , V , .

Подформулы.

1. Если формула есть переменная, то единственной ее подформулой является она сама.

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

3. Если формула имеет вид А * В , где знак *  {&, V, }, то ее подформулами являются она сама и все подформулы формул А и В.

В формуле А  В подформула А называется посылкой, а подформула В - заключением.

Проинтерпретируем логические связки &, V, ,  соответствующими логическими операциями (функциями).

Если все переменные формулы А содержатся среди переменных р12,...,рn, то пишем А(р12,...,рn). Если формула А(р12,...,рn) построена из переменных р12,...,рn и только из них, то скажем тогда, что р12,...,рn есть полный список переменных формулы А.

Интерпретация формулы А(р1,...,рn ) есть набор I = (a1,...,an) из И и Л.

Индукцией по построению формулы А определим понятие значения I(A) формулы А(р1,...,рn) на интерпретации I.

1. Если А есть рi, то I(A) = аi.

2. Если А есть формула (В * С), где знак *  {&,V,}, или же формула  В, то I (В * С) = I(В) * I(С); I(  В) =  (I(В)).

Для удобства вместо I(A) будем писать также А(a1,...,an).

Формула А общезначима (тождественно истинна), если она истинна на любой интерпретации. Формула А выполнима, если существует интерпретация, на которой формула А истинна. Формула А невыполнима (тождественно ложна), если она ложна на всех интерпретациях. Формула А опровержима, если существует интерпретация, на которой формула А ложна.

Интерпретация I удовлетворяет формуле А (А выполняется на I), если А истинна на I. Интерпретация I опровергает А, если А ложна на I. Если интерпретация I удовлетворяет формуле А, то I называется также моделью формулы А.

Подстановка (П). Индуктивное определение.

1. Если формула А есть переменная р, то подстановка формулы В на место переменной р в формуле А есть В.

2. Если формула А переменной р не содержит, то подстановка есть снова формула А.

3. Если формула А имеет вид  C или С * Е, где * есть один из знаков &, V, , то подстановки



=  ; = * .

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

Система аксиом (П.С.Новикова).

А1) р  (q  р).

А2) (р  (q  r))  ((р  q)  (р  r)).

A3) р & q  р.

А4) р & q  q.

А5) (р  q)  ((р  r)  (р  q & r)).

А6) р  р V q.

А7) q  р V q.

А8) (р  r)  ((q  r)  (р V q  r)).

А9) (р  q)  (  q   р).

А10) р    р.

А11)   р  р.

Заметим, что в качестве аксиом взяты тождественно истинные формулы.

Правила вывода (ПВ)

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

,

т.е. от формулы А(р) с переменной р можно перейти к формуле

Правило заключения (ПЗ) имеет вид



т.е. от двух формул А и А  В можно перейти к формуле В. Это правило известно еще как правило modus ponens (утверждающий модус).

Исчисление высказываний (ИВ) составляют формальные символы, формулы, аксиомы и правила вывода.

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

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

Всякая аксиома есть доказуемая формула, длина доказательства которой
равна 1.

Приведем примеры доказуемых формул и некоторых вспомогательных (производных) правил вывода, применение которых к формулам при необходимости можно исключить, но использование их сделает формальную систему ИВ выразительнее и естественнее.

Доказательства формул сопроводим краткими пояснениями. Например, A3 будет означать, что формула является аксиомой A3; ПЗ(2,3) - формула получена применением правила заключения (ПЗ) к формулам (2) и (3); - формула получена подстановкой в формулу (4) формулы  р на место переменной q. Знак ├ будет означать: формула доказуема в ИВ.

Теорема 1. р р.

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

(1) (р  (q  r))  ((р  q)  (р  r)), А2;

(2) (р  (q  р))  ((р  q)  (р  р)),

(3) р  (q  р), А1;

(4) (р  q)  (р  р), ПЗ(2,3);

(5) (р  (q  р))  (р  р),

(6) р  р, П3(3,5).
Формула р  р доказуема в ИВ и последовательность формул (l),(2),...,(6) есть ее доказательство.

Замечание. Формула р  р доказуема в любом аксиоматическом исчислении, содержащем аксиомы А1,А2, правило подстановки и правило заключения.
2.1.1. Правило одновременной подстановки




Пусть выражение означает формулу, представляющую собой результат одновременного замещения переменных р12,...,рk в формуле А на формулы B1,B2,...,Bk соответственно.
Утверждение.


Д

оказательство.
Пусть r1,r2,...,rk есть попарно различные переменные, отличные от всех переменных, встречающихся в формулах A,B1,B2,...,Bk.Тогда формула
есть результат сначала последовательного замещения переменных р12,...,рk в формуле А на переменные r1,r2,...,rk соответственно, а затем в получившейся формуле - результат последовательной замены переменных r1,r2,...,rk на формулы B1,B2,...,Bk соответственно.

Теорема 2. ├  (р V q)   р &  q.

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

(1) (р  q)  ((р  r)  (р  q&r)), A5;

  1. (
    &  q)),
     (pVq)   p)  ((  (pVq)   q)  (  (pVq)   p &  q )),

  2. p  p V q, A6;

  3. (p  q)  (  q  p), A9;

  4. (p  p V q)  (  (p V q)   p),

  5.  (p V q)   p, ПЗ(3,5);

  6. (  (p V q)   q)  (  (p V q)   p &  q), ПЗ(2,6);

  7. q  p V q, A7;

  8. (q  p V q)  (  (p V q)   q),

(10)  (p V q)   q, П3(8,9);

(11)  (р V q)   p &  q, П3(7,10).

2.2. Теорема дедукции (ТД) в исчислении высказываний

Пусть Г и  есть произвольные конечные совокупности формул в ИВ (возможно пустые) и А, В, С - произвольные формулы в ИВ.

Определение. Конечная последовательность формул ИВ есть вывод из совокупности формул Г, если всякая формула последовательности либо принадлежит Г, либо доказуема, либо получена из предыдущих формул последовательности по одному из правил вывода.

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

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

Введем следующие обозначения: Г ├ A - формула А выводима из совокупности формул Г; Т8 - теорема 8; ПВ7 - правило вывода 7.

Правило вывода 1. A, B ├ A & B.

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

(1) А, условие;

(2) В, условие;

(3) ├ (р  q)  ((р  r)  (р  q & r)), А5;

(4) ├ (А  А)  ((А В)  (А  А & В)),

(5) ├ р  р, Т1;

(6) ├ А  А,

(7)├ (A  B)  (A  A & B), ПЗ (4,6);

(8) ├ p  (q  p), A1;

(9) ├ B  (A  B),

(10) A  B, ПЗ(2,9);

(11) А  А & В, ПЗ(7,10);

  1. А & В, ПЗ(1,11).


а. А  В ├ А b. А & B ├ B

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

(1) A & B, условие; (1) A & B, условие;

(2) ├ p & q  p, A3; (2) ├ p & q  q, A4;

(3) ├ A & B  A, (3) ├ A & B  B,

(4) A, ПЗ(1,3); (4) В, ПЗ(1,3);
Правило вывода 2.


├ ├ ├




a
⊢ ⊢ ⊢

├ ├ ├

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

(1) Г, условие; (1) Г, условие;

… …

(2) A; (2) A & B;

… (3) A & B  A,

(3) B; (4) A & B  B,

(4) A & B, ПВ1. (5) A, ПЗ(2,3);

(6) B, ПЗ(2,4).






П


равило вывода 3.







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

  1. Г, условие;…;

  2. А;

  3. А  (В  А),

(4) В  А, ПЗ(2,3).

Теорема (дедукции). Если Г есть конечная совокупность формул, а А и В - произвольные формулы в ИВ, для которых Г,А ├ В, то Г ├ А  В.

Доказательство. Индукция по длине k вывода.

БАЗИС. k =1. Возможны три случая.

  1. В есть А. Тогда Г,А ├ А. Так как ├ А  А (как то Г ├ A  А.

2. ├ В. Тогда ├ А  В по ПВЗ; поэтому Г ├ А  В.

3. В  Г. Тогда Г ├ В и по ПВЗ Г ├ А  В.

ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Пусть теорема справедлива для всех выводов длины меньше k.

ШАГ ИНДУКЦИИ. Покажем, что теорема справедлива для выводов длины k. Пусть Г,А ├ В и пусть B1,B2,...,Bk-1k (= В) есть вывод длины k формулы В из совокупности Г,А. Возможны следующие случаи.

1. В есть А. 2. ├ В. 3. В О Г. Эти случаи рассмотрены в базисе.

4. В (= Bk) получается из двух формул Вi и Вi  Вk вывода по правилу заключения, т.е. вывод Вk из Г,А имеет вид

В12;...;Вi;...;Вi Вk;...;Вk (=В).

Тогда Г,А ├ Вi, Г,A ├ Вi  Bk. Так длины этих выводов меньше k, то по предположению индукции

(1) Г ├ А  Вi ;

  1. Г ├ А  (Вi  Вk).

Далее имеем:

(3) Г ├ (А  (Вi  Вk))  ((А  Вi)  (А  Вk)),

(4) Г ├ (А  Вi)  (А  Вk), П3(2,3);

(5) Г ├ А  Вk, П3(1,4), т.е. Г ├ A  В.




Следствие.


⊢ ⊢

Замечание. Теорема дедукции доказуема в любом аксиоматическом исчислении, содержащем аксиомы А1, А2, правило подстановки и правило заключения.
2.3. Производные правила вывода

Пусть, как и в предыдущем параграфе, Г и  есть произвольные конечные совокупности формул ИВ (возможно пустые) и А, В, С -произвольные формулы в ИВ.

П

равило вывода 4
(правило силлогизма).


├ ├



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

(1) Г ├ A  В, условие;

(2) Г ├ В  С, условие;

(3) Г ├ (А  (В  С))  ((А  В)  (А  С)),

(4) Г ├ А  (В  С), ПВЗ(2);

(5) Г ├ (А  В)  (А  С) П3(3,4);

(6) Г ├ А  С, П3(1,5).




Правило вывода 5 (контрапозиция).
Доказательство.

(1) Г ├ А  В, условие;

  1. Г ├ (А  В)  ( В   А),

  2. Г   В   А, П3(1,2).

Правило вывода 6 (снятие двойного отрицания в заключении).


Д

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


(1) Г ├ А    В, условие;

(2) Г ├   В  В,

(3) Г ├ А  В, ПВ4(1,2).
Правило вывода 7 (снятие двойного отрицания в посылке).

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

(1) Г ├   А  В, условие;

(2) Г ├ А    А,

(3) Г ├ A  В, ПВ4(1,2).




Правило вывода 8.



Правило вывода 9.
Доказательство. Г;...,В;...,А; т.е. Г ├ А.




Правило вывода 10.
Доказательство. Г;;…;В;…;А.




Правило вывода 11.
Доказательство.

(1) Г ├ А  В, условие;

(2) Г,A ├ A;

(3) Г,А ├ А  В, ПВ8(1);

(4) Г,А ├ В, ПЗ(2,3).




Правило вывода 12.
Теорема 3 (закон перестановки посылок).

├ (р  (q  r))  (q  (р  r)).

Доказательство. Покажем, что р  (q  r), q, p ├ r.

(1) р  (q  r), условие;

(2) q, условие; (4) q  r, П3(1,3);

(3) р, условие; (5) r, П3(2,4).

Далее последовательно применяем теорему дедукции.

Правило вывода 13 (перестановка посылок).



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

(1) Г ├ А  (В  С), условие;

(2) Г ├ (А  (В  С))  (В  (А  С)),

(3) Г ├ В  (А  С), П3(1,2).

Теорема 4 (закон соединения посылок).

├ (р  (q  r))  (p & q  r).

Доказательство. Покажем, что р  (q  r), p & q ├ r.

(1) р  (q  r), условие; (4) q, ПВ2(2);

(2) p & q, условие; (5) q  r, П3(1,3);

(3) р, ПВ2(2); (6) r, П3(4,5).

Далее последовательно применяем теорему дедукции.

Правило вывода 14 (соединение посылок).


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

(1) Г ├ А  (В  С), условие;

(2) Г ├ (А  (В  С))  (А & В  С),

(3) Г ├ А & В  С, П3(1,2).

Теорема 5 (закон разъединения посылок).

├ (р & q  r)  (р  (q  r)).

Доказательство. Покажем, что р & q  r, p, q├ r.

(1) р & q  r, условие; (4) p&q, ПВ2(2,3);

(2) р, условие; (5) r, П3(1,4).

(3) q, условие;

Далее последовательно применяем теорему дедукции.
Правило вывода 15 (разъединение посылок).



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

(1) Г ├ А & В  С, условие;

(2) Г ├ (А & В  С)  (А  (В  С)),

(3) Г ├ А  (В  С), П3(1,2).

Правило вывода 16 (введение конъюнкции).

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

(1) Г ├ С  А, условие;

(2) Г ├ С  В, условие;

(3) Г ├ (С  А)  ((С  В)  (С  А & В)),

(4) Г ├ (С  В)  (С  А & В), П3(1,3);

(5) Г ├ С  А & В, П3(2,4).

Правило вывода 17 (введение дизъюнкции).


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

(1) Г ├ А  С, условие;

(2) Г ├ В  С, условие;

(3) Г ├ (А  С)  ((В  С)  (А V В  С)),

(4) Г ├ (В  С)  (А V В  С), П3(1,3);

(5) Г ├ A V В  С, П3(2,4).

Теорема 6. ├ p &  p  q.

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

  1. p  ( q  p), A1;

  2. p  ( щ q  p),

  3. ├ ( щ q  p)  ( щ p  щ щ q),

(4) ├ р  (щ р  щ щ q), ПВ4(2,3), силлогизм;

(5) ├ р & щ р  щ щ q, ПВ14(4), соединение посылок;

(6) ├ p& щ pq, ПВ6(5), снятие двойного отрицания.

Высказывание р & щ р тождественно ложно, т.е. противоречиво при любом р. Теорема 6 утверждает, что из противоречия следует любое высказывание. Из нее легко показать справедливость правила вывода , которое утверждает, что в противоречивом исчислении (т.е. в исчислении, где доказуемо некоторое утверждение и его от­рицание) можно вывести любое утверждение.

Теорема 7 (закон исключенного третьего). ├ p V щ р.
Доказательство.

(1) ├ щ (р V щ р)  щ р & щ щ p,

(2) ├ щ р & щ щ р ® щ q,

(3) ├ щ (р V щ р) ® щ q, ПВ4(1,2), силлогизм;

(4) ├ щ щ q ®щ щ (р V щ р), ПВ5(3), контрапозиция;

(5) ├ q ®щ щ (р V щ р), ПВ7(4), снятие двойного отрицания;

(6) ├ q ® (р V щ р), ПВ6(5), снятие двойного отрицания;

(7) ├ р ® р, Т1;

(8) ├ (р ® р) ® (р V щ р),

(9) ├ р V ®р, П3(7,8).

Правило вывода 18 (приведение к абсурду).

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

(1) Г,А ├ В, условие;

(2) Г,А ├ щ В, условие;

(3) Г ├ А ® В, ТД(1);

(4) Г ├ А ® щ В, ТД(2);

(5) Г ├ A ® B&щ B, ПВ16(3,4);

(6) ├ В & щ В ® щ (В V щ В),

(7) Г ├ А ® щ (В V щ В), ПВ4(5,6), силлогизм;

(8) Г ├ щ щ (В V щ В) ® щ А, ПВ5(7), контрапозиция;

(9) Г ├ (В V щ В) ® щ А, ПВ7(8), снятие двойного отрицания;

(10) ├ В V щ В,

(11) Г ├ щ А, П3(9,10).

Правило приведения к абсурду используется в доказательствах от противного. Пусть по ходу некоторых рассуждений требуется доказать утверждение А. Допускаем противное: предполагаем справедливость его отрицания,
т.е. справедливость утверждения щ А, и доказываем, исходя из щ А, некоторое утверждение В и его отрицание щ В. Получили противоречие. Следовательно, наше предположение о справедливости утверждения щ А было неверным и потому справедливо его отрицание щ щ А, т.е. справедливо А.

Теорема 8. ├ р V q ® щ (щ р & щ q).

Д

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


(1) ├ (p ® щ (щ p&щ q)) ® ((q ® щ (щ р& щ q)) ® (p V q ®щ (щ p & щ q))),

(
щ
2) ├ щ р & щ q ® щ p,

(3) ├ щ p & щ q ® щ q,

(4) ├ щ щ p ® щ (щ p & щ q), ПВ5(2), контрапозиция;

(5) ├ щ щ q ® щ (щ p & щ q), ПВ5(3), контрапозиция;

(6) ├ р ® щ (щ р & щ q), ПВ7(4), снятие двойного отрицания;

(7) ├ q ® щ (щ p & щ q), ПВ7(5), снятие двойного отрицания;

(8) ├ (q ® щ (щ p& щ q)) ® (р V q ® щ (щ p&щ q)), П3(1,6);

(9) ├ р V q ® щ (щ p&щ q), П3(7,8).

Теорема 9. ├ щ р & щ q ® щ (p V q).

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

(1) ├ р V q ® щ (щ р & щ q), T8.

(2) ├ щ щ (щ р & щ q) ® щ (р V q), ПВ5(1), контрапозиция.

(3) ├ щ р & щ q ® щ (р V q), ПВ7(2), снятие двойного отрицания.

Теорема 10. ├ (р ® q) ® щ p V q.

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

(1) р, р ® q ├ q, правило заключения;

(2) ├ q ® щ р V q,

(3) р, р ® q ├ щ р V q, П3(1,2);

(4) ├ р ® ((р ® q) ® щ р V q), ТД(3);

(5) ├ щ р ® щ р V q,

(6) ├ (р ® q) ® (щ p ® щ p V q), ПВЗ(5);

(7) ├ щ р ® ((p ® q) ® щ р V q), ПВ13(6), перестановка посы­лок;

(8) ├ (р V щ p) ® ((p ® q) ® щ р V q), ПВ7(4,7), введение дизъюнкции;

(9) ├ p V щ p, T7;

(10) ├ (p ® q) ® щ р V q, П3(8,9).

2.4. Тождественно истинные и доказуемые формулы

Пусть А(p1p2,…,pn) - формула в ИВ и p1p2,…,pn - полный список ее переменных; а = (a1,a2,…,an) - набор из 0 и 1 длины n; Рa(А) означает значение формулы А на наборе а. Определим это понятие индукцией по построению формулы.

  1. Если А есть переменная рi, то

.

2. Если А есть формула В * С (где * есть один из знаков &, V, ®) или же формула щ В, то

Рa (В * С) = Рa (В) * Рa (С); Рa ( щ В) = щ Pa (В).

Примем обозначения р1 = р; р0 = щ р.

Лемма (о доказуемости формулы по значению на наборе).



├ щ





Доказательство. Индукция по построению формулы.
Пусть совокупность формул Г =
БАЗИС. Формула А есть переменная рi. Тогда Рai) = аi.

a) ai = 1. Тогда = рi = А; откуда Г ├ А.

b) аi = 0. Тогда = щ рi = щ А; откуда Г ├ щ A.

ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Предположим, что лемма справедлива для всех формул глубины построения меньше k.

ШАГ ИНДУКЦИИ. Покажем, что лемма справедлива для формул глубины построения k. Возможны следующие случаи.

а) А есть В & С. Возможны следующие подслучаи.

1. Ра (А) = 1. Покажем, что Г ├ А. Так как Ра (А) = Рa (В & С) = Ра(В) & Ра(С) = 1, то Ра(В) = 1, Ра(С) = 1. Так как глубина построения формулы В и формулы С меньше k, то по предположению индукции имеем

Г ├ В, Г ├ С, откуда Г ├ В & С, ПВ2.

2. Рa (А) = 0. Покажем, что Г ├ щ А. Так как Рa (А) = Ра (В&С) = Ра (В) & Ра (С) = 0, то Ра (В) = 0 или Ра (С) = 0. Пусть для определенности Ра (В) = 0. Так как глубина построения формулы В меньше k, то по предположению индукции

(1) Г ├ щ В. Далее получаем

(2) ├ В & С ® В,

(3) ├ щ В ® щ (В & С), ПВ5(2), контрапозиция;

(4) Г ├ щ (В & С), П3(1,3), т.е. Г ├ щ A.

b) А есть В V С. Возможны следующие подслучаи.

1. Ра (А) = 1. Покажем, что Г ├ А. Так как Ра (А) = Рa (В V С) = Ра(В) V Ра(С) = 1, то Ра(В) = 1 или Ра(С) = 1. Пусть для определенности имеем Ра (В) = 1. Так как глубина построения формулы В меньше k, то по предположению индукции

(1) Г ├ В. Далее получаем

(2) ├ В ® В V С,

(3) Г ├ В V С, П3(1,2), т.е. Г ├ А.

2. Ра (А) = 0. Покажем, что Г ├ щ А. Так как Ра (А) = Ра (В&С) = Ра (В) V Ра (С) = 0, то Ра (В) = 0, Рa (С) = 0. Так как глубина построения формулы В и формулы С меньше k, то по предположению индукции

(1) Г ├ щ В;

(2) Г ├ щ C. Далее получаем

(3) Г ├ щ В & щ C, ПВ2(1,2);

(4) ├ щ В & щ C ® щ (В V С),

(5) Г ├ щ (В V С), П3(3,4), т.е. Г ├ щ A.

c) А есть В ® С. Возможны следующие подслучаи.

1. Ра (А) = 1. Покажем, что Г ├ А. Так как Ра (А) = Ра (В ® С) = Ра (В) ® Рa (С) = 1, то Рa (В) = 0 или Ра (С) = 1.

Пусть Рa(В) = 0. Так как глубина построения формулы В меньше k, то по предположению индукции

  1. Г ├ щ В. Далее

  2. Г ├ В & щ B ®C,

(3) Г ├ В ® (щ В ® С), ПВ14(2), разъединение посылок;

(4) Г ├ щ В ® (В ® С), ПВ13(3), перестановка посылок;

(5) Г ├ В ® С, П3(1,4), т.е. Г ├ А.

Пусть Ра (С) = 1. Так как глубина построения формулы С меньше k, то по предположению индукции

(1) Г ├ С. Далее

(2) ├ С ® (В ® С),

(3) Г ├ В ® С, П3(1,2), т.е. Г ├ А.

2. Ра (А) = 0. Покажем, что Г ├ щ А. Так как Ра (А) = Ра (В ® С) = Ра(В) ® Ра(С) = 0, то Ра(В) = 1, Ра(С) = 0. Так как глубина построения формулы В и формулы С меньше k, то по предположению индукции

(1) Г ├ В;

(2) Г ├ щ C. Далее

(3) Г ├ ((В ® С) ® С) ® (щ C ® щ (В ® С)),

(4) ├ (В ® С) ® (В ® С),

(5) ├ В ® ((В ® С) ® С), ПВ13(4), перестановка посылок;

(6) Г ├ (В ® С) ® С, П3(1,5);

(7) Г ├ щ С ® щ (В ® С), ПВ5(6), контрапозиция;

(8) Г ├ щ (В ® С), П3(1,7), т.е. Г ├ щ А.

d) А есть щ В. Возможны следующие случаи.

1. Ра(А) = 1. Покажем, что Г ├ А. Так как Рa (А) = Ра ( щ В) = щ Ра (В) = 1, то
Рa(В) = 0. Так как глубина построения формулы В меньше k, то по предположению индукции Г ├ щ В, т.е. Г ├ А.

2. Ра (А) = 0. Покажем, что Г ├ щ А. Как и выше, Ра (В) = 1. По предположению индукции

(1) Г ├ В. Далее

(2) ├ В ® щ щ В,

  1. Г ├ щ щ В, т.е. Г ├ щ А.

Лемма доказана.

Теорема. Всякая тождественно истинная формула доказуема в ИВ.

Д


оказательство
. Пусть А(p1,p2,…,pn) есть тождественно истин­ная формула и p1,p2,…,pn - полный список ее переменных; а = (a1,a2,…,an) - произвольный набор из 0 и 1 длины п. Так как Рa (А) = 1 для любого набора а, в том числе и для наборов (a1,…,an-1,1) и (a1,…,an-1,0), то по доказанной выше лемме



  1. Далее




  2. ТД(1);


  3. ├ 

    ТД(2);


  4. ├ V 

    ПВ17(3,4), введение V;

  5. pn V щ pn,




  6. ПЗ(5,6).

Повторяя предыдущие рассуждения, получим




После конечного числа подобных рассуждений получим ├ А.

Теорема. Всякая доказуемая в ИВ формула общезначима.

Доказательство. Индукция по длине k доказательства.

БАЗИС. k = 1. Непосредственной проверкой убеждаемся, что все аксиомы (только они имеют длину доказательства k=l) тождественно истинны.

ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Допустим, что все доказуемые фор­мулы с длиной доказательства меньше k тождественно истинны.

ШАГ ИНДУКЦИИ. Покажем, что все доказуемые в ИВ формулы с длиной доказательства k тождественно истинны. Пусть формула А доказуема в ИВ и ее доказательство А12,...,Аk (=А) имеет длину k. Возможны следующие случаи.

1. А есть аксиома. Тогда А тождественно истинна.

2. Формула Аk (=А) есть (Аi(р)), т.е. получена из формулы Аi(р) в доказательстве А12,... ,Аi(р),... ,Ak с помощью подстановки. Так как длина доказательства А12,... ,Аi(р) формулы Аi(р) меньше k, то по предположению индукции формула Аi(р), а вместе с ней и формула А = Аi(С), тождественно истинна.

3. Формула Аk получена из формул Аi и Аi ® Аk в доказательстве А1,...,Аi,.., Аi ® Ak,...,Ak (=А) с помощью правила заключения.
  1   2   3


2. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации