1. [9 marks] In this question, you will prove that every truth table can be implemented us- ing only the conditional operator and the constant False. Hint: in your justifications, you are free to use the fact that ab =~avb. a. [3 marks] Show that a logical expression that is logically equivalent to ~p, and uses only p, and False. You must prove that your logical expression is correct using equivalence rules. (See, e.g., Epp 4th ed page 35, Epp 5th ed page 49, or Dave's excellent formula sheet) b. [3 marks] Show that V can be simulated using only and False. That is, design a logical expression that is logically equivalent to p V q and uses only p, q, and False. You must prove that your logical expression is correct using equivalence rules. v can be simulated using only and False. That is, design c. [3 marks] Show that A can be simulated using only and False. That is, design a logical expression that is logically equivalent to pAq and uses only p, q, and False. You must prove that your logical expression is correct using equivalence rules. Since for every truth table over k atomic propositions, we can write a propositional form that matches the truth table using , V and A, your answers to parts (a), (b) and (c) show that you every propositional form is logically equivalent to a propositional form that uses only and False. Addendum: when we use a computational system, such as a circuit built out of gates, or (later in the course) regular expressions, we like it to have as many features as possible since it makes it more convenient for us (think of how painful it would be to design circuits using only and False. Or using only NAND gates!) On the other hand, when we want to reason about what this system can or can not do, we like to use the smallest possible set of features, because it's easier to think about a small set of features than a large one (there are fewer cases to consider). That's why proving that every circuit can be designed using only and False can be useful. 1. [9 marks] In this question, you will prove that every truth table can be implemented us- ing only the conditional operator and the constant False. Hint: in your justifications, you are free to use the fact that ab =~avb. a. [3 marks] Show that a logical expression that is logically equivalent to ~p, and uses only p, and False. You must prove that your logical expression is correct using equivalence rules. (See, e.g., Epp 4th ed page 35, Epp 5th ed page 49, or Dave's excellent formula sheet) b. [3 marks] Show that V can be simulated using only and False. That is, design a logical expression that is logically equivalent to p V q and uses only p, q, and False. You must prove that your logical expression is correct using equivalence rules. v can be simulated using only and False. That is, design c. [3 marks] Show that A can be simulated using only and False. That is, design a logical expression that is logically equivalent to pAq and uses only p, q, and False. You must prove that your logical expression is correct using equivalence rules. Since for every truth table over k atomic propositions, we can write a propositional form that matches the truth table using , V and A, your answers to parts (a), (b) and (c) show that you every propositional form is logically equivalent to a propositional form that uses only and False. Addendum: when we use a computational system, such as a circuit built out of gates, or (later in the course) regular expressions, we like it to have as many features as possible since it makes it more convenient for us (think of how painful it would be to design circuits using only and False. Or using only NAND gates!) On the other hand, when we want to reason about what this system can or can not do, we like to use the smallest possible set of features, because it's easier to think about a small set of features than a large one (there are fewer cases to consider). That's why proving that every circuit can be designed using only and False can be useful
