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 \vee q) \rightarrow(q \vee p)

Passo 1

O enunciado pede para mostrar que
\vdash (p\vee q)\to(q\vee p).
Isso é a comutatividade da disjunção em lógica proposicional. Vamos usar Dedução Natural no estilo Gentzen, com as regras de introdução e eliminação de \vee e de introdução de \to.

Passo 2

Para provar (p\vee q)\to(q\vee p) por introdução de \to, assumimos temporariamente
1.\quad p\vee q
e a partir dessa hipótese vamos deduzir q\vee p.

Passo 3

Aplicamos prova por casos usando eliminação de \vee. Primeiro caso: suponha 2.\quad p Então, pela regra de introdução de \vee (que permite inferir A\vee B a partir de A), obtemos
3.\quad q\vee p.

Passo 4

Segundo caso: suponha 4.\quad q Então, novamente pela introdução de \vee, obtemos
5.\quad q\vee p.

Passo 5

Agora aplicamos eliminação de \vee à hipótese 1.\\ p\vee q. A regra diz que, se temos p\vee q, se de p podemos derivar q\vee p e de q também podemos derivar q\vee p, então inferimos
6.\quad q\vee p.

Passo 6

Por fim, descarregamos a hipótese 1.\\ p\vee q usando introdução de \to. Como de p\vee q chegamos a q\vee p, concluímos
\vdash (p\vee q)\to(q\vee p).

Resposta

\vdash (p\vee q)\to(q\vee p)

Exercícios relacionados