Math 314 Test I, Spring 2011Dr. HolmesSeptember 25, 2011On this test you are allowed your writing instrument and the test paper.The test paper has a style sheet for propositional logic and axioms for formalarithmetic attached. You may tear these off for easy reference. Cell phonesmust be turned off and out of sight.There are seven proofs on this exam. Of these, you need to do twopropositional proofs (problems 1-3), two formal arithmetic proofs (problems4-6) and problem 7, which is perhaps harder and only counts 3 points asopposed to 10 points for each of the other four required proofs. If you do allthree proofs in a category, your best work will count. I do not suggest doingall three proofs on one of the two categories before you have done two in theother.In all proofs, the justification of a line (assumption, lemma) should includereferences to other lines (assumptions, lemmas) it depends on and whereappropriate the names of rules, axioms or theorems used. You are expectedto state goals (things you are trying to prove) where appropriate and clearlydistinguish them from assumptions or lemmas (things you know and canuse).You will be handed two copies of the test. One of these you do in class; theother you may do at home and hand in on Monday. The take-home versionof the test is optional; if you do it it will count as a homework assignmentand may at my discretion be used to adjust the test grade itself. You areexpected to do it entirely by yourself; evidence that people have done ittogether will affect my willingness to use it to award any adjustments on thetest (for anyone, not just those individuals).11 Propositional Logic1. General remark for all propositional logic problems: the conditionsfor doing these problems are identical to those on Homework 1. Youmay not use substitutions of equivalent expressions: use the rules andstrategies on the style sheet only.Write a formal proof of((P → Q) ∧ (Q → R )) → (P → R)in the style taught in class.22. Write a formal proof of(¬A ∨ ¬B) → ¬(A ∧ B)in the style taught in class.33. Write a formal proof of¬(A ∨ B) → (¬A ∧ ¬B)in the style taught in class.42 Formal Arithmetic4. General remark for all formal arithmetic proofs on the test: you areallowed to make substitutions justified by axioms in one line ratherthan two: for example you can write a + (b + 0) = a + b justified byaxiom 6 with x := b, without a separate b + 0 = b line.Write out the proof in formal arithmetic of(∀x.1 · x = x)using the axioms. This proof requires induction. You should not useanything but the axioms, the definition of 1, and Theorem 1.55. Write out the proof in formal arithmetic of the left distributive law ofmultiplication over addition,(x + y) · z = x · z + y · z.You are permitted to use the axioms and the theorems about additiononly. Please do induction on z only; I do not want to read what willresult if you try anything else.66. Write out the proof in formal arithmetic of the commutative law ofaddition,(∀xy.x + y = y + x).There are lemmas stated in the list of axioms and theorems of formalarithemtic which you are allowed to use: if you do this problem I expectyou to prove one of the two lemmas as well (these are induction proofstoo). The proofs of the lemmas will use the axioms only.73 Challenge Problem7. This proof is worth less than the others: it is harder but intended asan A/B separator rather than a stumbling block to passing the test.Prove in formal arithmetic that for any x and y, x+y = 0 implies x = 0and y = 0. This is not an induction proof. You may use the axiomsof formal arithmetic (note especially axiom 3) and Theorem 2. Hint:start by supposing that y 6= 0 and reason to a contradiction. Then itis easy to see that x = 0 (but say why).84 Propositional Logic Style SheetNot all of these are relevant to the assigned proofs; you need to recognizewhich rules and strategies are appropriate.Conjunction (and): To prove A ∧ B, prove A (part 1), then prove B (part2). The parts are not cases, and you will lose credit if you call somethinga proof by cases which isn’t one.From A ∧ B, deduce A. From A ∧ B, deduce B. You need to explicitlybreak apart assumptions or lemmas which are “and” statements to usetheir components; you will lose credit if you don’t.Disjunction (or): To prove A ∨ B, assume ¬A and adopt the new goal B[or assume ¬B and adopt the new goal A; you do not need to do both].From A, deduce A ∨ B. From B, deduce A ∨ B (rule of addition).From A ∨ B and ¬A, deduce B. From A ∨ B and ¬B, deduce A. Thisis disjunctive syllogism.To deduce a conclusion C from an assumption or lemma A ∨ B, useproof by cases: in the first part (case 1) assume A and prove C; in thesecond part (case 2) assume B and prove C.Implication (if): To prove A → B, assume A and adopt the new goal B.alternative strategy: to prove A → B, assume ¬B and adopt the newgoal ¬A.Given A and A → B, deduce B (modus ponens).Given ¬B and A → B, deduce ¬A (modus tollens).If you have an assumption A → B you may want to try proving A (sothat you can further conclude B).Negation (not): To prove ¬A, assume A and try to prove ⊥ (contradic-tion).From ¬¬A deduce A (double negation).To prove any statement A, assume ¬A and try to prove ⊥. This isproof by contradiction.From A and ¬A, deduce ⊥.9If you have a negative assumption ¬A, the commonest way to use it isto wait until your goal is a contradiction, then try to prove A to getthe contradiction.5 Axioms and Theorems of Formal ArithmeticHere are the axioms of formal arithmetic.1. 0 is a natural number (in symbols, 0 ∈ N).2. If x and y are natural numbers, so are S(x), x + y, and x · y. (∀xy ∈N.S(x) ∈ N ∧ x + y ∈ N ∧ x · y ∈ N).3. 0 is not a successor. (∀x.S(x) 6= 0). Here we understand that x 6= yabbreviates ¬x = y. Here and in the following axioms we write ourquantifiers unrestricted: we could write (∀x ∈ N.S(x) 6= 0) instead,but in this context we are only talking about natural numbers, so wecan leave the restriction on our quantifiers implicit.4. Numbers with the same successor are the same. (∀xy.S(x) = S(y) →x = y).5. Let P(x) be any sentence about a natural number variable x. Weassert P (0) ∧ (∀y.P (y) → P (S(y))) → (∀x.P (x)). This is a sym-bolic presentation of the familiar principle of mathematical induction.From an extremely technical standpoint, this is an infinite collection ofaxioms, one for each sentence P (x). If we are also