12,080
edits
Changes
Directory:Jon Awbrey/Papers/Differential Logic : Introduction (view source)
Revision as of 03:28, 30 June 2009
, 03:28, 30 June 2009→Cactus Language for Propositional Logic: + previous intro
===Cactus Language for Propositional Logic===
===Cactus Language for Propositional Logic===
'''''NOTE.''' This section is currently under construction. In the meantime, see [[Logical Graph]].''
Table 1 outlines a notation for propositional calculus based on two types of logical connectives, both of variable <math>k\!</math>-ary scope.
{| 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.
|-
| A concatenation of propositional expressions in the form <math>e_1\ e_2\ \ldots\ e_{k-1}\ e_k</math> indicates 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.
|}
All other propositional connectives can be obtained in a very efficient style of representation through combinations of these two forms. Strictly speaking, the concatenation form is dispensable in light of the bracketed form, but it is convenient to maintain it as an abbreviation of 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 ordinary parentheses are needed for other purposes an alternate typeface <math>\texttt{(} \ldots \texttt{)}</math> may be used for logical operators.
The briefest 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 this text, 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 bracket expressions:
{| align="center" cellpadding="6" style="text-align:center"
|
<math>\begin{matrix}
x + y
& = &
\texttt{(} x, y \texttt{)}
\end{matrix}</math>
|-
|
<math>\begin{matrix}
x + y + z
& = &
\texttt{((} x, y \texttt{)}, z \texttt{)}
& = &
\texttt{(} x, \texttt{(} y, z \texttt{))}
\end{matrix}</math>
|}
It is important to note that the last expressions are not equivalent to the triple bracket <math>\texttt{(} x, y, z \texttt{)}.</math>
<br>
{| align="center" border="1" cellpadding="6" 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>
|- style="background:#f0f0ff"
| <math>\text{Expression}\!</math>
| <math>\text{Interpretation}\!</math>
| <math>\text{Other Notations}\!</math>
|-
| <math>~</math>
| <math>\operatorname{True}</math>
| <math>1\!</math>
|-
| <math>(~)</math>
| <math>\operatorname{False}</math>
| <math>0\!</math>
|-
| <math>x\!</math>
| <math>x\!</math>
| <math>x\!</math>
|-
| <math>(x)\!</math>
| <math>\operatorname{Not}\ x</math>
|
<math>\begin{matrix}
x' \\
\tilde{x} \\
\lnot x \\
\end{matrix}</math>
|-
| <math>x\ y\ z</math>
| <math>x\ \operatorname{and}\ y\ \operatorname{and}\ z</math>
| <math>x \land y \land z</math>
|-
| <math>((x)(y)(z))\!</math>
| <math>x\ \operatorname{or}\ y\ \operatorname{or}\ z</math>
| <math>x \lor y \lor z</math>
|-
| <math>(x\ (y))\!</math>
|
<math>\begin{matrix}
x\ \operatorname{implies}\ y \\
\operatorname{If}\ x\ \operatorname{then}\ y \\
\end{matrix}</math>
| <math>x \Rightarrow y\!</math>
|-
| <math>(x, y)\!</math>
|
<math>\begin{matrix}
x\ \operatorname{not~equal~to}\ y \\
x\ \operatorname{exclusive~or}\ y \\
\end{matrix}</math>
|
<math>\begin{matrix}
x \neq y \\
x + y \\
\end{matrix}</math>
|-
| <math>((x, y))\!</math>
|
<math>\begin{matrix}
x\ \operatorname{is~equal~to}\ y \\
x\ \operatorname{if~and~only~if}\ y \\
\end{matrix}</math>
|
<math>\begin{matrix}
x = y \\
x \Leftrightarrow y \\
\end{matrix}</math>
|-
| <math>(x, y, z)\!</math>
|
<math>\begin{matrix}
\operatorname{Just~one~of} \\
x, y, z \\
\operatorname{is~false}. \\
\end{matrix}</math>
|
<math>\begin{matrix}
x'y~z~ & \lor \\
x~y'z~ & \lor \\
x~y~z' & \\
\end{matrix}</math>
|-
| <math>((x),(y),(z))\!</math>
|
<math>\begin{matrix}
\operatorname{Just~one~of} \\
x, y, z \\
\operatorname{is~true}. \\
& \\
\operatorname{Partition~all} \\
\operatorname{into}\ x, y, z. \\
\end{matrix}</math>
|
<math>\begin{matrix}
x~y'z' & \lor \\
x'y~z' & \lor \\
x'y'z~ & \\
\end{matrix}</math>
|-
|
<math>\begin{matrix}
((x, y), z) \\
& \\
(x, (y, z)) \\
\end{matrix}</math>
|
<math>\begin{matrix}
\operatorname{Oddly~many~of} \\
x, y, z \\
\operatorname{are~true}. \\
\end{matrix}</math>
|
<p><math>x + y + z\!</math></p>
<br>
<p><math>\begin{matrix}
x~y~z~ & \lor \\
x~y'z' & \lor \\
x'y~z' & \lor \\
x'y'z~ & \\
\end{matrix}</math></p>
|-
| <math>(w, (x),(y),(z))\!</math>
|
<math>\begin{matrix}
\operatorname{Partition}\ w \\
\operatorname{into}\ x, y, z. \\
& \\
\operatorname{Genus}\ w\ \operatorname{comprises} \\
\operatorname{species}\ x, y, z. \\
\end{matrix}</math>
|
<math>\begin{matrix}
w'x'y'z' & \lor \\
w~x~y'z' & \lor \\
w~x'y~z' & \lor \\
w~x'y'z~ & \\
\end{matrix}</math>
|}
<br>
In this style of graphical representation, the value <math>\operatorname{true}</math> looks like a blank label and the value <math>\operatorname{false}</math> looks like an edge.
In this style of graphical representation, the value <math>\operatorname{true}</math> looks like a blank label and the value <math>\operatorname{false}</math> looks like an edge.