## Frankl, My Dear • 4

Let’s go back to the “key lemma” from (2) and try it out on a simple example, just to get a sense of what the terms mean.

Lemma.  Let $f(x_{1}, \dots, x_{n})$ be a Boolean function and let $x_{i}$ be fixed.  Then the Boolean inputs can be partitioned into six sets:

$\displaystyle A_{0}, A_{1}, B_{0}, B_{1}, C_{0}, C_{1}.$

These sets have the following properties:

1. The variable ${x_{i}}$ is equal to ${0}$ on ${A_{0} \cup B_{0} \cup C_{0}}.$
2. The variable ${x_{i}}$ is equal to ${1}$ on ${A_{1} \cup B_{1} \cup C_{1}}.$
3. The union ${A_{0} \cup A_{1}}$ is equal to ${J_{i}}.$
4. The function is always ${0}$ on ${B_{0} \cup B_{1}}.$
5. The function is always ${1}$ on ${C_{0} \cup C_{1}}.$
6. Finally ${|A_{0}| = |A_{1}|}$  and  ${|B_{0}| = |B_{1}|}$  and  ${|C_{0}| = |C_{1}|}.$

### Example 1

 (1)

Consider the boolean function ${f(x_1, x_2, x_3) = f(p, q, r) = pqr}$ pictured in Figure 1 and fix on the variable ${x_1 = p}.$

The lemma says that the boolean inputs can be partitioned into six sets:

$\displaystyle A_{0}, A_{1}, B_{0}, B_{1}, C_{0}, C_{1}.$

Let’s identify those six sets in the present example.

Back in a flash … in the meantime, exercise for the reader …

Later that day …

I had trouble with the term “Boolean input” in (2).  Sometimes people use it to mean one of the input wires to a logic gate, that is, one of the variables $x_i.$  Other times people use it to mean one of the coordinate elements $x \in \mathbb{B}^n.$  It’s always possible that I’m reading things wrong but it looks like the first sense is used to define the “influence” $I_{i}(f)$ and the related set $J_{i}(f)$ while the second sense is used to define the six sets of the Lemma.  At any rate, I will go with those two senses for now.

On that reading, the six sets named in the Lemma are shown in Figure 2.

 (2)

In other words:

$\begin{matrix} A_0 & = & \{ 011 \} & = & \tilde{p} q r \\ A_1 & = & \{ 111 \} & = & p q r \\ B_0 & = & \{ 000, 001, 010 \} & = & \tilde{p} \tilde{q} \tilde{r} \lor \tilde{p} \tilde{q} r \lor \tilde{p} q \tilde{r} \\ B_1 & = & \{ 100, 101, 110 \} & = & p \tilde{q} \tilde{r} \lor p \tilde{q} r \lor p q \tilde{r} \\ C_0 & = & \varnothing & = & 0 \\ C_1 & = & \varnothing & = & 0 \end{matrix}$

Resources.  A few pages on differential logic, which may or may not be useful here.

### 6 Responses to Frankl, My Dear • 4

This site uses Akismet to reduce spam. Learn how your comment data is processed.