1.Consider bit strings of 3 bits b2 b1 b0. Develop a proposition R expressed in terms of b0, b1, and b2 which is true (T) for such a bit string if and only if b2 b1 b0 = b0 b1 b2, i.e., if the bit string b2 b1 b0 is equal to its reverse. For example, R should be true (T) for bit string 010, but false F for bit string 001. Simplify you proposition as much as possible using the replacements laws of propositional logic.

2 Suppose that you have 2 two-bit bit strings a and b. Think of a as a1 a0 and b as b1 b0. So a (and, similarly b) represent the natural numbers 0, 1, 2, and 3 as the bit strings 00, 01, 10, and 11, respectively. Design a proposition L in terms of a0, a1, b0, and b1 such that L is true if and only if a b. For example, L should be true (T) when a = 10 and b = 11, L should be false when a = 01 and b = 00, and L should also be true when a = 01 and b = 01. Simplify you proposition as much as possible using the replacements laws of propositional logic.

3 Suppose that you have 2 two-bit bit strings a and b. Think of a as a1 a0 and b as b1 b0. So a and b represent the numbers 0, 1, 2, and 3 as the bit strings 00, 01, 10, and 11, respectively. Design 2 propositions in terms of a0, a1, b0, and b1 that implement the function max(0, ab). So for example max(0, 30) = 3 and max(0, 12) = 0. Notice that you need 2 propositions since max ranges from 0 to 3. Simplify your propositions as much as possible using the replacement laws.

4Argue that the Disjunctive Syllogism (Weak Resolution) inference rule is a special case of the Resolution inference rule.

5Argue that the Modus Ponens inference rule is a special case of the general form of the Proof by Cases inference rule

6 Building on the previous 3 questions, specify a list of dependencies among the set of Inference Rules. With a dependency we mean a pair of Inference Rules (Rule1, Rule2) stating that Rule1 is a special case of Rule2. For example such a dependency pair is (Weak Resolution, Resolution) because Weak Resolution is a special case of Resolution. Unlike in the previous 2 questions, you do not have to argue for the correctness of the actual dependencies, rather you should just list them.

7 Write the following arguments in symbolic form. Then prove (using inference rules and replacement laws) that the argument is valid or give a counter example that it is invalid. (These questions come from Ralph P. Grimaldi.) You can use letters to denote appropriate chosen atomic propositions. (a) If Dominic goes to the racetrack, then Helen will get mad. If Ralph plays cards all night, then Carmela will get mad. If either Helen or Carmela gets mad, then Veronica (their attorney) will be notified. Veronica has not heard from either of these two clients. Consequently, Dominic didnt make it to the racetrack and Ralph didnt play cards all night. (b)If there is a chance of rain or her headband is missing, then Lois will not mow the lawn. Whenever the temperature is over 80F, there is no chance for rain. Today the temperature is 85F and Lois is wearing her headband. Therefore (sometime today) Lois will mow her lawn

8Use inference rules and replacement laws, and give two different proofs, to prove that p q, q, r (p r) Make sure that you label the lines in each of your proof with the names of the inference rules or replacement laws that you used. Also indicate when you use a premise. Furthermore, make sure that one of your proofs is a proof by contradiction. (a) Proof 1: Proof by contradiction. (b)Proof 2: Use a different proof technique than proof by contradiction.

9Use inference rules and replacement laws, and give two different proof, to prove that p (q r), p s, t q, s r t Make sure that you label the lines in your proof with the names of the inference rules or replacement laws that you used. Also indicate when you use a premise. Furthermore, make sure that one of your proofs is the proof of a conditional. (a) Proof 1: Proof of a conditional. (b)Proof 2: Use a different proof technique than the proof of a conditional.

10 Show that there is no proof using inference rules and replacement laws to prove the following logical implication. p q, q r, r s, s q s