Predicate logic proofs PDF

Preview

Summary

Some examples of proofs within predicate logic ...

Description

Extra predicate logic proofs PHIL1031: Introduction to Logic Here are some extra predicate logic proofs you can practice (some of these may duplicate the ones in the tutorial exercises). Exercise 1. 1. ∀x(P x → Qx) → ∃x(Rx ∧ Sx), ∀x(P x → Sx) ∧ ∀x(Sx → Qx) ⊢ ∃xSx 2. ∀x(Ax → Bx), Am ∧ An ⊢ Bm ∧ Bn. 3. ∀x(Bx → Cx), ∃x(Ax ∧ Bx) ⊢ ∃x(Ax ∧ Cx). 4. ∀x(Jx → (K x ∧ Lx)), ∃y¬K y ⊢ ¬∀zJz . 5. ∀(Ax → (Bx ∨ Cx)), ∃x(Ax ∧ ¬Cx) ⊢ ∃xBx. 6. ∀x(Bx ∨ Ax), ∀x(Bx → Ax) ⊢ ∀xAx. 7. ¬∃x(Ax ∧ ¬Bx), ¬∃x(Ax ∧ ¬Cx) ⊢ ∀x(Ax → Cx). 8. ∀x((Ax ∧ Bx) → Cx), ¬∀x(Ax → Cx) ⊢ ∃x¬Bx. 9. ∃x¬Ax → ¬∃xBx, ¬∀xAx → ∃xBx, ∀x(¬Ax ∨ Cx) ⊢ ∀xCx. 10. ¬∃x(Ax ∨ Bx), ∃Cx → ∃xAx, ∃xDx → ∃xBx ⊢ ¬∃x(Cx ∨ Dx). If you are interested in further proofs, of a slightly higher level of difficulty, check out Chapter 9 of What is Logic?, specifically §9.4. The logical system investigated in Chapter 9, Peano Arithmetic, is a first-order system design to reason about the natural numbers. The language is introduced in Def. 9.2.1, with some extra notation defined in Defs. 9.2.2 and 9.2.3. Peano Arithemtic differs from the system that we have in that it introduces axioms. These axioms (PA1–PA9) can be written down in a proof at any stage, with the justification for those lines being the name of th axiom. These axioms are what provide Peano Arithmetic greater expressive power than first-order logic alone. How much greater? Enough to make PA incomplete: There are true statements about the natural numbers which cannot be proven in PA, if PA is consistent. (What to know more? Take Formal & Philosophical Logic :).)

1...