## Differential Logic • 2

### Cactus Language for Propositional Logic

The development of differential logic is facilitated by having a moderately efficient calculus in place at the level of boolean-valued functions and elementary logical propositions.  One very efficient calculus on both conceptual and computational grounds is based on just two types of logical connectives, both of variable $k$-ary scope.  The syntactic formulas of this calculus map into a family of graph-theoretic structures called “painted and rooted cacti” which lend visual representation to the functional structures of propositions and smooth the path to efficient computation.

The first kind of connective takes the form of a parenthesized sequence of propositional expressions, written $\texttt{(} e_1 \texttt{,} e_2 \texttt{,} \ldots \texttt{,} e_{k-1} \texttt{,} e_k \texttt{)}$ and meaning exactly one of the propositions $e_1, e_2, \ldots, e_{k-1}, e_k$ is false, in short, their minimal negation is true.  An expression of this form maps into a cactus structure called a lobe, in this case, “painted” with the colors $e_1, e_2, \ldots, e_{k-1}, e_k$ as shown below. The second kind of connective is a concatenated sequence of propositional expressions, written $e_1\ e_2\ \ldots\ e_{k-1}\ e_k$ and meaning all the propositions $e_1, e_2, \ldots, e_{k-1}, e_k$ are true, in short, their logical conjunction is true.  An expression of this form maps into a cactus structure called a node, in this case, “painted” with the colors $e_1, e_2, \ldots, e_{k-1}, e_k$ as shown below. All other propositional connectives can be obtained through combinations of these two forms.  As it happens, the parenthesized form is sufficient to define the concatenated form, making the latter formally dispensable, but it’s 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’s easiest to use plain parentheses for logical connectives.  In contexts where ordinary parentheses are needed for other purposes an alternate typeface $\texttt{(} \ldots \texttt{)}$ may be used for the logical operators.

This site uses Akismet to reduce spam. Learn how your comment data is processed.