Главная » Просмотр файлов » Дж. Андерсон - Дискретная математика и комбинаторика (2004)

Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 20

Файл №1127091 Дж. Андерсон - Дискретная математика и комбинаторика (2004) (Дж. Андерсон - Дискретная математика и комбинаторика (2004)) 20 страницаДж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091) страница 202019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Обычно целые числа "упорядочены" следующим образом: ., -4,-3, -2, -1,0,1,2, 3,4,5, где все положительные числа "идут за" нулем, а нуль "идет за" или "больше,чем" любое отрицательное число. Трихотомия позволяет установить, является ли число положительным, поэтому отношение > на множестве Я х Я можно определить так; а > Ь тогда и только тогда, когда а — Ь положительно. В силу трихотомии, а — 6 либо положительно, либо нуль, либо отрицательно. Поэтому можно объединить две из этих возможностей в одну и говорить, что а > Ь тогда и только тогда, когда а > Ь или а = Ь.

Сказанное выше формализуем в виде следующего определения. ОПРЕДЕЛЕНИЕ 3.9. Для целых чисел а и Ь имеем; а > Ь тогда и только тогда, когда а — Ь положительно; а > Ь тогда и только тогда, когда а > 6 или а = 6. Кроме того, Ь < а равносильно а > 6 и Ь < а равносильно а > 6. Очевидно, а > О равносильно утверждению, что а положительное, потому что а > О тогда и только тогда, когда а — О = а положительное. Аналогично, а < О равносильно утверждению, что а отрицательно. Хотя приведенные ниже утверждения хорошо известны и могут рассматриваться как предположения, они приведены для практики доказательства теорем.

ТЕОРЕМА 3.10. Для целых чисел а и Ь: а) (а>Ь)д(6>а) — а=6; б) (а>6)д(Ь>с)- а>с. ДОКАЗАТЕЛЬСТВО. а) Здесь мы используем принцип сведения к абсурду. Если, предположив, что утверждение в части (а) ложно, мы получим противоречие, то 'В отечественной литературе положительные целые числа принято называть числами натуральнымн. — Прим. ред. 128 ГЛДВА 3. Логика, целые числа и доказательства истинность этого утверждения будет доказана. Предположим, что утверждение в части (а) ложно. Тогда, если а > 6, Ь > а и а Ф Ь, то а > Ь и Ь > а.

Но в этом случае а — Ь положительно и 6 — а = — (а — 6) положительно, что противоречит аксиоме трихотомии (чЗ. Так как мы пришли к противоречию, должен иметь место случай а = Ь. б) Если а > Ь и 6 > с, то а — 6 и Ь вЂ” с положительны. Следовательно, согласно Ы2 число (а — Ь) + (Ь вЂ” с) = а — с положительно, и а > с. ТЕОРЕМА 3.11. Пусть а, 6, с и д — целые числа. Тогда а) (а > Ь) д (с > д) — а + с > Ь + д; б) (а>0)Л(с>г()- ас>аа; в) (а>Ь>0)д(с>д>0) — ас>Ы; г) (а > Ь > 0) д (с > д > 0) — ас > Ы.

ДОКАЗАТЕЛЬСТВО. а) Если а > Ь и с > д, то числа а — Ь и с — д положительны. Следовательно, (а — 6)+(с — д) положительно. Но (а — 6)+(с — д) = (а+с) — (Ь+д), и поэтому а+ с > с+ д. б) Если с > д, то разность с — д положительна. Поскольку а положительно, а(с — д) = ас — ад также положительно, и ас > ад. в) Если а > 6 > 0 и с > д > О, то ас > Ьс и Ьс > Ы. Поэтому ас > Ы. г) Доказательство этой части предоставляется читателю. Далее иллюстрируется применение доказательства перебором.

Выбор из трех возможностей обычно имеет вид р р (гх«ганг) г — ««г г — «я г — «д ТЕОРЕМА 3.12. Пусть и — целое число. Тогда из > О. ДОКАЗАТЕЛЬСТВО. Поскольку и — целое число, согласно аксиоме трихотомии оно либо положительно, либо отрицательно, либо равно О. Если и положительно, то и и положительно по аксиоме й)2, и из > О. Если и отрицательно, то и = — т для некоторого положительного целого числа ги.

Поэтому из = ( — ги)( — ги) = тз опять является положительным, и и > О. Если и = О, то ип = О, так что и > О. Следовательно, из > О. ° УПРАЖНЕНИЯ 1. Пусть а, Ь и с — целые числа. Докажите, что а) если Ь+ а = с+ а, то 6 = с; б) а 0 = 0 для любого целого числа а; в) — ( — а) = а для любого целого числа а; г) а. ( — 6) = — (аЬ); д) ( — а) ( — 6)=а Ь; е) — (а + Ь) = ( — а) + ( — 6). РдЗДЕЛ З.З. Математическая индукция 129 2. Докажите, что если а + Ь = а, то Ь = О.

3. Докажите, что если а > Ь > О и с > й > О, то ас > Ы, 4. Докажите, что аз > а для любого целого числа а. 5. Докажите неравенство аз + Ьз > 2аЬ для целых чисел а и Ь. 3.3. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ Одна из наиболее сложных проблем теории чисел состоит в доказательстве истинности утверждений для всех положительных целых чисел. Если утверждение истинно для первых десяти положительных чисел или даже для первых десяти биллионов положительных чисел, то из этого еще не следует, что утверждение истинно для всех положительных целых чисел. Обычно легко доказать, что утверждение не является истинным для всех положительных целых чисел.

В самом деле, используя тот факт, что отрицание (сх)Р(х) есть (Эх) Р(х), необходимо найти только одно положительное целое число, для которого утверждение Р(а) не является истинным. Эта процедура известна как нахождение комгпрлримера. Инструментом для доказательства истинности утверждений относительно всех положительных чисел является принцип индукции, который будет нашей последней аксиомой для множества положительных чисел Х. Это вовсе не означает, что доказательство любого утверждения относительно положительных чисел требует индукции. Многие теоремы могут быть доказаны на основе других теорем и аксиом.

Тем не менее, в основе доказательств многих рассматриваемых ниже теорем лежит принцип индукции. В дальнейшем принцип индукции будет сформулирован в другой, эквивалентной форме. (й)4) (Принцип математической индукции) Пусть Р(п) есть такое утверждение, что а) Р(1) истинно, и б) для каждого й, если Р(й) истинно, то Р(9+ 1) истинно. Тогда Р(п) истинно для любого целого положительного числа и.

В символической записи принцип математической индукции имеет вид (Р(1) д ((Ж) Р(к) — Р(lс + 1)) — (Уп) Р(п) . Математическую индукцию можно сравнить с бесконечным рядом костяшек домино. Свойство выстроенных в ряд домино состоит в том, что если опрокинуть одну костяшку, падает следующая. Пусть утверждение Р(п) состоит в том, что падает и-я костяшка. Опрокидывание первой костяшки домино обозначим Р(1), т.е. истинность Р(1) состоит в том, что первая костяшка падает.

Поскольку каждая костяшка опрокидывает следующую, то из истинности Р(й) следует истинность Р(й+ 1). Поскольку падают все костяшки, Р(п) истинно для каждого положительного целого числа п. В дальнейшем, проводя доказательство при помощи описанного выше принципа математической индукции, мы будем просто говорить, что доказываем утверждение по индукции. 130 ГЛАВА 3. Логика, целые чосла и оокаэательотеа ПРИМЕР 3.13.

Допустим, необходимо найти формулу для вычисления суммы первых и положительных целых чисел, 1+2+3+ +и. Такая формула была бы полезна, если надо было бы, например, найти сумму первых 100000 положительных целых чисел, не выполняя для этого 99999 операций сложения. Предположим, у нас имеются основания полагать, что сумма первых и положительных чисел равна -"-(-"з'— 'с. Докажем это утверждение по индукции.

Пусть Я„есть утверждение 1+2+3+ +и= п(п+ 1) 2 (1) Сначала покажем, что Яэ истинно. При и = 1 левая часть равенства 1+2+3+ .+и равна 1. Справа получаем п(п+ 1) 1(1+ 1) 2 2 так что Яэ истинно. Затем предполагаем, что для любого положительного числа й Яь истинно, т.е.

равенство (1) истинно для и = к. Это означает, что 1+2+3+ . +/с = к(й + 1) 2 Теперь необходимо доказать, что Яььэ истинно, т.е. равенство Я„истинно для и = й+ 1. Другими словами, требуется доказать, что 1 + 2 + 3 + + й + (/с + 1) = 2 Используя предположение 1+2+3+. +/с= й(й + 1) 2 и сравнивая это равенство с предыдущим, мы замечаем, что, добавив й + 1 к обеим частям последнего равенства, получим левую часть искомого равенства: 1+2+3+ +/с= й(й + 1) 2 1+2+3+- +Й+(/с+1) = +(0+1) = й(й+ 1) 2 й = (/с + 1)(- + 1) = 2 (й + 1)((й + 1) + 1) 2 Итак, доказано равенство 1+2+3+ +й+(9+1) = которое означает, что соотношение (1) справедливо для и = 0+1. Этот результат обеспечивает истинность Як+э.

Следовательно, в силу аксиомы й)4, Я„истинно для любого положительного целого числа п. П РЯЗДЕЛ З.З. Математическая индукция 131 ПРИМЕР 3.14. Требуется доказать, что 1+2+3+ +п п(п + 1)(2п + 1) 6 (2) Ц1+ 1)(2 1+ 1) 6 что дает нам 1 = 1 и обеспечивает истинность утверждения Я„при п = 1. Затем мы предполагаем, что равенство Я„истинно для п = й. То есть, г г й(й+ 1)(2й+ 1) 1г+2г+3г+ . +йг = 6 Теперь требуется доказать, что равенство Я„истинно для п = й+1. Иначе говоря, требуется доказать, что ,г .

г (й + 1)Ий + 1) + 1)(2(й + 1) + 1) (й + 1)(й + 2)(2й + 3) 6 Используя предположение й(й + 1Н2й + 1) 1+2+3+...+йг = замечаем, что, прибавив к обеим частям последнего равенства (й+ 1)г, мы полу- чим левую часть искомого равенства. Таким образом, г й(й+ 1)(2й+ 1), 1+2+3+ . +йг й(й + 1) (2й + 1) 1+2+3+ +й~+(й+1) = ' '' ' +(й+1) 6 й(й+1)(2й+1) 6(й+1)г 6 6 й(й+1)(2й+1) +6(й+1)' 6 (й + 1) [й(2й + 1) + 6(й + 1)] 6 (й+ 1)(2йг + тй+ 6) 6 (й+ 1)(2й+3)(й+2) 6 Пусть Я„обозначает утверждение, что равенство в уравнении (2) выполняется.

Сначала покажем, что утверждение Я„истинно для и = 1. Подставляя 1 в обе части равенства, получаем 132 ~ЛАВА 3. Пегова, целые числа и докаэательсгпва Итак, доказано равенство РАЗДЕЛ З.Э гаагпемагпичеекея индукцон 133 Поскольку в формулировке задачи сирашиваетси о всех возможных случаях оасиоложеиии облассей и лиииЙ, ззо иоивоаис к бескоиечио большому числ1 134 ГЛДИА 3. Логока, цепые виспа о дпказатепьгппаа РАЗДЕЛ 3.3.

Математическая индукцюя 135 цвет был изменен по обе стороны от 1, делая цвета разли ~нв1ми по обе стороны от такой гоанииы. Таким обоазом. зтот чеотеж. выполненный с использованием 136 ГЛК8А 3. Логика, целые числа и доказательства ТЕОРЕМА 3.18. Если множество целых чисел имеет наименьшее целое число, то такое число единственно. ДОКАЗАТЕЛЬСТВО.

Допустим, что числа а и Ь оба являются наименьшими элементами множества А. По определению наименьшего элемента а < Ь и Ь < а. Следовательно, а = Ь. Теперь сформулируем два утверждения, эквивалентные принципу индукции. (Хб) (Принцип полного упорядочения) Каждое непустое множество положительных целых чисел содержит наименьший элемент. (Хб) 1'Второй принцип индукции) Пусть Р(п) — утверждение. Если а) Р(1) истинно, и б) для произвольного к из истинности Р(т) для всех т < 9 следует истинность Р(п), то Р(п) истинно для всех положительных целых чисел и. В символической форме принцип индукции имеет вид (Р(1) д ((Уй)(Ут < й)Р(т)) — Р(9)) — (чп) Р(п) . Пример использования второго принципа индукции Хб будет приведен ниже при доказательстве того, что каждое целое число представляет собой произведение простых чисел.

Следующая теорема — пример утверждения, которое может показаться слишком очевидным для проведения его доказательства, но поскольку рассматриваемая модель целых чисел определена совокупностью правил, для наших "целых чисел" эти утверждения могут не оказаться столь очевидными или даже истинными. Мы можем установить это, доказывая соответствующую теорему с использованием имеющихся правил. Доказательство является хорошим примером использования принципа полного упорядочения Х5.

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

Тип файла
DJVU-файл
Размер
7,96 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6430
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее