TAOCP 7.1.4 Exercise 89

Let $f$ be a Boolean function of variables $x_1, x_2$, taking values in ${\bot,\top}$, with the usual ordering $\bot < \top$.

taocpmathematicsalgorithmsvolume-4simple

Section 7.1.4: Binary Decision Diagrams

Exercise 89. [15] [15] Are the following quantified formulas true or false? (a) ∃x1∃x2f = ∃x2∃x1f. (b) ∀x1∀x2f = ∀x2∀x1f. (c) ∀x1∃x2f ≤∃x2∀x1f. (d) ∀x1∃x2f ≥∃x2∀x1f.

Verified: no
Solve time: 5m01s

Solution

Let $f$ be a Boolean function of variables $x_1, x_2$, taking values in ${\bot,\top}$, with the usual ordering $\bot < \top$. All quantified expressions are interpreted pointwise over Boolean values, and equality means equality of the resulting Boolean function.

(a) $\exists x_1 \exists x_2 f = \exists x_2 \exists x_1 f$

For any fixed assignment of the remaining variables (if any), the expression $\exists x_1 \exists x_2 f$ evaluates to $\top$ exactly when there exists a choice of $(x_1,x_2)$ such that $f=\top$. The order of existential quantification does not change the existence of a witness pair, since

$$ {(x_1,x_2)} = {(x_2,x_1)} $$

as sets of all Boolean assignments, up to renaming of coordinates.

Formally, if $\exists x_1 \exists x_2 f=\top$, then there exist values $a,b \in {\bot,\top}$ such that $f(x_1=a,x_2=b)=\top$. Then $\exists x_2 \exists x_1 f=\top$ by choosing $x_2=b$ first and $x_1=a$ second. The reverse implication is identical. Hence the two functions agree at every assignment.

Thus (a) is true.

(b) $\forall x_1 \forall x_2 f = \forall x_2 \forall x_1 f$

The expression $\forall x_1 \forall x_2 f$ evaluates to $\top$ exactly when $f(x_1,x_2)=\top$ for all four Boolean pairs $(x_1,x_2)$. The order of universal quantifiers does not change the set of assignments being tested, since both expressions require verification of all pairs.

Formally, $\forall x_1 \forall x_2 f=\top$ if and only if for all $a,b \in {\bot,\top}$ we have $f(a,b)=\top$. The same condition defines $\forall x_2 \forall x_1 f$. Therefore the two expressions are identical as Boolean functions.

Thus (b) is true.

(c) $\forall x_1 \exists x_2 f \le \exists x_2 \forall x_1 f$

The inequality $g \le h$ means that whenever $g=\top$, also $h=\top$. The left side $\forall x_1 \exists x_2 f$ asserts that for each $x_1 \in {\bot,\top}$ there exists a possibly different $x_2$ such that $f(x_1,x_2)=\top$.

The right side $\exists x_2 \forall x_1 f$ asserts the existence of a single value $x_2$ such that for both $x_1=\bot$ and $x_1=\top$, the value $f(x_1,x_2)=\top$ holds.

A counterexample suffices to refute the implication. Define $f$ by its truth table

$$ f(\bot,\bot)=\top,\quad f(\bot,\top)=\bot,\quad f(\top,\bot)=\bot,\quad f(\top,\top)=\top. $$

For $x_1=\bot$, choosing $x_2=\bot$ gives $\top$, and for $x_1=\top$, choosing $x_2=\top$ gives $\top$, hence $\forall x_1 \exists x_2 f=\top$.

For $\exists x_2 \forall x_1 f$, test $x_2=\bot$: then $f(\top,\bot)=\bot$, so failure. Test $x_2=\top$: then $f(\bot,\top)=\bot$, so failure. Hence $\exists x_2 \forall x_1 f=\bot$.

Therefore the inequality fails.

Thus (c) is false.

(d) $\forall x_1 \exists x_2 f \ge \exists x_2 \forall x_1 f$

The inequality reverses the direction of (c), so it asserts that whenever $\exists x_2 \forall x_1 f=\top$, then $\forall x_1 \exists x_2 f=\top$.

Assume $\exists x_2 \forall x_1 f=\top$. Then there exists $b \in {\bot,\top}$ such that for both $a \in {\bot,\top}$ we have $f(a,b)=\top$. Fixing this same $b$, for each $x_1=a$ we can choose $x_2=b$ and obtain $f(a,b)=\top$. Hence $\forall x_1 \exists x_2 f=\top$.

If $\exists x_2 \forall x_1 f=\bot$, the implication condition is vacuous since the antecedent is false.

Thus whenever the right-hand side is true, the left-hand side is true.

Therefore (d) is true.

This completes the solution. ∎