Logic and Discrete Mathematics (eBook)

A Concise Introduction, Solutions Manual

Willem Conradie, Valentin Goranko, Claudette Robinson (Autoren)

eBook Download: EPUB

2015
John Wiley & Sons (Verlag)
978-1-119-00010-5 (ISBN)

Infos

Solutions manual to accompany Logic and Discrete Mathematics: A Concise Introduction
This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade.

Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in this accompanying solutions manual.

Autor

Willem Conradie is a senior lecturer in the Department of Mathematics at the University of Johannesburg, South Africa. For the past 9 years he has been teaching second and third year undergraduate courses based on drafts of the proposed book. Valentin Goranko is an associate professor at the Department of Informatics and Mathematical Modeling of the Technical University of Denmark. His main research interests are in theory and applications of logic to computer science and artificial intelligence. He has published about 75 authored and co-authored research papers and 3 chapters in research books and handbooks. Claudette Robinson is a PhD student and lecturer in the Department of Mathematics at the University of Johannesburg, South Africa.

Inhalt

Preface vii

About the Companion Website ix

1. Preliminaries 1

2. Sets, Relations, Orders 5

3. Propositional Logic 29

4. First-Order Logic 57

5. Number Theory 99

6. Combinatorics 130

7. Graph Theory 159

Textauszug

Chapter 2
Sets, Relations, Orders

2.1 Set Inclusions and Equalities

To keep the solutions as clear and concise as possible, we will make use of the logical notation introduced in Section 1.2. We will also be making use of the logical constant , which always takes the truth value “true”, and the logical constant , which always takes the truth value “false”.

1. (1a) 
2. (1b)
3. (1c)
4. (1d) Let . Then and , which means that and .
5. (1e) Assume . First, the left-to-right inclusion follows from 1(d). For the other inclusion, let . However, since , . Hence, . For the converse direction, assume . Then there is some such that but . Hence, but , which means that .
6. (1f)
7. (1g)
8. (1h)
9. (1i)  For the sake of a contradiction, assume or . If , then there is some such that but ; implies that and ,which contradicts the fact that . On the other hand, if , then there is some such that but . Hence, and , which again is a contradiction.
10. (1j) Assume and let . Then or . If , we are done. On the other hand, if , then since . Hence, . For the other inclusion, let ; then, clearly, . For the converse, assume and let . We have to show that . However, implies that . Hence, since , .
11. (1k) Assume and , and let . Then or . If , then since and, similiarly, if , then since . Hence, in both cases, , which means that .
12. (2a) For the sake of a contradiction, assume . Then or . However, since is a subset of any set, . This means that there is some such that but . Hence, and . This is a contradiction since has no elements.
13. (2b) For the right-to-left inclusion, let . However, has no elements, so . Hence, . For the left-to-right inclusion, suppose . Then there is some such that but ; implies that and , which contradicts the fact that .
14. (2c) For the sake of a contradiction, assume . Then there is some such that and . However, implies that and , which contradicts the fact that .
15. (2d) For the left-to-right direction, assume . Then there is some such that but . However, this means that . Hence, . For the converse, assume . Then there is some in . Hence, but , which means that .
16. (2e) For the sake of a contradiction, assume . Then there is some such that . Hence, and . This means that while and while , which is a contradiction.
17. (2f)
18. (2g)
19. (2h)
20. (2i)
21. (2j)
22. (2k) , so, by 1(d), .
23. (2l) , so, by 1(i), .
24. (3a) Assume and let . Then . However, , so , which means that .
25. (3b) Assume and . Then and . To show that , we have to show that . To see this, let . Then and . However, and , so , which proves that . The fact that follows from 1(k). To show that , let . Then and . However, since , , and so , which proves that . Finally, by 2(c), , so .
26. (4a) 
27. (4b) 
28. (4c) 
29. (4d) 

2.2 Functions

1. (1a) is the function from to given by , and, furthermore, dom rng
2. (1b) is the function from to given by , and, furthermore, dom rng is the set of non-negative real numbers.
3. (1c) No, is not defined.
4. (1d) No, is binary, not unary.
5. (1e) No, has range , while has domain .
6. (2a)
7. (2b)
8. (2c)
9. (2d)
10. (3) Let : and : , where and .
11. (4) Let : and : , where and .
12. (5a) cod
13. (5b)

    rng

    rng

    rng

14. (5c) and are injective.
15. (5d) and are surjective.
16. (5e) is the only bijective function.
17. (6a) The fixed points of are 0 and 1.
18. (6b)
19. (6c) has infinitely many fixed points.
20. (7) Let : and assume is bijective. Then has an inverse which is also bijective by Proposition 4.2.11. Hence, has an inverse . Now, let . Then where the second and last steps follow from Definition 4.2.10.
21. (8a) Let : and : be surjective mappings and let . To show that is surjective, we have to find some such that . However, since is surjective, there is some such that . Similarly, since is surjective, there is some such that . Hence, , as desired.
22. (8b) Let : and : , and assume that is injective. Now, suppose . Then . Hence, by definition, . However, is injective, so , and we are done.
23. (9) Let : , : and : . Then
24. (10) Let : . To prove the left-to-right direction, assume is surjective, and consider the mappings : and : . Furthermore, suppose . We have to show that . Now, let . Since is surjective, there is some such that . Hence,
25. For the converse, suppose is not surjective. Then there is some such that, for all , . We have to find two mappings and such that but . Let : and : such that for all , and for all but for an arbitrary fixed element . Then
26. while and we are done.

2.3 Binary Relations and Operations on Them

1. (1) dom(ParentOf) is the set of all humans who have children, while rng(ParentOf) is the set of all humans.

   dom(IsMArriedTo) and rng(IsMarriedTo) are the set of all married humans.

   dom(OwnsDog) is the set of all humans owning a dog, while rng(OwnsDog) is the set of all dogs owned by some human.

   dom(IsCitizenOf) is the set of all humans who are citizens of some country, while rng(IsCitizenOf) are the set all countries.

   dom(IsMemberOf) is the set of all humans who are member of some club, while rng(IsMemberOf) is the set of all clubs that have at least one member.

2. (2a)
3. (2b)
4. (2c)
5. (2d)
6. (3a) The set of all Dachshunds owned by citizens of European countries.
7. (3b) The set of all Scotish Terriers owned by the children of members of the Rotary Club.
8. (3c) The set of all Scotish Terriers owned by parents of members of the Rotary Club.
9. (3d) The set of all those humans who have a parent who is a citizen of a European country and a parent who is a citizen of an African country.
10. (3e) The set of parents whose children are citizens of both African and European countries.
11. (3f) The set of all sons of members of the Rotary Club.
12. (3g) The set of all mothers of members of the Rotary Club.
13. (4a) :
14. (4b) :
15. (4c) :
16. (4d) :
17. (4e) :
18. (4f) :
19. (5a) The graphical representation of contains the overlapping arrows if we were to put the graphical representations of and on top of each other.
20. (5b) The graphical representation of contains the arrows of both graphical representations of and .
21. (5c)  The graphical representation of contains the arrows of the graphical representation of but without those occurring in the graphical representation of .
22. (5d) The graphical representation of contains all possible arrows between nodes but without those occurring in the graphical representation of .
23. (5e) The graphical representation of is the same as the graphical representation of but with the arrows in the opposite direction.
24. (5f) If there is an arrow from to in and an arrow from to in , there is an arrow from to in .
25. (6a)
26. (6b)
27. (6c)
28. (6d)
29. (6e)
30. (6f)
31. (7a) Place 1's everywhere where there are 1's in the matrix representations of both and and 0's everywhere else.
32. (7b) Place 1's everywhere where there is a 1 in at least one of the matrix representations of and and 0's everywhere else.
33. (7c) Change all the 1's in the matrix representation of to 0's if the matrix representation of also contains a 1 in the corresponding row and column, and leave the remaining entries the same as in the matrix representation of .
34. (7d) In the matrix representation of , change the 0's to 1's and the 1's to 0's.
35. (7e) Reflect the representation matrix of about its diagonal.
36. (7f) If there is a 1 in row column of the representation matrix of and a 1 in row column of the representation matrix of , place a 1 in row column of the representation matrix of , and 0's everywhere else.
37. (8a) 
38. (8b) 
39. (8c) 
40. (9a) Consider the set with and on .
41. (9b) Consider the set with and on .
42. (9c) Consider the set with and on .
43. (9d) Consider the set with and on .
44. (10a) 
45. (10c) 
46. (10b) 
47. (10d) 
48. (11) 

2.4 Special Binary Relations

1. (2a) The relation on , defined by iff and leave the same remainder after division by .
2. (2b) The inclusion relation on a collections of sets.
3. (2c) The...

Produkt-Details

• Erscheint lt. Verlag: 8.5.2015
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Technik
• Schlagworte: companion website • Computer Science • Discrete Mathematics • Diskrete Mathematik • graph theory • Informatik • Logic • Logic & Foundations • Logik • Logik u. Grundlagen der Mathematik • Mathematics • Mathematik • Orders • preface • propositional logic • Relations • theory
• ISBN-10: 1-119-00010-6 / 1119000106
• ISBN-13: 978-1-119-00010-5 / 9781119000105