Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 19
Текст из файла (страница 19)
Докажите, что из Зх (Р(х) д Я(х)) следует, что Вх Р(х) д Бх Я(х). РАЗДЕЛ 3.2. Основные положения теории доказательств и теории целых чисел 123 11. Проверьте правильность умозаключений при помощи диаграмм Эйлера. Все адвокаты богаты Некоторые адвокаты богаты Все богатые едят омаров Некоторые врачи богаты се адвокаты едят омаров .. екоторые врачи — адвокаты 12. Проверьте правильность умозаключений при помощи диаграмм Эйлера. Некоторые марсиане зеленые Все мужчины любят мясо Все елки зеленые Некоторые учителя — мужчины екоторые марсиане — елки ,. екоторые учителя любят мясо 13.
Проверьте правильность умозаключений при помощи диаграмм Эйлера. Все врачи любят музыку Некоторые врачи умные Все поэты любят музыку Все умные люди поэты се врачи — поэты екоторые врачи — поэты 14. Проверьте правильность умозаключений при помощи диаграмм Эйлера. Все машины дорогие Все мужчины смотрят телевизор Велосипед недорогой Некоторые слесари — мужчины елосипед — не машина ... екоторые слесари смотрят телевизор 15. Проверьте правильность умозаключений при помощи диаграмм Эйлера. Все люди смертны Некоторые гуси — мужчины Гуси — не люди Некоторые мужчины играют в гольф :.
Губ«р ,, Некоторые гуси играют в гольф 3.2. ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕОРИИ ДОКАЗАТЕЛЬСТВ И ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ В данном разделе рассматриваются некоторые свойства целых чисел, которые докажут свою полезность в дальнейшем. Возможно, более важная цель — использовать множество целых чисел как хорошо известную предметную область для развития и применения на практике техники доказательства теорем. Первая проблема — с чего начать. Что можно считать известным и, следовательно, использовать в доказательстве теорем? В общем курсе по теории чисел можно было бы начать с основных аксиом теории чисел и развивать изложение в этом направлении.
В нашем случае это не совсем целесообразно. Вторая проблема— решить, какие детали включать в рассмотрение. Нужно ли объяснять, почему в одном месте доказательства имеем 4+ х + 5 = у, а в другом — у = х + 9? Если обращать внимание на все несущественные детали, то основные моменты доказательства затеряются в таком хаосе. Обычно предполагается, что все детали читателю понятны и в случае необходимости он может сам их воспроизвести. Не существует точных правил, которые бы говорили, о чем нужно упомянуть, а что можно опустить.
Изящное изложение доказательства теоремы — искусство. В дальнейшем мы будем предполагать, что большинство аксиом, перечисленных в этом разделе, известны и могут использоваться без подробных разъяснений. Для начала примем следующие аксиомы равенства. Они распространяются на элементы любого множества, в том числе и множества 2 целых чисел. 124 гллВА э. логика, целые числа ц доказательстве (Е1) Для любого а, а = а, (Е2) Для любых а и Ь, если а = Ь, то Ь = а. (ЕЗ) Для любых а, Ь и с, если а = Ь и Ь = с, то а = с. Аксиомы Е1, Е2 и ЕЗ говорят о том, что равенство на любом множестве обладает свойствами отношения эквивалентности.
Эти аксиомы распространяются на все математические формы, а не только на теорию чисел. Примем также следующие свойства сложения, вычитания и умножения на множестве Я целых чисел. (11) Если а и Ь вЂ” целые числа, то а+6 и а 6 — целые числа. Множество целых чисел замкнуто относительно операций сложения и умножения. (12) Еслиа=Ьис=а,тоа+с=6+а и а с=Ь г(. (13) Для любых целых чисел а и 6 имеют место равенства а+ Ь = 6+ а и а 6 = 6 а. Множество целых чисел коммутативно относительно операций сложения и умножения. (14) Для любых целых чисел а, Ь и с имеют место равенства (а+6)+с = а+(6+с) и а (Ь с) = (а Ь) с. Множество целых чисел ассоциативно относительно операций сложения и умножения.
(15) Для любых целых чисел а, Ь и с имеет место равенство а (Ь+с) = (а 6)+(а.с). Умножение целых чисел дистрибутивно относительно сложения. (16) Существуют единственные целые числа О и 1 такие, что а+ О = О+ а = а и а 1 = 1. а = а для любого целого числа а. Целое число О называется нейтральным элементом сложения, или нулем множества целых чисел, целое число 1 называется нейтральным элементогг умножения. (17) Для каждого целого числа а существует единственное целое число -а, называемое его обратным элементом относительно сложения, такое, что а + (-а) = ( — а) + а = О.
(18) Если Ь и с — целые числа и для некоторого ненулевого числа а имеем а Ь = а с, то Ь = с. Это утверждение называется мультипликативным свойством сокращения. Как уже отмечалось, в математике принято доказывать теоремы без излишнего формализма, поскольку предполагается, что читателю известны многие детали, поэтому нет необходимости излагать их явно. Для иллюстрации такого подхода сначала будет дано формальное доказательство того, что квадрат четного числа есть число четное. Поскольку предметная область — множество целых чисел, формально утверждение теоремы имеет вид Уп(п — четное — п — четное).
г Формальное доказательство теоремы изложено ниже. Для доказательства истинности утверждения с навешенным квантором всеобщности одновременно используется принцип универсального обобщения. РАЗДЕП 3.2 Основные полоксения теории доказательств и теории цепык чисел 125 1.
2. 3. 4. фиксированный элемент универса задано (предположение) определение четного числа 1, 3 и универсальная конкретиза- ция 2, 4 и правило отделения 5 и экзистенциональная конкрети- зация следует из аксиомы !2, известно 7 и универсальная конкретизация б, 8 и правило отделения 9 и свойство ассоциативности це- лых чисел (шаги опущены для краткости) свойство транзитивности равенства а — целое число а — четное 'чп(п — четное — (Ун)(п = 2/с)) а — четное ч (Э!с)(а = 2н) 5. (Э!с)(а = 2!с) б. а = 27, для некоторого 7, 7. УттГа(т = а — тг = аг) 8. (а = 27,) — аг = (27,)г 9.
аг = (27,)г 1О. (27)г = 2(27г) 11. ЧхЧуЧг((х = у и у = г) х = г) 12 пг (21)г и (27,)г 2(2г,г) — аг = 2(27,г) 13. аг = (2Ь)г и (27,)г = 2(2г,г) 14. аг = 2(2г,г) !5 (хй)(аг = 2!с) 9, 11 и универсальная конкретиза- ция 9, !О и закон конъюнкции 12, 13 и правило отделения 14 и экзистенциональное обобще- ние для фиксированного значения (2г г) определение четного целого числа 16 и универсальная конкретизация для фиксированного значения аг 15, 17 и правило отделения 2, 18 и то, что ((р д 9) — (р — 9) есть тавтология) 1, 19 и универсальное обобщение !б. Чх((х/с)(х = 2н) — х — четное) !7.
(хгс)(аг = 2/с) — а — четное 18. аг — четное 19. а — четное — а — четное г 20. Чп(п — четное — пг — четное) ДОКАЗАТЕЛЬСТВО. Предположим, что и — (произвольное) четное целое число. По определению четного целого числа существует целое число 7, такое, что Если целые числа равны, то равны квадраты этих чисел, так что пг = (2г,)г. Но (2~)г (2Б) (27 ) 2(27 г) Приведенные выше рассуждения выписаны более формально, чем это принято в курсах математической логики. Этот пример иллюстрирует, как в конкретном случае взаимодействуют законы логики, кванторы, правильные умозаключения и вывод. Более типичное для данной книги математическое доказательство приведено ниже.
ТЕОРЕМА 3.6. Если и четно, то пг тоже четно. 128 ГЛАВА 3. Логика, целые числе и доказательстве поэтому пз = 2(2Ез) и пз = 2й для некоторого целого числа й (а именно 1 = 2г,з). По определению четного целого числа пз — четное число. В качестве другого примера рассмотрим утверждение, обратное предыдущему. ТЕОРЕМА 3.7.
Если пз четно, то и п четно. ДОКАЗАТЕЛЬСТВО. Доказательство этой теоремы будет примером доказательства методом контралозиции вместо прямого доказательства самой теоремы. Этот метод доказательства возможен, т.к. Р 'Я= Я ' Р. Это означает, что доказательство о — р эквивалентно доказательству р — и. Утверждение Ч ' Р означает следующее: Если п не является четным, то п тоже не является четным. Пусть п — целое число, которое не является четным (наномним, что четные целые числа имеют вид 2К, а нечетные целые числа имеют вид 21 + 1, и целое число является либо четным, либо нечетным, но не может быть и тем, и другим одновременно).
Необходимо показать, что число пз — нечетное. Поскольку п нечетное, существует целое число Е такое, что п=21+1. Возводя в квадрат обе части соотношения, получаем пз = (21+ 1)з = = 4Дг + 41, + 1 = = 2(2г'~+ 2Ь) + 1. Так что, если 1 = 2Ез+ 21„имеем п~ = 2.У+ 1.
По определению нечетного числа число пз нечетно, и теорема доказана. Доказательство следующей теоремы предоставляем читателю. ТЕОРЕМА 3.8. Пусть а, Ь и с — целые числа. а) Если 6+ а = с+ а, то Ь = с. б) Для любого целого числа а имеет место равенство а О = О. в) Для любого целого числа а имеет место равенство — ( — а) = а. г) а ( — 6) = — (а6). д) ( — а) ( — Ь)=а 6. е) — (а + Ь) = ( — а) + ( — Ь). РАЗДЕП 3.2.
Основные положения тесрио доказательств и теории целых чисел 127 Множество целых чисел Я содержит подмножество Аг положительных целых чисел. Примем в качестве аксиом следующие утверждения относительно множества Аг. (зч1) Целое число 1 есть положительное целое число.
(Ы2) Множество положительных целых чисел замкнуто относительно сложения и умножения, т.е. если а и 6 — положительные целые числа, то а+6 и а 6— положительные целые числа. (ХЗ) 1Аксиолеа лзрихотомии) Для каждого целого числа а истинным является одно и только одно из перечисленных ниже утверждений: а) а — положительное целое число; б) а=О; в) -а — положительное целое число. Далее приведено частичное упорядочение целых чисел, в котором целые числа расположены по принципу "большее за меньшим".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
