1.5 Quantifiers & Predicate Logic | 1.5 Quantifiers & Predicate Logic | Unit 1: Proofs | Mathematics for Computer Science | Electrical Engineering and Computer Science

Predicate Logic

Which of the following are valid?

\(\exists x\exists y. P(x, y) \text{ IMPLIES } \exists y\exists x. P(x, y)\)

\(\forall x\exists y. Q(x, y) \text{ IMPLIES } \exists y\forall x. Q(x, y)\)

\(\exists x\forall y. R(x, y) \text{ IMPLIES } \forall y\exists x. R(x, y)\)

\(\text{NOT}[\exists x. S(x)] \text{ IFF } \forall x. \text{NOT}[S(x)]\)

Quantifiers of the same type (existential or universal) can be reordered without altering the meaning of the statement.
For example, let \(Q(x, y)\) be (\(y > x)\) and suppose the domain is nonnegative integers. Then the left side asserts that for every nonnegative integer, there is a larger nonnegative integer, which is true. The right side asserts that there exists a nonnegative integer greater than every other nonnegative integer, which is false. Therefore, the implication as a whole is false, and the statement is not valid.
Suppose that the left side is true. Then there exists an \(x_0\) such that for all \(y\), \(R(x_0\), \(y)\) is true. Thus, for all \(y\), there exists an \(x\) (namely, \(x_0\)) such that \(R(x, y)\) is true. Therefore, the right side is also true, and the statement is valid.
If it's not true that there is an element in the domain with property \(S\), then every element in the domain must not have property \(S\). Conversely, if every element in the domain does not have property \(S\), it can't be true that some element in the domain has property \(S\).