$24
Discrete Mathematics Homework #1 Solution
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 ∨ (b L c)) ∨ (c → b).
Truth Table:
a
b
c
(a ∨ (b L c))
(c → b)
(a ∨ (b L c)) ∨ (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: (p L q) ∧ (p → r) ∧ (¬r → q)
Truth Table:
p
q
r
(p L q)
(p → r)
(¬r → q)
(p L q) ∧ (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
X 1 1
= 1 −
1≤x≤n x(x + 1)
(n + 1)
1 1
1
x(x+1) =
x − x+1
X 1 1
−
1 1 1 1
= 1 − + − + −
1
+ ... −
1
1≤x≤n x
x + 1
2 2 3 3 4
n + 1
X 1 1
−
= 1 −
1
1≤x≤n x
x + 1
n + 1
X 1 1
= 1 −
1≤x≤n x(x + 1)
(n + 1)
