Questão 2 (2 pts.). Sejam:
  • \Gamma=\{\neg(p \wedge \neg q), q \vee r\} e
  • \varphi=p \rightarrow r.
    Determine se \Gamma \vDash \varphi e justifique a resposta.

Passo 1

O enunciado dá as fórmulas e pede para decidir se a consequência semântica vale. As informações são:
  • Conjunto de premissas \Gamma = \{\neg(p \wedge \neg q),\; q \vee r\}.
  • Fórmula a verificar \varphi = p \rightarrow r.
A pergunta é: vale \Gamma \vDash \varphi? Ou seja, toda valuation que torna todas as fórmulas de \Gamma verdadeiras também torna \varphi verdadeira?

Passo 2

Vamos lembrar o que significa \Gamma \vDash \varphi. Por definição:
\Gamma \vDash \varphi
se, e somente se, para toda valuation v (atribuição de verdade a p,q,r), se v(\psi)=\text{V} para todo \psi\in\Gamma então também v(\varphi)=\text{V}.
Para refutar \Gamma \vDash \varphi basta apresentar uma valuation v tal que todas as fórmulas de \Gamma sejam verdadeiras em v e \varphi seja falsa em v. Esse v é um contraexemplo semântico.

Passo 3

É útil transformar as fórmulas em formas equivalentes mais simples (isso ajuda a raciocinar). Aplicando equivalências conhecidas:
\neg(p\wedge\neg q)\equiv \neg p \vee q
essa equivalência vem da Lei de De Morgan e da dupla negação. Também
p\rightarrow r \equiv \neg p \vee r,
que é a definição material da implicação. Assim podemos reescrever:
\Gamma=\{\neg p \vee q,\; q \vee r\},\qquad \varphi\equiv \neg p \vee r.

Passo 4

Para que \varphi seja falsa (isto é, para que p\rightarrow r seja falsa) precisamos que a disjunção \neg p \vee r seja falsa. Uma disjunção só é falsa quando ambos os disjuntos são falsos, logo:
\varphi\\ \text{é falsa} \iff \neg p = \text{F e } r=\text{F} \iff p=\text{V e } r=\text{F}.é
Portanto, qualquer contraexemplo terá de satisfazer p=\text{V} e r=\text{F}.

Passo 5

Com p=\text{V} e r=\text{F} vamos ver o que as premissas exigem. Primeiro, avalie \neg(p\wedge\neg q) quando p=\text{V}:
p\wedge\neg q = \text{V}\wedge\neg q = \neg q,
portanto
\neg(p\wedge\neg q)=\neg(\neg q)=q.
Ou seja, quando p=\text{V}, a primeira premissa vale exatamente q.

Passo 6

A segunda premissa é q\vee r. Com r=\text{F} ela se reduz a q\vee\text{F}=q. Assim, sob a condição p=\text{V}, r=\text{F}, as duas premissas exigem ambas que q=\text{V} para serem verdadeiras.

Passo 7

Portanto, escolha a valuation v definida por
v(p)=\text{V},\qquad v(q)=\text{V},\qquad v(r)=\text{F}.
Agora avaliamos cada fórmula em v.

Passo 8

Avaliação explícita em v:
  • Primeiro premissa: \neg(p\wedge\neg q). Com p=\text{V}, q=\text{V},
p\wedge\neg q = \text{V}\wedge\neg\text{V}=\text{V}\wedge\text{F}=\text{F},
então
\neg(p\wedge\neg q)=\neg\text{F}=\text{V}.
  • Segunda premissa: q\vee r = \text{V}\vee\text{F}=\text{V}.
  • Conclusão: \varphi = p\rightarrow r. Com p=\text{V}, r=\text{F},
p\rightarrow r = \text{V}\rightarrow\text{F}=\text{F}.
Logo em v ambas as fórmulas de \Gamma são verdadeiras e \varphi é falsa.

Passo 9

Tendo encontrado uma valuation v que torna todas as premissas verdadeiras e a conclusão falsa, concluímos que não é verdade que toda valuation que satisfaz \Gamma também satisfaz \varphi. Portanto \Gamma não semanticalmente implica \varphi.

Resposta

Não, \Gamma \nvDash \varphi.

Exercícios relacionados