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$.

  • 0
    I was thinking could I just do a simple statement such as P(x) AND !P(x) thus saying that at least one has to be true and false?2012-07-05
  • 0
    Nothing can ever be both true *and* false.2012-07-05
  • 0
    Sorry I was thinking of all 5 elements in the domain as a group. (P(−2)∨P(−1)∨P(0)∨P(1)∨P(2))∧¬(P(−2)∨P(−1)∨P(0)∨P(1)∨P(2))2012-07-05
  • 1
    Nothing, including your big disjunction $(P(−2)∨P(−1)∨P(0)∨P(1)∨P(2))$, can ever be both true *and* false.2012-07-05
  • 0
    Sorry I forgot to change the signs on the negation to be ands (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?2012-07-05
  • 1
    What you just said is correct. But that is not what $\lnot\forall x.P(x)$ means. $\lnot\forall x.P(x)$ says that they are *not all* true. It does not say that any of them *are* true. For example, not all cows are purple.2012-07-05
  • 0
    Oh I was always thinking that one of them had to be true. So really the simple answer is ¬(P(−2)∧P(−1)∧P(0)∧P(1)∧P(2)). As long as they are not all true it is true.2012-07-05
  • 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 ;-)