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.
\vdash p \wedge(q \vee r) \rightarrow(p \wedge q) \vee(p \wedge r)

Passo 1

O enunciado pede para mostrarmos que
\vdash p \wedge (q \vee r) \rightarrow (p \wedge q) \vee (p \wedge r)
no sistema de Dedução Natural (Gentzen). A ideia é assumir o antecedente p\wedge(q\vee r), derivar o consequente (p\wedge q)\vee(p\wedge r) por eliminação de \wedge e \vee, e então usar introdução de \rightarrow para fechar a prova.

Passo 2

Assuma
p \wedge (q \vee r).
Pela eliminação de \wedge extraímos p
e q \vee r.

Passo 3

Para eliminar a disjunção q\vee r, fazemos duas subprovas de eliminação de \vee:
Subprova 1:
Assuma q.
Com p e q, por introdução de \wedge obtemos p \wedge q. Então, por introdução de \vee à esquerda, concluímos
(p\wedge q)\vee(p\wedge r).
Fim da Subprova 1.
Subprova 2:
Assuma r.
Com p e r, por introdução de \wedge obtemos p \wedge r. Então, por introdução de \vee à direita, concluímos
(p\wedge q)\vee(p\wedge r).
Fim da Subprova 2.

Passo 4

Agora aplicamos eliminação de \vee sobre a fórmula q\vee r usando as conclusões das duas subprovas. Dessa forma inferimos diretamente
(p\wedge q)\vee(p\wedge r).

Passo 5

Descarregamos a suposição inicial p\wedge(q\vee r) e aplicamos introdução de \rightarrow. Assim concluímos
p\wedge(q\vee r)\rightarrow(p\wedge q)\vee(p\wedge r).

Resposta

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

Exercícios relacionados