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 (pqr)(pqr)(pr) is in disjunctive normal form, but p(q(rs)) and r(pq) 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 (pq)(rp), 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 Morgan's Laws, and - The double negation law. Note: When a proposition is presented in disjunctive normal form, it is easy to determine whether or not the proposition is satisfiable (if you can see how, you probably already have a good understanding of what disjunctive normal form is). Any efficient method to determine which generic propositions are satisfiable, could be used to solve many of the most important problems in computer science. As a result, it is widely believed that there is no efficient way to find a compound The Associative Laws (see Table 6 in section 1.3.2) justify writing expressions involving only or only without parentheses. Since (pq)rp(qr), we can safely write pqr to represent both, without worrying about how someone might interpret it. We can also use the associative laws to show that all of parenthesized expressions involving four atomic propostions are logically equivalent. Example If we define t to be the compound proposition pq, then we can see that ((pq)r)s(tr)st(rs)(pq)(rs)bysubstitutionoftpqbytheassociativelawforbysubstitutionofpqt Note: We may not always make the t substitutions explicit. With practice, we will become comfortable summarizing the above derivation as: ((pq)r)s(pq)(rs) by the associative law applied to pq,r, and s. (a) Find a similar sequence of equivalences that proves (p(qr))sp(q(rs)). (b) The expression pqrs can be parenthesized in 5 different ways. Four of these ways are listed in either the example above or part (a), what is the fifth way to parenthesize pqrs ? (c) Use logical equivalences to show that your expression in (b) is equivalent to one of the expressions in (a). (d) Use logical equivalences to show that your expression in (b) is equivalent to one of the expressions in the example