Part I: Propositional Logic
10. Summary of Propositional Logic
10.1 Elements of the language
- Principle of Bivalence: each sentence is either true or false, never both, never neither.
- Each atomic sentence is a sentence.
- Syntax: if Φ and Ψ are sentences, then the following are also sentences
- ¬Φ
- (Φ→Ψ)
- (Φ ^ Ψ)
- (Φ v Ψ)
- (Φ↔Ψ)
- Semantics: if Φ and Ψ are sentences, then the meanings of the connectives are fully given by their truth tables. These truth tables are:
| Φ | ¬Φ |
| T | F |
| F | T |
| Φ | Ψ | (Φ→Ψ) |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
| Φ | Ψ | (Φ ^ Ψ) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| Φ | Ψ | (Φ v Ψ) |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| Φ | Ψ | (Φ↔Ψ) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
- A sentence of the propositional logic that must be true is a tautology.
- A sentence that must be false is a contradictory sentence.
- A sentence that is neither a tautology nor a contradictory sentence is a contingent sentence.
- Two sentences Φ and Ψ are equivalent, or logically equivalent, when (Φ↔Ψ) is a theorem.
10.2 Reasoning with the language
- An argument is an ordered list of sentences, one sentence of which we call the “conclusion” and the others of which we call the “premises”.
- A valid argument is an argument in which: necessarily, if the premises are true, then the conclusion is true.
- A sound argument is a valid argument with true premises.
- Inference rules allow us to write down a sentence that must be true, assuming that certain other sentences are true. We say that the new sentence is “derived from” those other sentences using the inference rule.
- Schematically, we can write out the inference rules in the following way (think of these as saying, if you have written the sentence(s) above the line, then you can write the sentence below the line):
| Modus ponens | Modus tollens | Double negation | Double negation |
| (Φ→Ψ)
Φ _____ Ψ |
(Φ→Ψ)
¬Ψ _____ ¬Φ |
Φ
_____ ¬¬Φ |
¬¬Φ
_____ Φ |
| Addition | Addition | Modus tollendo ponens | Modus tollendo ponens |
| Φ
_____ (Φ v Ψ) |
Ψ
_____ (Φ v Ψ) |
(Φ v Ψ)
¬Φ _____ Ψ |
(Φ v Ψ)
¬Ψ _____ Φ |
| Adjunction | Simplification | Simplification | Bicondition |
| Φ
Ψ _____ (Φ ^ Ψ) |
(Φ ^ Ψ)
_____ Φ |
(Φ ^ Ψ)
_____ Ψ |
(Φ→Ψ)
(Ψ→Φ) _____ (Φ↔Ψ) |
| Equivalence | Equivalence | Equivalence | Equivalence |
| (Φ↔Ψ)
Φ _____ Ψ |
(Φ↔Ψ)
Ψ _____ Φ |
(Φ↔Ψ)
¬Φ _____ ¬Ψ |
(Φ↔Ψ)
¬Ψ _____ ¬Φ |
- A proof (or derivation) is a syntactic method for showing an argument is valid. Our system has three kinds of proof (or derivation): direct, conditional, and indirect.
- A direct proof (or direct derivation) is an ordered list of sentences in which every sentence is either a premise or is derived from earlier lines using an inference rule. The last line of the proof is the conclusion.
- A conditional proof (or conditional derivation) is an ordered list of sentences in which every sentence is either a premise, is the special assumption for conditional derivation, or is derived from earlier lines using an inference rule. If the assumption for conditional derivation is Φ, and we derive as some step in the proof Ψ, then we can write after this (Φ→Ψ) as our conclusion.
- An indirect proof (or indirect derivation, and also known as a reductio ad absurdum) is: an ordered list of sentences in which every sentence is either 1) a premise, 2) the special assumption for indirect derivation (also sometimes called the “assumption for reductio”), or 3) derived from earlier lines using an inference rule. If our assumption for indirect derivation is ¬Φ, and we derive as some step in the proof Ψ and also as some step of our proof ¬Ψ, then we conclude that Φ.
- We can use Fitch bars to write out the three proof schemas in the following way:
![\[ \fitchctx{ \pline{\phi}\\ \ellipsesline\\ \pline{\psi} } \]](https://milnepublishing.geneseo.edu/app/uploads/quicklatex/quicklatex.com-31e04ac5420871d59f57ec6fcb948214_l3.png "Rendered by QuickLaTeX.com")
![\[ \fitchctx{ \subproof{\pline{\phi}}{ \ellipsesline\\ \pline{\psi} } \fpline{(\phi \lif \psi)} } \]](https://milnepublishing.geneseo.edu/app/uploads/quicklatex/quicklatex.com-2f46df4a9e0479a7e59b3600a973707f_l3.png "Rendered by QuickLaTeX.com")
![\[ \fitchctx{ \subproof{\pline{\lnot \phi}}{ \ellipsesline\\ \pline{\psi}\\ \pline{\lnot \psi} } \fpline{\phi} } \]](https://milnepublishing.geneseo.edu/app/uploads/quicklatex/quicklatex.com-78adcfd2484235103afc6dfb18d20cfa_l3.png "Rendered by QuickLaTeX.com")
- A sentence that we can prove without premises is a theorem.
- Suppose Φ is a theorem, and it contains the atomic sentences P1…Pn. If we replace each and every occurrence of one of those atomic sentences Pi in Φ with another sentence Ψ, the resulting sentence is also a theorem. This can be repeated for any atomic sentences in the theorem.
