Exercício 01: Demonstre a validade dos seguintes argumentos:
p \rightarrow q, q \rightarrow r \vdash \neg p \vee r

Passo 1

O enunciado dá as duas premissas
p \rightarrow q,\qquad q \rightarrow r
e pede para demonstrar que a conclusão
\neg p \vee r
é uma consequência lógica dessas premissas; ou seja, mostrar que sempre que p\rightarrow q e q\rightarrow r são verdadeiras, então \neg p \vee r também é verdadeira.

Passo 2

Vou provar a validade fazendo uma análise por casos simples sobre o valor de verdade de p. Essa técnica é bem básica e direta: consideramos as duas possibilidades para p (verdadeiro ou falso) e mostramos que em ambas o disjunto \neg p \vee r fica verdadeiro quando as premissas são verdadeiras. Antes de começar, lembro duas regras usadas aqui:
  • Modus ponens: de A\rightarrow B e A segue B.
  • Introdução da disjunção: se X é verdadeiro então X\vee Y é verdadeiro (para qualquer Y).

Passo 3

Caso 1: suponha p é verdadeira.
  • Das premissas temos p\rightarrow q. Aplicando modus ponens com p obtemos q.
  • Das premissas temos também q\rightarrow r. Aplicando modus ponens com q obtemos r.
  • Se r é verdadeira então a disjunção \neg p \vee r é verdadeira (introdução da disjunção).
    Portanto, quando p é verdadeira e as premissas valem, a conclusão \neg p \vee r vale.

Passo 4

Caso 2: suponha p é falsa.
  • Se p é falsa então \neg p é verdadeira por definição.
  • Se \neg p é verdadeira então a disjunção \neg p \vee r é verdadeira (introdução da disjunção).
    Portanto, quando p é falsa e as premissas valem, a conclusão \neg p \vee r vale.

Passo 5

Como os dois casos possíveis para p (verdadeiro ou falso) cobrem todas as situações e em ambos obtivemos que \neg p \vee r é verdadeira sempre que as premissas (p\rightarrow q,\; q\rightarrow r) são verdadeiras, concluímos que as premissas implicam semanticamente a conclusão. Em linguagem lógica:
\{\,p\rightarrow q,\; q\rightarrow r\,\}\models \neg p \vee r.
Ou seja, o argumento é válido.

Passo 6

(Observação alternativa, útil para prova em sala) Pode-se ver a mesma ideia por dedução condicional: assumindo p e usando as premissas obtém-se r; então por prova condicional conclui-se p\rightarrow r. Como, em lógica clássica, p\rightarrow r é logicamente equivalente a \neg p \vee r, obtemos a conclusão desejada. Os passos formais seriam:
  • Assuma p.
  • De p e p\rightarrow q obtenha q.
  • De q e q\rightarrow r obtenha r.
  • Discharge a suposição de p e deduza p\rightarrow r.
  • Substitua p\rightarrow r por \neg p \vee r (equivalência clássica).

Resposta

\neg p \vee r

Exercícios relacionados