2
$\begingroup$

With a domain from -2 to 2 I'm trying to write the following using disjunctions conjunctions and nagations. I'm not sure how correct I am and wanted to know if I did them correct? Could someone help with the last one I just cant figure out how to start that expression?

$∀ x\ P(x) = P(-2) ∧ P(-1) ∧ P(0) ∧ P(1) ∧ P(2)$

\neg ∀x\ P(x) = (P(−2)∨P(−1)∨P(0)∨P(1)∨P(2))∧¬(P(−2)∧P(−1)∧P(0)∧P(1)∧P(2))
In English doesn't that mean: At least one element is true and one element is false?

∃x\ \neg P(x) = $

Edit: The last two with the correct answer of "At least one is not true".

∃x¬P(x) = ¬P(-2) ∨¬P(-1) ∨¬P(0) ∨¬P(1) ∨¬P(2)

¬∀xP(x) = ¬(P(-2) ∧ P(-1) ∧ P(0) ∧ P(1) ∧ P(2))

2 Answers 2

3

The last two should have the same answer, since the second one, $\lnot\forall x.P(x)$ says that it is not true that $P(x)$ holds for every $x$, while the third one, $\exists c.\lnot P(x)$ says that there exists an $x$ for which $P(x)$ does not hold. These mean exactly the same thing. "Not every crow is black" is the same as "There is a crow that is not black."

But your answer for the second one is not correct.

Mouse over for hint:

$\lnot\forall x.P(x)$ says that it is not true that every element of the domain satisfies $P$. But $P(-2)\lor P(-1)\lor\ldots\lor P(2)$ says that $P(x)$ is true for -2, or for -1, or…

EDIT: Now your second one is correct, if you and I have the same idea for the part you indicated by "…", but it could be much simpler.

EDIT: Now your second one is incorrect again. $\lnot\forall x.P(x)$ says that $P(x)$ is not true for every $x$. It does $not$ say that $P(x)$ is true for any $x$; it might be false for all $x$.

  • 1
    Right! ${}{}{}{}$2012-07-05
2

If the domain $\Omega$ is finite, then $\Big(\forall x\in\Omega\ \ P(x)\Big) \iff \left(\bigwedge_{x\in\Omega}P(x)\right)$ and $\Big(\exists x\in\Omega\ \ P(x)\Big) \iff \left(\bigvee_{x\in\Omega}P(x)\right)$ assuming that the alternative of zero elements is false and conjunction of zero terms is true. In old books $\bigvee$ and $\bigwedge$ denote just the regular quantifiers $\exists$ and $\forall$ respectively, here the symbols are used as big (indexed) alternative and conjunction in a fashion similar to sums $\sum$ and products $\prod$.

Also this somehow explains the De Morgan's laws for quantifiers:

$\neg \forall x\ P(x) \iff \neg \bigwedge_x P(x) \iff \bigvee_x \neg P(x) \iff \exists x\ \neg P(x),$ $\neg \exists x\ P(x) \iff \neg \bigvee_x P(x) \iff \bigwedge_x \neg P(x) \iff \forall x\ \neg P(x),$

just because $\neg\Big(P(x_1) \land P(x_2) \land P(x_3) \land \ldots\Big) \iff \Big(\neg P(x_1) \lor \neg P(x_2) \lor \neg P(x_3) \lor \ldots \Big),$ $\neg\Big(P(x_1) \lor P(x_2) \lor P(x_3) \lor \ldots\Big) \iff \Big(\neg P(x_1) \land \neg P(x_2) \land \neg P(x_3) \land \ldots \Big).$

Those are just hints, but I hope it helps ;-)