Cálculo proposicioal

Axiomas

As sentenças seguintes são consideradas teoremas $\forall P,Q,R$.

  1. $P\implies (Q\implies P)$
  2. $(P \implies (Q \implies R)) \implies ((P\implies Q) \implies (P \implies R))$
  3. $ (\neg A \implies B) \implies ((\neg A \implies \neg B) \implies A) $

Regra de inferência

Se $A$ e $A\implies B$ são teoremas do cálculo proposicional, então $B$ é um teorema do cálculo proposicional. Temos, portanto $$ \left\{A , (A \implies B) \right\} \vdash B .$$

Essa regra de inferência é denominada modus ponens (MP).

Teoremas

Seguem teoremas considerados (por mim) importantes:

Teorema 1 (Reflexividade da implicação)

É possível deduzir a fórmula $A\implies A$ sem tomar hipóteses (além dos axiomas), ou seja, $\vdash A\implies A$. Segue a demonstração:

  1. $A\implies ((A \implies A ) \implies A)$ (Axioma 1)
  2. $(A \implies ((A \implies A) \implies A)) \implies ((A\implies (A \implies A)) \implies (A \implies A))$ (Axioma 2)
  3. $(A\implies (A \implies A)) \implies (A \implies A) $ (MP 1,2)
  4. $A \implies (A \implies A)$ (Axioma 1)
  5. $A\implies A$ (MP 4,3)

Teorema da dedução (volta)

Se $\Gamma \vdash A \implies B$ , então $\Gamma\cup \{A\}\vdash B$. Se $\Gamma \vdash A \implies B$, temos que $A \implies B$ é deduzível dos axiomas e de um conjunto de hipóteses $\Gamma$. Então temos:

  1. $\Gamma$ (Hipótese)
  2. $A$ (Hipótese)
  3. $A\implies B$ ( 1 e ($\Gamma \vdash A \implies B$))
  4. $B$ (MP 2,3)
Portanto $\Gamma \cup \{A\} \vdash B$.

Teorema da dedução

Se $\Gamma\cup \{A\}\vdash B$, então $\Gamma \vdash A \implies B$. A demonstração e sua importância estão presentes aqui.