1. Qual das seguintes fórmulas é uma tautologia?
  1. ((\mathrm{p} \rightarrow \mathrm{q}) \wedge(\mathrm{q} \rightarrow \mathrm{p})) \rightarrow \neg(\mathrm{p} \vee \mathrm{q})
  2. ((\mathrm{p} \wedge \mathrm{q}) \rightarrow \mathrm{r}) \wedge(\neg \mathrm{r})
  3. ((\mathrm{p} \rightarrow \mathrm{q}) \wedge(\mathrm{q} \rightarrow \mathrm{r})) \rightarrow(\mathrm{p} \rightarrow \mathrm{r})
  4. (\neg p \rightarrow(q \vee r)) \wedge(\neg q)

Passo 1

Resumindo o enunciado, queremos saber qual das quatro fórmulas abaixo é verdadeira para toda atribuição de valores lógicos (isto é, qual é uma tautologia):
  1. \bigl((p\rightarrow q)\wedge(q\rightarrow p)\bigr)\rightarrow \neg(p\vee q)
  2. \bigl((p\wedge q)\rightarrow r\bigr)\wedge(\neg r)
  3. \bigl((p\rightarrow q)\wedge(q\rightarrow r)\bigr)\rightarrow(p\rightarrow r)
  4. \bigl(\neg p\rightarrow(q\vee r)\bigr)\wedge(\neg q)
    O conteúdo é lógica proposicional e vamos usar a definição de tautologia (verdadeira em todas as valorações) testando contraexemplos quando possível e, no caso do candidato 3, usando raciocínio lógico para mostrar que nunca pode ser falsa.

Passo 2

Analisamos a fórmula 1 e buscamos uma valoração que a torne falsa. Para que A\rightarrow B seja falsa, precisamos de A verdadeiro e B falso. Seja p=\text{V} e q=\text{V}.
  • p\rightarrow q é V, e q\rightarrow p é V, logo o antecedente (p\rightarrow q)\wedge(q\rightarrow p) é V.
  • p\vee q é V, então \neg(p\vee q) é F.
    Portanto a implicação é F, mostrando que a fórmula 1 não é verdadeira em todas as valorações.

Passo 3

Analisamos a fórmula 2 que é uma conjunção. Basta um dos termos ser F para a conjunção falhar. Tome p=\text{V}, q=\text{V} e r=\text{V}.
  • p\wedge q é V, e daí (p\wedge q)\rightarrow r é V \rightarrowV = V.
  • \neg r é F.
    Logo V \wedgeF = F, provando que a fórmula 2 também não é tautologia.

Passo 4

Analisamos a fórmula 4. De novo, basta encontrar uma valoração que a torne F. Seja p=\text{F}, q=\text{F}, r=\text{F}.
  • \neg p é V, mas q\vee r é F, então \neg p\rightarrow(q\vee r) é V \rightarrowF = F.
  • \neg q é V.
    A conjunção F \wedgeV = F, então a fórmula 4 não é tautologia.

Passo 5

Agora a fórmula 3:
\bigl((p\rightarrow q)\wedge(q\rightarrow r)\bigr)\rightarrow(p\rightarrow r).
Para checar que isso é sempre V, fazemos uma prova por casos:
  • Se p for F, então p\rightarrow r é V de imediato (implicação com antecedente F é sempre V), logo a implicação externa é V.
  • Se p for V, então para (p\rightarrow q)\wedge(q\rightarrow r) ser V precisamos de q V (pois p\rightarrow q = V \rightarrowq só é V se q=V) e daí, para q\rightarrow r ser V precisamos de r V. Logo p V implica r V, portanto p\rightarrow r é V.
    Em ambos os casos a implicação final é V, mostrando que a fórmula 3 não pode ser falsa em nenhuma valoração, ou seja, é uma tautologia.

Resposta

  1. \bigl((p\rightarrow q)\wedge(q\rightarrow r)\bigr)\rightarrow(p\rightarrow r)

Exercícios relacionados