Часть 1. (p  (q  r))  (p  q).

Случай 1.1. (р  (p  q)), р. д. ф., Т10.

Случай 2.1. (q  r)  (p  q).

	q  r	допущ.;
	q	УК (1);
	p  q	ВД (2).

Часть 2. (p  (q  r))  (p  r).

Случай 2.1. p  (p  r), р.д.ф., Т10.

Случай 2.2. (q  r)  (p  r).

	q  r	допущ.;
	r	УК (1);
	p  r	ВД (2).

Упражнения.

I. Постройте доказательство формулы:

1. ((Q  R)  (R  S)  S)  (Q  R);

2. ((A  B)  C)  (C  D)  D;

3. (((X  Y)  (Z  X) X)  (Y  Z);

4. ((E  F)  (F  (E  G))  E)  G;

5. ((P  Q)  (Q  P))  (R  S)  (P  R)  (Q  S);

6. ((Q  R)  (S  T))  ((U  V)  (W  X))  (Q  U)  (R  V);

7. ((A  B)  (C  D)  (A  C))  ((A  B)  (C  D));

8. (((H  I)  (J  (K  L))  I)  (J  K);

9. ((Y  Z)  (Z  (Y  (R  S))  (R  S))  (R  S))  Y;

10. (A  B)  (B  C)  (C  A)  (A  C)  (A  C).

II. Решите задачу, записав условие в символической форме и построив доказательство полученной формулы:

1.Если она получила телеграмму, то она полетела самолетом; если она полетела самолетом, то не опоздает на встречу. Но если телеграмма была неправильно адресована, тогда она опоздает навстречу. Либо она получила телеграмму, либо телеграмма была неправильно адресована. Значит, либо она полетела самолетом, либо она опоздает на встречу.

2.Если дождь будет продолжаться, то река поднимется. Если дождь будет продолжаться и река поднимется, то мост станет непригодным. Но если продолжение дождя делает мост непригодным, то одной единственной дороги для города недостаточно. Либо одной дороги для города недостаточно, либо разработчики городских дорог допустили ошибку. Значит, разработчики городских дорог допустили ошибку.

3.Так как Смит выиграл у полицейского в бильярд, то Смит — не полицейский. Смит выиграл у в бильярд полицейского. Если Джонс — машинист, то Джонс — не полицейский. Джонс — машинист. Если Смит — не полицейский, и Джонс тоже не полицейский, тогда полицейский — Робинсон. Если Джонс — машинист, а Робинсон — полицейский, тогда Смит — инженер. Значит, Смит — инженер.

§ 4. Слабое косвенное доказательство

Здесь мы расширим исчисление положительной логики добавлением правилa [II.2]^min построения слабого косвенного доказательства.

Слабое косвенное доказательство формулы

A₁  (A₂  ... (А_n  С₁) …) (*)

строится согласно следующему предписанию. На любом шаге построения можно написать:

1. одну из формул A₁, A₂, ..., А_n в качестве допущения;

1а) формулу С, полученную из С стиранием первого слева знака отрицания¹¹, в качестве допущения слабого косвенного доказательства.

2) формулу, следующую из ранее написанных формул, по одному из правил логического следования.

3) ранее доказанную формулу.

Слабое косвенное доказательство формулы (*) считаете» построенным, если в соответствии с пп. 1 —3, включая и п. 1а, получена последовательность формул, содержащая формулу С, пару противоречащих формул и оканчивающаяся одной из формул данной пары.

Слабое косвенное доказательство — это частный случай косвенного доказательства, характеризующийся следующими ограничительными условиями:

1) если при построении косвенного доказательства мы согласно п. 1а могли вводить формулу, получаемую из консеквента его тезиса как стиранием, так и приписыванием слева знака отрицания, то в слабом косвенном доказательстве мы располагаем только первой возможностью (стиранием знака отрицания);

2) если для окончания косвенного доказательства требуется получение последовательности формул, содержащей пару противоречащих формул, и не требуется, чтобы в эту последовательность входило специальное допущение косвенного доказательства, то одним из непременных условий окончания слабого

косвенного доказательства является наличие допущения слабого косвенного доказательства.

Так, в примере на с. 73 лишь (III) является слабым косвенным доказательством.

Таким образом, введенная нами логическая система имеет следующие правила: правила [I] логического следования, правило [II. 1] построения прямого доказательства, правило [II.2]^min построения слабого косвенного доказательства, и представляет собой¹² одно из логических исчислений так называемой минимальной логики.

Если в полной системе N, вообще говоря, можно было бы обойтись без правила [II. 1] построения прямого доказательства, то в описанной логической системе минимальной логики правило [II. 2] не делает избыточным применение [II. 1] потому, что ни одна кратная импликация, консеквент которой не начинается со знака отрицания, не может быть доказана с помощью правила [II.2]^min.

Рассмотрим некоторые теоремы и производные правила, которые можно установить в минимальной логике.

Т13. (А  В)  ((А  ~В)  ~А).

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

1. А В допущ.;

2. А ~В допущ.;

3. А допущ. слаб. косв. док.;

4. В МП (3, 1);

5. ~В МП (3, 2);

Пртврч.: 4, 5.

Относительно Т13 производно правило введения отрицания

ВО	А  В А  ~В.
	А

Т14. А  ~~А — обратный закон двойного отрицания.

Заметим, что (прямой) закон двойного отрицания— ~~А  А нельзя доказать ни в минимальной, ни в конструктивной логике (система конструктивной логики рассматривается в § 5 данной главы).

Т15. ~~~А  ~А.

Т16. ~ (А  ~А) — закон противоречия.

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

1. А  ~А допущ. слаб. косв. док.;

2. А УК (1);

3. ~А УК (1);

Пртврч.: 2, 3.

Обращаем внимание на то, что это — косвенное доказательство нулькратной импликации и поэтому в него не вводится других допущений, кроме специального допущения косвенного доказательства.

Т17. (А  В)  (~В  ~А).

Т18. (А  ~В)  (В  ~А).

Относительно Т17, Т18 производно правило модус толленс, имеющее две схемы:

МТ	А  В ~В,	А  ~В В.
	~А	~А

Согласно правилу МТ из импликации и формулы, противоречащей ее консеквенту, следует отрицание ее антецедента.

Т19. ~(А  В)  (А  ~В).

Т20. ~(А  В)  (В  ~А).

Относительно Т19, Т20 производно правило, имеющее две схемы. Его мы будем называть удалением отрицания конъюнкции:

УОК	~(А  В) А,	~(А  В) В.
	~В	~А

Т21. ~А  ~(А  В).

Т22. ~В  ~(А  В).

Относительно Т21, Т22 производно правило, которое можно назвать введением отрицания конъюнкции:

ВОК	~А	~В
	~(А  В),	~(А  В).

Т23. (~А ~B)  ~(А  В).

Т24. (А  B)  ((A  C)  ((~B  ~C)  ~А)).

Относительно Т24 производно правило простой деструктивной дилеммы

Дил₃ А  B A  C ~B  ~C.

~А

Данное правило позволяет из двух импликаций с одинаковым антецедентом и из дизъюнкции отрицаний их консеквентов вывести отрицание антецедента этих импликаций.

Т25. (A  C)  ((B  D)  ((~C  ~D)  (~A  ~B))).

Относительно Т25 производно правило сложной деструктивной дилеммы

Дил₄. A  C B  D ~C  ~D,

~A  ~B

которое означает, что из двух импликаций и дизъюнкции отрицаний их консеквентов следует дизъюнкция отрицаний их антецедентов.

Т26. ~А  (А  ~В).

Т27. ~А  (~В  ~(А  В)).

Относительно Т27 производно правило введения отрицания дизъюнкции

ВОД	~А ~В
	~(А  В)

Т28. ~( А  В)  ~А.

Т29. ~( А  В)  ~В.

Т30. ~( А  В)  (~А  ~В).

Относительно Т28, Т29 производно правило, которое можно назвать правилом удаления отрицания дизъюнкции:

УОД	~ (А  В)	~ (А  В).
	~А	~В

Т31. ~~(А  В)—двойное отрицание закона исключенного третьего. Сам же закон исключенного третьего недоказуем в минимальной логике.

Т32. ~( А  В)  (~А  ~В).

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

Часть 1. ~( А  В)  (~А  ~В) р. д. ф., Т30.

Часть 2. (~A  ~B)  ~ (A  B).

1. ~A  ~B допущ.;

2. ~А УК (1);

3. ~В

~ (А  В) ВОД (2, 3).

Т33. (А  ~В)  ~(А  В).

На этом мы заканчиваем обзор теорем и производных правил минимальной логики.

Упражнения.

I. Каждая из нижеследующих групп формул является доказательством. Укажите для каждой строки использованные правила вывода с указанием строк, к которым они были применены.

I.1. ((N  O)  ((N  O)  P)  (N  P))  N.

1. N  O;

2. (N  O)  P;

3. (N  P);

4. N;

5. O;

6. N  O;

7. P;

8. N  P.

I.2. ((F  G)  (F  (H  G))  ((I  H)  G)  I)  H.

1. F  G;

2. F  (H  G);

3. (I  H)  G;

4. I;

5. H;

6. I  H;

7. G;

8. F;

9. H  G;

10. G;

11.  (I  H).

I.3. (I  J)  (I  (K  J))  (L  K)   (I  J)   (L  J).

1. I  J;

2. I  (K  J);

3. L  K;

4. (I  J);

5. L  J;

6. L;

7. J;

8. K;

9. I;

10. K  J;

11. K.

II. Докажите формулу, используя правило построения слабого косвенного доказательства:

1. (S  T)  (T  U)  S;

2.  (K  L)  (K  L)  K;

3. ((K  L)  M)  (( M   (L  K)   (K  L);

4. ((W  X)  (Y  Z))   ((W  X)  (Y  Z))   (W  X);

5. ((Q  R)  (R  S)  S)  (Q  R);

6. ((T  U)  (V  U)  (V  W))  T;

7. (((M  N)  (O  N))  (N  M)  M))  O.