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

Passo 1

Vou listar claramente o que o enunciado nos dá e o que pede.
  • Premissas:
    • p \rightarrow \neg r.
    • q \rightarrow r.
    • q.
  • O que se pede:
    • Mostrar que a conclusão \neg p segue logicamente das premissas, ou seja, provar p \rightarrow \neg r,\\ q \rightarrow r,\\ q \vdash \neg p.

Passo 2

Escolha do método e explicação das regras que vou usar (com exemplos simples).
  • Estratégia: para provar uma negação \neg p é muito comum usar prova por contradição (também chamada de introdução de negação): assumir p e mostrar que dessa suposição segue uma contradição; daí conclui-se \neg p.
  • Regra “Modus Ponens” (eliminação da implicação): se se tem \;A \rightarrow B\; e também A, então pode-se inferir B.
    • Esquema: de \;A \rightarrow B,\; A\; inferir \;B.
    • Exemplo rápido: de r \rightarrow s e r segue s.
  • Regra “Introdução de negação” (¬-I, prova por contradição): se, supondo A, é possível derivar uma contradição (algo da forma C \land \neg C ou o símbolo absurdo \bot), então pode-se concluir \neg A, descartando a suposição.
    • Esquema: se assumindo A obtém-se \bot, então inferir \neg A.
    • Exemplo rápido: se assumo x e consigo tanto y quanto \neg y, concluo \neg x.

Passo 3

Aplicando modus ponens com as premissas envolvendo q.
  • Temos a premissa \;q \rightarrow r\;.
  • Temos também a premissa \;q\;.
  • Pela regra de modus ponens (de \;q \rightarrow r e q inferimos r), obtemos: r.Justificativa: a implicação diz que sempre que q é verdade, então r também o é; como q é dada, concluímos r.

Passo 4

Preparar a prova por contradição: assumir p e ver o que acontece.
  • Para provar \neg p vou assumir provisoriamente: p \quad (\text{assunção para } \neg\text{-I}).çã

Passo 5

Aplicando modus ponens com a premissa \;p \rightarrow \neg r\; e a assunção p.
  • Temos \;p \rightarrow \neg r\; (premissa).
  • Temos p (assunção do passo anterior).
  • Pela regra de modus ponens, de \;p \rightarrow \neg r e p inferimos: \neg r.Explicação: a implicação diz que se p então \neg r; como assumimos p, tiramos \neg r.

Passo 6

Obter a contradição juntando os resultados dos passos anteriores.
  • Do Passo 3 obtivemos r.
  • Do Passo 5 obtivemos \neg r.
  • Então temos simultaneamente r e \neg r, isto é uma contradição. Podemos escrever isso como: r \land \neg r \quad\text{(contradição)}\quad\text{ou simplesmente}\quad \bot.çã

Passo 7

Concluir \neg p por descarte da assunção (introdução de negação).
  • Como a suposição p levou a uma contradição ( \bot), pela regra de introdução de negação podemos concluir que a suposição é falsa; portanto: \neg p.
  • Essa \neg p é deduzida usando apenas as premissas iniciais e a regra de prova por contradição, então a inferência é válida.

Resposta

\neg p