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

Passo 1

O enunciado nos dá as seguintes premissas (peguei-as do enunciado):
  • p \vee q
  • s \rightarrow (q \wedge r)
  • p \rightarrow s
  • q \rightarrow s
E pede que se demonstre que a partir dessas premissas se pode concluir
r \wedge q.
Ou seja, preciso mostrar que o argumento
p \vee q,\; s \rightarrow (q \wedge r),\; p \rightarrow s,\; q \rightarrow s \;\vdash\; r \wedge q
é válido — isto é, que r \wedge q pode ser deduzido logicamente das quatro premissas.

Passo 2

Plano de resolução (o que vou fazer, explicado passo a passo e com as regras usadas):
  • A presença de p \vee q sugere usar uma prova por casos (regra de eliminação da disjunção, \vee-E): assumo p e mostro a conclusão; assumo q e mostro a conclusão; então concluo a partir de p \vee q.
  • As regras básicas que vou usar (explicadas de forma simples):
    • Modus ponens (eliminação da implicação, \rightarrow-E): de A e A \rightarrow B infero B. Ex.: de p e p \rightarrow s obtenho s.
    • Eliminação da conjunção ( \wedge-E): de A \wedge B infero A e infero B separadamente.
    • Introdução da conjunção ( \wedge-I): de A e B infero A \wedge B.
    • Eliminação da disjunção ( \vee-E, prova por casos): de A \vee B, se assumindo A se obtém C e assumindo B se obtém C, então infere-se C sem as suposições.
  • Vou trabalhar explicitando as suposições temporárias (para cada caso) e depois as descarregar com \vee-E.

Passo 3

Caso 1: suponho p. Vou deduzir r \wedge q a partir dessa suposição e das premissas.
  • Suponha p. (suposição para o caso)
  • Das premissas temos p \rightarrow s. Aplicando modus ponens com p obtenho s. Explicação: modus ponens é a regra que transforma p e p \rightarrow s em s.
  • Das premissas temos s \rightarrow (q \wedge r). Aplicando modus ponens com s obtenho q \wedge r. Explicação: novamente, de s e s \rightarrow (q \wedge r) segue q \wedge r.
  • Agora, de q \wedge r posso aplicar eliminação da conjunção para obter q e também para obter r. Isto é, de q \wedge r infiro q e infiro r.
  • Com r e q em mãos, aplico introdução da conjunção ( \wedge-I) para formar r \wedge q. Observação: mesmo que já tivéssemos q \wedge r, aqui reorganizamos para obter r \wedge q por meio de \wedge-E seguido de \wedge-I (não é necessário ter uma regra de “comutatividade” explícita).
  • Concluímos que, sob a suposição p, consegue-se r \wedge q. Agora essa suposição será descarregada quando usarmos a eliminação da disjunção.
Resumo do caso 1 em forma de passos curtos:
  • p (suposição)
  • de p e p \rightarrow s segue s ( \rightarrow-E)
  • de s e s \rightarrow (q \wedge r) segue q \wedge r ( \rightarrow-E)
  • de q \wedge r segue r e q ( \wedge-E)
  • de r e q segue r \wedge q ( \wedge-I)
  • portanto, r \wedge q (sob a hipótese p).

Passo 4

Caso 2: suponho q. Vou deduzir r \wedge q a partir dessa suposição e das premissas.
  • Suponha q. (segunda suposição para o caso)
  • Das premissas temos q \rightarrow s. Aplicando modus ponens com q obtenho s.
  • Das premissas temos s \rightarrow (q \wedge r). Aplicando modus ponens com s obtenho q \wedge r.
  • De q \wedge r aplico eliminação da conjunção para obter r e também q.
  • Com r e q em mãos, aplico introdução da conjunção para formar r \wedge q.
  • Concluímos que, sob a suposição q, consegue-se r \wedge q.
Resumo do caso 2 em forma de passos curtos:
  • q (suposição)
  • de q e q \rightarrow s segue s ( \rightarrow-E)
  • de s e s \rightarrow (q \wedge r) segue q \wedge r ( \rightarrow-E)
  • de q \wedge r segue r e q ( \wedge-E)
  • de r e q segue r \wedge q ( \wedge-I)
  • portanto, r \wedge q (sob a hipótese q).

Passo 5

Aplicação da eliminação da disjunção ( \vee-E) para juntar os casos:
  • Temos p \vee q como premissa.
  • Mostramos que a partir de p se obtém r \wedge q (Passo 3).
  • Mostramos que a partir de q se obtém r \wedge q (Passo 4).
  • Pela regra \vee-E: de p \vee q, se p implica r \wedge q e q implica r \wedge q, então podemos concluir r \wedge q sem depender das suposições p ou q.
  • Logo, a partir das quatro premissas iniciais obtém-se r \wedge q.

Passo 6

Conclusão final da prova e comentários didáticos:
  • A ideia central foi a prova por casos (disjunção p \vee q). Em cada ramo (assumindo p ou assumindo q) usamos modus ponens duas vezes: primeiro para chegar a s (usando p \rightarrow s ou q \rightarrow s), e depois para obter q \wedge r a partir de s e da premissa s \rightarrow (q \wedge r).
  • Depois transformamos q \wedge r em r \wedge q por eliminação e reintrodução da conjunção (pegar os componentes e re-formar a conjunção na ordem desejada).
  • Assim a conclusão r \wedge q é obtida de forma correta e as suposições locais ( p e q) são descartadas ao aplicar \vee-E, ficando apenas as premissas originais.

Resposta

r \wedge q

Exercícios relacionados