Changes

copy text from [http://www.opencycle.net/ OpenCycle] of which Jon Awbrey is the sole author
In [[logic]] and [[mathematics]], the '''minimal negation operator''' <math>\nu\!</math> is a [[multigrade operator]] <math>(\nu_{k})_{k \in \mathbb{N}}</math> where each <math>\nu_{k}\!</math> is a ''k''-ary [[boolean function]] defined in such a way that <math>\nu_{k}(x_1, \ldots , x_k) = 1</math> if and only if exactly one of the arguments <math>x_{j}</math> is 0.

In contexts where the initial letter <math>\nu\!</math> is understood, the minimal negation operators can be indicated by argument lists in parentheses. The first four members of this family of operators are shown below, with paraphrases in a couple of other notations, where tildes and primes, respectively, indicate logical negation.

: <math>\begin{matrix}
(\ ) & = & 0 & = & \mbox{false} \\
(x) & = & \tilde{x} & = & x' \\
(x, y) & = & \tilde{x}y \lor x\tilde{y} & = & x'y \lor xy' \\
(x, y, z) & = & \tilde{x}yz \lor x\tilde{y}z \lor xy\tilde{z} & = & x'yz \lor xy'z \lor xyz'
\end{matrix}</math>

It may also be noted that <math>(x, y)\!</math> is the same function as <math>x + y\!</math> and <math>x \ne y</math>, and that the inclusive disjunctions indicated for <math>(x, y)\!</math> and for <math>(x, y, z)\!</math> may be replaced with exclusive disjunctions without affecting the meaning, because the terms disjoined are already disjoint. However, the function <math>(x, y, z)\!</math> is not the same thing as the function <math>x + y + z\!</math>.

The minimal negation operator ('''mno''') has a legion of aliases: ''logical boundary operator'', ''[[limen|limen operator]]'', ''threshold operator'', or ''least action operator'', to name but a few. The rationale for these names is visible in the [[venn diagram]]s of the corresponding operations on [[set]]s.

The next section discusses two ways of visualizing the operation of minimal negation operators. A few bits of terminology will be needed as a language for talking about the pictures, but the formal details are tedious reading, and may already be familiar to many. As a result, the full definitions of the terms marked in '''bold''' are relegated to a Glossary at the end of the article.

==Truth tables==

Table 1 is a [[truth table]] for the sixteen boolean functions of type f&nbsp;:&nbsp;'''B'''<sup>3</sup>&nbsp;&rarr;&nbsp;'''B''', each of which is either a boundary of a point in '''B'''<sup>3</sup> or the complement of such a boundary.

{| align="center" border="1" cellpadding="4" cellspacing="0" style="background:paleturquoise; font-weight:bold; text-align:center; width:80%"
|+ Table 1. Logical Boundaries and Their Complements
| width="20%" | L<sub>1</sub>
| width="20%" | L<sub>2</sub>
| width="20%" | L<sub>3</sub>
| width="20%" | L<sub>4</sub>
|-
| Decimal
| Binary
| Sequential
| Parenthetical
|-
| &nbsp;
| align="right" | p =
| 1 1 1 1 0 0 0 0
| &nbsp;
|-
| &nbsp;
| align="right" | q =
| 1 1 0 0 1 1 0 0
| &nbsp;
|-
| &nbsp;
| align="right" | r =
| 1 0 1 0 1 0 1 0
| &nbsp;
|}
{| align="center" border="1" cellpadding="4" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:80%"
|-
| width="20%" | f<sub>104</sub>
| width="20%" | f<sub>01101000</sub>
| width="20%" | 0 1 1 0 1 0 0 0
| width="20%" | ( p , q , r )
|-
| f<sub>148</sub> || f<sub>10010100</sub> || 1 0 0 1 0 1 0 0 || ( p , q , (r))
|-
| f<sub>146</sub> || f<sub>10010010</sub> || 1 0 0 1 0 0 1 0 || ( p , (q), r )
|-
| f<sub>97</sub> || f<sub>01100001</sub> || 0 1 1 0 0 0 0 1 || ( p , (q), (r))
|-
| f<sub>134</sub> || f<sub>10000110</sub> || 1 0 0 0 0 1 1 0 || ((p), q , r )
|-
| f<sub>73</sub> || f<sub>01001001</sub> || 0 1 0 0 1 0 0 1 || ((p), q , (r))
|-
| f<sub>41</sub> || f<sub>00101001</sub> || 0 0 1 0 1 0 0 1 || ((p), (q), r )
|-
| f<sub>22</sub> || f<sub>00010110</sub> || 0 0 0 1 0 1 1 0 || ((p), (q), (r))
|}
{| align="center" border="1" cellpadding="4" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:80%"
|-
| width="20%" | f<sub>233</sub>
| width="20%" | f<sub>11101001</sub>
| width="20%" | 1 1 1 0 1 0 0 1
| width="20%" | (((p), (q), (r)))
|-
| f<sub>214</sub> || f<sub>11010110</sub> || 1 1 0 1 0 1 1 0 || (((p), (q), r ))
|-
| f<sub>182</sub> || f<sub>10110110</sub> || 1 0 1 1 0 1 1 0 || (((p), q , (r)))
|-
| f<sub>121</sub> || f<sub>01111001</sub> || 0 1 1 1 1 0 0 1 || (((p), q , r ))
|-
| f<sub>158</sub> || f<sub>10011110</sub> || 1 0 0 1 1 1 1 0 || (( p , (q), (r)))
|-
| f<sub>109</sub> || f<sub>01101101</sub> || 0 1 1 0 1 1 0 1 || (( p , (q), r ))
|-
| f<sub>107</sub> || f<sub>01101011</sub> || 0 1 1 0 1 0 1 1 || (( p , q , (r)))
|-
| f<sub>151</sub> || f<sub>10010111</sub> || 1 0 0 1 0 1 1 1 || (( p , q , r ))
|}
<br>

==Charts and graphs==

Two common ways of visualizing the space '''B'''<sup>''k''</sup> of 2<sup>''k''</sup> points are the [[hypercube]] picture and the [[venn diagram]] picture. Depending on how literally or figuratively one regards these pictures, each point of '''B'''<sup>k</sup> is either identified with or represented by a point of the ''k''-cube and also by a cell of the venn diagram on ''k'' "circles".

In addition, each point of '''B'''<sup>k</sup> is the unique point in the '''[[fiber (mathematics)|fiber]] of truth''' <math>[|s|]</math> of a '''singular proposition''' ''s''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''', and thus it is the unique point where a '''singular conjunction''' of ''k'' '''literals''' is 1.

For example, consider two cases at opposite vertices of the cube:

* The point <math>(1, 1, \ldots , 1, 1)</math> with all 1's as coordinates is the point where the conjunction of all posited variables evaluates to 1, namely, the point where:
:: <math>x_1\ x_2\ \ldots\ x_{n-1}\ x_n = 1.</math>

* The point <math>(0, 0, \ldots , 0, 0)</math> with all 0's as coordinates is the point where the conjunction of all negated variables evaluates to 1, namely, the point where:
:: <math>(x_1)(x_2)\ldots(x_{n-1})(x_n) = 1.</math>

To pass from these limiting examples to the general case, observe that a singular proposition ''s''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''' can be given canonical expression as a conjunction of literals, <math>s = e_1 e_2 \ldots e_{k-1} e_k</math>. Then the proposition <math>\nu (e_1, e_2, \ldots, e_{k-1}, e_k)</math> is 1 on the points adjacent to the point where ''s'' is 1, and 0 everywhere else on the cube.

For example, consider the case where ''k'' = 3. Then the minimal negation operation <math>\nu (p, q, r)\!</math>, when there is no risk of confusion written more simply as <math>(p, q, r)\!</math>, has the following venn diagram:

<pre>
o-------------------------------------------------o
| |
| |
| o-------------o |
| / \ |
| / \ |
| / \ |
| / \ |
| o o |
| | P | |
| | | |
| | | |
| o---o---------o o---------o---o |
| / \`````````\ /`````````/ \ |
| / \`````````o`````````/ \ |
| / \```````/ \```````/ \ |
| / \`````/ \`````/ \ |
| o o---o-----o---o o |
| | |`````| | |
| | |`````| | |
| | Q |`````| R | |
| o o`````o o |
| \ \```/ / |
| \ \`/ / |
| \ o / |
| \ / \ / |
| o-------------o o-------------o |
| |
| |
o-------------------------------------------------o
Figure 1. (p, q, r)
</pre>

For a contrasting example, the boolean function expressed by the form <math>((p),(q),(r))\!</math> has the following venn diagram:

<pre>
o-------------------------------------------------o
| |
| |
| o-------------o |
| /```````````````\ |
| /`````````````````\ |
| /```````````````````\ |
| /`````````````````````\ |
| o```````````````````````o |
| |`````````` P ``````````| |
| |```````````````````````| |
| |```````````````````````| |
| o---o---------o```o---------o---o |
| /`````\ \`/ /`````\ |
| /```````\ o /```````\ |
| /`````````\ / \ /`````````\ |
| /```````````\ / \ /```````````\ |
| o`````````````o---o-----o---o`````````````o |
| |`````````````````| |`````````````````| |
| |`````````````````| |`````````````````| |
| |``````` Q ```````| |``````` R ```````| |
| o`````````````````o o`````````````````o |
| \`````````````````\ /`````````````````/ |
| \`````````````````\ /`````````````````/ |
| \`````````````````o`````````````````/ |
| \```````````````/ \```````````````/ |
| o-------------o o-------------o |
| |
| |
o-------------------------------------------------o
Figure 2. ((p),(q),(r))
</pre>

==Glossary of basic terms==

* A '''[[boolean domain]]''' '''B''' is a generic 2-element [[set]], say, '''B''' = {0, 1}, whose elements are interpreted as [[logical value]]s, usually but not invariably with 0 = ''false'' and ''1'' = ''true''.

* A '''[[boolean variable]]''' ''x'' is a [[variable]] that takes its value from a boolean domain, as ''x''&nbsp;&isin;&nbsp;'''B'''.

* In situations where [[boolean value]]s are interpreted as [[logical value]]s, a [[boolean-valued function]] ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;'''B''' or a [[boolean function]] ''g''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''' is frequently called a '''[[proposition]]'''.

* Given a sequence of ''k'' boolean variables, ''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''k''</sub>, each variable ''x''<sub>''j''</sub> may be treated either as a [[basis element]] of the space '''B'''<sup>''k''</sup> or as a [[coordinate projection]] ''x''<sub>''j''</sub>&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B'''.

* This means that the ''k'' objects ''x''<sub>''j''</sub> for ''j'' = 1 to ''k'' are just so many boolean functions ''x''<sub>''j''</sub>&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''' , subject to logical interpretation as a set of ''basic propositions'' that generate the complete set of <math>2^{2^k}</math> propositions over '''B'''<sup>''k''</sup>.

* A '''literal''' is one of the 2''k'' propositions ''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''k''</sub>, (''x''<sub>1</sub>),&nbsp;…,&nbsp;(''x''<sub>''k''</sub>), in other words, either a ''posited'' basic proposition ''x''<sub>''j''</sub> or a ''negated'' basic proposition (''x''<sub>''j''</sub>), for some ''j'' = 1 to ''k''.

* In mathematics generally, the '''[[fiber (mathematics)|fiber]]''' of a point ''y'' under a function ''f''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;''Y'' is defined as the inverse image <math>f^{-1}(y)</math>.

* In the case of a boolean function ''f''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''', there are just two fibers:
** The fiber of 0 under ''f'', defined as <math>f^{-1}(0)</math>, is the set of points where ''f'' is 0.
** The fiber of 1 under ''f'', defined as <math>f^{-1}(1)</math>, is the set of points where ''f'' is 1.

* When 1 is interpreted as the logical value ''true'', then <math>f^{-1}(1)</math> is called the '''fiber&nbsp;of&nbsp;truth''' in the proposition ''f''. Frequent mention of this fiber makes it useful to have a shorter way of referring to it. This leads to the definition of the notation <math>[|f|] = f^{-1}(1)\!</math> for the fiber of truth in the proposition ''f''.

* A '''singular boolean function''' ''s''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''' is a boolean function whose fiber of 1 is a single point of '''B'''<sup>''k''</sup>.

* In the interpretation where 1 equals ''true'', a singular boolean function is called a '''singular proposition'''.

* Singular boolean functions and singular propositions serve as functional or logical representatives of the points in '''B'''<sup>''k''</sup>.

* A '''singular conjunction''' in '''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''' is a conjunction of ''k'' literals that includes just one conjunct of the pair <math>\{ x_j,\ \nu (x_j) \}</math> for each ''j'' = 1 to ''k''.

* A singular proposition ''s''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;→&nbsp;'''B''' can be expressed as a singular conjunction:
<br>
:{|
|
| <math>s\ \ =\ e_1 e_2 \ldots e_{k-1} e_k</math>,
|-
| where
| <math>e_j\ =\ x_j\!</math>
|-
| or
| <math>e_j\ =\ \nu (x_j)\!</math>,
|-
| for
| <math>j\ \ =\ 1\ \mbox{to}\ k</math>.
|}

==See also==

{|
| valign=top |
* [[Ampheck]]
* [[Anamnesis]]
* [[BACD]]
* [[George Boole|Boole, George]]
* [[Boolean algebra]]
* [[Boolean function]]
* [[Boolean logic]]
* [[Boolean-valued function]]
| valign=top |
* [[Continuous predicate]]
* [[Differentiable manifold]]
* [[Differential topology]]
* [[Dynamical system]]
* [[Exclusive disjunction]]
* [[Gottfried Leibniz|Leibniz, G.W.]]
* [[Logical connective]]
* [[Logical graph]]
| valign=top |
* [[Meno]]
* [[Multigrade operator]]
* [[Parametric operator]]
* [[Charles Sanders Peirce|Peirce, C.S.]]
* [[Sole sufficient operator]]
* [[Truth table]]
* [[Universal algebra]]
* [[Zeroth order logic]]
|}

==External links==

* [http://atlas.wolfram.com/ Wolfram Atlas of Simple Programs]
** [http://atlas.wolfram.com/01/01/ ECARs (Elementary Cellular Automata Rules)]
** [http://atlas.wolfram.com/01/01/rulelist.html ECAR Index]
** [http://atlas.wolfram.com/01/01/views/3/TableView.html ECAR Rule Icons]
** [http://atlas.wolfram.com/01/01/views/87/TableView.html ECAR Examples]
** [http://atlas.wolfram.com/01/01/views/172/TableView.html ECAR Boolean Forms]
12,080

edits