12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Friday November 22, 2024
Jump to navigationJump to searchDirectory talk:Jon Awbrey/Papers/Differential Logic : Introduction (view source)
Revision as of 16:44, 29 November 2015
, 16:44, 29 November 2015add work area
==Discussion Area==
==Work Area==
===Cactus Language for Propositional Logic===
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%"
| 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>
{| align="center" border="1" cellpadding="8" cellspacing="0" style="text-align:center; width:90%"
|+ <math>\text{Table 1.}~~\text{Syntax and Semantics of a Calculus for Propositional Logic}\!</math>
|- style="background:#f0f0ff"
| <math>\text{Graph}\!</math>
| <math>\text{Expression}~\!</math>
| <math>\text{Interpretation}\!</math>
| <math>\text{Other Notations}\!</math>
|-
| height="100px" | [[Image:Rooted Node.jpg|20px]]
| <math>~\!</math>
| <math>\mathrm{true}\!</math>
| <math>1\!</math>
|-
| height="100px" | [[Image:Rooted Edge.jpg|20px]]
| <math>\texttt{(~)}\!</math>
| <math>\mathrm{false}\!</math>
| <math>0\!</math>
|-
| height="100px" | [[Image:Cactus A Big.jpg|20px]]
| <math>a\!</math>
| <math>a\!</math>
| <math>a\!</math>
|-
| height="120px" | [[Image:Cactus (A) Big.jpg|20px]]
| <math>\texttt{(} a \texttt{)}\!</math>
| <math>\mathrm{not}~ a\!</math>
| <math>\lnot a \quad \bar{a} \quad \tilde{a} \quad a^\prime~\!</math>
|-
| height="100px" | [[Image:Cactus ABC Big.jpg|50px]]
| <math>a ~ b ~ c\!</math>
| <math>a ~\mathrm{and}~ b ~\mathrm{and}~ c\!</math>
| <math>a \land b \land c\!</math>
|-
| height="160px" | [[Image:Cactus ((A)(B)(C)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{)(} b \texttt{)(} c \texttt{))}\!</math>
| <math>a ~\mathrm{or}~ b ~\mathrm{or}~ c\!</math>
| <math>a \lor b \lor c\!</math>
|-
| height="120px" | [[Image:Cactus (A(B)) Big.jpg|60px]]
| <math>\texttt{(} a \texttt{(} b \texttt{))}\!</math>
|
<math>\begin{matrix}
a ~\mathrm{implies}~ b
\\[6pt]
\mathrm{if}~ a ~\mathrm{then}~ b
\end{matrix}\!</math>
| <math>a \Rightarrow b\!</math>
|-
| height="120px" | [[Image:Cactus (A,B) Big ISW.jpg|65px]]
| <math>\texttt{(} a \texttt{,} b \texttt{)}\!</math>
|
<math>\begin{matrix}
a ~\mathrm{not~equal~to}~ b
\\[6pt]
a ~\mathrm{exclusive~or}~ b
\end{matrix}\!</math>
|
<math>\begin{matrix}
a \neq b
\\[6pt]
a + b
\end{matrix}\!</math>
|-
| height="160px" | [[Image:Cactus ((A,B)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{,} b \texttt{))}\!</math>
|
<math>\begin{matrix}
a ~\mathrm{is~equal~to}~ b
\\[6pt]
a ~\mathrm{if~and~only~if}~ b
\end{matrix}\!</math>
|
<math>\begin{matrix}
a = b
\\[6pt]
a \Leftrightarrow b
\end{matrix}\!</math>
|-
| height="120px" | [[Image:Cactus (A,B,C) Big.jpg|65px]]
| <math>\texttt{(} a \texttt{,} b \texttt{,} c \texttt{)}\!</math>
|
<math>\begin{matrix}
\mathrm{just~one~of}
\\
a, b, c
\\
\mathrm{is~false}.
\end{matrix}\!</math>
|
<math>\begin{matrix}
& \bar{a} ~ b ~ c
\\
\lor & a ~ \bar{b} ~ c
\\
\lor & a ~ b ~ \bar{c}
\end{matrix}\!</math>
|-
| height="160px" | [[Image:Cactus ((A),(B),(C)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{),(} b \texttt{),(} c \texttt{))}\!</math>
|
<math>\begin{matrix}
\mathrm{just~one~of}
\\
a, b, c
\\
\mathrm{is~true}.
\\[6pt]
\mathrm{partition~all}
\\
\mathrm{into}~ a, b, c.
\end{matrix}\!</math>
|
<math>\begin{matrix}
& a ~ \bar{b} ~ \bar{c}
\\
\lor & \bar{a} ~ b ~ \bar{c}
\\
\lor & \bar{a} ~ \bar{b} ~ c
\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}
\mathrm{oddly~many~of}
\\
a, b, c
\\
\mathrm{are~true}.
\end{matrix}\!</math>
|
<p><math>a + b + c\!</math></p>
<br>
<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>
|-
| 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}
\mathrm{partition}~ x
\\
\mathrm{into}~ a, b, c.
\\[6pt]
\mathrm{genus}~ x ~\mathrm{comprises}
\\
\mathrm{species}~ a, b, c.
\end{matrix}\!</math>
|
<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>
|}
<br>
The simplest expression for logical truth is the empty word, usually denoted by <math>\boldsymbol\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>
==Logical Cacti==
==Logical Cacti==
