Description

Homework 1
1. (10 points) Let p and q be the propositions. p : She speaks English. q: She speaks Turkish.
Give a simple verbal sentence which describes each of the following:
(a) (p ∧ q). : She speaks English and Turkish.
(b) (p ∨ q). : She speaks English or Turkish.
(c) (p ∧¬q). : She speaks English and doesn’t speak Turkish.
(d) (p ↔ q). : She speaks English if and only if she speaks Turkish.
(e) (p ∨ q) ∧ (p → ¬q). : She speaks English or Turkish, and if she speaks English then she doesn’t speak Turkish
2. (10 points) Show whether the following propositions are logically equivalent to p → q. (a) q → p.
One counter example will be enough to show that p → q and q → p are not logically equivalent to each other:
p q p → q q → p
F T T F
(b) ¬p →¬q.
Again, a counter example:
p q p → q ¬p →¬q
T F F T
(c) ¬q →¬p. (1)
Truth Table:
p q p → q ¬q →¬p
T T T T
F F T T
T F F F
F T T T
Hence, p → q ≡ ¬q → p.
(d) ¬p ∨ q.
Truth Table:
p q p → q ¬p ∨ q
T T T T
F F T T
T F F F
F T T T
Hence, p → q ≡ ¬p ∨ q. (1)
(e) ¬(p ∧¬q).
¬(p ∧¬q) ≡¬p ∨ q. (De Morgan’s Law) p → q ≡ ¬p ∨ q. (1)
Hence, ¬(p ∧¬q) ≡ p → q
3. (10 points) Construct truth tables for the following and determine whether each of the following is a tautology or neither.
(a) [p → (q ∧ r)] ↔ [(p → q) ∧ (p → r)].
Truth Table:
p q r [p → (q ∧ r)] [(p → q) ∧ (p → r)] [p → (q ∧ r)] ↔ [(p → q) ∧ (p → r)]
T T T T T T
T T F F F T
T F T F F T
T F F F F T
F F T T T T
F T F T T T
F F F T T T
F T T T T T
Tautology.
(b) (a ∨ (bLc)) ∨ (c → b).
Truth Table:
a b c (a ∨ (bLc)) (c → b) (a ∨ (bLc)) ∨ (c → b)
T T T T T T
T T F T T T
T F T T F T
T F F T T T
F F T T F T
F T F T T T
F F F F T T
F T T F T T
Tautology.
4. (10 points) Write these propositions using p, q and r and logical connectives. Test the validity of the following argument using truth table. p: Tom is a singer. q: Tom is a footballer. r: Tom has good voice.
Tom is either a singer or a footballer. If he is a singer then he has good voice. Tom does not have good voice so he is a footballer.
Proposition: (pLq) ∧ (p → r) ∧ (¬r → q)
Truth Table:
p q r (pLq) (p → r) (¬r → q) (pLq) ∧ (p → r) ∧ (¬r → q)
T T T F T T F
T T F F F T F
T F T T T T T
T F F T F F F
F F T F T F F
F T F T T T T
F F F F T F F
F T T T T T T
5. (10 points) Show, without using truth table, if (d∨(a∧c∧d))∧((a∧b∧¬c)∨a∨(a∧b)) is logically equivalent to (a ∧ d). Explain why (simplify and use the laws of logic).
(d ∨ (a ∧ c ∧ d)) ≡d Absorption law
(a ∧ b ∧¬c) ∨ a ≡a Absorption Law
(a ∨ (a ∧ b)) ≡ (d ∧ a) Absorption law
6. (6 points) A = {1,2,3,4},B = {3,4,5},X = {a,b},Y = {b,c,d}. List the elements of each of the following sets.
(a) (A × X) ∩ (B × Y ) = {(3,b),(4,b)}
(b) (A ∩ X) × Y . = {b,c,d}
(c) (A×X)∪(B×Y ) = {(1,a),(1,b),(2,a),(2,b),(3,a),(3,b),(4,a),(4,b),(3,c),(3,d),(4,c) ,(4,d),(5,b),(5,c),(5,d)}
7. (4 points) Find the power set P(E) of E = [{a,b,c},{b,c},{1,2}].
E = {a,b,c}∪{b,c}∪{1,2}
E = {a,b,c,1,2}
P(E) = [{a},{b},{c},{1},{2},{a,b},{a,c},{c,b},{a,1},{a,2},{b,1},{b,2},
{c,1},{c,2},{1,2},{a,b,c,1},{a,b,c,2},{2,b,c,1},{a,2,c,1},{a,b,2,1} {a,b,c,1,2},{}]
8. (15 points) Prove by mathematical induction that for all positive integers n ≥ 1, 42n+1 + 3n+2 is divisible by 13.
a1 ≡ 0 mod(13)
an = 42n+1 + 3n+2 → an+1 = 42n+3 + 3n+3 We assume the proposition is true, hence:
m,n ∈ N
an = 13.m ⇒ 13.m = 4.4n + 9.3n ⇒ 3.13.m = 12.4n + 27.3n an+1 = 13.n = 64.4n + 27.3n
an+1 − an ⇒ 13(n − m) = 52.2n ⇒ 13(n − m) − 51.2n ≡ 0 mod(13)
9. (15 points) Use mathematical induction to prove that for n ≥ 1