Logic MT24, Example proofs in propositional logic
Flashcards
The proof system $L _ 0$ is over the language $\mathcal L _ 0 := \mathcal L _ \text{prop}(\lnot, \to)$ and consists of:
Axioms: Any formula of the following form, where $\alpha, \beta, \gamma \in \text{Form}(\mathcal L _ 0)$:
- A1: $(\alpha \to (\beta \to \alpha))$ (“if A, then anything implies B”)
- A2: $((\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma)))$ (“if A shows that B implies C, then if A implies B, A also implies C”)
- A3: $((\lnot \alpha \to \beta) \to ((\lnot \alpha \to \lnot \beta) \to \alpha)))$ (“contradiction”)
Rules of inference:
-
Modus ponens (MP): For any $\phi, \psi \in \text{Form}(\mathcal L _ 0)$, from $\phi$ and $(\phi \to \psi)$ infer $\psi$.
Prove in $L _ 0$ (without using completeness or the deduction theorem) that for any $\phi \in \text{Form}(\mathcal L _ 0)$,
\[\vdash (\phi \to \phi)\]
- $(\phi \to ((\phi \to \phi) \to \phi))$ (A1 with $\alpha = \phi, \beta = (\phi \to \phi)$)
- $((\phi \to ((\phi \to \phi) \to \phi)) \to ((\phi \to (\phi \to \phi)) \to (\phi \to \phi)))$ (A2 with $\alpha = \phi, \beta = (\phi \to \phi), \gamma = \phi$)
- $((\phi \to (\phi \to \phi)) \to (\phi \to \phi))$ (MP 2,1)
- $(\phi \to (\phi \to \phi))$ (A1 with $\alpha, \beta = \phi$)
- $(\phi \to \phi)$ (MP 4, 3)
Tips for remembering:
- Need only A1 and A2
- Helps to work backwards
- There is no point trying to use the proof of the deduction theorem to help (the proof relies on this result)
@example~
The proof system $L _ 0$ is over the language $\mathcal L _ 0 := \mathcal L _ \text{prop}(\lnot, \to)$ and consists of:
Axioms: Any formula of the following form, where $\alpha, \beta, \gamma \in \text{Form}(\mathcal L _ 0)$:
- A1: $(\alpha \to (\beta \to \alpha))$ (“if A, then anything implies B”)
- A2: $((\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma)))$ (“if A shows that B implies C, then if A implies B, A also implies C”)
- A3: $((\lnot \alpha \to \beta) \to ((\lnot \alpha \to \lnot \beta) \to \alpha)))$ (“contradiction”)
Rules of inference:
-
Modus ponens (MP): For any $\phi, \psi \in \text{Form}(\mathcal L _ 0)$, from $\phi$ and $(\phi \to \psi)$ infer $\psi$.
Prove in $L _ 0$ (without using completeness or the deduction theorem) that for any $\phi, \psi \in \text{Form}(\mathcal L _ 0)$,
\[\\{\psi, \lnot \psi\\} \vdash \phi\]
Axioms: Any formula of the following form, where $\alpha, \beta, \gamma \in \text{Form}(\mathcal L _ 0)$:
- A1: $(\alpha \to (\beta \to \alpha))$ (“if A, then anything implies B”)
- A2: $((\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma)))$ (“if A shows that B implies C, then if A implies B, A also implies C”)
- A3: $((\lnot \alpha \to \beta) \to ((\lnot \alpha \to \lnot \beta) \to \alpha)))$ (“contradiction”)
Rules of inference:
- Modus ponens (MP): For any $\phi, \psi \in \text{Form}(\mathcal L _ 0)$, from $\phi$ and $(\phi \to \psi)$ infer $\psi$.
- $((\lnot \phi \to \psi) \to ((\lnot \phi \to \lnot \psi) \to \phi))$ (A3 with $\alpha = \phi, \psi = \beta$)
- $\psi$ (Hyp)
- $(\psi \to (\lnot \phi \to \psi))$ (A1 with $\alpha = \psi, \beta = \lnot \phi$)
- $(\lnot \phi \to \psi)$ (MP 2,3)
- $((\lnot \phi \to \lnot \psi) \to \phi$ (MP 4,1)
- $\lnot \psi$ (Hyp)
- $(\lnot \psi \to (\lnot \phi \to \lnot \psi))$ (A1 with $\alpha = \lnot \psi, \beta = \lnot \phi$)
- $(\lnot \phi \to \lnot \psi)$ (MP 6,7)
- $\phi$ (MP 8,5)
Tips for remembering:
- A3 definitely needs to be used, so it becomes a problem of deriving $(\lnot \phi \to \psi)$ and $(\lnot \phi \to \lnot \psi)$ from $\{\psi, \lnot \psi\}$ so that you can use MP twice
- But these two sub-results follow straightforwardly from A1 and MP
@example~
Suppose we have two proofs:
- $\beta _ 1, \ldots, \beta _ {r-1}, (\phi \to \alpha _ k)$
- $\gamma _ 1, \ldots, \gamma _ {s-1}, (\phi \to (\alpha _ k \to \alpha _ m))$
Can you give a proof of $\phi \to \alpha _ m$?
- $\beta _ 1, \ldots, \beta _ {r-1}, (\phi \to \alpha _ k)$
- $\gamma _ 1, \ldots, \gamma _ {s-1}, (\phi \to (\alpha _ k \to \alpha _ m))$
…followed by…
- A2: $((\phi \to (\alpha _ k \to \alpha _ m)) \to ((\phi \to \alpha _ k) \to (\alpha _ k \to \alpha _ m)))$
- MP: $((\phi \to \alpha _ k) \to (\phi \to \alpha _ m))$
- MP: $(\phi \to \alpha _ m)$
@example~
Show that there is no proof $\vdash (\phi \to \phi)$ in $\mathcal L _ 0$ which uses less than 5 lines.
Any derivation of $(\phi \to \phi)$ in $\mathcal L _ 0$ must end with an application of MP on the last line, since $(\phi \to \phi)$ is not an instance of any of the axioms. So the derivation must look like:
- Line $i$: $\alpha$
- Line $j$: $(\alpha \to (\phi \to \phi))$
- Line $k$: $(\phi \to \phi)$
We show that either $i$ or $j$ must’ve also been obtained by MP, and hence that the proof used at least 5 lines.
Line $j$ is only an axiom if:
- It is an instance of A1, so $\alpha = \phi$
- It is an instance of A3, so $\alpha = (\lnot \phi \to \lnot \phi)$
But then in either case $\alpha$ is not an axiom. Hence $\alpha$ must’ve been obtained by MP. So either line $i$ or line $j$ was obtained by MP and the overall proof must have at least 5 lines.
@example~ @exam~
Other examples
- Tautologies used in the proof that the Henkin construction for a complete witnessing $\mathcal L$-theory is a model:
- $(\tau \to (\lnot \rho \to \lnot (\tau \to \rho)))$
- $\lnot (\tau \to \rho) \to \tau$
- $\lnot (\tau \to \rho) \to \lnot \rho$