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

Passo 1

O enunciado pede para mostrar que a fórmula
(\neg p \rightarrow q) \rightarrow \bigl((\neg p \rightarrow \neg q) \rightarrow p\bigr)
é um teorema do cálculo proposicional. Vamos usar Dedução Natural (estilo Gentzen), com as regras de introdução e eliminação de \rightarrow, introdução de \neg via redução ao absurdo (RAA) e eliminação de contradição.

Passo 2

Assuma \neg p \rightarrow q (hipótese 1)
e sob essa hipótese queremos derivar
(\neg p \rightarrow \neg q) \rightarrow p.

Passo 3

Em seguida, suponha
\neg p \rightarrow \neg q
(hipótese 2)
e sob essas duas hipóteses queremos derivar p.

Passo 4

Para obter p, recorremos à redução ao absurdo. Suponha provisoriamente \neg p (hipótese 3).
De \neg p e da hipótese 1 aplicamos eliminação de \rightarrow e obtemos q.
De \neg p e da hipótese 2 aplicamos eliminação de \rightarrow e obtemos \neg q.
Ora, de q e \neg q segue a contradição \bot.

Passo 5

Pela regra de redução ao absurdo (RAA), das hipóteses 3\colon \neg p até \bot concluímos p.

Passo 6

Agora fechamos a hipótese 2. Pelo teorema de introdução de \rightarrow a partir da suposição \neg p \rightarrow \neg q até p, inferimos
(\neg p \rightarrow \neg q) \rightarrow p.

Passo 7

Finalmente fechamos a hipótese 1. Pela introdução de \rightarrow a partir da suposição \neg p \rightarrow q até (\neg p \rightarrow \neg q) \rightarrow p, concluímos
(\neg p \rightarrow q) \rightarrow \bigl((\neg p \rightarrow \neg q) \rightarrow p\bigr).

Resposta

(\neg p \rightarrow q) \rightarrow \bigl((\neg p \rightarrow \neg q) \rightarrow p\bigr)

Exercícios relacionados