12,089
edits
Changes
Directory:Jon Awbrey/Papers/Differential Logic and Dynamic Systems 3.0 (view source)
Revision as of 02:56, 12 July 2009
, 02:56, 12 July 2009→Review and Transition: fold in revisions
This note continues a previous discussion on the problem of dealing with change and diversity in logic-based intelligent systems. It is useful to begin by summarizing essential material from previous reports.
This note continues a previous discussion on the problem of dealing with change and diversity in logic-based intelligent systems. It is useful to begin by summarizing essential material from previous reports.
The development of differential logic is greatly facilitated by having a conceptually efficient calculus in place at the level of [[boolean-valued functions]] and elementary logical propositions. A calculus that is very efficient from both conceptual and computational standpoints is based on just two types of logical connectives, both of variable <math>k\!</math>-ary scope. The formulas of this calculus map into a species of graph-theoretical structures called ''painted and rooted cacti'' (PARCs) that lend visual representation to their functional structure and smooth the path to efficient computation.
{| align="center" cellpadding="6" width="90%"
{| align="center" cellpadding="6" width="90%"
| A bracketed list of propositional expressions in the form <math>\texttt{(} e_1, e_2, \ldots, e_{k-1}, e_k \texttt{)}</math> indicates that exactly one of the propositions <math>e_1, e_2, \ldots, e_{k-1}, e_k</math> is false.
| The first kind of propositional expression is a parenthesized sequence of propositional expressions, written as <math>\texttt{(} e_1 \texttt{,} e_2 \texttt{,} \ldots \texttt{,} e_{k-1} \texttt{,} e_k \texttt{)}</math> and read to say that exactly one of the propositions <math>e_1, e_2, \ldots, e_{k-1}, e_k</math> is false, in other words, that their [[minimal negation]] is true. A clause of this form maps into a PARC structure called a ''lobe'', in this case, one that is ''painted'' with the colors <math>e_1, e_2, \ldots, e_{k-1}, e_k</math> as shown below.
|}
|}
{| align="center" cellpadding="10"
| [[Image:Cactus Graph Lobe Connective.jpg|500px]]
|}
{| align="center" cellpadding="6" width="90%"
| The second kind of propositional expression is a concatenated sequence of propositional expressions, written as <math>e_1\ e_2\ \ldots\ e_{k-1}\ e_k</math> and read to say that all of the propositions <math>e_1, e_2, \ldots, e_{k-1}, e_k</math> are true, in other words, that their [[logical conjunction]] is true. A clause of this form maps into a PARC structure called a ''node'', in this case, one that is ''painted'' with the colors <math>e_1, e_2, \ldots, e_{k-1}, e_k</math> as shown below.
|}
{| align="center" cellpadding="10"
| [[Image:Cactus Graph Node Connective.jpg|500px]]
|}
All other propositional connectives can be obtained through combinations of these two forms. Strictly speaking, the parenthesized form is sufficient to define the concatenated form, making the latter formally dispensable, but it is convenient to maintain it as a concise way of expressing more complicated combinations of parenthesized forms. While working with expressions solely in propositional calculus, it is easiest to use plain parentheses for logical connectives. In contexts where ordinary parentheses are needed for other purposes an alternate typeface <math>\texttt{(} \ldots \texttt{)}</math> may be used for logical operators.
Table 1 collects a sample of basic propositional forms as expressed in terms of cactus language connectives.
& = &
<br>
<br>
{| align="center" border="1" cellpadding="6" cellspacing="0" style="background:#f8f8ff; text-align:center; width:90%"
{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:#f8f8ff; text-align:center; width:90%"
|+ <math>\text{Table 1.}~~\text{Syntax and Semantics of a Calculus for Propositional Logic}</math>
|+ <math>\text{Table 1.}~~\text{Syntax and Semantics of a Calculus for Propositional Logic}</math>
|- style="background:#f0f0ff"
|- style="background:#f0f0ff"
| <math>\text{Graph}\!</math>
| <math>\text{Expression}\!</math>
| <math>\text{Expression}\!</math>
| <math>\text{Interpretation}\!</math>
| <math>\text{Interpretation}\!</math>
| <math>\text{Other Notations}\!</math>
| <math>\text{Other Notations}\!</math>
|-
|-
| height="100px" | [[Image:Cactus Node Big Fat.jpg|20px]]
| <math>~</math>
| <math>~</math>
| <math>\operatorname{True}</math>
| <math>\operatorname{true}</math>
| <math>1\!</math>
| <math>1\!</math>
|-
|-
| <math>(~)</math>
| height="100px" | [[Image:Cactus Spike Big Fat.jpg|20px]]
| <math>\operatorname{False}</math>
| <math>\texttt{(~)}</math>
| <math>\operatorname{false}</math>
| <math>0\!</math>
| <math>0\!</math>
|-
|-
| <math>x\!</math>
| height="100px" | [[Image:Cactus A Big.jpg|20px]]
| <math>x\!</math>
| <math>a\!</math>
| <math>x\!</math>
| <math>a\!</math>
| <math>a\!</math>
|-
|-
| <math>(x)\!</math>
| height="120px" | [[Image:Cactus (A) Big.jpg|20px]]
| <math>\operatorname{Not}\ x</math>
| <math>\texttt{(} a \texttt{)}</math>
|
| <math>\operatorname{not}~ a</math>
<math>\begin{matrix}
| <math>\lnot a \quad \bar{a} \quad \tilde{a} \quad a^\prime</math>
\tilde{x} \\
|-
|-
| <math>x\ y\ z</math>
| height="100px" | [[Image:Cactus ABC Big.jpg|50px]]
| <math>x\ \operatorname{and}\ y\ \operatorname{and}\ z</math>
| <math>a ~ b ~ c</math>
| <math>x \land y \land z</math>
| <math>a ~\operatorname{and}~ b ~\operatorname{and}~ c</math>
| <math>a \land b \land c</math>
|-
|-
| <math>((x)(y)(z))\!</math>
| height="160px" | [[Image:Cactus ((A)(B)(C)) Big.jpg|65px]]
| <math>x\ \operatorname{or}\ y\ \operatorname{or}\ z</math>
| <math>\texttt{((} a \texttt{)(} b \texttt{)(} c \texttt{))}</math>
| <math>x \lor y \lor z</math>
| <math>a ~\operatorname{or}~ b ~\operatorname{or}~ c</math>
| <math>a \lor b \lor c</math>
|-
|-
| <math>(x\ (y))\!</math>
| height="120px" | [[Image:Cactus (A(B)) Big.jpg|60px]]
| <math>\texttt{(} a \texttt{(} b \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a ~\operatorname{implies}~ b
\operatorname{If}\ x\ \operatorname{then}\ y \\
\\[6pt]
\operatorname{if}~ a ~\operatorname{then}~ b
\end{matrix}</math>
\end{matrix}</math>
| <math>x \Rightarrow y\!</math>
| <math>a \Rightarrow b</math>
|-
|-
| <math>(x, y)\!</math>
| height="120px" | [[Image:Cactus (A,B) Big.jpg|65px]]
| <math>\texttt{(} a \texttt{,} b \texttt{)}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a ~\operatorname{not~equal~to}~ b
\\[6pt]
a ~\operatorname{exclusive~or}~ b
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a \neq b
\\[6pt]
a + b
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| <math>((x, y))\!</math>
| height="160px" | [[Image:Cactus ((A,B)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{,} b \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a ~\operatorname{is~equal~to}~ b
\\[6pt]
a ~\operatorname{if~and~only~if}~ b
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a = b
\\[6pt]
a \Leftrightarrow b
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| <math>(x, y, z)\!</math>
| height="120px" | [[Image:Cactus (A,B,C) Big.jpg|65px]]
| <math>\texttt{(} a \texttt{,} b \texttt{,} c \texttt{)}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\operatorname{Just~one~of} \\
\operatorname{just~one~of}
\\
\operatorname{is~false}. \\
a, b, c
\\
\operatorname{is~false}.
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
& \bar{a} ~ b ~ c
\\
\lor & a ~ \bar{b} ~ c
\\
\lor & a ~ b ~ \bar{c}
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| <math>((x),(y),(z))\!</math>
| height="160px" | [[Image:Cactus ((A),(B),(C)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{),(} b \texttt{),(} c \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\operatorname{Just~one~of} \\
\operatorname{just~one~of}
\\
\operatorname{is~true}. \\
a, b, c
\\
\operatorname{Partition~all} \\
\operatorname{is~true}.
\operatorname{into}\ x, y, z. \\
\\[6pt]
\operatorname{partition~all}
\\
\operatorname{into}~ a, b, c.
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
& a ~ \bar{b} ~ \bar{c}
\\
\lor & \bar{a} ~ b ~ \bar{c}
\\
\lor & \bar{a} ~ \bar{b} ~ c
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| height="160px" | [[Image:Cactus (A,(B,C)) Big.jpg|90px]]
| <math>\texttt{(} a \texttt{,(} b \texttt{,} c \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\operatorname{oddly~many~of}
\\
a, b, c
\\
\operatorname{are~true}.
\operatorname{Oddly~many~of} \\
\operatorname{are~true}. \\
\end{matrix}</math>
\end{matrix}</math>
|
|
<p><math>x + y + z\!</math></p>
<p><math>a + b + c\!</math></p>
<br>
<br>
<p><math>\begin{matrix}
<p><math>\begin{matrix}
& a ~ b ~ c
\\
\lor & a ~ \bar{b} ~ \bar{c}
\\
\lor & \bar{a} ~ b ~ \bar{c}
\\
\lor & \bar{a} ~ \bar{b} ~ c
\end{matrix}</math></p>
\end{matrix}</math></p>
|-
|-
| <math>(w, (x),(y),(z))\!</math>
| height="160px" | [[Image:Cactus (X,(A),(B),(C)) Big.jpg|90px]]
| <math>\texttt{(} x \texttt{,(} a \texttt{),(} b \texttt{),(} c \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\operatorname{Partition}\ w \\
\operatorname{partition}~ x
\operatorname{into}\ x, y, z. \\
\\
\operatorname{into}~ a, b, c.
\operatorname{Genus}\ w\ \operatorname{comprises} \\
\\[6pt]
\operatorname{species}\ x, y, z. \\
\operatorname{genus}~ x ~\operatorname{comprises}
\\
\operatorname{species}~ a, b, c.
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
& \bar{x} ~ \bar{a} ~ \bar{b} ~ \bar{c}
\\
\lor & x ~ a ~ \bar{b} ~ \bar{c}
\\
\lor & x ~ \bar{a} ~ b ~ \bar{c}
\\
\lor & x ~ \bar{a} ~ \bar{b} ~ c
\end{matrix}</math>
\end{matrix}</math>
|}
|}
<br>
<br>
The simplest expression for logical truth is the empty word, usually denoted by <math>\varepsilon\!</math> or <math>\lambda\!</math> in formal languages, where it forms the identity element for concatenation. To make it visible in context, it may be denoted by the equivalent expression <math>{}^{\backprime\backprime} \texttt{((~))} {}^{\prime\prime},</math> or, especially if operating in an algebraic context, by a simple <math>{}^{\backprime\backprime} 1 {}^{\prime\prime}.</math> Also when working in an algebraic mode, the plus sign <math>{}^{\backprime\backprime} + {}^{\prime\prime}</math> may be used for [[exclusive disjunction]]. For example, we have the following paraphrases of algebraic expressions by means of parenthesized expressions:
{| align="center" cellpadding="6" style="text-align:center"
|
<math>\begin{matrix}
a + b
& = &
\texttt{(} a \texttt{,} b \texttt{)}
\end{matrix}</math>
|-
|
<math>\begin{matrix}
a + b + c
& = &
\texttt{((} a \texttt{,} b \texttt{),} c \texttt{)}
& = &
\texttt{(} a \texttt{,(} b \texttt{,} c \texttt{))}
\end{matrix}</math>
|}
It is important to note that the last expressions are not equivalent to the 3-place parenthesis <math>\texttt{(} a \texttt{,} b \texttt{,} c \texttt{)}.</math>
This treatment of propositional logic is derived from the work of [[C.S. Peirce]] [P1, P2], who gave this approach an extensive development in his graphical systems of predicate, relational, and modal logic [Rob]. More recently, these ideas were revived and supplemented in an alternative interpretation by George Spencer-Brown [SpB]. Both of these authors used other forms of enclosure where I use parentheses, but the structural topologies of expression and the functional varieties of interpretation are fundamentally the same.
The usage that one often sees, of a plus sign "<math>+\!</math>" to represent inclusive disjunction, and the reference to this operation as ''boolean addition'', is a misnomer on at least two counts. Boole used the plus sign to represent exclusive disjunction (at any rate, an operation of aggregation restricted in its logical interpretation to cases where the represented sets are disjoint (Boole, 32)), as any mathematician with a sensitivity to the ring and field properties of algebra would do:
{| align="center" cellpadding="6" width="90%"
{| align="center" cellpadding="6" width="90%"