Frankl, My Dear : 5

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

Putting all thought of the Frankl Conjecture out of our minds for the moment, let’s return to the proposition in Example 1 and work through its differential analysis from scratch.

Example 1

Venn Diagram PQR

Consider the proposition p \land q \land r, in boolean terms the function f : \mathbb{B}^3 \to \mathbb{B} such that f(p, q, r) = pqr, as illustrated by the venn diagram in Figure 1.

The enlargement \mathrm{E}f of f is the boolean function \mathrm{E}f : \mathbb{B}^3 \times \mathbb{D}^3 \to \mathbb{B} defined by the following equation:

\mathrm{E}f(p, q, r, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r) ~=~ f(p + \mathrm{d}p, q + \mathrm{d}q, r + \mathrm{d}r).

Given that f is the boolean product of its three arguments, \mathrm{E}f may be written as follows:

\mathrm{E}f ~=~ (p + \mathrm{d}p)(q + \mathrm{d}q)(r + \mathrm{d}r).

Difficulties of notation in differential logic are greatly eased by introducing the family of minimal negation operators on finite numbers of boolean variables. For our immediate purposes we need only the minimal negation operators on one and two variables.

  • The minimal negation operator on one variable x is notated with monospace parentheses as \texttt{(} x \texttt{)} and is simply another notation for the logical negation \lnot x.
  • The minimal negation operator on two variables x, y is notated with monospace delimiters as \texttt{(} x \texttt{,} y \texttt{)} and is simply another notation for the exclusive disjunction x + y.

In this notation the previous expression for \mathrm{E}f takes the following form:

\mathrm{E}f ~=~ \texttt{(} p \texttt{,} \mathrm{d}p \texttt{)(} q \texttt{,} \mathrm{d}q \texttt{)(} r \texttt{,} \mathrm{d}r \texttt{)}.

A canonical form for \mathrm{E}f may be derived by means of a boolean expansion, in effect, a case analysis that evaluates \mathrm{E}f at each triple of values for the base variables p, q, r and forms the disjunction of the partial evaluations. Each term of the boolean expansion corresponds to a cell of the venn diagram and is formed by multiplying the value of that cell by a coefficient that amounts to the value of \mathrm{E}f on that cell.

For example, in the case pqr where all three base variables are true, the corresponding coefficient is computed as follows:

\begin{array}{lll}  \mathrm{E}f(1, 1, 1, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r)  & = & (1 + \mathrm{d}p)(1 + \mathrm{d}q)(1 + \mathrm{d}r)  \\[4pt]  & = & \lnot\mathrm{d}p \land \lnot\mathrm{d}q \land \lnot\mathrm{d}r  \\[4pt]  & = & \texttt{(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)}  \end{array}

Collecting the cases yields the boolean expansion of \mathrm{E}f via the following computation:

Step 1

\mathrm{E}f(p, q, r, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r) =

\begin{smallmatrix}  &  p q r \cdot f(1 + \mathrm{d}p, 1 + \mathrm{d}q, 1 + \mathrm{d}r)  & + &  p q \tilde{r} \cdot f(1 + \mathrm{d}p, 1 + \mathrm{d}q, 0 + \mathrm{d}r)  & + &  p \tilde{q} r \cdot f(1 + \mathrm{d}p, 0 + \mathrm{d}q, 1 + \mathrm{d}r)  & + &  p \tilde{q} \tilde{r} \cdot f(1 + \mathrm{d}p, 0 + \mathrm{d}q, 0 + \mathrm{d}q)  \\[4pt]  + &  \tilde{p} q r \cdot f(0 + \mathrm{d}p, 1 + \mathrm{d}q, 1 + \mathrm{d}r)  & + &  \tilde{p} q \tilde{r} \cdot f(0 + \mathrm{d}p, 1 + \mathrm{d}q, 0 + \mathrm{d}r)  & + &  \tilde{p} \tilde{q} r \cdot f(0 + \mathrm{d}p, 0 + \mathrm{d}q, 1 + \mathrm{d}r)  & + &  \tilde{p} \tilde{q} \tilde{r} \cdot f(0 + \mathrm{d}p, 0 + \mathrm{d}q, 0 + \mathrm{d}q)  \end{smallmatrix}

Step 2

\mathrm{E}f(p, q, r, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r) =

\begin{smallmatrix}  &  p q r \,\cdot\,  \texttt{(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)}  & + &  p q \texttt{(} r \texttt{)} \,\cdot\,  \texttt{(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)} \mathrm{d}r  & + &  p \texttt{(} q \texttt{)} r \,\cdot\,  \texttt{(} \mathrm{d}p \texttt{)} \mathrm{d}q \texttt{(} \mathrm{d}r \texttt{)}  & + &  p \texttt{(} q \texttt{)(} r \texttt{)} \,\cdot\,  \texttt{(} \mathrm{d}p \texttt{)} \mathrm{d}q \, \mathrm{d}r  \\[4pt]  + &  \texttt{(} p \texttt{)} q r \,\cdot\,  \mathrm{d}p \texttt{(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)}  & + &  \texttt{(} p \texttt{)} q \texttt{(} r \texttt{)} \,\cdot\,  \mathrm{d}p \texttt{(} \mathrm{d}q \texttt{)} \mathrm{d}r  & + &  \texttt{(} p \texttt{)(} q \texttt{)} r \,\cdot\,  \mathrm{d}p \, \mathrm{d}q \texttt{(} \mathrm{d}r \texttt{)}  & + &  \texttt{(} p \texttt{)(} q \texttt{)(} r \texttt{)} \,\cdot\,  \mathrm{d}p \, \mathrm{d}q \, \mathrm{d}r  \end{smallmatrix}

To be continued …


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.

3 Responses to Frankl, My Dear : 5

  1. Pingback: Frankl, My Dear : 6 | Inquiry Into Inquiry

  2. Pingback: Frankl, My Dear : 9 | Inquiry Into Inquiry

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

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s