Directory talk:Jon Awbrey/Papers/Propositional Equation Reasoning Systems

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 \(k\!\)-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.

The first kind of propositional expression is a parenthesized sequence of propositional expressions, written as \(\texttt{(} e_1 \texttt{,} e_2 \texttt{,} \ldots \texttt{,} e_{k-1} \texttt{,} e_k \texttt{)}\) and read to say that exactly one of the propositions \(e_1, e_2, \ldots, e_{k-1}, e_k\) 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 \(e_1, e_2, \ldots, e_{k-1}, e_k\) as shown below.

The second kind of propositional expression is a concatenated sequence of propositional expressions, written as \(e_1\ e_2\ \ldots\ e_{k-1}\ e_k\) and read to say that all of the propositions \(e_1, e_2, \ldots, e_{k-1}, e_k\) 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 \(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. 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 \(\texttt{(} \ldots \texttt{)}\) may be used for logical operators.

Table 1 collects a sample of basic propositional forms as expressed in terms of cactus language connectives.

\(\text{Table 1.}~~\text{Syntax and Semantics of a Calculus for Propositional Logic}\)

\(\text{Graph}\!\)	\(\text{Expression}\!\)	\(\text{Interpretation}\!\)	\(\text{Other Notations}\!\)
	\(~\)	\(\operatorname{true}\)	\(1\!\)
	\(\texttt{(~)}\)	\(\operatorname{false}\)	\(0\!\)
	\(a\!\)	\(a\!\)	\(a\!\)
	\(\texttt{(} a \texttt{)}\)	\(\operatorname{not}~ a\)	\(\lnot a \quad \bar{a} \quad \tilde{a} \quad a^\prime\)
	\(a ~ b ~ c\)	\(a ~\operatorname{and}~ b ~\operatorname{and}~ c\)	\(a \land b \land c\)
	\(\texttt{((} a \texttt{)(} b \texttt{)(} c \texttt{))}\)	\(a ~\operatorname{or}~ b ~\operatorname{or}~ c\)	\(a \lor b \lor c\)
	\(\texttt{(} a \texttt{(} b \texttt{))}\)	\(\begin{matrix} a ~\operatorname{implies}~ b \\[6pt] \operatorname{if}~ a ~\operatorname{then}~ b \end{matrix}\)	\(a \Rightarrow b\)
	\(\texttt{(} a \texttt{,} b \texttt{)}\)	\(\begin{matrix} a ~\operatorname{not~equal~to}~ b \\[6pt] a ~\operatorname{exclusive~or}~ b \end{matrix}\)	\(\begin{matrix} a \neq b \\[6pt] a + b \end{matrix}\)
	\(\texttt{((} a \texttt{,} b \texttt{))}\)	\(\begin{matrix} a ~\operatorname{is~equal~to}~ b \\[6pt] a ~\operatorname{if~and~only~if}~ b \end{matrix}\)	\(\begin{matrix} a = b \\[6pt] a \Leftrightarrow b \end{matrix}\)
	\(\texttt{(} a \texttt{,} b \texttt{,} c \texttt{)}\)	\(\begin{matrix} \operatorname{just~one~of} \\ a, b, c \\ \operatorname{is~false}. \end{matrix}\)	\(\begin{matrix} & \bar{a} ~ b ~ c \\ \lor & a ~ \bar{b} ~ c \\ \lor & a ~ b ~ \bar{c} \end{matrix}\)
	\(\texttt{((} a \texttt{),(} b \texttt{),(} c \texttt{))}\)	\(\begin{matrix} \operatorname{just~one~of} \\ a, b, c \\ \operatorname{is~true}. \\[6pt] \operatorname{partition~all} \\ \operatorname{into}~ a, b, c. \end{matrix}\)	\(\begin{matrix} & a ~ \bar{b} ~ \bar{c} \\ \lor & \bar{a} ~ b ~ \bar{c} \\ \lor & \bar{a} ~ \bar{b} ~ c \end{matrix}\)
	\(\texttt{(} a \texttt{,(} b \texttt{,} c \texttt{))}\)	\(\begin{matrix} \operatorname{oddly~many~of} \\ a, b, c \\ \operatorname{are~true}. \end{matrix}\)	\(a + b + c\!\) \(\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}\)
	\(\texttt{(} x \texttt{,(} a \texttt{),(} b \texttt{),(} c \texttt{))}\)	\(\begin{matrix} \operatorname{partition}~ x \\ \operatorname{into}~ a, b, c. \\[6pt] \operatorname{genus}~ x ~\operatorname{comprises} \\ \operatorname{species}~ a, b, c. \end{matrix}\)	\(\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}\)

The simplest expression for logical truth is the empty word, usually denoted by \(\varepsilon\!\) or \(\lambda\!\) 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 \({}^{\backprime\backprime} \texttt{((~))} {}^{\prime\prime},\) or, especially if operating in an algebraic context, by a simple \({}^{\backprime\backprime} 1 {}^{\prime\prime}.\) Also when working in an algebraic mode, the plus sign \({}^{\backprime\backprime} + {}^{\prime\prime}\) may be used for exclusive disjunction. For example, we have the following paraphrases of algebraic expressions by means of parenthesized expressions:

\(\begin{matrix} a + b & = & \texttt{(} a \texttt{,} b \texttt{)} \end{matrix}\)

\(\begin{matrix} a + b + c & = & \texttt{(} a \texttt{,(} b \texttt{,} c \texttt{))} & = & \texttt{((} a \texttt{,} b \texttt{),} c \texttt{)} \end{matrix}\)

It is important to note that the last expressions are not equivalent to the 3-place parenthesis \(\texttt{(} a \texttt{,} b \texttt{,} c \texttt{)}.\)