Subject: Functional Completeness From: "William J. Rapaport" Date: Mon, 14 Sep 2009 19:58:35 -0400 (EDT) One of your HW problems is to show that NOR is functionally complete by showing that any negation and any inclusive disjunction can be written as a logically equivalent proposition using only the NOR connective. But to finish up that proof, we need to prove that - (NOT) and v (OR) is a functionally complete set of connectives. To do that, we have to show that any conjunction, any conditional, any biconditional, and any exclusive disjunction can be written as logically equivalent propositions using only - and v. Step 1: Show that (p <-> q) equiv ((p -> q) ^ (q -> p)); i.e., show that any biconditional can be rewritten as a logically equivalent proposition that uses only the conditional (->) and conjunction (^), i.e., as (IF p THEN q) AND (IF q THEN p). proof: Left up to you. Use a truth table! Step 2: Show that (p -> q) equiv (-p v q); i.e., show that any conditional can be rewritten as a logically equivalent proposition that uses only negation and disjunction. proof: We did this in lecture. So far, we have shown that only - and v are needed to represent both conditionals and biconditionals. We showed it directly for conditionals (in lecture). And we showed it indirectly for biconditionals: Using the 2 steps above, we can see that (p <-> q) equiv (-p v q) ^ (-q v p). Step 3. Show that (p + q) can be written using only -,v,^: proof: (p + q) equiv (p v q) ^ -(p ^ q). As I recall, we did this in lecture, too. But if my recall is wrong, you can prove this with a truth table. Step 4. Show that any conjunction can be written using only - and v. proof: (p ^ q) equiv (--p ^ --q), by DN. equiv -(-p v -q), by DeMorgan We're done. End of proof. But here's a test. Can you rewrite the following proposition using only - and v? (((p -> q) ^ (q -> p)) -> (p <-> q))