My question is this, for the following sentence: Every pet has an owner , when translated into predicate logic gives $\forall x\enspace(P(x) \rightarrow O(x))$, but what is the equivalent with a $\exists x$ instead of $\forall x$? Is there a general rule when changing between the two?
Asked
Active
Viewed 1,973 times
1
-
I don't know what $P$ and $O$ stand for, but taking the natural interpretation, your statement says that every pet is an owner, which isn't what you want. – Git Gud Jun 03 '15 at 13:23
-
for all $x$ $P(x)$ is the same as not not for all $x$ $P(x)$, which is the same as not there exists x such that not $P(x)$. – Gerry Myerson Jun 03 '15 at 13:39
-
OK, if $O(x)$ means '$x$ has an owner', it's fine. – Git Gud Jun 03 '15 at 13:41
2 Answers
1
The negation of a universal statement is an existential statement: $\lnot \forall x A \equiv \exists x \neg A$.
Thus, in your case this would be: $$ \forall x ( P(x)\to O(x))\equiv \lnot (\exists x\lnot (P(x)\to O(x))) \equiv \lnot (\exists x(P(x)\land \neg O(x)))\,. $$
Dilworth
- 179
0
Hint: Negate the negation of $\forall x . P(x) \Longrightarrow O(x)$, where:
$P(x)$ means x is a pet;
$O(x)$ means x has an owner.
anak
- 1,164
-
so it would be simply be ∃x(-P(x)⟹-O(x)) where - is a negation? Does the implication remain when negating it? – user4357505 Jun 03 '15 at 14:05
-
To negate $\forall x . P(x) \Longrightarrow O(x)$, first place a negation symbol in front of it all. Perhaps it would be best to read up on negating predicate and propositional phrases. I can lead you through it, but that wouldn't be fair to you. – anak Jun 03 '15 at 14:07
-
-
$\neg [\forall x . P(x) \Longrightarrow O(x)] \equiv \exists . \neg[P(x) \Longrightarrow O(x)]$. – anak Jun 03 '15 at 14:11
-
-
Yes. Now. since we know that for any proposition $Z(x)$ that $\neg \neg Z(x) \equiv Z(x)$, then you can place a negation symbol in front of $\exists x . P(x) \wedge \neg O(x)$ to get the original phrase you came up with. – anak Jun 03 '15 at 14:18