TAOCP 7.1.1 Exercise 56
Let $f(x,y,z)=(x\lor y)\land(x\lor z)\land(y\lor z).$ First simplify several specializations of $f$.
Exercise 56. ▶ [20] [20] The satisfiability problem for a Boolean function $f(x_1, x_2, \ldots, x_n)$ can be stated formally as the question of whether or not the quantified formula
$$\exists x_1 ; \exists x_2 ; \ldots ; \exists x_n ; f(x_1, x_2, \ldots, x_n)$$
is true; here "$\exists x_i , \alpha$" means, "there exists a Boolean value $x_i$ such that $\alpha$ holds."
A much more general evaluation problem arises when we replace one or more of the existential quantifiers $\exists x_j$ by the universal quantifier $\forall x_j$, where "$\forall x_j , \alpha$" means "for all Boolean values $x_j$, $\alpha$ holds."
Which of the eight quantified formulas $\exists x ; \exists y ; \exists z ; f(x, y, z)$, $\exists x ; \exists y ; \forall z ; f(x, y, z)$, ..., $\forall x ; \forall y ; \forall z ; f(x, y, z)$ are true when $f(x, y, z) = (x \lor y) \land (x \lor z) \land (y \lor z)$?
Verified: yes
Solve time: 1m20s
Solution
Let
$f(x,y,z)=(x\lor y)\land(x\lor z)\land(y\lor z).$
First simplify several specializations of $f$.
If $z=0$, then
$f(x,y,0)=(x\lor y)\land x \land y = x\land y.$
If $x=1$, then
$f(1,y,z)=(1\lor y)\land(1\lor z)\land(y\lor z)=y\lor z.$
If $x=0$, then
$f(0,y,z)=(0\lor y)\land(0\lor z)\land(y\lor z)=y\land z.$
Thus $f(x,y,z)=1$ exactly when at least two of $x,y,z$ are $1$.
The eight quantified formulas are evaluated in order.
For $\exists x,\exists y,\exists z, f(x,y,z)$, the assignment $x=1,y=1,z=0$ gives
$f(1,1,0)=(1\lor1)\land(1\lor0)\land(1\lor0)=1,$
so the formula is true.
For $\exists x,\exists y,\forall z, f(x,y,z)$, choose $x=1,y=1$. Then
$f(1,1,0)=1,\qquad f(1,1,1)=1,$
so $\forall z, f(1,1,z)$ holds, and the formula is true.
For $\exists x,\forall y,\exists z, f(x,y,z)$, take $x=1$. Then $f(1,y,z)=y\lor z$. For each $y$, choosing $z=1$ yields $y\lor z=1$, so $\exists z, f(1,y,z)$ holds for every $y$. Hence the formula is true.
For $\exists x,\forall y,\forall z, f(x,y,z)$, consider $x=1$. Then $f(1,0,0)=0$, so $\forall y,\forall z, f(1,y,z)$ fails. For $x=0$, $f(0,1,1)=1$ but $f(0,0,0)=0$, so $\forall y,\forall z, f(0,y,z)$ also fails. No choice of $x$ satisfies the condition, so the formula is false.
For $\forall x,\exists y,\exists z, f(x,y,z)$, if $x=0$ then $f(0,y,z)=y\land z$, and $y=z=1$ gives $f(0,1,1)=1$. If $x=1$ then $f(1,y,z)=y\lor z$, and $y=1,z=0$ gives $f(1,1,0)=1$. Thus the formula is true.
For $\forall x,\exists y,\forall z, f(x,y,z)$, take $x=0$. Then $f(0,y,z)=y\land z$. For any fixed $y$, $f(0,y,0)=0$, so no choice of $y$ makes $\forall z, f(0,y,z)$ hold. Hence the universal condition over $x$ fails, and the formula is false.
For $\forall x,\forall y,\exists z, f(x,y,z)$, take $x=0,y=0$. Then $f(0,0,z)=0$ for both $z=0$ and $z=1$, so no $z$ satisfies $f(0,0,z)=1$. Hence the formula is false.
For $\forall x,\forall y,\forall z, f(x,y,z)$, the assignment $x=0,y=0,z=0$ yields $f(0,0,0)=0$, so the formula is false.
The truth values, in order, are:
$\text{T, T, T, F, T, F, F, F}.$
This completes the solution. ∎