Answer Happy

3. [16 marks] Here is a list of five propositional forms and three circuits. This list contains four pairs of logically equivalent entries (we will say a circuit is equivalent to a propositional form if the propositional form describes the value of the circuit's output for all possible combinations of input values). For instance, maybe A = B, C = D, E = F and G = H). First determine the four pairs, and then prove for each pair that one element of the pair is logically equivalent to the other one. (A) ~((p+q) V (q+r)) (B) ((p+q) →r) V (r→(g+p)) (C) ((~q→(p Vr)) →p) V~(p→(q^r)) (D) (~p^q^~r) V (p^~q^r) (E) q^ (per) (F) O qo output ro (G) output (H) output You are allowed to use truth tables to figure out the equivalences; however at least three of your proofs must use a sequence of known logical equivalences. The fourth proof can use either a sequence of known logical equivalences, or a truth table. Hint: you might want to translate the circuits into formulas that mirror exactly as the circuit is implemented, before using any logical equivalence rules. O P qo