Homework 1 Solutions

Homework 1 Solutions Question 1 I know that if it is my birthday, then I will get gifts. I check the calendar and notice that it is not my birthday. I conclude that I will not get gifts. Formalise this reasoning in terms of suitably defined propositions. Is this reasoning correct? If yes, state which rule of inference is being used. If not, state precisely what the error is. Solution: Let p, q be propositions where p = it is my birthday q = I will get gifts Then p = ⇒ q = if it is my birthday, then I will get gifts The reasoning provided in the question can thus be formalised as p = ⇒ q, ¬ p ¬ q This reasoning is not correct, as it is using the logical fallacy known as "Denying the Antecedent" (fallacy of the inverse). Question 2 Resolve this apparent contradiction: Every implication or it’s converse is true. Check this by trying out all possible values of p and q in the compound proposition ( p = ⇒ q ) ∨ ( q = ⇒ p ) It is always true no matter if p or q are true or false. But clearly there are statements where neither statement implies the other, For example “ n is divisible by 2 " and “ n is divisible by 3 ". Clearly neither statement implies the other! Solution: The following truth table verifies that every implication or it’s converse is true: p q p = ⇒ q q = ⇒ p ( p = ⇒ q ) ∨ ( q = ⇒ p ) T T T T T T F F T T F T T F T F F T T T It is true that there exist statements where neither statement implies the other. However, this is because statements include propositions and predicates. The example statements " n is divisible by 2 "

and " n is divisible by 3 " are predicates where n is variable. For any fixed value of n these predicates become propositions, at which point it can be seen that at least one of the statement implies the other. This might seem odd, but recall that an implication can be true just because its premise is false. Question 3 Let p and q and r be propositions. What is the negation of ( p ∨ q ) ∧ ( r ∨ ¬ p ) ? Simplify the expression using DeMorgan’s laws as far as possible. Solution: ¬ (( p ∨ q ) ∧ ( r ∨ ¬ p )) = ¬ ( p ∨ q ) ∨ ¬ ( r ∨ ¬ p ) = ( ¬ p ∧ ¬ q ) ∨ ( ¬ r ∧ p ) Question 4 What is the negation of the statement: “If all pizza is tasty, then no pizza is topped with pineapple." Write your answer in words. Solution: From lecture notes exercise 5 we have: ¬ ( p = ⇒ q ) = p ∧ ¬ q The negation of the provided statement is then "All pizza is tasty, and there exists a pizza topped with pineapple." Question 5 Formally write a proposition signifying: “for every real number, there is a real number bigger than it." Now write down the negation of this proposition. Solution: ∀ x ∈ R , ∃ y ∈ R , y > x . The negation is ¬ ( ∀ x ∈ R , ∃ y ∈ R , y > x ) ∃ x ∈ R , ¬ ( ∃ y ∈ R , y > x ) ∃ x ∈ R , ∀ y ∈ R , ¬ ( y > x ) ∃ x ∈ R , ∀ y ∈ R , y ≤ x That is, there exists a real number which is greater than all real numbers. Page 2

3. If there is no traffic, I will reach my destination on time. I did not reach on time. Thus, there definitely must have been traffic. Solution: 1. Let T , L , and B be predicates where • T ( x ) = x is tall. • L ( x ) = x has large shoe size. • B ( x ) = x is a basketball player. We are given that ∀ x, B ( x ) = ⇒ T ( x ) and ∀ x, B ( x ) = ⇒ L ( x ) . The claim can then be formally written as ( ∀ x, B ( x ) = ⇒ T ( x )) , ( ∀ x, B ( x ) = ⇒ L ( x )) ∀ x, T ( x ) = ⇒ L ( x ) This statement fails because the given statements only assert characteristics of basketball play- ers. ∃ x s.t. ¬ B ( x ) , T ( x ) , and ¬ L ( x ) . Thus, B ( x ) = ⇒ T ( x ) and B ( x ) = ⇒ L ( x ) would both be true, but T ( x ) = ⇒ L ( x ) would not. 2. Let p , q , and r be propositions where p = it is snowing q = it is cold r = I stay indoors Then p = ⇒ r = if it is snowing I will stay indoors q = ⇒ r = if it is cold I will stay indoors The reasoning provided in the question can thus be formalized as p = ⇒ r, q = ⇒ r, p q Notice by definition of implication this is equivalent to: r, p q However, the logic breaks down as we have nothing to imply it snowing or us being inside would lead to it being cold. 3. Let p , q be propositions where p = there is no traffic q = we reach our destination on time Then p = ⇒ q = if there is no traffic, I will reach my destination on time The reasoning provided in the question can thus be formalised as p = ⇒ q, ¬ q ¬ p This reasoning is correct. The rule of inference it is using is the contrapositive. Page 4

Question 9 Write down the negation of the proposition ∀ x ∈ R , ∃ y ∈ R , ∀ z ∈ R , ( x < ( y + z )) . Which is true, the proposition or its negation? Justify your answer. Solution: The negation of the given proposition can be expressed as follows: ¬ ( ∀ x ∈ R , ∃ y ∈ R , ∀ z ∈ R , ( x < ( y + z ))) , which can be simplified to ∃ x ∈ R , ∀ y ∈ R , ∃ z ∈ R , ( x ≥ ( y + z )) . The negation is true. We only need to show an existence of such x . Take x = 0 , and ∀ y ∈ R , take z = − ( y + 1) , then x ≥ − 1 = y + z . Question 10 Write down the negation of the proposition ∀ x ∃ y ∀ z ∃ t (( x + t < y + z )) . Which is true, the proposition or its negation? Justify your answer. We are working in the domain of real numbers. ( Hint: To help figure out if the proposition is true, try setting t = z .) Solution: The negation of the given proposition can be expressed as follows: ¬ ( ∀ x ∃ y ∀ z ∃ t (( x + t < y + z ))) , which can be simplified to ∃ x ∀ y ∃ z ∀ t (( x + t ≥ y + z )) . The proposition is true. Given any x , take y = x +1 , and ∀ z , we pick t = z . Then, x + t = x + z < y + z . Page 5