Problem 4. (40 Points) We saw in class the Conditional Identity, namely that p + = npVq. We might wonder then why it is necessary to even include as an operator since it's redundant. Well we include it because it is simpler to write and it is a very common operation in logic. However, this then might lead to the question of how many of our operators are redundant? Without then we are down to 4 operators: 7,1, V, and e. Can we show we need even fewer? a) (5 Points) Come up with an expression using 7, 4, and V that is logically equivalent to p q . Show its equivalence with a truth table or laws of propositional logic. b) (5 Points) We now only need 3 operators. Can we get it down to 2? Give an expression using only - and V that is logically equivalent to p^ q. Show its equivalence with a truth table or laws of propositional logic. c) (10 Points) We now only need 2 operators! Fantastic! Could we have done another two operators? Come up with an expression using - and that is logically equivalent to p V q. Show its equivalence with a truth table or laws of propositional logic. Then explain why showing p Va can be expressed using just and is sufficient to show we can express A and using only 7 and + Thus we seem to only need 2 operators. In fact, if you play around with it a second, you will probably notice we can't remove any other operators with what we've seen so far. d) (3 Points) However, there are a few other operators that we could try (that we haven't defined). How many binary operators are there? A binary operator connects two boolean expressions p, q. In other words, how many distinct ways (up to reordering rows) can you fill in a truth table of three columns, with p, q and p* q? So far we have seen 4 binary operators/ways to fill in the table where *=+, V,1,2). Explain how you arrived at your answer. One such special operator is called NAND. There are a few notations for NAND, but for this exercise we will use p 1 q. p q can defined as (p 19). e) (2 Points) Draw the truth table for NAND. f) (15 Points) Using only NAND, write two expressions that are equivalent to p and pVq. Prove these are equivalent using truth tables and explain why showing these two operators is enough to show that all of the operators we have defined so far can be defined in terms of NAND. Problem 4. (40 Points) We saw in class the Conditional Identity, namely that p + = npVq. We might wonder then why it is necessary to even include as an operator since it's redundant. Well we include it because it is simpler to write and it is a very common operation in logic. However, this then might lead to the question of how many of our operators are redundant? Without then we are down to 4 operators: 7,1, V, and e. Can we show we need even fewer? a) (5 Points) Come up with an expression using 7, 4, and V that is logically equivalent to p q . Show its equivalence with a truth table or laws of propositional logic. b) (5 Points) We now only need 3 operators. Can we get it down to 2? Give an expression using only - and V that is logically equivalent to p^ q. Show its equivalence with a truth table or laws of propositional logic. c) (10 Points) We now only need 2 operators! Fantastic! Could we have done another two operators? Come up with an expression using - and that is logically equivalent to p V q. Show its equivalence with a truth table or laws of propositional logic. Then explain why showing p Va can be expressed using just and is sufficient to show we can express A and using only 7 and + Thus we seem to only need 2 operators. In fact, if you play around with it a second, you will probably notice we can't remove any other operators with what we've seen so far. d) (3 Points) However, there are a few other operators that we could try (that we haven't defined). How many binary operators are there? A binary operator connects two boolean expressions p, q. In other words, how many distinct ways (up to reordering rows) can you fill in a truth table of three columns, with p, q and p* q? So far we have seen 4 binary operators/ways to fill in the table where *=+, V,1,2). Explain how you arrived at your answer. One such special operator is called NAND. There are a few notations for NAND, but for this exercise we will use p 1 q. p q can defined as (p 19). e) (2 Points) Draw the truth table for NAND. f) (15 Points) Using only NAND, write two expressions that are equivalent to p and pVq. Prove these are equivalent using truth tables and explain why showing these two operators is enough to show that all of the operators we have defined so far can be defined in terms of NAND
