Лекция 16 Теория математических доказательств. Косвенные доказательства

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

Не имея, в силу ряда причин (недоступность объекта исследования, утрата реальности его существования и т.п.) возможности провести прямое доказательство истинности какого-либо утверждения, тезиса, строят антитезис. Убеждаются, что антитезис ведет к противоречиям, и, стало быть, является ложным. Тогда из факта ложности антитезиса делают - на основании закона исключенного третьего (a v ) - вывод об истинности тезиса.

Известны следующие схемы косвенных доказательств:

доказательство от противного, доказательство через контрпример.
Доказательство «от противного» в математике — один из самых часто используемых методов доказательства утверждений. Дана последовательность формул G и отрицание A (G , A). Если из этого следует B и его отрицание (G , A, B, , не-B), то можно сделать вывод, что из последовательности формул G вытекает истинность A. Иначе говоря, из ложности антитезиса следует истинность тезиса. Этот способ доказательства основывается на истинности формулы в классической логике и законе двойного отрицания .

Доказательство утверждения A проводится следующим образом.

1. 
   Сначала принимают предположение, что утверждение A неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение B, которое заведомо неверно.
   
2. 
   Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение , которое по закону двойного отрицания равносильно утверждению A.
   

1. 
   Предположим, что это не так, что формулы не равносильны, т.е. .
   
2. 
   Тогда, должно найтись P(x) и Q(x) такие, что равносильность не выполняется. В этом случае, возможно три варианта:
   

3. 
   Рассмотрим случай 2а. P(x) и Q(x) оба тождественно истинные
   

P(x)	Q(x)	P(x) &Q(x)
Тожд. истинные	Тожд. истинные	Тожд. истин.	1	1	1	1

Рассмотрим случай 2b. P(x) –тождественно истинная, а Q(x) - нет

P(x)	Q(x)	P(x) &Q(x)
Тожд. истиные	0	0	1	0	0	0
Тожд. истиные	1	1	1	0	0	0

Рассмотрим случай 2c. P(x) и Q(x) оба не тождественно истинные

P(x)	Q(x)	P(x) &Q(x)
0	0	0	0	0	0	0
0	1	0	0	0	0	0
1	0	0	0	0	0	0
1	1	1	0	0	0	0

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

4. 
   Следовательно, указанные формулы равносильны.
   

1. 
   Предположим, что это не так, что формула не общезначима, т.е. должно найтись P(x) и Q(x), такие, на которых формула равно 0.
   
2. 
   Тогда,
   

Таким образом, мы получили тождественно истинное высказывание для любых R(x) и Q(x).

3. 
   Следовательно, наше предположение об отсутствии общезначимости было неверным, и наша формула – общезначима.
   

1. 
   Сначала принимают предположение, что утверждение A верно, а затем рассматривается особый случай – контрпример, при котором данное утверждение A неверно.
   
2. 
   Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение.
   

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

3. 
   Правая и левая части формулы не равны между собой. Это означает, что мы получили противоречие и на данном контрпримере рассматриваемая формула ложна.
   
4. 
   Следовательно, наше предположение об общезначимости было неверным.
   
5. 
   Значит, рассматриваемая формула не является общезначимой.
   

Литература

1. 
   Капитонова Ю.В. и др. Лекции по дискретной математики СПб.: БХВ-Петербург, 2004.- 624с.
   
2. 
   www.wikipedia.org