Group  ^{List No.}^{Last Name}^{Name}  ^{Student No.}^{Department}  ^{Section}^{Signature} ^{:}^{:}  ^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{Code}^{Acad. Year}^{Semester}^{Instructor}^{Date}^{Time}^{Duration}  M E T U Department of Mathematics^{Fundamentals of Mathematics}^{Midterm 1}^{Math 111}^{2013}^{Fall}^{G.Ercan, S.Finashin,}^{M.Kuzucuoğlu, ^{}Ö.Küçüksakallı.}^{November 7, 2013}^{17:40}^{100 minutes}  ^{6 QUESTIONS ON 6 PAGES}^{60 TOTAL POINTS}^{1}  ^{2}  ^{3}  ^{4}  ^{5}  ^{6}

1. (10pts) Using truth tables, determine if the statement (P → ¬Q) ↔ (R → (¬Q ∨ P)) is a tautology, a contradiction, or neither.

Solution

\begin{matrix}P & Q & R | & (P & → & ¬Q) & ↔ & (R & → & (¬Q & ∨ & P)) \\ T & T & T | & T & F & F & F & T & T & F & T & T \\ T & T & F | & T & F & F & F & F & T & F & T & T \\ T & F & T | & T & T & T & T & T & T & T & T & T \\ T & F & F | & T & T & T & T & F & T & T & T & T \\ F & T & T | & F & T & F & F & T & F & F & F & F \\ F & T & F | & F & T & F & F & F & T & F & F & F \\ F & F & T | & F & T & T & T & T & T & T & T & F \\ F & F & F | & F & T & T & T & F & T & T & T & F \end{matrix}

2. (10pts) Assume that x and y take real values. Determine whether the following statements (1)–(4) are true or false. Explain your answers briefly.

P (x, y) = “x^{2} + y = 5′′

1. ∃x ∀y P (x, y) Solution: “There exists x such that for all y we have x^{2} + y = 5.” This is false, because for any given value of x the identity x^{2} + y = 5 is true just for one (and not all) values of y.

2. ∀y ∃x P (x, y) Solution: “For all y there exists x such that x^{2} + y = 5.” This is false, because if we take y > 5 then x^{2} = 5 − y < 0, and we cannot find any x satisfying the identity.

3. ∃y ∀x P (x, y) Solution: “There exists y such that for all x we have x^{2} + y = 5.” This is false, because for any given value of y the identity x^{2} + y = 5 is true not more than for two (and not all) values of x.

4. ∀x ∃y P (x, y) Solution: “For all x there exists y such that x^{2} + y = 5.” This is true, because for any given value of x we choose y = 5 − x^{2}, which is a real number, and the required identity is satisfied.

3. (10pts) Give a derivation for the following argument (which is known to be valid).

P → (Q → R)
T → Q
P ∨ S
\underline{¬S}
¬R → ¬T

Solution

(1) P → (Q → R)

(2) T → Q

(3) P ∨ S

(4) \underline{¬S}

(5) P (3), (4), Modus T ollendo P onens (6) Q → R (1), (6), Modus P onens

(7) T → R (2), (6), Hypothetical Syllogism (8) ¬R → ¬T (7), Contrapositive 4. (10pts) Let a, b and c be integers. Prove that if a does not divide bc, then a does not divide b. Solution 5. (10pts) Prove that the following three statements about an integer n are equivalent.

1. 3 ∤ n

2. 3 | n^{2} − 1

3. there exists an integer k such that n = 3k + 1, or n = 3k + 2.

Solution 6. (10pts) Let A, B and C be sets. Prove that if A ⊆ B and B ∩ C = ∅, then A ∩ C = ∅. Solution