Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

В теории доказательств общепринята запись правил вывода не только в строчной форме, но и в вертикальной форме дерева, поэтому в определениях правил вывода мы будем выписывать обе формы их представ­ления.

исключение «и» ├

исключение «и» ├

введение «и» ├

введение «или» слева ├

введение «или» справа ├

исключение «или» Если ├ и ├ ,

то ├

Последнее правило можно прочесть так: если С доказано с использованием допущения А, и С доказано с использованием допущения В, и при этом мы знаем, что верно , то можно считать доказанным С (уже без предположений о верности A и В).

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

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

правило исключения импликации ├

правило введения импликации если ├ ,

то ├

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

Правило исключения импликации ├ называется 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) отказаться, то правило (е) уже будет совершенно необходимо.

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

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

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

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

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

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

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

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

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

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

Теорема 2

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

1. .

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

Тогда .

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

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

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

Теорема 4

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

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

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

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

.

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

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

.

Докажем, что

.

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

.

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

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

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

Определение

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

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

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

Пусть , тогда

. (1)

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

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

. (2)

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

.

В самом деле,

.

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

, (3)

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

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

.

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

.

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

.

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

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

Пример 1

Доказать, что

. (1)

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

Метод математической индукции будем оформлять по следующей схеме.

1. Базис индукции: проверим равенство при . Левая часть (ЛЧ)=1, правая часть (ПЧ)= . Равенство при , то есть базис индукции, выполняется.

2. Индуктивное предположение: допустим, равенство (1) верно при , то есть допустим, что

. (2)

3. Индуктивный переход: докажем равенство (1) при , то есть докажем, что . В самом деле, . Здесь мы применили индуктивное предположение. Далее , что и требовалось доказать.

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

Пример 2

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

. (3)

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

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

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

. (4)

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

.

В самом деле,

.

Пример 3

Доказать, что для любого делится на 9. (5)

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

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

2. Индуктивное предположение: допустим, (5) выполняется при , то есть делится на 9. (6)

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

.

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

Пример 4

для любого .

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

При n=1 неравенство очевидно: 2>1. Допустим, . Докажем, что . В самом деле, , так как по индуктивному предположению и – очевидное неравенство.

Пример 5

для любого натурального .

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

При n=5 получаем верное неравенство 32>25. Допустим, неравенство верно при , то есть . Докажем, что . Это неравенство равносильно . Если мы докажем, что , то будет доказано и исходное неравенство. Неравенство доказываем индукцией (индукция в индукции). При имеем верное неравенство . Допустим, неравенство верно при , то есть . Докажем при , то есть докажем, что или . Очевидно, что это неравенство верно в силу индуктивного предположения.

57.Задачи для самостоятельного решения.

1. Доказать методом математической индукции, что для любого .

2. Доказать методом математической индукции, что для любого ;

3. Доказать методом математической индукции, что для любого .

4. Доказать методом математической индукции, что для любого .

5. Доказать методом математической индукции, что для любого ;

6. Доказать методом математической индукции, что для любого .

7. Доказать методом математической индукции, что для любого ;

8. Доказать методом математической индукции, что для любого .

9. Доказать методом математической индукции, что для любого справедливо равенство

10. Доказать методом математической индукции, что для любого

11. Доказать методом математической индукции, что для любого .

12. Доказать методом математической индукции, что для любого .

13. Доказать методом математической индукции, что для любого .

14. Доказать методом математической индукции, что для любого .

15. Доказать методом математической индукции, что для любого .

16. Доказать методом математической индукции, что для любого .

17. Доказать методом математической индукции, что для любого .

18. Доказать методом математической индукции, что для любого .

19. Доказать методом математической индукции, что для любого ;

20. Доказать методом математической индукции, что для любого .

1. Элементы комбинаторики.

58.Основные понятия комбинаторики.

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

Комбинаторика — раздел математического анализа, посвященный способам под­счета числа элементов в конечных множествах.

Характеристики

Список файлов лекций