Formal Methods: First-Order Logic 3.3 Proofs - Johns Hopkins University
Formal Methods: First-Order Logic 3.3 Proofs
Johns Hopkins University, Fall 2017
Extending the Fitch System to FOL
Recall our two dicta.
Dictum: To show an argument is invalid, produce a counterexample.
Dictum: To establish an argument is valid, prove the conclusion from the premises.
In order to establish the tautological validity of arguments in the language of sentential logic LSENT , we earlier introduced a Fitch-style natural deduction system F for sentential logic. By the Soundness and Completeness Theorems, 1, ..., n |=SENT iff 1, ..., n F .
We are now going to extend the Fitch system with new rules for the identity symbol = and quantifier symbols and . Doing so will allow us to establish the logical validity of arguments in a first-order language.
But first, let us quickly review the rules in our original proof system (these can now be applied to wff's in a first-order language).
Review of Sentential Rules
Reiteration (a.k.a. Repetition) n ... R: n
Review of Sentential Rules
Conjunction Elimination (I)
n ...
Elim: n
Conjunction Elimination (II)
n ...
Elim: n
Review of Sentential Rules
Conjunction Introduction
n ...
m ...
Intro: n, m
Rather than writing a separate scheme for inferring , let us just say that the order of and as they appear in the proof does not matter. (We may have n < m or m < n.)
Review of Sentential Rules
Negation Introduction (a.k.a. Intuitionistic Reductio)
n ...
m
?
? Intro: n-m
Review of Sentential Rules
For reasons of symmetry, we institute the derivational strategy of classical reductio ad absurdum as the rule ? Elim.
Negation Elimination (a.k.a. Classical Reductio)
n ? ...
m
? Elim: n-m
Review of Sentential Rules
The cancelling of a double negation at the head of a wff is then easily proved from classical reductio as follows.
Double Negation Elimination
1 ?? [Show ]
2 ? 3 4
? Elim: 2-3
Of course, we could have taken double negation elimination as a primitive rule and derived classical reductio from it and intuitionistic reductio. But pedagogically, it's best to emphasize the difference between the two forms of reductio.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- formal proofs and boolean logic ii extending f with rules for
- formal verification of a modern sat solver
- a circuit based sat solver for logic synthesis
- logic and proof university of cambridge
- logic and proof lean
- formal and informal proofs university of pittsburgh
- lecture 8 predicate logic proofs university of washington
- formal veri cation with smt solvers why and how
- formal methods first order logic 3 3 proofs johns hopkins university
- chapter 8 hilbert proof systems formal proofs deduction theorem
Related searches
- johns hopkins university interactive map
- johns hopkins university departments
- johns hopkins university corona dashboard
- johns hopkins university health system
- johns hopkins university portal
- johns hopkins university investment office
- johns hopkins university baltimore address
- johns hopkins university contact
- johns hopkins university phd nursing
- johns hopkins university email
- johns hopkins university communication
- johns hopkins university business analytics