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

Passo 1

O enunciado dá três premissas e pede para demonstrar que a conclusão r segue delas. Vou listar tudo claramente:
  • Premissas:
    • \;p \rightarrow q
    • \;\neg p \rightarrow \neg\neg r
    • \;\neg q
  • O que se pede: mostrar que, a partir dessas premissas, se pode deduzir r. Em notação de sequente:
    p \rightarrow q,\\ \neg p \rightarrow \neg\neg r,\\ \neg q \vdash r.

Passo 2

Escolha do método: vou usar dedução natural (provas por suposição e regras básicas: \rightarrow-eliminação (modus ponens), \neg-introdução (prova por contradição parcial) e eliminação da dupla negação). Essas são ferramentas básicas e diretas para essa tarefa: a ideia intuitiva é mostrar que \neg q e p\rightarrow q nos forçam a concluir \neg p; então usar \neg p\rightarrow\neg\neg r para obter \neg\neg r e finalmente eliminar as negações para obter r.

Passo 3

Vou explicar as regras que vou usar (com linguagem simples):
  • Regra \rightarrow-eliminação (modus ponens): se se tem \;A\rightarrow B e também A, então pode-se inferir B. Em símbolo: de \;A\rightarrow B e A segue B.
  • Regra de \neg-introdução (introdução da negação / prova por contradição): para provar \neg A, assume-se provisoriamente A e mostra-se que dessa suposição segue uma contradição (um par B e \neg B, que costuma ser abreviado por \bot). Se a suposição leva a \bot, então pode-se concluir \neg A, dischargando a suposição.
  • Símbolo de contradição: \bot representa “contradição” (algo do tipo B e \neg B simultaneamente).
  • Eliminação da dupla negação: em lógica clássica, de \neg\neg A pode-se inferir A. Essa é a regra que transforma a negação dupla em afirmação simples.
Vou usar essas regras passo a passo.

Passo 4

Primeiro bloco: derivar \neg p a partir de \;p \rightarrow q e \neg q.
  1. \;p \rightarrow q (premissa)
  2. \;\neg q (premissa)
Agora faço uma suposição temporária para aplicar \neg-introdução:
  1. Suponha \;p. (suposição para demonstrar \neg p)
Aplicando modus ponens (regra de \rightarrow-eliminação) com (1) e (3):
  1. De (1) e (3) segue \;q. (por \rightarrow-eliminação)
Mas temos (2) que é \neg q. Assim, das linhas (4) e (2) obtemos uma contradição:
  1. \bot (contradição entre q e \neg q)
Como a suposição p levou a \bot, por \neg-introdução podemos concluir:
  1. \;\neg p. (a suposição em (3) é descarregada)

Passo 5

Segundo bloco: usar \neg p com a segunda premissa para obter \neg\neg r, e depois eliminar as negações.
  1. \;\neg p \rightarrow \neg\neg r (premissa)
Aplicando modus ponens com (6) e (7):
  1. De (6) e (7) segue \;\neg\neg r. (por \rightarrow-eliminação)
Agora aplico eliminação da dupla negação:
  1. De (8) segue \;r. (eliminação da dupla negação)
Portanto, a partir das três premissas chegamos a r.

Passo 6

Comentário final e verificação: todas as suposições temporárias foram devidamente descarregadas (a única suposição que fiz foi p em (3), que foi usada apenas para obter \neg p por \neg-introdução). As regras usadas são aceitáveis em dedução natural clássica. Logo o argumento é válido: as premissas implicam r.

Resposta

r

Exercícios relacionados