Frankl, My Dear : 3

Posted on September 17, 2014 by

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

Here’s a few pages on differential logic, whose ideas I’ll be trying out in the present setting:

I next need to look at the following “key lemma” from (2) and see if I can wrap my head, or at least my own formalism, around what it says.

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}|}.

This may take a while …

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 : 3

  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:

Gravatar
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 )

Cancel

Connecting to %s

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