Demonstre que as fórmulas abaixo são teoremas. Para as provas, você pode escolher entre o Sistema Axiomático de Hilbert, utilizando apenas os axiomas apresentados em sala e a regra do modus ponens(MP) ou o Sistema de Dedução Natural no estilo de Gentzen.
\quad \vdash(p \wedge q) \rightarrow(q \wedge p)

Passo 1

Resumo do enunciado: queremos mostrar que
\vdash (p \wedge q)\rightarrow (q \wedge p)
Ou seja, sem premissas, provar a fórmula \,(p\wedge q)\to(q\wedge p).
Conteúdo: lógica proposicional, usando Dedução Natural (Gentzen) com as regras
\wedge-eliminação,
\wedge-introdução,
\rightarrow-introdução.

Passo 2

Suponha temporariamente a hipótese
1.\quad p\wedge q
Isso nos permitirá usar a regra de introdução de condicional no final.

Passo 3

De 1. aplicamos eliminação de conjunção para obter as duas partes:
2.\quad p \quad(\wedge\text{-eliminação em }1)çã
3.\quad q \quad(\wedge\text{-eliminação em }1)çã

Passo 4

Agora, com q e p em mãos, usamos introdução de conjunção para construir q\wedge p:
4.\quad q\wedge p \quad(\wedge\text{-introdução em }3,2)çã

Passo 5

Finalmente, aplicamos introdução de condicional, desligando a hipótese 1 e concluindo a prova:
5.\quad (p\wedge q)\rightarrow(q\wedge p) \quad(\rightarrow\text{-introdução de }1\text{ a }4)çã

Resposta

\vdash (p\wedge q)\rightarrow(q\wedge p).

Exercícios relacionados