Frankl, My Dear : 12

It is one of the rules of my system of general harmony, that the present is big with the future, and that he who sees all sees in that which is that which shall be.

Leibniz • Theodicy

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

We continue with the differential analysis of the proposition in Example 1.

Example 1

Venn Diagram PQR

Like any moderately complex proposition, the difference map of a proposition has many equivalent logical expressions and can be read in many different ways.

Venn Diagram Frankl Figure 5

The expansion of \mathrm{D}f computed in Post 9 and further discussed in Post 10 is shown again below with the terms arranged by number of positive differential features, from lowest to highest.

\begin{array}{*{4}{l}}  \multicolumn{4}{l}{\mathrm{D}f(p, q, r, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r) =}  \\[10pt]  &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)}  & + &  \texttt{(} p \texttt{)~} q \texttt{~~} r \texttt{~} \cdot  \texttt{~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)}  \\[10pt]  + &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{(} \mathrm{d}p \texttt{)~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)}  & + &  \texttt{~} p \texttt{~(} q \texttt{)~} r \texttt{~} \cdot  \texttt{(} \mathrm{d}p \texttt{)~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)}  \\[10pt]  + &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)~} \mathrm{d}r \texttt{~}  & + &  \texttt{~} p \texttt{~~} q \texttt{~(} r \texttt{)} \cdot  \texttt{(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)~} \mathrm{d}r \texttt{~}  \end{array}
\begin{array}{*{4}{l}}  + &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)}  & + &  \texttt{(} p \texttt{)(} q \texttt{)~} r \texttt{~} \cdot  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)}  \\[10pt]  + &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)~} \mathrm{d}r \texttt{~}  & + &  \texttt{(} p \texttt{)~} q \texttt{~(} r \texttt{)} \cdot  \texttt{~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)~} \mathrm{d}r \texttt{~}  \\[10pt]  + &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{(} \mathrm{d}p \texttt{)~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~}  & + &  \texttt{~} p \texttt{~(} q \texttt{)(} r \texttt{)} \cdot  \texttt{(} \mathrm{d}p \texttt{)~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~}  \\[10pt]  + &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~} \cdot  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~}  & + &  \texttt{(} p \texttt{)(} q \texttt{)(} r \texttt{)} \cdot  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~}  \end{array}

The terms of the difference map \mathrm{D}f may be obtained from the table below by multiplying the base factor at the head of each column by the differential factor that appears beneath it in the body of the table.

Table 4.0 PQR Difference Map

The full boolean expansion of \mathrm{D}f may be condensed to a degree by collecting terms that share the same base factors, as shown in the following display:

\begin{array}{*{4}{c}}  \multicolumn{4}{l}{\mathrm{D}f(p, q, r, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r) =}  \\[10pt]  &  \texttt{~} p \texttt{~~} q \texttt{~~} r \texttt{~}  & \cdot &  \texttt{((} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{))}  \\[4pt]  + &  \texttt{(} p \texttt{)~} q \texttt{~~} r \texttt{~}  & \cdot &  \texttt{~~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)~}  \\[4pt]  + &  \texttt{~} p \texttt{~(} q \texttt{)~} r \texttt{~}  & \cdot &  \texttt{~(} \mathrm{d}p \texttt{)~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)~}  \\[4pt]  + &  \texttt{~} p \texttt{~~} q \texttt{~(} r \texttt{)}  & \cdot &  \texttt{~(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)~} \mathrm{d}r \texttt{~~}  \\[4pt]  + &  \texttt{(} p \texttt{)(} q \texttt{)~} r \texttt{~}  & \cdot &  \texttt{~~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)~}  \\[4pt]  + &  \texttt{(} p \texttt{)~} q \texttt{~(} r \texttt{)}  & \cdot &  \texttt{~~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)~} \mathrm{d}r \texttt{~~}  \\[4pt]  + &  \texttt{~} p \texttt{~(} q \texttt{)(} r \texttt{)}  & \cdot &  \texttt{~(} \mathrm{d}p \texttt{)~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~~}  \\[4pt]  + &  \texttt{(} p \texttt{)(} q \texttt{)(} r \texttt{)}  & \cdot &  \texttt{~~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~~}  \end{array}

This amounts to summing terms along columns of the previous table, as shown at the bottom margin of the next table:

Table 4.0 PQR Difference Map Col Sum

Collecting terms with the same differential factors produces the following expression:

\begin{array}{*{4}{c}}  \multicolumn{4}{l}{\mathrm{D}f(p, q, r, \mathrm{d}p, \mathrm{d}q, \mathrm{d}r) =}  \\[10pt]  &  \texttt{~} \mathrm{d}p \texttt{~(} \mathrm{d}q \texttt{)(} \mathrm{d}r \texttt{)}  & \cdot &  q \texttt{~} r  \\[4pt]  + &  \texttt{~} \mathrm{d}q \texttt{~(} \mathrm{d}p \texttt{)(} \mathrm{d}r \texttt{)}  & \cdot &  p \texttt{~} r  \\[4pt]  + &  \texttt{~} \mathrm{d}r \texttt{~(} \mathrm{d}p \texttt{)(} \mathrm{d}q \texttt{)}  & \cdot &  p \texttt{~} q  \\[4pt]  + &  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~(} \mathrm{d}r \texttt{)}  & \cdot &  \texttt{((} p \texttt{,} q \texttt{))} ~ r  \\[4pt]  + &  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}r \texttt{~(} \mathrm{d}q \texttt{)}  & \cdot &  \texttt{((} p \texttt{,} r \texttt{))} ~ q  \\[4pt]  + &  \texttt{~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~(} \mathrm{d}p \texttt{)}  & \cdot &  \texttt{((} q \texttt{,} r \texttt{))} ~ p  \\[4pt]  + &  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~}  & \cdot &  p \texttt{~} q \texttt{~} r  \\[4pt]  + &  \texttt{~} \mathrm{d}p \texttt{~~} \mathrm{d}q \texttt{~~} \mathrm{d}r \texttt{~}  & \cdot &  \texttt{(} p \texttt{)(} q \texttt{)(} r \texttt{)}  \end{array}

This is roughly what one would get by summing along rows of the previous tables.

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.

One Response to Frankl, My Dear : 12

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