After comparing conditional forms of quantified implications, we now collect general logical laws for quantified statements. These laws explain when quantifiers distribute over connectives and when they do not. Some forms are equivalences, while others are only one-way implications. In this lesson, logical laws for quantified statements will be tested through formulas, proof, and counterexamples. :::theorem[Existential Quantifier over Conjunction] For predicates $p(x)$ and $q(x)$, $$\begin{equation*} \exists x[p(x)\land q(x)]\to[(\exists x\,p(x))\land(\exists x\,q(x))] \end{equation*}$$ is true. The converse is not always true. ::: :::proof Given that $p(x)$ and $q(x)$ are predicates over the same universe. To prove that $\exists x[p(x)\land q(x)]\to[(\exists x\,p(x))\land(\exists x\,q(x))]$. Suppose $\exists x[p(x)\land q(x)]$ is true. Then there exists an element $a$ such that both $p(a)$ and $q(a)$ are true. Therefore $\exists x\,p(x)$ is true, and $\exists x\,q(x)$ is true. Hence $(\exists x\,p(x))\land(\exists x\,q(x))$ is true. $\square$ ::: :::example[Existential Quantifier Does Not Distribute over Conjunction] Let the universe be the set of all integers. Let $r(x):2x+1=5$ and $s(x):x^2=9$. The statement $\exists x[r(x)\land s(x)]$ is false. The equation $2x+1=5$ gives $x=2$, but $2^2\neq 9$. The equation $x^2=9$ gives $x=3$ or $x=-3$, but neither satisfies $2x+1=5$. However, $\exists x\,r(x)$ is true and $\exists x\,s(x)$ is true. Hence $\exists x[r(x)\land s(x)]$ is not logically equivalent to $(\exists x\,r(x))\land(\exists x\,s(x))$. ::: Quantifier distribution laws compare a quantified compound statement with a compound statement built from separate quantifiers. Choose finite truth sets for two predicates over the same universe. The test bench evaluates both sides of each law and shows which pairs agree for the chosen data. This makes the failed converses visible, because two different witnesses can make separate existential statements true without making the conjunction true at one shared element. :::scientific-preview[Quantifier Law Test Bench] ::: :::theorem[Existential Quantifier over Disjunction] For predicates $p(x)$ and $q(x)$, $$\begin{equation*} \exists x[p(x)\lor q(x)]\leftrightarrow[(\exists x\,p(x))\lor(\exists x\,q(x))]. \end{equation*}$$ ::: :::proof Given that $p(x)$ and $q(x)$ are predicates over the same universe. To prove that $\exists x[p(x)\lor q(x)]\leftrightarrow[(\exists x\,p(x))\lor(\exists x\,q(x))]$. Suppose $\exists x[p(x)\lor q(x)]$ is true. Then there exists an element $a$ such that $p(a)\lor q(a)$ is true. Therefore either $p(a)$ is true or $q(a)$ is true. Thus $\exists x\,p(x)$ is true or $\exists x\,q(x)$ is true. Conversely, suppose $(\exists x\,p(x))\lor(\exists x\,q(x))$ is true. Then either there exists an element satisfying $p(x)$, or there exists an element satisfying $q(x)$. In either case, there exists an element satisfying $p(x)\lor q(x)$. Hence the equivalence is true. $\square$ ::: :::theorem[Universal Quantifier over Conjunction] For predicates $p(x)$ and $q(x)$, $$\begin{equation*} \forall x[p(x)\land q(x)]\leftrightarrow[(\forall x\,p(x))\land(\forall x\,q(x))]. \end{equation*}$$ ::: :::proof Given that $p(x)$ and $q(x)$ are predicates over the same universe. To prove the stated equivalence. The statement $\forall x[p(x)\land q(x)]$ means that every element satisfies both $p(x)$ and $q(x)$. This happens exactly when every element satisfies $p(x)$ and every element satisfies $q(x)$. Therefore $\forall x[p(x)\land q(x)]$ is equivalent to $(\forall x\,p(x))\land(\forall x\,q(x))$. Hence the equivalence holds. $\square$ ::: :::theorem[Universal Quantifier over Disjunction] For predicates $p(x)$ and $q(x)$, $$\begin{equation*} [(\forall x\,p(x))\lor(\forall x\,q(x))]\to\forall x[p(x)\lor q(x)] \end{equation*}$$ is true. The converse is not always true. ::: :::proof Given that $p(x)$ and $q(x)$ are predicates over the same universe. To prove that $[(\forall x\,p(x))\lor(\forall x\,q(x))]\to\forall x[p(x)\lor q(x)]$. Suppose $(\forall x\,p(x))\lor(\forall x\,q(x))$ is true. If $\forall x\,p(x)$ is true, then for every element $a$, $p(a)$ is true, so $p(a)\lor q(a)$ is true. If $\forall x\,q(x)$ is true, then for every element $a$, $q(a)$ is true, so $p(a)\lor q(a)$ is true. Therefore, in either case, $\forall x[p(x)\lor q(x)]$ is true. Hence the implication holds. $\square$ ::: :::definition[Standard Quantified Equivalences] For predicates $p(x)$, $q(x)$, and $r(x)$ over the same universe, the following equivalences hold: $$\begin{align*} \forall x[p(x)\land(q(x)\land r(x))]&\leftrightarrow\forall x[(p(x)\land q(x))\land r(x)],\\ \exists x[p(x)\to q(x)]&\leftrightarrow\exists x[\neg p(x)\lor q(x)],\\ \forall x\,\neg\neg p(x)&\leftrightarrow\forall x\,p(x),\\ \exists x\,\neg\neg p(x)&\leftrightarrow\exists x\,p(x). \end{align*}$$ ::: :::definition[De Morgan Laws under Quantifiers] For predicates $p(x)$ and $q(x)$, $$\begin{align*} \forall x\neg[p(x)\land q(x)]&\leftrightarrow\forall x[\neg p(x)\lor\neg q(x)],\\ \forall x\neg[p(x)\lor q(x)]&\leftrightarrow\forall x[\neg p(x)\land\neg q(x)],\\ \exists x\neg[p(x)\land q(x)]&\leftrightarrow\exists x[\neg p(x)\lor\neg q(x)],\\ \exists x\neg[p(x)\lor q(x)]&\leftrightarrow\exists x[\neg p(x)\land\neg q(x)]. \end{align*}$$ ::: :::exercise Determine whether each pair is logically equivalent or only related by one-way implication: $\exists x[p(x)\land q(x)]$ and $(\exists x\,p(x))\land(\exists x\,q(x))$; $\exists x[p(x)\lor q(x)]$ and $(\exists x\,p(x))\lor(\exists x\,q(x))$; $\forall x[p(x)\land q(x)]$ and $(\forall x\,p(x))\land(\forall x\,q(x))$; $\forall x[p(x)\lor q(x)]$ and $(\forall x\,p(x))\lor(\forall x\,q(x))$. ::: :::answer The first pair has only the implication from the single existential conjunction to the conjunction of existentials. The second pair is logically equivalent. The third pair is logically equivalent. The fourth pair has only the implication from $(\forall x\,p(x))\lor(\forall x\,q(x))$ to $\forall x[p(x)\lor q(x)]$. ::: :::faq[Frequently Asked Questions] Q: Does $\exists$ distribute over $\land$? A: Not as an equivalence. One element must satisfy both predicates. Q: Does $\exists$ distribute over $\lor$? A: Yes. An element satisfying either predicate gives the existential disjunction. Q: Does $\forall$ distribute over $\land$? A: Yes. Every element satisfying both is the same as every element satisfying each separately. ::: :::call-to-action[Apply Quantifier Laws] subtitle: Practise distinguishing equivalence from implication before negating quantified statements. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/negation-of-quantified-statements button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/converse-inverse-and-contrapositive-of-quantified-implications :::