Final Exam Review

1. Topics to study

a) Chapter 2 – Fundamentals of Logic b) Chapter 3 – Set Theory c) Chapter 4 – Induction and the Division Algorithm d) Chapter 5 & 7 – Relations and Functions e) Chapter 1 – Combinatorics f) Chapter 8 – Inclusion/Exclusion Principle

2. Chapter 2 – Fundamentals of Logic

a) Logical Connectives i) Conjunction ii) Disjunction iii) Negation iv) XOR v) Implication vi) Bi-Direction

b) Truth Table construction

8. Construct a truth table for each of the following compound statements, where p, q, r denote primitive statements. Tell whether the given statement is a tautology.

a. ¬ (p Ú ¬q) → ¬p p q ¬q ¬p p Ú ¬q ¬ (p Ú ¬q) ¬ (p Ú ¬q) → ¬p
0 0 1 1 1 0 1
0 1 0 1 0 1 1
1 0 1 0 1 0 1
1 1 0 0 1 0 1

The statement is a tautology.

b. p → (q → r) p q r q → r p → (q → r)
0 0 0 1 1
0 0 1 1 1
0 1 0 0 1
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 0 0
1 1 1 1 1

The statement is not a tautology.

c. (p → q) → r p q r p → q (p → q) → r
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1

The statement is not a tautology.

d. (p → q) → (q → p) p q p → q q → p (p → q) → (q → p)
0 0 1 1 1
0 1 1 0 0
1 0 0 1 1
1 1 1 1 1
The statement is not a tautology.

e. (p  (p → q)) → q p q p → q p  (p → q) (p  (p → q)) → q
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1
The statement is a tautology.

f. (p  q) → p p q p  q (p  q) → p
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 1

The statement is a tautology.

g. q ↔ (¬p Ú ¬q) p q ¬p ¬q ¬p Ú ¬q q ↔ (¬p Ú ¬q)
0 0 1 1 1 0
0 1 1 0 1 1
1 0 0 1 1 0
1 1 0 0 0 0

The statement is not a tautology.

h. [(p → q)  (q → r)] → (p → r) p q r p → q q → r [(p → q)  (q → r)] p → r [(p → q)  (q → r)] → (p → r)
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 1 0 1 0 0 1 1
0 1 1 1 1 1 1 1
1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1

The statement is a tautology.

12. Find a truth value assignment, if any, for the primitive statements p, q, r, s, t that make each of the following compound statements false.

a. [(p  q)  r] → (s Ú t)

p q r s t (p  q) [(p  q)  r] s Ú t [(p  q)  r] → (s Ú t)
1 1 1 0 0 1 1 0 0

b. [p  (q  r)] → (s XOR t) p q r s t (p  q) [(p  q)  r] s Ú t [(p  q)  r] → (s Ú t)
1 1 1 1 1 1 1 0 0
(1 of 2 solutions)

13. If the statement q has the truth value of 1, determine all truth value assignments for the primitive statements, p, r and s for which the truth value of the following statement is true. (q → [(¬p Ú r)  ¬s])  [¬s → (¬r  q)]

Short Cuts x y z j k q p r s ¬p Ú r x  ¬s q → y ¬r  q ¬s → j z  k
1 0 0 0 1 1 1 1 1 1

c) Laws of Logic (Most important ones listed below) i) Double Negation ii) DeMorgan’s Law iii) Commutative Law iv) Associative Law v) Distributive Law vi) Idempotent Law vii) Identity Law viii) Inverse Law ix) Domination Law x) Absorption Law xi) Contrapositive Law xii) Definition of Implication

Prove that ((p  T)  (q  F))  (p  q  r  r)  p  q.

((p  T)  (q  F))  (p  q  r  r)
 ((p  T)  (q  F))  (p  q  r) Idempotent
 ((p  T)  q)  ((p  q ) r) Associative and Identity
 (p  q)  ((p  q)  r) Identity
 p  q Absorption

Prove that (p  (r  r))  (q  (q  (p  q)))  p

(p  (r  r))  (q  (q  (p  q)))
 (p  T)  (q  (q  (p  q))) Inverse
 (p)  (q  (q  (p  q))) Identity
 p  (q  (q  (p  q))) Double Negation
 p  (q  (q  (p  q))) DeMorgan’s
 p  (q  q) Absorption
 p  (T) Inverse
 p  F
 p Identity