CMPS 211 Homework 1 with Solution, Spring 2016

American University of Beirut Department of Computer Science CMPS 211 Assignment 1 - Solution Key Exercise 1 Which of these are propositions? What are the truth values of those that are propositions? (a) limx→+∞ ax = +∞, for all a > 0 true (b) The weather is nice today. true (c) When is the first quiz? not a proposition (a question) (d) Stop sleeping and go to class! not a proposition (an order) (e) Turtles are the fastest animals. false Exercise 2 Let f, e, h, and g be the propositions • f : Your program is correct. • e : Your program is stuck in an infinite loop • h : The compiler gives syntax error. • g : The program outputs the required results. Write these propositions using f, e, h, g and logical connectives (including negations). (a) If your program is correct, then the compiler does not give syntax errors, your program is not stuck in an infinite loop, and the output produced is the required output. f → (¬h ∧ ¬e ∧ g) (b) If your program is not stuck in an infinite loop, then the output the program produces is the required output. ¬e → g (c) If your program is stuck in an infinite loop, then the program does not output the required results, and if the program does not output the required results, then the program is not correct. (e → ¬g) ∧ (¬g → ¬f) Note that this is not equivalent to e → ¬g → ¬f 1 (d) To produce the required output it is necessary that your program terminates (is not stuck). g → ¬e (e) Compiling your program successfully is not sufficient for the program to be correct. ¬(¬h → f) This is equivalent to ¬h ∧ ¬f (It is possible to compile successfully and have an incorrect program). Exercise 3 Determine whether these bi-conditionals are true or false. (a) 1 > 0 if and only if 2 > 1. The bi-conditional is true, both statements are true all the time. (b) 1 + 1 = 2 if and only if �∞ n=1 1 n diverges. �∞ n=1 1 n diverges, and 1 + 1 = 2 is true, therefore the bi-conditional is true. (c) p ∧ ¬p if and only if humans are immortal. Humans are mortal, and p ∧ ¬p is a contradiction and therefore false. false ↔ false, therefore the bi-conditional is true. Exercise 4 Determine whether this compound proposition is satisfiable. (p ∨ ¬r ∨ ¬s) ∧ (¬p ∨ ¬q ∨ ¬s) ∧ (p ∨ ¬q ∨ ¬s) ∧ (p ∨ q ∨ ¬s) ∧ (p ∨ q ∨ ¬r) Solution: Take p true, q true, s false, r, false: (t ∨ ¬f ∨ ¬t) ∧ (¬t ∨ ¬t ∨ ¬f) ∧ (t ∨ ¬f ∨ ¬f) ∧ (t ∨ t ∨ ¬f) ∧ (t ∨ t ∨ ¬f) t ∧ (f ∨ f ∨ t) ∧ t ∧ t ∧ t (f ∨ f ∨ t) t Therefore (a) is satisfiable. Optional reading: Normal Forms - Section 1.7 in your textbook Exercise 5 Given the following propositions: • m : I study hard and practice mathematics. • c : I am a good Computer Scientist. 2 Express each of these propositions as an English Sentence. (a) c ↔ m I am a good computer Scientist if and only if I study hard and practice mathematics. Alternative: Studying hard and practicing mathematics is necessary and sufficient to being a good computer scientist. (b) ¬m ∧ ¬c I don’t study hard and practice mathematics, and I am not a good computer scientist. (c) ¬m ∨ (m ∧ c) I don’t study hard and practice mathematics, or I study hard and practice mathematics and I am a good computer scientist. Exercise 6 For each of these sentences, determine whether an inclusive or, or an exclusive or, is intended. Explain your answer. (a) You can either pick the thesis option or the project option for masters. Exclusive, You cannot pick both thesis and project options for your masters. (b) A proposition is either true or false (Law of excluded middle.) Exclusive, a proposition cannot be true and false at the same time! (c) You can attend all the lectures or you will have grades deducted. Inclusive, you might attend all lectures and still have grades deducted for other reasons. (d) To be on the honor’s list you need to have a GPA of 85 at least, or be in the top 10%. Inclusive, many people who are on the honor’s list are both in the top 10% and have a GPA greater than 85. Exercise 7 State the contra-positive, converse, and inverse of each of these conditional statements. (a) You cannot have any pudding if you do not eat your meat. The original statement is p → q where p: you didn’t eat meat, q: you cannot have pudding. Contra-positive (¬q → ¬p): if you had some pudding, then you did eat your meat. Converse (q → p): if you cannot have any pudding, then you did not eat your meat. Inverse (¬p → ¬q): you can have some pudding if you did eat your meat. (b) It is necessary that you are a good logician to be a good computer scientist. The original statement is p → q where p: you are a good computer scientist, q: you are a good logician. Contra-positive (¬q → ¬p): if you are not a good logician, then you are not a good computer scientist. Converse (q → p): It is necessary that you are a good computer scientist to be a good logician. Inverse (¬p → ¬q): if you are not a good computer scientist, then you are not a good logician. 3 (c) To feel energetic, it is sufficient to sleep early. The original statement is p → q where p: you sleep early, q: you feel energetic. Contra-positive (¬q → ¬p): if you are not feeling energetic, then you did not sleep early. Converse (q → p): To sleep early, it is sufficient to feel energetic. Inverse (¬p → ¬q): if you did not sleep early, then you are not going to feel energetic. Exercise 8 Construct a truth table for each of these compound propositions. (a) (p ∧ q) → p p q p ∧ q (p ∧ q) → p T T T T T F F T F T F T F F F T (b) (p XOR q) → (p ∧ q) p q p XOR q p ∧ q p XOR q → p ∧ q T T F T T T F T F F F T T F F F F F F T (c) p ∨ q ∧ ¬r ↔ q → ¬p p q r ¬p ¬r q ∧ ¬r p ∨ (q ∧ ¬r) q → ¬p (p ∨ (q ∧ ¬r)) ↔ (q → ¬p) t t t f f f t f f t t f f t t t f f t f t f f f t t t t f f f t f t t t f t t t f f f t f f t f t t t t t t f f t t f f f t f f f f t t f f t f Exercise 9 Let • F(x) = x is well-formulated, • V(x) = x is valuable • P(x) =x is a research problem where the domain for x consists of all English text. Express each of these statements using quantifiers, logical connectives, and F(x), V(x), and P(x). Then express their negations in English and using quantifiers. 4 (a) All valuable problems are well-formulated ∀x ((P(x) ∧ V (x)) → F(x)) (b) Some research problems are not valuable. ∃x P(x) ∧ ¬V (x) (c) Some research problems are not well-formulated. ∃x P(x) ∧ ¬F(x) (d) Does (c) follow from (a) and (b)? Part a states that all valuable problems are well-formulated (∀xV (x) → F(x)), however, the inverse is not necessarily true. If a problem is not valuable, it does not mean it is necessarily not well-formulated (∀x ¬V (x) ̸→ ¬F(x)) This means that the research problems that are not valuable (mentioned in part b) may still be well-formulated. Since the inverse does not follow from the initial implication, therefore (c) does not follow from (a), (b). However, (b) follows from (a) and (c) through the contra-positive. Exercise 10 Show that ∀xP(x) ∨ ∀xQ(x) and ∀x∀y(P(x) ∨ Q(y)), where all quantifiers have the same nonempty domain, are logically equivalent. (The new variable y is used to combine the quan- tifications correctly.) Solution: To prove ∀xP(x) ∨ ∀xQ(x) ↔ ∀x∀y(P(x) ∨ Q(y)) , we need to prove: 1. ∀xP(x) ∨ ∀xQ(x) → ∀x∀y(P(x) ∨ Q(y)) 2. ∀x∀y(P(x) ∨ Q(y)) → ∀xP(x) ∨ ∀xQ(x) First Way: This is a verbose way, explicitly showing each step in the proof - This is the preferred way of solving this problem. First, ∀xP(x) ∨ ∀xQ(x) →∀x∀y(P(x) ∨ Q(y)): 1. ∀xP(x) ∨ ∀xQ(x) - Premise 2. (P(x1) ∨ P(x2) ∨ ... ∨ P(xn)) ∨ (Q(x1) ∨ Q(x2) ∨ ... ∨ Q(xn)) - Definition of Universal Quantification 3. (P(x1)∨P(x2)∨...∨P(xn))∨(Q(y1)∨Q(y2)∨...∨Q(yn)) - Permute the xis inQ(x) to yis 4. (P(x1) ∨ Q(y1)) ∨ (P(x2) ∨ Q(y2)) ∨... ∨ (P(xn) ∨ Q(yn)) - Commutativity and Associativity of ∨ 5 5. [(P(x1) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn)) ∨ (P(x2) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn)) ∨ ... ∨ (P(xn) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn))] - Addition Rule 6. ∀y[(P(x1) ∨ Q(y)) ∨ (P(x2) ∨ Q(y)) ∨ ... ∨ (P(xn) ∨ Q(y))] - Universal Generalization from 5 7. ∀x∀y(P(x) ∨ Q(y)) - Universal Generalizationfrom 6 Then, ∀xP(x) ∨ ∀xQ(x) →∀x∀y(P(x) ∨ Q(y)) is true. Second, ∀x∀y(P(x) ∨ Q(y)) →∀xP(x) ∨ ∀xQ(x): 1. ∀x∀y(P(x) ∨ Q(y)) - Premise 2. ∀y[(P(x1) ∨ Q(y)) ∨ (P(x2) ∨ Q(y)) ∨ ... ∨ (P(xn) ∨ Q(y))] - Universal Instantiation from 1 / Def of Universal Quantifi- cation 3. [(P(x1) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn)) ∨ (P(x2) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn)) ∨ ... ∨ (P(xn) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn))] - Universal Instantiation from 2/ Def of Universal Quantification 4. (P(x1) ∨ P(x2) ∨ ... ∨ P(xn)) ∨ (Q(y1) ∨ Q(y2) ∨ ... ∨ Q(yn)) - Commutativity and Associativity of ∨from3 5. ∀xP(x) ∨ ∀yQ(y) - Universal Generalzation from 4 Which is same as ∀xP(x) ∨ ∀xQ(x) since x and y have same domain, and are independent. Then, ∀x∀y(P(x) ∨ Q(y)) →∀xP(x) ∨ ∀xQ(x) is true. ∴ ∀xP(x) ∨ ∀xQ(x) ↔ ∀x∀y(P(x) ∨ Q(y)) 6 Second Way: First, ∀xP(x) ∨ ∀xQ(x) →∀x∀y(P(x) ∨ Q(y)): 1. ∀xP(x) ∨ ∀xQ(x) Premise 2. P(c) ∨ ∀xQ(x) U.I from 1 3. P(c) ∨ Q(d) U.I from 2 4. ∀xP(x) ∨ Q(d) U.G from 3 5. ∀x∀y(P(x) ∨ Q(y)) U.G from 4 Then, ∀xP(x) ∨ ∀xQ(x) →∀x∀y(P(x) ∨ Q(y)) is true. Second, ∀x∀y(P(x) ∨ Q(y)) →∀xP(x) ∨ ∀xQ(x): 1. ∀x∀y(P(x) ∨ Q(y)) Premise 2. ∀y(P(c) ∨ yQ(y)) U.I from 1 3. P(c) ∨ Q(d) U.I from 2 4. ∀xP(x) ∨ Q(d) U.G from 3 5. ∀xP(x) ∨ ∀yQ(y) U.G from 4 Which is same as ∀xP(x) ∨ ∀xQ(x) since x and y have same domain, and are independent. Then, ∀x∀y(P(x) ∨ Q(y)) →∀xP(x) ∨ ∀xQ(x) is true. ∴ ∀xP(x) ∨ ∀xQ(x) ↔ ∀x∀y(P(x) ∨ Q(y)) Description: Suppose that ∀xP(x) ∨ ∀xQ(x) is true, We can rename the second variable to y (since it is independent from the first part), so it follows that ∀xP(X) ∨ ∀yQ(y) is true. However, this means that ∀x(P(x) ∨ ∀yQ(y)) is also true, x can be taken outside of the or since the other term in the or is independent of x, similarly, it follows that ∀x∀y(P(x) ∨ Q(y)) is true. Suppose that ∀x∀y(P(x) ∨ Q(y)) is true, since each term either depends on x or on y, it follows that ∀xP(x) ∨ ∀yQ(y) is true, renaming the variable y to x does not change the truth value, since the first x variable has a different scope, therefore, it follows that ∀xP(x)∨∀xQ(x) is true. 7 Exercise 11 Translate in two ways each of these statements into logical expressions using predicates, quan- tifiers, and logical connectives. First, let the domain consist of fruits, and in the second let it be all types of food. Solution: The following symbols are used throughout the solution as follows: The domain of fr is all fruits, and that of fd is all food. Define: fruit(x): x is a fruit (a) Some fruits taste sweet. Define: sweet(x): x tastes sweet • ∃fr sweet(fr) • ∃fd (fruit(fd) ∧ sweet(fd)) (b) All people eat at least one kind of fruits. Define: eat(p, x): p eats x, where domain of p is all people. • ∀p ∃fr eat(p, fr) • ∀p ∃fd (fruit(fd) ∧ eat(p, fd)) (c) Some people eat no kind of fruits. Define: eat(p, x): p eats x, where domain of p is all people. • ∃p ∀fr ¬eat(p, fr) • ∃p ∀fd (fruit(fd) → ¬eat(p, fd)) (d) Maria likes exactly 1 kind of fruits. Define: likes(p, x): p likes x, where domain of p is all people. • ∃fr1 (like(Maria, fr1) ∧ ∀fr2 (fr1 ̸= fr2 → ¬like(Maria, fr2))) • ∃fd1 (fruit(fd1)∧like(Maria, fd1)∧∀fd2 ((fruit(fd2)∧fd1 ̸= fd2) → ¬like(Maria, fd2))) (e) Some people eat 2 (or more) kinds of fruits. Define: eat(p, x): p eats x, where domain of p is all people. • ∃p ∃fr1 ∃fr2 (fr1 ̸= fr2 ∧ eat(p, fr1) ∧ eat(p, fr2)) • ∃p ∃fd1 ∃fd2 (fruit(fd1) ∧ fruit(fd2) ∧ fd1 ̸= fd2 ∧ eat(p, fd1) ∧ eat(p, fd2)) (f) Tarek likes exactly two kind of fruits. Define: likes(p, x): p likes x, where domain of p is all people. • ∃fr1 ∃fr2 (fr1 ̸= fr2 ∧ like(Tarek, fr1) ∧ like(Tarek, fr2) ∧ ∀fr3 (fr3 ̸= fr1 ∧ fr3 ̸= fr2 → ¬like(Tarek, fr3)) • ∃fd1 ∃fd2 (fruit(fd1) ∧ fruit(fd2) ∧ fd1 ̸= fd2 ∧ like(Tarek, fd1) ∧ like(Tarek, fd2) ∧∀fd3 (fruit(fd3) ∧ fd3 ̸= fd1 ∧ fd3 ̸= fd2 → ¬like(Tarek, fd3)) 8 (g) All fruits bought by Joe were eaten by Joy. Define: bought(p, x): p bought x, and ate(p, x): p ate x, where domain of p is all people. • ∀fr (bought(Joe, fr) → ate(Joy, fr)) • ∀fd ((fruit(fd) ∧ (bought(Joe, fd)) → ate(Joy, fd))) Exercise 12 Express these propositions and their negations using quantifiers, and in English. Please specify the domain of each propositional function. (a) There is a student who does not play any sport. Define: play(x, s): x plays s, where domain of x is all students, and that of s is all sports. Quantified: ∃x ∀s ¬play(x, s) Negated with Quantifiers: ∀x ∃s play(x, s) English Negation: All students play at least one sport. (b) All TAs take all the available graduate courses. Define: take(ta, gc) : ta is taking gc, and av(gc) : gc is available, where domain of ta is all Teaching Assistants, and that of gc is all available grad courses. Quantified: ∀ta ∀gc av(gc) → take(ta, gc) Negated with Quantifiers: ∃ta ∃gc av(x) ∧ ¬take(x, s) English Negation: some TA did not take some available grad course. (c) Some band has played in at least one city in every country. Define: played(b, ct): b has played in ct, and in(cr, ct): ct is in cr, where the domain of b is all bands, that of cr is all countries, and that of ct is all cities. Quantified: ∃b ∀cr ∃ct (in(cr, ct) ∧ played(b, ct)) Negated with Quantifiers: ∀b ∃cr ∀ct ¬in(cr, ct) ∨ ¬played(b, ct) English Negation: For all bands, there is a country, such that this band has never played in any city inside this country. (d) Every library in the university has at least one book that was not used by any student. Define: in(lib, b) : b is in lib, used(s, b) : s used b, where the domain of lib is all libraries in the university, that of b is all books, and that of s is all students. Quantified: ∀lib ∃b ∀s (in(lib, b) ∧ ¬used(s, b)) Negated with Quantifiers: ∃lib ∀b ∃s (in(lib, b) → used(s, b)) English Negation: there is a library in the university, such that all its books have been used by at least one student. (e) There is a student in this class who has tried every dish offered by all restau- rants on Bliss street. Define: tried(s, d): s has tried d, and offered(d, r) : disofferedatr, wherethedomainofsisallstudentsinth Quantified :∃s ∀d ∀r(offered(d, r) → tried(s, d) Negated with Quantifiers: ∀s ∃d ∃r(¬tried(x, s) ∧ offered(d, r) English Negation: All students did not try at least one dish offered by some restaurant on bliss street. (f) Every Lebanese soccer player has played with all other Lebanese soccer players in at least 1 game. 9 Define: played(g, p): p has played in g, where domain of p is all players, and that of g is all soccer games. Quantified: ∀p1 ∀p2 (p1 ̸= p2 → ∃g (played(g, p1) ∧ played(g, p2))) Negated with Quantifiers: ∃p1 ∃p2 (p1 ̸= p2 ∧ ∀g (¬played(g, p1) ∨ ¬played(g, p2))) English Negation: There exist a pair of Lebanese soccer players that did not played with each other in any game. Exercise 13 Let L(x, y) be the statement “computer x and computer y are on the same local network”, and A(x, y) “computer x can access computer y”, B(x, z): “computer x belongs to organization z”, where the domain x and y is computers, and that of z is organizations. Express each of those statements and their negations using quantifiers: (a) All Computers that are on the same local network can access one another. Statement ∀c1 ∀c2 (L(c1, c2) → (A(c1, c2) ∧ A(c2, c1))) Negation ∃c1 ∃c2 (L(c1, c2) ∧ (¬A(c1, c2) ∨ ¬A(c2, c1))) (b) All computers that belong to the same organization are on the same local network. Statement ∀z ∀c1 ∀c2 ((B(c1, z) ∧ B(c2, z)) → L(c1, c2)) Negation ∃z ∃c1 ∃c2 ((B(c1, z) ∧ B(c2, z)) ∧ ¬L(c1, c2)) (c) For all computers, if a computer can access another computer, then all computers that can access the first can also access the second (Transitivity.) Statement ∀c1 ∀c2(A(c1, c2) → (∀c3 (A(c3, c1) → A(c3, c2)))) Negation ∃c1 ∃c2(A(c1, c2) ∧ (∃c3 (A(c3, c1) ∧ ¬A(c3, c2)))) (d) Some computers that belong to different organizations can access one another. Statement ∃c1 ∃c2 ∃z1 ∃z2(z1 ̸= z2 ∧ B(c1, z1) ∧ B(c2, z2) ∧ A(c1, c2) ∧ A(c2, c1)) Negation ∀c1 ∀c2 ∀z1 ∀z2(z1 = z2 ∨ ¬B(c1, z1) ∨ ¬B(c2, z2) ∨ ¬A(c1, c2) ∨ ¬A(c2, c1)) OR ∀c1 ∀c2 ∀z1 ∀z2(((z1 ̸= z2 ∧ B(c1, z1) ∧ B(c2, z2)) → (¬A(c1, c2) ∨ ¬A(c2, c1))) Express each of those statements and their negations in English: (A) ∀x, y(A(x, y) → A(y, x)) (Symmetry) Statement: If a computer can access another, then the second computer can access the first. Negation: a computer can access another, but the second computer can not access the first. (B) ∀z1, z2, x ∃y [(z1 ̸= z2 ∧ B(y, z1) ∧ B(x, z2)) → ¬A(x, y)] Statement: For all distinct pairs of organizations, all the computers in the first organization cannot access at least one computer in the second. Negation: There exist a distinct pair of organizations, such that a computer in the first organization can access any computer in the second. Exercise 14 Show that p → (q → r) is logically equivalent to (p ∧ q) → r in two different ways, (a) and (b+c): (a) Use a truth table. 10 p q r q → r p → (q → r) p ∧ q (p ∧ q) → r t t t t t t t t t f f f t f t f t t t f t t f f t t f t f t t t t f t f t f f t f t f f t t t f t f f f t t f t (b) Give a direct proof that if p → (q → r), then (p ∧ q) → r. 1. p → (q → r) Premise 2. p → (¬q ∨ r) Ex3 §1.2 3. ¬p ∨ (¬q ∨ r) Ex3 §1.2 4. (¬p ∨ ¬q) ∨ r Associativity 5. ¬(p ∧ q) ∨ r De Morgan 6. (p ∧ q) → r Ex3 §1.2 (c) Give a direct proof of the converse of the statement in (b). 1. (p ∧ q) → r Premise 2. ¬(p ∧ q) ∨ r Ex3 §1.2 3. (¬p ∨ ¬q) ∨ r De Morgan 4. ¬p ∨ (¬q ∨ r) Associativity 5. ¬p ∨ (q → r) Ex3 §1.2 6. p → (q → r) Ex3 §1.2 Extra Practice (Not To Be Submitted) From the textbook ”Discrete Mathematics and Its applications 7th Edition” Sec. 1.1 (exercises 1 → 25) Sec. 1.2 (exercises 1 → 8, 10 → 22) Sec. 1.3 (exercises 1 → 16) Sec. 1.4 (exercises 1 → 25) Sec. 1.5 (exercises 1 → 26) 11