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

Правило исключения импликации ├ называется modus ponens.

Это правило — настоящий камень преткновения для теории доказательств. Дело в том, что при помощи этого правила можно фактически заменять одну формулу на любую другую, из неё вытекающую. Если большинство других правил при­менимы только в определённых ситуациях, и вариантов их применения обычно не очень много, то modus ponens можно применять практически всегда, и невоз­можно угадать, на какую именно формулу В нужно сейчас заменить формулу А. Это свойство modus ponens делает его очень сложным для автоматизации: как объяснить компьютеру, когда применять modus ponens?

Поэтому логики неоднократно пытались либо удалить modus ponens из доказательств вообще, либо как-нибудь его ограничить, чтобы его можно было автоматизировать; та­кие попытки называются общим термином cut elimination.

Обратимся к правилам, имеющим дело с логическим значком отрицания. Введём псевдоформулу  «ложь», истинностное значение которой во всех ин­терпретациях будем считать нулём (можно было бы вместо неё считать ложью, например, для какой-нибудь предметной переменной х и какого-нибудь предиката А). С помощью такой псевдоформулы можно, например, лег­ко записать противоречивость множества формул Г следующим образом:

Г╞

Теперь можно сформулировать правила для значка отрицания и константы «ложь»:

(е) правило исключения   ├ A

Это правило допускает простую интерпретацию: из лжи следует все что угодно (ex falsum sequitor quodlibet). Поскольку в явном виде этот логический принцип впервые сформулировал Иоанн Дуне Скот, его иногда называют «правилом Дунса Скота».

(i) правило введения константы «ложь» ├ 

(i) правило введения отрицания Если ├, то ├

(RAA) правило сведения к противоречию Если ├, то ├

(reductio ad absurdum)

Замечание.

Правило Дунса Скота (е) в приведённой системе лишнее: оно сле­дует из (RAA) и других правил; а вот если от (RAA) отказаться, то правило (е) уже будет совершенно необходимо.

2. Метод математической индукции.

Метод математической индукции ММИ лежит в основе доказательства огромного числа теорем в различных разделах дискретной математики.

Буквой обычно обозначается множество натуральных чисел:

 – расширенное множество натуральных чисел, то есть

Пусть обозначает некоторое свойство натуральных чисел.

Теорема 1 (стандартный ММИ)

Пусть свойство верно при и пусть из истинности при следует его истинность при . Тогда свойство верно для любого .

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

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

Теперь сформулируем несколько утверждений, эквивалентных ММИ.

Теорема 2

Пусть множество обладает следующими свойствами.

1..

2. Для любого , если , то .

Тогда .

Теорема 3 (возвратный ММИ)

Пусть свойство Р(n) выполняется при n=1 и из того, что оно верно для любого , следует, что Р верно при n. Тогда Р верно при любом натуральном n.

И последнее. Индуктивный процесс не обязан начинаться с 1. В качестве базиса индукции может выступать любое целое число a.

Теорема 4

Пусть свойство P(n) выполняется при n=a и из истинности его для любого следует истинность для k+1. Тогда P(n) истинно для любого целого .

3. Доказательство неравенств методом математической индукции. Неравенство Коши-Буняковского.

Теорема 1 (неравенство Коши-Буняковского)

Для любых чисел

.

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

При неравенство верно. Допустим,

.

Докажем, что

.

Перепишем это неравенство, частично раскрыв скобки:

.

Легко заметить, что для того, чтобы доказать это неравенство, достаточно доказать

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

А это и доказывает неравенство Коши-Буняковского.

Определение

1. Число называется средним арифметическим чисел .

2. Если , то число называется средним геометрическим чисел .

Теорема 3 (неравенство Коши)

Пусть , тогда

. (1)

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

Шаг первый: сначала индукцией докажем это неравенство для натуральных чисел вида . При m=1 надо доказать, что . Это неравенство эквивалентно , то есть . Последнее неравенство верно, значит, и первоначальное верно, так как они равносильны. Допустим, неравенство верно при m=k, то есть

. (2)

Докажем неравенство (1) для m=k+1, то есть докажем, что

.

В самом деле,

.

Итак, мы доказали неравенство Коши, когда количество чисел в средних есть степень двойки. А как быть с остальными? Для них мы докажем неравенство Коши, используя еще одну модификацию индукции – "индукцию вниз". Допустим, что неравенство Коши верно для n=k, то есть допустим, что

, (3)

и докажем это неравенство для n=k-1. Для этого в неравенстве Коши положим , тогда (3) будет иметь вид:

После элементарных алгебраических преобразований получили:

.

Сократим неравенство на второй множитель правой части:

.

И, наконец, возведем обе части неравенства в степень :

.

Неравенство Коши доказано полностью.