This site is supported by donations to The OEIS Foundation.

# Differential Propositional Calculus • Part 1

Author: Jon Awbrey

A differential propositional calculus is a propositional calculus extended by a set of terms for describing aspects of change and difference, for example, processes taking place in a universe of discourse or transformations mapping a source universe to a target universe.

## Casual Introduction

Consider the situation represented by the venn diagram in Figure 1.

 ${\displaystyle {\text{Figure 1.}}~~{\text{Local Habitations, And Names}}}$

The area of the rectangle represents a universe of discourse, ${\displaystyle X.}$ This might be a population of individuals having various additional properties or it might be a collection of locations that various individuals occupy. The area of the “circle” represents the individuals that have the property ${\displaystyle q}$ or the locations that fall within the corresponding region ${\displaystyle Q.}$ Four individuals, ${\displaystyle a,b,c,d,}$ are singled out by name. It happens that ${\displaystyle b}$ and ${\displaystyle c}$ currently reside in region ${\displaystyle Q}$ while ${\displaystyle a}$ and ${\displaystyle d}$ do not.

Now consider the situation represented by the venn diagram in Figure 2.

 ${\displaystyle {\text{Figure 2.}}~~{\text{Same Names, Different Habitations}}}$

Figure 2 differs from Figure 1 solely in the circumstance that the object ${\displaystyle c}$ is outside the region ${\displaystyle Q}$ while the object ${\displaystyle d}$ is inside the region ${\displaystyle Q.}$ So far, there is nothing that says that our encountering these Figures in this order is other than purely accidental, but if we interpret the present sequence of frames as a “moving picture” representation of their natural order in a temporal process, then it would be natural to say that ${\displaystyle a}$ and ${\displaystyle b}$ have remained as they were with regard to quality ${\displaystyle q}$ while ${\displaystyle c}$ and ${\displaystyle d}$ have changed their standings in that respect. In particular, ${\displaystyle c}$ has moved from the region where ${\displaystyle q}$ is ${\displaystyle \mathrm {true} }$ to the region where ${\displaystyle q}$ is ${\displaystyle \mathrm {false} }$ while ${\displaystyle d}$ has moved from the region where ${\displaystyle q}$ is ${\displaystyle \mathrm {false} }$ to the region where ${\displaystyle q}$ is ${\displaystyle \mathrm {true} .}$

Figure 3 reprises the situation shown in Figure 1, but this time interpolates a new quality that is specifically tailored to account for the relation between Figure 1 and Figure 2.

 ${\displaystyle {\text{Figure 3.}}~~{\text{Back, To The Future}}}$

This new quality, ${\displaystyle \mathrm {d} q,}$ is an example of a differential quality, since its absence or presence qualifies the absence or presence of change occurring in another quality. As with any other quality, it is represented in the venn diagram by means of a “circle” that distinguishes two halves of the universe of discourse, in this case, the portions of ${\displaystyle X}$ outside and inside the region ${\displaystyle \mathrm {d} Q.}$

Figure 1 represents a universe of discourse, ${\displaystyle X,}$ together with a basis of discussion, ${\displaystyle \{q\},}$ for expressing propositions about the contents of that universe. Once the quality ${\displaystyle q}$ is given a name, say, the symbol ${\displaystyle {}^{\backprime \backprime }q{}^{\prime \prime },}$ we have the basis for a formal language that is specifically cut out for discussing ${\displaystyle X}$ in terms of ${\displaystyle q,}$ and this formal language is more formally known as the propositional calculus with alphabet ${\displaystyle \{{}^{\backprime \backprime }q{}^{\prime \prime }\}.}$

In the context marked by ${\displaystyle X}$ and ${\displaystyle \{q\}}$ there are but four different pieces of information that can be expressed in the corresponding propositional calculus, namely, the propositions: ${\displaystyle \mathrm {false} ,~\lnot q,~q,~\mathrm {true} .}$ Referring to the sample of points in Figure 1, the constant proposition ${\displaystyle \mathrm {false} }$ holds of no points, the proposition ${\displaystyle \lnot q}$ holds of ${\displaystyle a}$ and ${\displaystyle d,}$ the proposition ${\displaystyle q}$ holds of ${\displaystyle b}$ and ${\displaystyle c,}$ and the constant proposition ${\displaystyle \mathrm {true} }$ holds of all points in the sample.

Figure 3 preserves the same universe of discourse and extends the basis of discussion to a set of two qualities, ${\displaystyle \{q,\mathrm {d} q\}.}$ In parallel fashion, the initial propositional calculus is extended by means of the enlarged alphabet, ${\displaystyle \{{}^{\backprime \backprime }q{}^{\prime \prime },{}^{\backprime \backprime }\mathrm {d} q{}^{\prime \prime }\}.}$ Any propositional calculus over two basic propositions allows for the expression of 16 propositions all together. Just by way of salient examples in the present setting, we can pick out the most informative propositions that apply to each of our sample points. Using overlines to express logical negation, these are given as follows:

 ${\displaystyle {\begin{matrix}{\overline {q}}~{\overline {\mathrm {d} q}}~{\text{describes}}~a\\[8pt]{\overline {q}}~\mathrm {d} q~{\text{describes}}~d\\[8pt]q~{\overline {\mathrm {d} q}}~{\text{describes}}~b\\[8pt]q~\mathrm {d} q~{\text{describes}}~c\end{matrix}}}$

Table 5 exhibits the rules of inference that give the differential quality ${\displaystyle \mathrm {d} q}$ its meaning in practice.

 ${\displaystyle {\begin{matrix}{\text{From}}&{\overline {q}}&{\text{and}}&{\overline {\mathrm {d} q}}&{\text{infer}}&{\overline {q}}&{\text{next.}}\\[8pt]{\text{From}}&{\overline {q}}&{\text{and}}&\mathrm {d} q&{\text{infer}}&q&{\text{next.}}\\[8pt]{\text{From}}&q&{\text{and}}&{\overline {\mathrm {d} q}}&{\text{infer}}&q&{\text{next.}}\\[8pt]{\text{From}}&q&{\text{and}}&\mathrm {d} q&{\text{infer}}&{\overline {q}}&{\text{next.}}\end{matrix}}}$

## Cactus Calculus

Table 6 outlines a syntax for propositional calculus based on two types of logical connectives, both of variable ${\displaystyle k}$-ary scope.

• A bracketed list of propositional expressions in the form ${\displaystyle {\texttt {(}}e_{1}{\texttt {,}}e_{2}{\texttt {,}}\ldots {\texttt {,}}e_{k-1}{\texttt {,}}e_{k}{\texttt {)}}}$ indicates exactly one of the propositions ${\displaystyle e_{1},e_{2},\ldots ,e_{k-1},e_{k}}$ is false.
• A concatenation of propositional expressions in the form ${\displaystyle e_{1}~e_{2}~\ldots ~e_{k-1}~e_{k}}$ indicates all the propositions ${\displaystyle e_{1},e_{2},\ldots ,e_{k-1},e_{k}}$ are true, in other words, their logical conjunction is true.

 ${\displaystyle {\text{Expression}}}$ ${\displaystyle {\text{Interpretation}}}$ ${\displaystyle {\text{Other Notations}}}$ ${\displaystyle {\text{True}}}$ ${\displaystyle 1}$ ${\displaystyle {\texttt {(}}~{\texttt {)}}}$ ${\displaystyle {\text{False}}}$ ${\displaystyle 0}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\texttt {(}}x{\texttt {)}}}$ ${\displaystyle {\text{Not}}~x}$ ${\displaystyle {\begin{matrix}x'\\{\tilde {x}}\\\lnot x\end{matrix}}}$ ${\displaystyle x~y~z}$ ${\displaystyle x~{\text{and}}~y~{\text{and}}~z}$ ${\displaystyle x\land y\land z}$ ${\displaystyle {\texttt {((}}x{\texttt {)(}}y{\texttt {)(}}z{\texttt {))}}}$ ${\displaystyle x~{\text{or}}~y~{\text{or}}~z}$ ${\displaystyle x\lor y\lor z}$ ${\displaystyle {\texttt {(}}x~{\texttt {(}}y{\texttt {))}}}$ ${\displaystyle {\begin{matrix}x~{\text{implies}}~y\\\mathrm {If} ~x~{\text{then}}~y\end{matrix}}}$ ${\displaystyle x\Rightarrow y}$ ${\displaystyle {\texttt {(}}x{\texttt {,}}y{\texttt {)}}}$ ${\displaystyle {\begin{matrix}x~{\text{not equal to}}~y\\x~{\text{exclusive or}}~y\end{matrix}}}$ ${\displaystyle {\begin{matrix}x\neq y\\x+y\end{matrix}}}$ ${\displaystyle {\texttt {((}}x{\texttt {,}}y{\texttt {))}}}$ ${\displaystyle {\begin{matrix}x~{\text{is equal to}}~y\\x~{\text{if and only if}}~y\end{matrix}}}$ ${\displaystyle {\begin{matrix}x=y\\x\Leftrightarrow y\end{matrix}}}$ ${\displaystyle {\texttt {(}}x{\texttt {,}}y{\texttt {,}}z{\texttt {)}}}$ ${\displaystyle {\begin{matrix}{\text{Just one of}}\\x,y,z\\{\text{is false}}.\end{matrix}}}$ ${\displaystyle {\begin{array}{l}x'y~z~~~\lor \\x~y'z~~~\lor \\x~y~z'\end{array}}}$ ${\displaystyle {\texttt {((}}x{\texttt {),(}}y{\texttt {),(}}z{\texttt {))}}}$ ${\displaystyle {\begin{matrix}{\text{Just one of}}\\x,y,z\\{\text{is true}}.\\[5pt]{\text{Partition all}}\\{\text{into}}~x,y,z.\end{matrix}}}$ ${\displaystyle {\begin{array}{l}x~y'z'~~\lor \\x'y~z'~~\lor \\x'y'z\end{array}}}$ ${\displaystyle {\begin{matrix}{\texttt {((}}x{\texttt {,}}y{\texttt {),}}z{\texttt {)}}\\&\\{\texttt {(}}x{\texttt {,(}}y{\texttt {,}}z{\texttt {))}}\end{matrix}}}$ ${\displaystyle {\begin{matrix}{\text{Oddly many of}}\\x,y,z\\{\text{are true}}.\end{matrix}}}$ ${\displaystyle {\begin{array}{l}x+y+z\\[5pt]x~y~z~~~\lor \\x~y'z'~~\lor \\x'y~z'~~\lor \\x'y'z\end{array}}}$ ${\displaystyle {\texttt {(}}w{\texttt {,(}}x{\texttt {),(}}y{\texttt {),(}}z{\texttt {))}}}$ ${\displaystyle {\begin{matrix}{\text{Partition}}~w\\{\text{into}}~x,y,z.\\[5pt]{\text{Genus}}~w~{\text{comprises}}\\{\text{species}}~x,y,z.\end{matrix}}}$ ${\displaystyle {\begin{array}{l}w'x'y'z'~~\lor \\w~x~y'z'~~\lor \\w~x'y~z'~~\lor \\w~x'y'z\end{array}}}$

All other propositional connectives can be obtained through combinations of these two forms. Strictly speaking, the concatenation form is dispensable in light of the bracket form, but it is convenient to maintain it as an abbreviation for more complicated bracket expressions. While working with expressions solely in propositional calculus, it is easiest to use plain parentheses for logical connectives. In contexts where parentheses are needed for other purposes “teletype” parentheses ${\displaystyle {\texttt {(}}\ldots {\texttt {)}}}$ or barred parentheses ${\displaystyle (\!|\ldots |\!)}$ may be used for logical operators.

The briefest expression for logical truth is the empty word, abstractly denoted ${\displaystyle {\boldsymbol {\varepsilon }}}$ or ${\displaystyle {\boldsymbol {\lambda }}}$ in formal languages, where it forms the identity element for concatenation. It may be given visible expression in this context by means of the logically equivalent form ${\displaystyle {\texttt {((}}~{\texttt {))}},}$ or, especially if operating in an algebraic context, by a simple ${\displaystyle 1.}$ Also when working in an algebraic mode, the plus sign ${\displaystyle {+}}$ may be used for exclusive disjunction. For example, we have the following paraphrases of algebraic expressions:

 ${\displaystyle {\begin{matrix}x+y~=~{\texttt {(}}x{\texttt {,}}y{\texttt {)}}\\[6pt]x+y+z~=~{\texttt {((}}x{\texttt {,}}y{\texttt {),}}z{\texttt {)}}~=~{\texttt {(}}x{\texttt {,(}}y{\texttt {,}}z{\texttt {))}}\end{matrix}}}$

It is important to note that the last expressions are not equivalent to the triple bracket ${\displaystyle {\texttt {(}}x{\texttt {,}}y{\texttt {,}}z{\texttt {)}}.}$