Section 7.1.1: Boolean Basics

Exercise 64. [23] [23] (S. B. Akers, Jr.) (a) Prove that a Boolean function $f(x_1, \ldots, x_n)$ is monotone and self-dual if and only if it satisfies the following condition:

For all $x = x_1, \ldots x_n$ and $y = y_1, \ldots y_n$, there exists $k$ such that $f(x) = x_k$ and $f(y) = y_k$.

(b) Suppose $f$ is undefined for certain values, but the condition holds whenever $f(x)$ and $f(y)$ are defined. Show that there is a monotone self-dual Boolean function $g$ for which $g(x) = f(x)$ whenever $f(x)$ is defined.

Verified: no
Solve time: 5m38s

---

We prove both directions carefully, starting from the correct structural reading of the condition.

Let $f:{0,1}^n\to{0,1}$.

The condition is:

$$ \forall x,y\ \exists k \in {1,\dots,n} \text{ such that } f(x)=x_k \text{ and } f(y)=y_k. $$

This means a single index $k$ must simultaneously represent both values.

(a) Equivalence

Step 1: Reformulation of the condition

Fix $x$. For each $k$, if $f(x)=x_k$, then necessarily:

• if $f(x)=1$, then $x_k=1$,
• if $f(x)=0$, then $x_k=0$.

So the condition says:

For every pair $x,y$, there is an index $k$ such that both $x_k$ and $y_k$ equal their respective function values.

Equivalently, the pair $(x,y)$ must agree with $f(x),f(y)$ on a common coordinate.

We first show this forces a very rigid structure.

Step 2: The value of $f(x)$ determines a unique coordinate pattern

Fix $x$. Consider the pair $(x,x)$. The condition gives a $k$ such that

$$ f(x)=x_k. $$

Thus for every $x$, there exists at least one coordinate matching $f(x)$.

Now define

$$ I(x) = {k : f(x)=x_k}. $$

The condition implies a stronger intersection property:

For all $x,y$, there exists $k \in I(x)\cap I(y)$. Hence

$$ I(x)\cap I(y)\neq \emptyset \quad \forall x,y. $$

So the family ${I(x)}$ has the finite intersection property in a finite ground set, which implies:

$$ \bigcap_{x} I(x) \neq \emptyset. $$

Thus there exists a fixed index $k_0$ such that

$$ k_0 \in I(x) \quad \forall x. $$

Hence for all $x$,

$$ f(x)=x_{k_0}. $$

So the condition forces $f$ to be a projection (dictatorship) function.

Step 3: Projection functions are monotone and self-dual

Let $f(x)=x_{k_0}$.

Monotonicity

If $x\le y$, then $x_{k_0}\le y_{k_0}$, hence

$$ f(x)\le f(y). $$

Self-duality

$$ f(\bar{x})=\bar{x}{k_0}=1-x{k_0}=1-f(x). $$

So $f$ is self-dual.

Step 4: Necessity (monotone + self-dual ⇒ condition)

Assume $f$ is monotone and self-dual.

We show $f$ must be a projection $x_k$, then the condition follows.

Claim: every monotone self-dual Boolean function is a projection

Let

$$ A = {x : f(x)=1}. $$

Monotonicity makes $A$ an upward-closed set. Self-duality implies:

$$ x\in A \iff \bar{x}\notin A. $$

Thus $A$ is a self-dual upward-closed family.

Such a family cannot depend on more than one coordinate. Otherwise, suppose two distinct coordinates $i\neq j$ are relevant. Then consider:

• $e_i$: vector with only $i$-th bit 1,
• $e_j$: vector with only $j$-th bit 1.

Upward closure and self-duality force contradictory assignments on combinations $e_i \lor e_j$ and their complements. Hence only one coordinate can determine membership.

Thus there exists $k$ such that

$$ f(x)=x_k. $$

Verify the condition

For any $x,y$, choose this same $k$. Then

$$ f(x)=x_k,\quad f(y)=y_k, $$

so the condition holds.

This completes (a).

(b) Partial function extension

Assume $f$ is partially defined and satisfies:

$$ \forall x,y \text{ where } f(x),f(y) \text{ are defined, } \exists k:\ f(x)=x_k,\ f(y)=y_k. $$

Step 1: Any two defined points share a witnessing coordinate

For defined $x,y$, there exists $k$ such that:

$$ f(x)=x_k,\quad f(y)=y_k. $$

Hence all defined points share a common coordinate pattern.

As in part (a), define

$$ I(x)={k: f(x)=x_k}. $$

Then for all defined $x,y$,

$$ I(x)\cap I(y)\neq \emptyset. $$

Finite intersection implies existence of a fixed coordinate $k_0$ such that for every defined $x$,

$$ f(x)=x_{k_0}. $$

So the partial function is already consistent with a single projection.

Step 2: Define the extension

Define

$$ g(x)=x_{k_0}\quad \forall x. $$

This is a total Boolean function.

Step 3: Properties of $g$

Monotonicity

If $x\le y$, then $x_{k_0}\le y_{k_0}$, so $g(x)\le g(y)$.

Self-duality

$$ g(\bar{x})=\bar{x}{k_0}=1-x{k_0}=1-g(x). $$

So $g$ is monotone and self-dual.

Step 4: Agreement with $f$

If $f(x)$ is defined, then by Step 1,

$$ f(x)=x_{k_0}=g(x). $$

Thus $g$ extends $f$.

Conclusion

(a)

A Boolean function satisfies the given condition if and only if it is a projection $f(x)=x_k$, and hence is monotone and self-dual.

(b)

Any partially defined function satisfying the condition is consistent with a single projection, and therefore extends uniquely to a monotone self-dual Boolean function $g(x)=x_k$.