Demuestra que John no tiene el sueño ligero

Question

Defina cada frase en términos de CNF. Demuestra que Juan no tiene el sueño ligero.

(1): All wolves howl.
(2): Anyone who has casts as pets will not have mice.
(3): Anyone who is a light sleeper can't live near anything that howls.
(4): John either has cats or lives near wolves.
(5): If John is a light sleeper, John has mice.

$Wolf(x): x$ es un lobo

$Howl(x): x$ aullidos

$Have(x,y): x$ tiene y

$Cat(x): x$ es un gato

$Mouse(x): x$ es un ratón

$LS(x): x$ tiene un sueño ligero

$Live(x,y): x$ vive cerca de y

Empecé escribiendo cada frase en términos de cuantificadores:

(1): $\forall x(Wolf(x)\rightarrow Howl(x))$

(2): $\forall x\forall y\forall z(Have(x,Cat(y)) \rightarrow \neg Have(x,Mouse(z))$

(3): $\forall x \forall y((\neg LS(x) \wedge Howls(y)) \rightarrow \neg Live(x,y))$

(4): $\exists x, \exists y(Have(Frank,Cat(x))\vee Live(Frank,Wolf(y)))$

(5): $\exists (LS(Frank)\rightarrow Have(Frank,Mouse(x)))$

Así que mi primera pregunta es si estas oraciones con cuantificador son correctas. Mi segunda pregunta es cómo podemos llevarlas a CNF. Entiendo que algo como $x\rightarrow y$ puede convertirse en $\neg x \vee \neg y$ pero no veo cómo podemos eliminar los cuantificadores por completo. ¿Puede alguien mostrarme cómo se hace esto con una de las oraciones con cuantificador?

Answer 1

Sugerencias :

Sea P un animal y A una persona:

(1): $P$ es un lobo $\implies$ P aullido.

(2): $A$ tiene gatos como mascotas $\implies $ A no tiene ratones.

(3): $A$ tiene un sueño ligero $\implies$ $A$ no vivas cerca de nada que aúlle.

(4): John tiene gatos XOR John vive cerca de los lobos. [ este puede ser expresado como : (Juan tiene gatos Y John no vive cerca de los lobos) O (John no tiene gatos Y John vive cerca de los lobos ]

(5): John tiene el sueño ligero $\implies$ John tiene ratones.

empezar con (5) y hacer una prueba por contradicción.

Actualización :

por contradicción supongamos que Juan tiene un sueño ligero. por ( 5 ) esto implica que Juan tiene ratones. por ( 2 ) [ su Contraposición] esto implica que Juan no tiene gatos. por ( 4 ) esto implica que Juan vive cerca de los lobos. por el ( 3 ) [ su Contraposición] Y ( 1 ) : esto implica que Juan no tiene el sueño ligero ( y esta es la contradicción porque suponíamos que Juan tiene el sueño ligero)

Por lo tanto, John no tiene un sueño ligero