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

Passo 1

O enunciado pede para mostrar que \vdash (p \rightarrow q) \rightarrow \bigl((q \rightarrow r)\rightarrow (p \rightarrow r)\bigr).
Vamos usar o Sistema de Dedução Natural (estilo Gentzen), com as regras de Introdução e Eliminação de \rightarrow.

Passo 2

Para provar \vdash (p \rightarrow q) \rightarrow \bigl((q \rightarrow r)\rightarrow (p \rightarrow r)\bigr), assumimos provisoriamente as premissas
1.\quad p \rightarrow q
2.\quad q \rightarrow r
e mostramos sob essas hipóteses que p \rightarrow r.

Passo 3

Assuma adicionalmente 3.\quad p
para derivar r.
De 1 e 3, por Eliminação de \rightarrow ( \rightarrowE), obtém-se
4.\quad q.
De 2 e 4, por \rightarrowE, obtém-se
5.\quad r.

Passo 4

Como r foi obtido sob a hipótese p (linha 3), aplicamos Introdução de \rightarrow ( \rightarrowI) e descartamos a hipótese 3 para concluir
6.\quad p \rightarrow r.

Passo 5

Agora que derivamos p \rightarrow r sob a hipótese q \rightarrow r (linha 2), por \rightarrowI descartamos a hipótese 2 e inferimos
7.\quad (q \rightarrow r)\rightarrow(p \rightarrow r).

Passo 6

Finalmente, derivamos (q \rightarrow r)\rightarrow(p \rightarrow r) sob a hipótese p \rightarrow q (linha 1). Aplicando \rightarrowI e descartando a hipótese 1, obtemos
8.\quad (p \rightarrow q)\rightarrow\bigl((q \rightarrow r)\rightarrow(p \rightarrow r)\bigr).

Resposta

\vdash (p \rightarrow q)\rightarrow\bigl((q \rightarrow r)\rightarrow(p \rightarrow r)\bigr)

Exercícios relacionados