Question B4: A compound proposition is said to be in disjunctive normal form if it is written as a disjunction of conjunctions of variables or their negations (see exercise 46 of section 1.3), so for example (p q r) (p q r) (p r) is in disjunctive normal form, but p q (r s) and r (p q) are not. The precedence of logical operators (see table 8 of section 1.1) that we use in this course is set up specifically so that if an expression is in disjunctive normal form, then leaving out the parentheses will not change its meaning. It is an important aspect of digital design that every compound proposition is logically equivalent to a proposition that is written in disjunctive normal form.

(a) Write a truth table for the compound proposition (p q) (r p), () and use it to construct an expression in disjunctive normal form that is logically equivalent to (). Hint: for every row in which () is true, find a conjunction of variables and negations of variables that is true for precisely that row.

(b) Find a sequence of logical equivalences from tables 6 and 7 that shows your expression and () are equivalent. You may use any of the equivalences that you wish, but it should be possible to find an equivalence even if you limit yourself to

The conditional-disjunction equivalence,

The distributive laws,

The associative laws,

De Morgans Laws, and

The double negation law.