1
$\begingroup$

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$

I need to translate this into conjunctive normal form. So the first thing I do is eliminate the $\rightarrow$:

$$\forall x [\neg \exists z Have(x,cat(z))] \vee \forall y[\neg Have(x,mouse(y))]$$

Then we apply the negation:

$$\forall x[\forall z \neg Have(x,cat(z))] \vee \forall y[\neg Have(x,mouse(y))]$$

Then apply the Skolem function & drop universal quantifiers (?):

$$\neg Have(x,F(x)) \vee \neg Have(x, G(y))$$

So this last sentence is in conjunctive normal form, but I'm not sure if it means the same thing as the original sentence. The last sentence may read as "$x$ has a cat or $x$ has a mouse." Is this the same thing as "Anyone who has cats as pets will not have mice?" Are my steps correct?

$\endgroup$
5
  • $\begingroup$ The $\exists y \neg Have(x,mouse(y))$ is translated as there is a mouse you don't have, not that you don't have a mouse. You need the negation on the outside, or a universal quantifier. $\endgroup$
    – James
    Commented Oct 21, 2014 at 0:19
  • $\begingroup$ @James Thank you. I fixed that. Is the resulting reduction correct now? $\endgroup$
    – Jenn Parker
    Commented Oct 21, 2014 at 0:25
  • $\begingroup$ No, there are still problems. In the first step, you have introduced a negation in front of the $\forall x$ and after it. There should only be one negation. I presume that the $\forall x$ is supposed to have widest scope, even though this isn't consistent with your brackets. Hence you need to drop the $\neg$ out front. $\endgroup$
    – James
    Commented Oct 21, 2014 at 1:32
  • $\begingroup$ Also, a less pressing, but still strange thing, is that you are using $cat(z)$ and $mouse(y)$ as functions, even though it would be more conventional to have relations representing the property of being a cat, and a mouse, respectively. $\endgroup$
    – James
    Commented Oct 21, 2014 at 1:34
  • $\begingroup$ @James I have tried to correct my mistakes. Does this look good now? $\endgroup$
    – Jenn Parker
    Commented Oct 21, 2014 at 1:37

1 Answer 1

Reset to default
1
$\begingroup$

Ok, I decided to convert the comments into an answer. The sentence in English is "Anyone who has cats as pets will not have mice". This naturally translates as $$\forall x (\exists y(Cat(y) \land Have(x,y))\rightarrow \neg \exists z (Mouse(z) \land Have(x,z)))$$ remove $\rightarrow$

$$\forall x (\neg\exists y(Cat(y) \land Have(x,y))\lor \neg \exists z (Mouse(z) \land Have(x,z)))$$

move negations in

$$\forall x (\forall y(\neg Cat(y) \lor \neg Have(x,y))\lor \forall z (\neg Mouse(z) \lor \neg Have(x,z)))$$

Pull out quantifiers

$$\forall x,y,z (\neg Cat(y) \lor \neg Have(x,y) \lor \neg Mouse(z) \lor \neg Have(x,z))$$

Skolem function things (trivial step as there are no existentials). Drop universals

$$\neg Cat(y) \lor \neg Have(x,y) \lor \neg Mouse(z) \lor \neg Have(x,z)$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .