Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 154
Текст из файла (страница 154)
3. а) если ему нравятся фиолетовые галстуки и он популярен, то у него странные друзья; 6) если он популярен, то у него нет странных друзей; в) если ему нравятся фиолетовые галстуки, то он популярен, или у него странные друзья; г) если ему нравятся фиолетовые галстуки, то он не популярен, и если он популярен, то у него странные друзья.
5. а) 6) 858 Ответы к упражнениям в) г) 7. а) Ответы к упражнениям 869 г) г) Г. в) Т; б) Т; 9. а) Т; Раздел 1.З. 1. а) 6) 8 ГГГГГГЕГ РРГГ в) 860 Ответы к упражнениям г) Таблицы истинности не совпадают, поэтому высказывания не эквивалентны. р дш рмо ге теорема 1.31з) закон коммутативности р эа ж оы р са двойное отрицание — о - р теорема 1.3(з) Следовательно, р о ге о — р, и инверсия высказывания эквивалентна конверсии. 5. а) если он кентавр, то у него шесть ног; б) если он преуспеваюший политик, то он избран; в) если он имеет деньги, то он популярен. 7. а) если я хороший гражданин, то я голосую; б) если я не голосую, то я не являюсь хорошим гражданином; в) если я не являюсь хорошим гражданином, то я не голосую.
Раздел а.4. 1. а) в) 3. а) неправильное; б) правильное; в) правильное; г) правильное. в) неправильное; 5. а) правильное; г) правильное. 7. а) 6) - (-рид) 2 в (рд о)- в зиг в) — рд -д РЛ -4 в г) (хи тв) з р 7 р ( гЧ в) хН гв — ~ р р ~'4 в 6) да; 9. а) нет; в) нет; г) да; д) нет. 1. 2. 3. 4. 5. 6. !. 2. 3. 4. 5. 6.
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. !1. 1. 2. 3. 4. 5. 6. 7. 8. 9. (в л г) гв Г вм г в гв в ю б) неправильное; дано дано 1 закон де Моргана 3 и теорема !.3(и) 2 и контрапозиция силлогизм; дано дано дано 2, 3 и гпобиз ропепз 1 и контрапозиция 4, 5 и тобол рапепз; дано дано дано дано ! и закон де Моргана 5 и двойное отрицание 3, 6 и тодиз ропепз 2 и контрапозиция 7, 8 и гподиз ропепз 4 и теорема 1.3(и) 9, 1О и тобик ропепз.
дано дано дано дано 1 и теорема 1.3(п) 2„ 5 и тодиз ропепз 3 и контрапозиция 6, 7 и тог(из ропепз 4, 8 и тодиз ропепз. Ответы к упражнениям 881 862 Ответы к упражнениям Раздел 1.6. 6) 1. а) в) 3. а) (рлдл- ) ч (рл-длт)ч (рл-дл- )ч (-рл-дл-т); 6) ( рЛдЛт) '4( рЛдЛ г) Ч( рЛ дЛ т); В) (р Л д Л т) Ч (р Л д Л г) Ч (р Л д Л т) Ч ( р Л д Л г). Раздел 1.6. 1. а) гч(рл д); 6) (тле) /(рл-дл-з)ч(рл- л-з); в) (рл- )ч (- лз) ч(-длтл-з). 3. а) д д д д р р дЧ( рЛ т); т т т т г з ( дл з) ч (длглз).
г т т т 6) (д+ т')(р'+ т)(д+ т' + з); Г) (р'+ дг')', 6) (рт)'+ дт'; Г) ((р+ д + т)(р + д + т ) ); б) р р р р в) д д р р р р Раздел 1.7. 1. а) рд(д ~- т'); в) (рд г) + д~г+ рд т~; д) рт + рд (р -~- г -~- з ). 3. а) (р'д')'+ д'т; в) (рд + г) + (д + т); д) (р+ д)((дг')'+ (р'+ т)). (рл т) ч (дл т)ч ч(-рл -тле) ч(-рл -злт); з Ответы к упражнениям 863 Раздел 2.1. 1. ( — 9, -8, — 7, -6, — 5, — 4, -3, — 2, — 1,0, 1,2,3,4,5,6,7,8,9).
3. 1а, е,ю,о,и). 5. а) Р в) Р г ' ф 6) Р г) Р 364 Ответы и упражнениям 5. (х:0 <х< 24 их кратно 3). 7. (х: х — название американского штата, которое начинается с буквы "О"). 9. о, (а). 11. О, (а), (6),(с), (а, Ь), (а,с), (Ь,с), (а,6, с). 13. о. 15. а) истинно; 17. а) 2; б) ложно; б) 1; в) ложно; г) истинно; д) ложно. в) 4; г) 6; д) 3. д) Т 13.
а) (о) !5. )У. Раздел 2.3. б) г) Раздел 2.2. 1. а) (1, 2, 3,4, 5, 6, 7, 8, 10); б) (4, 5, 6, 7); в) (2,4,5,6,7); г) (2,4,5,6,7,8,10); д) (1,2,3,8,9,10); е) о; ж) (1, 2, 3, 8, 9, 10); з) (1,2,3). 3. а) ((1,а), (2, а), (З,а),(1,6), (2, Ь), (3,6)); б) ((а, а), (а, Ь), (Ь, а), (Ь, Ь) ); в) о. 5. (о). 7. (о,(о)). 9. в) Т; б) Т; в) Р; г) Т; 11. х6(АОВ)'а>хф(АОВ) определение дополнения ео (х Е (АгзВ)) определение ф е: ((х Е А) Ч (х е В)) определение объединения ез (х 6 А)л (х Е В) закон де Моргана; ез (х ф А) д (х ф В) определение ф «ах ф А П В определение пересечения. б) (о,(о)); в) (о, (о), (о, (о) )).
Ответы к упражнениям 865 б) 3. а) г) а) е) ж) 5. а) А', б) ИАОВ) — С)О(АПВ); а) ПАЕВ) О(АПС) О(В ОС))', г) ИА и В) О (А и С) О (В л С)) — (А и В й С). 7. 866 Ответы к упражнениям Раздел 2.4. 1. х х = х х + 0 = закон тождества закон дополнения закон дистрибутивности закон дополнения закон тождества =х х+х х . (х+ хх)— .1= 3.
х (х+ у) = (х+ О) (х+ у) = =х+(О.у) = =х+О= закон тождества закон дистрибутивности свойства констант закон тождества. 5. 1 -Ь О = 1 закон тождества Раздел 2.5. 1. а) область значений = (1,2,4,5); область определения = (а,с,Ы); б) область значений = (2, 4, 6,...); область определения = (1, 2, 3,.... в) область значений = Рм область определения = (х: х 6 Я и х ) О). 3. а) Н ' = ((7,1),(6,4),(6,5),(8,2)), Я ' = ((10, 6),(11, 6),(10, 7),(13, 8)); б) Я о )7 = ((1, 10),(4, 10),(4, 11),(5, 10),(5, 11),(2, 13)); в) Я о Я ' = ((10, 10),(10, 11),(11, 10),(11, 11),(13, 13)), Я ' о Я = ((6, 6), (6, 7), (7, 6), (7, 7), (8, 8)); г) Л ' о Я ' = ((10, 4), (10, 5), (11, 4),(1 1, 5),(10, 1),(13, 2)); д) То ф о В) = ((1, Л), (4, Л), (5, Л), (2,*), (2, С))); е) Т о Я = ((6,й),(7, Л),(8, «)(8, С))); ж) (Т о Я) о й = ((1, Ь), (4, г5), (5, Ь), (2, «), (2,())).
5. а) ((х, у); у = 9хз+ 5); б) ((х,у):у=з'.ь15); в) ((х, у): у = х т/х — 5; г) ((х у).у зх 1 0 = 0 закон тождества. Следовательно, 0 удовлетворяет закону дополнения для 1 и, согласно закону единственности дополнения, является единственным элементом, который обладает таким свойством. 7. а) ху'+ (а'у)', б) ((О х) + у)(х ч-у'-ь з); в) ((х + у) ° 0) + (1 ° х) + з. 9. Если х + у = х + з и х' + у = х' + з, то у = з. 11. х + у' = 1 тогда и только тогда, когда х + у = х.
13. Объединение и пересечение двух конечных множеств является конечным множеством. Объединение и пересечение двух коконечных множеств коконечно. Объединение конечного множества и коконечного множество коконечно. Пересечение конечного множества и коконечного множества конечно. Поэтому свойство объединения и пересечения определено для всех рассматриваемык множеств. Для множеств было показано выполнение законов коммутативности, ассоциативности и дистрибутивности. Пустое множество конечно, а множество сг коконечно. Поэтому они относятся к рассматриваемым множествам.
Лополнение конечного множества коконечно, а дополнение коконечного множества конечно. Следовательно, дополнение определено для всех рассматриваемых множеств. Справедливость законов тождества и законов дополнения для множеств была доказана ранее. Ответы к упражнениям 887 д) (р:р > Ь). 7. а) Ца,а), (а, Ь), (Ь, а), (Ь,с), (с, Ь), (Ь,а), (с(,Ь), (с, е), (е, с), (е,Н), (а, е)); б) Ца, а), (а, 6),(Ь,а),(6, с),(с, 6), (Ь, И), (а, Ь), (с, е), (е, с), (е, И), (Н, е), (Ь, Ь), (с, с), (И, И), (е, еЦ; в) АхА; г) Ца,а),(а, 6),(Ь, с), (Ь, Ы),(с, е),(е, 4).
(с, Ь),(а, с),(а, 8),(6, е),(Ь, Ь),(с, Н),(с, сЦ. 9. а) ЬГ П Ъ' = ( (а, Ь), (6, с),(Ь, Ь), (е, е),(Ь,а), (с, Ь), (гК,а), (а, с), (с,аЦ; б) 5 гз Т = Ца, а), (а, Ь),(Ь, с), (Ь, 8), (с, е), (е, Н), (с, а), (6, а), (е, е), (<Е, е), (с, ЬЦ; в) Ьà — Т = Ца, а),(Ь, 6),(с, с),(г), Н),(а, с),(с,аЦ; г) ЬГ сз Я = ЦЬ, Ь),(е, е),(Ь,а),(с, Ь),(с, с),(с(,г(),(а, с),(Ь, Ы),(с, е),(е, аЦ 11. Пусть В и Я вЂ” симметричные отношения и (а, Ь) б ВГт Я. Поскольку В симметрично, то (6,а) Е В. Поскольку 5 симметрично, то (Ь, а) б Я. Следовательно, (Ь,а) б В и Я и НОЯ симметрично.
13. а) Ца,а), (Ь, Ь), (с, с), (г(, И), (е, е), (а, Ь),(6,а), (с, Ь), (Ь, сЦ; б) Ца, а), (Ь,6), (с,с), (г),аЦ; в) Ца,а), (Ь, Ь), (с, с), (д, Н),(е, е), (а, Ь) ). г) истинно; 17. а) истинно; д) истинна. б) ложно. Пусть В = Цб,сЦ и Я = Ца, ЬЦ, тогда В и Я транзитивны, но Н и Я = Ца, 6), (Ь, сЦ не транзитивно', в) ложно. Пусть Н = Цс а)(Ь ЬЦ и Я = Ца, Ь), (Ь с), (а, с)), тогда В и Я транзитивны, но В о Я = Ца, Ь), (Ь, а), (а, аЦ не транзитивно; г) ложно. Пусть В = Ца,6),(6,с),(а,сЦ и 5 = Ца,сЦ, тогда Н и Я транзитивны, но  — Я = Ца,б), (Ь, сЦ не транзитивно; д) В = Ца Ь), (6 с), (а сЦ и Я = Ца сЦ, тогда В и 5 транзитивны, но Н Ь Я = Ца 6), (6 сЦ не транзитивно.
19. а) б) е ° в) Ь г) 15. а) истинно; б) истинно; в) ложно. Пусть В = ЦЬ,с),(с,ЬЦ и Я = ЦЬ,а),(а, ЬЦ, тогда (а,с) е В о Я, но (с,а) ф Но Я. 888 Ответы к упражнениям 21. а) Ъ' = (а, Ь,с,д); Е = ((а, Ь), (а, д), (Ь, Н), (с, д), (а, с) ); й = ((а,6), (Ь, а), (а, д), (Н,а), (Ь д), (д,6), (с, д), (<М, с), (а, с), (с, а)). б) 1г = (а, Ь, с, Н); Е = ((а,Ь), (а,д), (Ь,д), (с,И), (а,с), (Ь, с)); й = ((а, 6), (Ь, а), (а, д), (д, а), (Ь, д), (д, Ь), (с, д), (д, с), (а, с), (с, а), (Ь, с), (с, Ь)).
в) и =(а,Ь,с,д,е,Д; Е = ((а, с), (а, д), (а, е), (а, Д, (Ь, с), (Ь, д), (Ь, е), (Ь, У)); й = ((а, с), (с, а), (а,д), (И, а), (а, е), (е, а), (а, У), (Х,а), (Ь, с), (с,6),(Ь,д); (д, Ь), (Ь, е), (е, Ь), (Ь, г), ( (, Ь) ). г) Ъ' = (а,Ь,с,д,е,); Е = ((а, Ь), (с, д), (г(, е); (с, е), й = ((а, Ь),(Ь,а), (с, Н),(д, с),(д, е),(е, Н), (с, е),(е, с)). 23. а) ;(',--); 25. а) )г=(а,Ь,с,д,е,); Е = ((а, Ь), (Ь, а), (а, е), (6, е), (с, Ы), (Ы, с), (Н, е),(с, е)). б) $' = (а, Ь,с,д); Е = ((д, Ь), (Н, а), (с, Н), (Ь, с) ).
в) и = (а,Ь,с,д,е,); Е = ((а, Ь),(Ь, с),(с, д),(д, е),(е, а),(Ь, д),(6, е),(с, е),(д,а)). г) Ъ' = (а, Ь, с, Н, е, ), Е = ((а, Ь), (Ь, с), (с, д), (Н, е), (е, а), (Ь, д), (Ь, е),(с, е), (е, Н), (а, с)). Покажите, что (ТоЯ) ой С То(Вой). Пусть (а,И) б (ТоЯ) ой, тогда сушествует Ь б В 27 такое, что (а, Ь) б й и (6,д) б То Я. Поскольку (6,д) б То Я, то сушествует с б С такое, что (Ь, с) б Я и (с, Н) б Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
