Notes - Logic MT24, Example proofs in propositional logic

Created: January 01, 2025
Updated: March 18, 2025

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) that for any $\phi \in \text{Form}(\mathcal L _ 0)$,

\[\vdash (\phi \to \phi)\]
  1. $((\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$)
  2. $(\phi \to ((\phi \to \phi) \to \phi))$ (A1 with $\alpha = \phi, \beta = (\phi \to \phi)$)
  3. $((\phi \to (\phi \to \phi)) \to (\phi \to \phi))$ (MP 2,1)
  4. $(\phi \to (\phi \to \phi))$ (A1 with $\alpha, \beta = \phi$)
  5. $(\phi \to \phi)$ (MP 4, 3)

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) that for any $\phi, \psi \in \text{Form}(\mathcal L _ 0)$,

\[\\{\psi, \lnot \psi\\} \vdash \phi\]
  1. $((\lnot \phi \to \psi) \to ((\lnot \phi \to \lnot \psi) \to \phi))$ (A3 with $\alpha = \phi, \psi = \beta$)
  2. $\psi$ (Hyp)
  3. $(\psi \to (\lnot \phi \to \psi))$ (A1 with $\alpha = \psi, \beta = \lnot \phi$)
  4. $(\lnot \phi \to \psi)$ (MP 2,3)
  5. $((\lnot \phi \to \lnot \psi) \to \phi$ (MP 4,1)
  6. $\lnot \psi$ (Hyp)
  7. $(\lnot \psi \to (\lnot \phi \to \lnot \psi))$ (A1 with $\alpha = \lnot \psi, \beta = \lnot \phi$)
  8. $(\lnot \phi \to \lnot \psi)$ (MP 6,7)
  9. $\phi$ (MP 8,5)

@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) that for any $\alpha \in \text{Form}(\mathcal L _ 0)$,

\[\vdash \alpha\]
  1. $(\alpha \to (\alpha \to \alpha))$ (A1)
  2. $(\alpha \to ((\alpha \to \alpha) \to \alpha))$ (A1)
  3. $((\alpha \to ((\alpha \to \alpha)) \to ((\alpha \to (\alpha \to \alpha)) \to (\alpha \to \alpha)))$ (A2)
  4. $((\alpha \to (\alpha \to \alpha)) \to (\alpha \to \alpha))$ (MP2,3)
  5. $(\alpha \to \alpha)$ (MP1,4)

@example~



Related posts