Frankl, My Dear : 4

Re: Dick Lipton & Ken Regan(1)(2)

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


Venn Diagram PQR
(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.


Venn Diagram Frankl 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.

This entry was posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl and tagged , , , , , , , , . Bookmark the permalink.

One Response to Frankl, My Dear : 4

  1. Pingback: Survey of Differential Logic • 1 | Inquiry Into Inquiry

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

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