MATH 318, Assignment 3
1. (4 points) Write truth tables of the following formulas. Which
of them are tautologies?
(A) (¬p) → q, (B) (p ∧ q) ∨ (¬p),
(C) p → ((¬p) → q), (D) q ∨ (p → (q ∧ (p → q))).
2. (2 points) Devise formulas (using connectives amongst ∨, ∧ and
¬) and switching circuits (using gates amongst OR, AND and
NOT) which realize each of the following Boolean functions:
(A)
q\
p 0 1
0 1 1
1 0 1
(B)
q\
p 0 1
0 0 1
1 1 1
3. (2 points) Write DNF and CNF formulas equivalent to the formula ((p ∨ ¬q) ∧ (r ∨ p)) ∨ r.
4. (1) (1 point) Write a formula equivalent to p → q using only
the connective NAND,
(2) (1 point) Write a formula equivalent to (p ∧ q) ∨ ¬p using
only the connective NOR,
5. (2 points) Consider the formula
(. . .((p → p) → p) → . . .) → p,
where the variable p occurs n many times. For which n is the
above formula a tautology? Justify your answer.
6. (4 points) Suppose ϕ is a formula written using only the biconditional connective ↔ (besides variables and parentheses).
Show that ϕ is a tautology if and only if every variable occurs
in ϕ an even number of times.
1
2
7. (2 points) Using Karnaugh maps, find a formula realizing the
following Boolean function f with 4 variables p, q, r, s:
p q r s f(p, q, r, s)
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
The following problems are for extra credit.
8*. (4 points) Show that the set {∨, ∧} is not complete.
9*. (4 points) Show that the set {XOR} is not complete.
