lekcii_dm

около квадратных скобок показывается то место в дереве, где «оборванный лист» был использован (то есть посылки, заключенные в квадратные скобки, стали ненужными). Дерево вывода можно читать так: необорванные листья доказывают корень.

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

A 1

то ├A B

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

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

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

191

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

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

Г╞

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

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

A 1

192

A 1

(reductio ad absurdum)

Замечание.

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

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

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

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

N 1,2,3,...,n,... .

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

N 0 0,1,2,3,...,n,... .

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

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

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

193

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

Символом n! обозначается факториал произведение n! 1 2 n , где n N . Например, 5! 1 2 3 4 5 120. По определению полагают 0! 1.

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

Теорема 2

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

2. Для любого k N , если k A, то k 1 A . Тогда A N .

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

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

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

Теорема 4

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

194

математической индукции. Неравенство КошиБуняковского.

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

Для любых чисел a1,...,an ,b1,...,bn

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

При n 1 неравенство a1b1 2 a12b12 верно. Допустим,

a1b1 a2b2 ... ak bk 2 a12 ... ak 2 b12 ... bk 2 .

Докажем, что

a1b1 ... ak bk ak 1bk 1 2

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

a1b1 ... ak bk 2 2ak 1bk 1 a1b1 ... ak bk ak 12bk 12

a12 ... ak 2 b12 ... bk 2 ak 12bk 12

ak 12 b12 ... bk 2 bk 12 a12 ... ak 2 .

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

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

ak 1b1 a1bk 1 2 ak 1b2 a2bk 1 2 ... ak 1bk ak bk 1 2 0.

195

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

Определение

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

чисел a1,a2 ,...,an .

2.Если a1 0,...,an 0, то число a1 a2 ... an 1n называется средним геометрическим чисел a1,a2 ,...,an .

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

Пусть a1 0,...,an 0, тогда

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

Шаг первый: сначала индукцией докажем это неравенство для

Последнее неравенство верно, значит, и первоначальное верно, так как они равносильны. Допустим, неравенство верно при m=k, то есть

196

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

После элементарных алгебраических преобразований получили: a1 a2k ...1 ak 1 a1 a2 ... ak 1 1k a1 a2k ...1 ak 1 1k .

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

a1 a2k ...1 ak 1 k 1k a1 a2 ... ak 1 1k .

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

a1 a2k ...1 ak 1 a1 a2 ... ak 1 1k 1.

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

197

6.04. Примеры задач и упражнений.

На основании ММИ равенство (1) верно при любом n .

198

Пример 2

Доказать, что для любого n N

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

1.Базис индукции: проверим утверждение (3) при n 1. ЛЧ=1 1! 1, ПЧ= 1 1! 1 2! 1 1. Базис индукции доказан.

2.Индуктивное утверждение: допустим, (3) верно при n l , то есть допустим:

3. Индуктивный переход: докажем (3) при n l 1, используя (4), то есть докажем, что

1 1! 2 2! ... l l! l 1 l 1! l 2 ! 1.

В самом деле,

1 1! 2 2! ... l l! l 1 l 1!

l 1! 1 l 1 l 1!

l 1! l 2 1 l 2 ! 1.

199

1. Базис индукции: проверим (5) при n 1. ЛЧ=4+15-1=18 делится

на 9.

3. Индуктивный переход: докажем (5) при n m 1, используя (6), то есть докажем, что 4m 1 15(m 1) 1 делится на 9.

4m 1 15(m 1) 1 4 4m 15m 15 1

(4m 15m 1) (3 4m 15).

Первая скобка делится на 9 по индуктивному предположению. Осталось доказать, что второй слагаемый делится на 9, то есть надо доказать, что 4m 5 делится на 3. Это утверждение мы будем доказывать методом математической индукции, то есть нам придется применять "индукцию в индукции". При m=1 4+5=9 делится на 3. Допустим, 4k 5 делится на 3. Докажем, что 4k 1 5 делится на 3, но 4k 1 5 4 4k 5 4k 5 3 4k . Первый слагаемый делится на три по индуктивному предположению, а второе – очевидно. Таким образом, мы доказали, что 4m 5 делится на 3, а вместе с этим, что 4n 15n 1 делится на 9.

200