Logic MT24, Example proofs in propositional logic
Flashcards
The proof system $L _ 0$ is over the language $\mathcal L _ 0 := \mathcal L _ \mathrm{prop}(\lnot, \to)$ and consists of:
Axioms: Any formula of the following form, where $\alpha, \beta, \gamma \in \mathrm{Form}(\mathcal L _ 0)$:
- A1: $(\alpha \to (\beta \to \alpha))$ (“if A, then anything implies A”)
- 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 \mathrm{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 \mathrm{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 1,2)
- $(\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)
The proof system $L _ 0$ is over the language $\mathcal L _ 0 := \mathcal L _ \mathrm{prop}(\lnot, \to)$ and consists of:
Axioms: Any formula of the following form, where $\alpha, \beta, \gamma \in \mathrm{Form}(\mathcal L _ 0)$:
- A1: $(\alpha \to (\beta \to \alpha))$ (“if A, then anything implies A”)
- 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 \mathrm{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 \mathrm{Form}(\mathcal L _ 0)$,
\[\{\psi, \lnot \psi\} \vdash \phi\]
- $((\lnot \phi \to \psi) \to ((\lnot \phi \to \lnot \psi) \to \phi))$ (A3 with $\alpha = \phi, \beta = \psi$)
- $\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
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))$
@Show how to combine them into 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 (\phi \to \alpha _ m)))$
- MP: $((\phi \to \alpha _ k) \to (\phi \to \alpha _ m))$
- MP: $(\phi \to \alpha _ m)$
@Show that for a propositional variable $\phi$, there is no proof $\vdash (\phi \to \phi)$ in $L _ 0$ which uses less than 5 lines.
Any derivation of $(\phi \to \phi)$ in $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 (each application of MP needs two premise lines).
Line $j$ can only be an axiom via A1, forcing $\alpha = \phi$: an A2 match would force $\phi$ to be an implication (impossible, $\phi$ is a variable), and an A3 match would force $\phi = \alpha'$ and $\phi = (\lnot \alpha' \to \lnot \beta')$ simultaneously, making $\phi$ a proper subformula of itself (impossible).
But in that case line $i$ is $\alpha = \phi$, a propositional variable, which is not an axiom. Hence either line $j$ or line $i$ must’ve been obtained by MP and the overall proof must have at least 5 lines.
Remark: the restriction to a propositional variable matters. If $\phi$ is itself an axiom instance, then $\phi,\ (\phi \to (\phi \to \phi)),\ (\phi \to \phi)$ is a 3-line proof.
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$