Question B1: Our table of logical equivalences (table 6 in section 1.3) only lists two distributive laws, but the laws (p q) r (p r) (q r) and (p q) r (p r) (q r) are also true, and are also sometimes referred to as distributive laws. Use equivalences that are in the tables to show that these two extra equivalences are true. Hint: It might help you to think about the corresponing rules from arithmetic. How are the statements a (b + c) = a b + a c and (a + b) c = a c + b c related?

Question B2: Logical quantifiers are affected by both the statement and by the universe of discourse. (a) Determine the truth value of each of the following quantified statements, if the universe is all integers:

(i) n(n 2 = n)

(ii) n(n 2 = 2)

(iii) n(n 2 n)

(iv) n (n > 5) (n 1 1)

(b) Which of your answers in (a) would change if the universe was all real numbers instead?

Question B3: The Associative Laws (see Table 6 in section 1.3.2) justify writing expressions involving only or only without parentheses. Since (pq)r p(q r), we can safely write pq r 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 p q, then we can see that (p q) r s (t r) s by substitution of t p q t (r s) by the associative law for (p q) (r s) by substitution of p q t Note: We may not always make the t substitutions explicit. With practice, we will become comfortable summarizing the above derivation as: (p q) r s (p q) (r s) by the associative law applied to p q, r, and s.

(a) Find a similar sequence of equivalences that proves p (q r) s p q (r s) . (b) The expression p q r s 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 p q r s?

(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.

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.

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 compoun