Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 155
Текст из файла (страница 155)
Поскольку (а, Ь) б й и (Ь, с) б Я, то (а, с) б Я о й. Поскольку (6, Н) б Т о Я и (а, 6) б й, то (а, д) б (Т о Я) о й. Таким образом, Т о (В о й) С (Т о Я) о й. Раздел 2.6. 1. (а), (г). Ответы к упражнениям 889 б) 3. а) Л. в) ° ° ° ° аЬсд 5. а) ((а,а),(Ь, Ь),(с, с),(а, д),(е, е),(а, а),(4(, с),(д, Ь),(а, е),(а, Ь),(с, Ь)); б) ((а„а), (Ь, 6),(с, с), (д, д), (е, е), (д, Ь), (41,а), (д, е), (с, е),(с, а), (с, 6),(е,а), (е, 6)); в) ((а, а), (Ь, 6), (с, с), (д, д), (е, е), (Д 2 ), (а, Ь), (а, с), (2, Ь), (2, с), (Д 4(), (е, д),; (е, с)) г) ((а, а), (Ь, Ь), (с, с),(д, д), (е, е), (е,а), (е, Ь), (е, с), (е, д), (П, а), (41, Ь), (с(, с)); д) ((а,а),(6, Ь),(с, с),(п,а),(е, е),(с,а),(с, Ь),(е,а), (е, Ь)). 7. Никакие два элемента не сравнимы.
Раздел 2.7. 1. в) нет; б) нет. в) да, (р] = (9: 9 имеет такую же таблицу истинности, как и р); г) да, ((а, Ь] = ((с, д): ай = Ьс); д) да, [и] = (п, — и); е) да, (и] = (и). 3. а) да, (В] = (С: С содержит такое же количество элементов, как и В); б) да, [Ц = А; в) да, (Ц = (1,3,5,7,9), (2] = (2,4,6,8,10); г) нет; д) Да, (и] = (т; т параллельно и); е) Да, [р] = (9: р написано на том же языке программирования, что и 4).
5. а) для всех а 6 А имеем У(а) = У(а), поэтому й рефлексивно. Если 7(а) = 7(Ь), то /(Ь) = 7(а), поэтому В симметрично. Если 7(а) = 7(Ь) и 7(Ь) = 7(с), то Г(а) = 7(с), поэтому В транзитивно. Следовательно,  — отношение эквивалентности; б) (Ц (1 1),[2] (2 2) [0] — (0) [3] — (3) ( 1] — ( ) [,Ц вЂ” (4) 7.
а) нет; б) Я = ( ( 1, Ц, (1, 2), (2, 1), (2, 2), (3, 3), (4, 4), (5, 5), (3, 4)(4, 3), (3, 5), (5, 3), (4, 5), (5, 4), (6, 6), (6, 7), (7, 6), (7, 7) ); в) нет; г) нет; д) АхА. 9. Да. Покажем, что Д рефлексивно. Имеем, что (а,Ь)В(а,Ь) тогда и только тогда, когда аЬ = аЬ. Покажем, что й симметрично. Допустим, что (а Ь)Н(с д). Но (а,Ь)В(с д) тогда и только тогда, когда ад = Ьс. Также (с, д) В(а, Ь) тогда и только тогда, когда сб = ад. Следовательно, (с,41)В(а, Ь).
Покажем, что Л транзитивно. Пусть (а, Ь)й(с, д) и (с, д)В(е,/). Следовательно, а41 = Ьс и с( = ед. Из первого равенства а4(7 = Ьсу. Подставляя с7 = ед в это равенство, получаем а4(7' = Ьей. Разделив на д, получаем ау' = Ьс и (а, 6)В(е,у). Раздел 3.4. ) 32+ 12 ~ 52. 6) 2 В-4. в) (3 — Ц<7; г) 24 = 4!. д) Джон любит Сью больше, чем Мэри. 870 Ответы к упражнениям 3. а) существуют х и у такие, что хз + уз > 2бз; 6) существует х такое, что 7 = — 4; в) для каждого г существует х такое, что )х — 1) < г; г) существует и такое, что для всех у выполняется р = тд; д) Джон любит Сью больше, чем кого-либо. 5.
а) предметная область для х — множество всех улиц. Область для р — множество всех праздников. Рс(х,у): х имеет свой у. 'тхЗуЛ(х, у); 6) предметная область для х — множество всех машин. Область для у — множество всех людей. Я(х,у): х умнее, чем у. ~х~гяях, я); в) предметная область — люди, Т(х, у): х играет в теннис лучше, чем и. ЫхТ(х,Фрэд); г) предметная область для х — множество всех действий. Область для у — множество всех противодействий. ЬГ(х,у):х имеет равное и противоположно направленное и. 'ухни(х,я); д) предметная область — игроки в гольф. Ъ'(х,у):х будет в конце концов обыгран более сильным у.
Чхху)г(х, р). Ч. а) истинно; 6) истинно; в) 9. ЧхР(х) ы ЧхЯ(х) Р(а) ч ЧхЯ(х) для произвольного Р(а) ы Я(Ь) для произвольного Ь Р(а) Ч с,'та) 'тх(Р(х) ы Я(х)) г) истинно; д) ложно. истинно; дано универсальная конкретизация универсальная конкретизация поскольку Ь произвольно, выберем Ь = а универсальное обобщение. 11. а) 6) 6) 12. а) 14. а) Ответы к упражнениям 871 Раздел 8.8. 1. а) Ь + а = с + а дано (6+ а) + (-а) = (с+ а) + (-а) !2 Ь+ (а+ ( — а)) = (с+ а) + ( — а) закон ассоциативности ЬЬО=с+О Ь=а б) а 0 = а.
(О+ 0) = = а (0) + а (0) Таким образам, а . 0 — а 0 = (а .(0) + а . (0)) — а . 0 = а 0 — а . 0 = а (0) + (а (0)) — а 0) = 0 = а ° (0) + 0 = =а (0) !7 аддитивно обратный элемент !6 аддитивно нейтральный элемент; !6 аддитивно нейтральный элемент закон дистрибутивности. аддитивно обратный элемент закон ассоциативности аддитивно обратный элемент аддитивно нейтральный элемент; в) поскольку -а является обратным к а, имеем а+ ( — а) = (-а) +а. Но это удовлетворяет требованию, при котором а является обратным к — а. Следовательно, а = — ( — а); г) а. ( — 6) + а.
6 = а. (-Ь+ 6) = согласно закону дистрибутивности =а 0= по определению обратного элемента =0 согласно пункту (6). Аналогично, а Ь+ а. ( — Ь) = О, поэтому, по определению, а (-Ь) является аддитивно обратным элементом для а Ь, поэтому а (-6) = — аЬ; д) а ( — 6) + ( — а) ( — Ь) = ( — 6) .
а -г ( — Ь) ( — а) = закон коммутативности = (-6) (а -ь (-а)) = закон дистрибутивности =(-Ь) 0= определение обратного элемента =0 согласно пункту (б). Аналогично, ( — а) ( — Ь) + а ( — Ь) = О, поэтому ( — а) (-Ь) — обратный элемент для а ( — 6). Но а. Ь вЂ” элемент, обратный для а (-6). Следовательно, а Ь = ( — а) . ( — 6). 3. Учитывая, что если а > 6 > 0 и с > с( > О, то ас > Ы.
Требуется рассмотреть только случай, когда а = с или с = с!. Если а = Ь и с > д, то ас > ас!. Следовательно, ас > Ы. Случай с = с! аналогичен. б. Поскольку (а — Ь) > О, имеем (а — Ь) = (а — 6)(а — Ь) = а(а — 6) + (-Ь)(а — Ь) > О, согласно закону дистрибутивности. Используя совместно закон дистрибутйвности, пункты (д) и (е) задачи! и закон коммутативности, получаем а(а — Ь)+( — 6)(а-Ь) = а — аЬ вЂ” аЬ+Ьз. Следовательно, а — 2аЫ- Ь > О. Прибавляя 2аЬ к обеим частям неравенства, получаем аз+ Ьз > 2аЬ.
()с + Ц(3(/с + 1) — 1) (!с + 1)(3/с + 2) 2 2 Раздел 8.8. 1. Для и = 1 имеем 1 = -'+'-), поэтому утверждение истинно. Предположим, что утверждение истинно для и = )с, так что 1 + 4 + 7 -!- .. + (36 — 2) = ыгз 1з. Теперь необходимо доказать, что утверждение истинно для и = )с ч- 1, так что 872 Ответы к упражнениям Если прибавить(3(6+ 1) — 2) = 36+ 1 к обеим частям утверждения, записанного для и = 6, имеем 1 + 4 ч- 7 + + (3/с — 2) + (3(/с + 1) — 2) = Ч- 3/с Ч- 1— /с(3/с — 1) 3(с~+56+2 (/с+1)(3/с+2) 2 2 2 1 2 + 2 3 -г + 6(6 + 1) + ()с + 1)(/с + 2) 3 Прибавляя ()с+ 1)()с + 2) к обеим частям равенства, записанного для и = 6, имеем 1 .
2 + 2 . 3 + .. + /с(/с + 1) + (/с Ч- 1)(/с + 2) = + (Й + 1)(Й ч- 2), Й()с + 1) (/с + 2) но lс()с + 1)(/с -Ь 2) 3 Ус(/с+ 1)(Ус+ 2) Ч- 3(/с+ 1)(1с -'г 2) (Ус+ 3)(Ус+ 1)(/с+ 2) что доказывает истинность утверждения для и = й + 1. 9. Пусть гс = 1. Тогда аЬ = аЬ, что и требовалось. Предположим истинность утверждения для гс = )с, согласно которому (аЬ)" = а"Ь". Мы хотим доказать, что (аЬ)"+' = а"ю'Ь»+'. Но (аЬ)"~~ = (аЬ) (а6)= =а Ь (аЬ)= ь ьь =а а 6 Ь = согласно определению, введенному в предыдущей задаче согласно индуктивному предположению согласно коммутативности умножения согласно определению, введенному в предыдущей задаче.
=а "+'Ь"+' и справедливость утверждения для и = й + 1 доказана. 3. Для п = 1 имеем 1 = 2 — 1, поэтому утверждение истинно для и = 1. Предположим, что оно истинно для п = )с, поэтому 1+2+2з+ +2" ' = 2" — 1. Мы хотим доказать истинность утверждения для и = 6+1, т.е. 1+2+2 + . +2" '+2" = 2"+' — 1. Прибавляя 2" к обеим частям утверждения, записанного для и = Ь, имеем 1+2+2з+..+2" '+2 = 2" — 1+2". Но 2 — 1+2" = 2 2 — 1 = 2а ю — 1. Таким образом, истинность утверждения для и = 6+1 доказана. 5.
Для и = 1 имеем 1 = 1з, поэтому утверждение истинно. Предположим, что оно истинно для и = )с, поэтому имеем 1+ 3+ 5+ + (2п — 1) = пз. Мы хотим доказать истинность утверждения для и = )с + 1, т.е. равенство 1 + 3 + 5 + . + (2п — 1) + (2п + 1) = (и + 1)з. Прибавляя 2п + 1 к обеим частям равенства, записанного для п = 6, имеем 14-3+5+ +(2п — 1)+(2пн-1) = па+(2пч-1) = (и+1)з, что доказывает истинность утверждения для и = /с -Ь 1. 7. Для и = 1 имеем 1(1+ 1) = Ц1 + 1) (1 + 2) 3 или 2 = 2, поэтому утверждение истинно.
Предположим, что оно истинно для и = )с, поэтому имеем 1 2 + 2 3 -Ь . + Й((с Ч- 1) = 6(6 + 1)(6 + 2) . Мы хотим доказать, что утверждение истинно для и = 6+1, т.е. равенство 3 Ответы к упражнениям 873 11. В этой задаче используются результаты предыдущей задачи. Пусть и = 5, тогда 2' > 5з, что и требовалось. Предположим, что утверждение истинно для о = й, поэтому 2" > йз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
