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.

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | Leave a comment

Character, Action, Discretion

 Character is revealed by action.          ~~ Aristotle
 Action is discrete.                       ~~ Planck
----------------------------------------------------------
 The better part of valour is discretion.  ~~ Shakespeare
Posted in Action, Anthem, Arete, Aristotle, Character, Discretion, Planck, Shakespeare, Syllogism, Valor, Valour, Virtue | Tagged , , , , , , , , , , , | Leave a comment

Frankl, My Dear : 3

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 …

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | Leave a comment

Consequences of Triadic Relation Irreducibility : 2

From time to time I come to the realization that there are ways of reading Peirce that make no sense to me.  When I stop to think about the potential sources of that evident divergence from common sense, the first thing that comes to mind is the fact that people come to reading Peirce with so many different aims, backgrounds, and collateral experiences with the objects that he wraps his signs and ideas around.

Thinking about that leads to all sorts of questions that I see no way of beginning to address with any sense of coherence.  All I can do is try to give a good account of what makes sense to me and why.  My experience with failures to communicate over many trials tells me that the biggest and most numerous rifts in our several understandings of Peirce all point back to the visions of relations, triadic relations, and triadic sign relations that dance in our various and sundry heads.

So that is what I’ll take up first …

Posted in Logic, Logic of Relatives, Mathematics, Peirce, Peirce List, Philosophy, Pragmatism, Relation Theory, Semiotics, Sign Relations, Thirdness, Triadic Relations, Triadicity | Tagged , , , , , , , , , , , , | Leave a comment

Consequences of Triadic Relation Irreducibility : 1

2014 Sep 10

I will have to be out of the loop for some days, but this post will give me a peg on which I can hang a few thoughts via mobile device that have been tugging at the edge of my mind for a while.

2014 Sep 13

I am still a bit loopy from jumping through a triple of orthogonal loops and it’s taking me longer to get back in the saddle than I thought it might, so let me just paste in a passel of links to a collection of background materials I’ve referenced before, a lot of it work-in-hopeful-progress, the rest of it more polished, published, and with luck less perishable.

Basic Concepts

Related Readings

Posted in Logic, Logic of Relatives, Mathematics, Peirce, Peirce List, Philosophy, Pragmatism, Relation Theory, Semiotics, Sign Relations, Thirdness, Triadic Relations, Triadicity | Tagged , , , , , , , , , , , , | Leave a comment

Frankl, My Dear : 2

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

Supplied by the cache of definitions from Post 1, I can return to the passage from (2) that seemed to jog a bit of memory and see if what I imagined I saw there makes any sense.

Let us use {J_{i}(f)} to denote those {x} such that

\displaystyle f(x) \neq f(x^{i}).

Obviously the following is true:

\displaystyle \frac{|J_{i}(f)|}{2^{n}} = I_{i}(f).

There must be a better notation than {J_{i}} — we are open to suggestions. Any?

I responded to their query about a better notation for {J_{i}} in a series of comments along the following lines:

I think {J_{i}(f)} is just the set of places where the partial differential of {f} with respect to {x_i} is {1}.

See Tables A9 and A10 in my article on Differential Logic and Dynamic Systems.

For example, look at {f_8 (x, y),} which is just the logical conjunction {xy}.

In this case, {\partial_x f = y}.

This means that crossing the boundary of {x} will change the value of {f} exactly in those places where {y} is true.

The See a Number, Make a Set principle leads to the following observation, that an arbitrary set of cells in a venn diagram or an arbitrary set of vertices in a {k}-cube is described by a proposition or a boolean function as its fiber of {1}, so the above types of differential operators take us from propositions to propositions, in other words, they stay within the same general datatype.

To be continued …

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | Leave a comment

Frankl, My Dear : 1

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

I need to think a little about the context that Lipton and Regan have wrapped around the Frankl Conjecture, if not exactly about the problem itself.  This will be a scratch-worky post-in-progress (PIP❢), or a series of posts, and I may even delete it down the road if it runs out of gas or turns into too much nonsense.

Just to get started, let me post the passage from the 2nd of the above articles where I thought I spied something familiar, though it was late, past my bedtime, and I was pondering weak and weary, etc.

Let us use {J_{i}(f)} to denote those {x} such that

\displaystyle f(x) \neq f(x^{i}).

Obviously the following is true:

\displaystyle \frac{|J_{i}(f)|}{2^{n}} = I_{i}(f).

There must be a better notation than {J_{i}} — we are open to suggestions. Any?

In order to understand the above formulas, we have to back up a little and pick up a couple of earlier definitions, rephrasing them slightly in the style of notation to which I would like you to become accustomed.

Let {\mathbb{B} = \{0,1\}} and let {f : \mathbb{B}^{n} \to \mathbb{B}} be a boolean function. The influence of the {i}^\text{th} input of {f} is defined by

\displaystyle I_{i}(f) = \mathrm{Prob}_{x}[ f(x) \neq f(x^{i}) ],

where {x^{i}} is equal to

\displaystyle x_{1}, \dots, x_{i-1}, \neg x_{i}, x_{i+1}, \dots, x_{n}.

There is another way of expressing the bit flip operation {x \mapsto x^i} that I like a bit better.  Here is the formal definition, using {j} instead of {i} as the index of the indicated variable.

Definition.  Let the function {\lnot_j : \mathbb{B}^k \to \mathbb{B}} be defined for each integer {j} in the interval {[1, k]} by the following equation:

{\lnot_j (x_1, \ldots, x_j, \ldots, x_k) ~=~ x_1 \land \ldots \land x_{j-1} \land \lnot x_j \land x_{j+1} \land \ldots \land x_k}.

It is conventional to write logical conjunction as multiplication, with or without a dot between conjuncts. It is also convenient in many contexts to write logical negation {\lnot x_j} with a tilde as {\tilde{x}_j} or with distinctive parentheses as {\texttt{(} x_j \texttt{)}}. Thus we may see the function {\lnot_j : \mathbb{B}^k \to \mathbb{B}} written in either of the following forms:

\begin{matrix}  \lnot_j (x_1, \ldots, x_j, \ldots, x_k)  & = &  x_1 x_2 \ldots x_{j-1} \tilde{x}_j x_{j+1} \ldots x_{k-1} x_k  \\[4pt]  & = &  x_1 x_2 \ldots x_{j-1} \texttt{(} x_j \texttt{)} x_{j+1} \ldots x_{k-1} x_k  \end{matrix}

Visually speaking, {\lnot_j (x_1, \ldots, x_k)} is a singular proposition that picks out a single cell {x} of the associated venn diagram, namely, the cell where {x_j} is false and all the rest of the {x_i} are true.  By way of context, I used the above notations for {\lnot_j} in defining minimal negation operators, which may eventually find use in this discussion.

This looks like a good place to break and start a second post in the series.

To be continued …

Posted in Boolean Algebra, Boolean Functions, Computational Complexity, Differential Logic, Frankl Conjecture, Logic, Logical Graphs, Mathematics, Péter Frankl | Tagged , , , , , , , , | 1 Comment