Minimal_Negation

Minimal_Negation_Operator 2007-04-07T19:16:24Z Proteus fmt boiler   In [[logic]] and [[mathematics]], the '''minimal negation operator''' ν is a [[multigrade operator]] (ν''k'')''k''∈'''N''' where each ν''k'' is a ''k''-ary [[boolean function]] defined in such a way that ν''k''(''x''1, …, ''x''''k'') = 1 if and only if exactly one of the arguments ''x''''j'' is 0. In contexts where the initial letter ν 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'' : '''B'''3 → '''B''', each of which is either a boundary of a point in '''B'''3 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%" | L1 | width="20%" | L2 | width="20%" | L3 | width="20%" | L4 |- | Decimal | Binary | Sequential | Parenthetical |- |   | align="right" | p = | 1 1 1 1 0 0 0 0 |   |- |   | align="right" | q = | 1 1 0 0 1 1 0 0 |   |- |   | align="right" | r = | 1 0 1 0 1 0 1 0 |   |} {| align="center" border="1" cellpadding="4" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:80%" |- | width="20%" | f104 | width="20%" | f01101000 | width="20%" | 0 1 1 0 1 0 0 0 | width="20%" | ( p , q , r ) |- | f148 || f10010100 || 1 0 0 1 0 1 0 0 || ( p , q , (r)) |- | f146 || f10010010 || 1 0 0 1 0 0 1 0 || ( p , (q), r ) |- | f97 || f01100001 || 0 1 1 0 0 0 0 1 || ( p , (q), (r)) |- | f134 || f10000110 || 1 0 0 0 0 1 1 0 || ((p), q , r ) |- | f73 || f01001001 || 0 1 0 0 1 0 0 1 || ((p), q , (r)) |- | f41 || f00101001 || 0 0 1 0 1 0 0 1 || ((p), (q), r ) |- | f22 || f00010110 || 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%" | f233 | width="20%" | f11101001 | width="20%" | 1 1 1 0 1 0 0 1 | width="20%" | (((p), (q), (r))) |- | f214 || f11010110 || 1 1 0 1 0 1 1 0 || (((p), (q), r )) |- | f182 || f10110110 || 1 0 1 1 0 1 1 0 || (((p), q , (r))) |- | f121 || f01111001 || 0 1 1 1 1 0 0 1 || (((p), q , r )) |- | f158 || f10011110 || 1 0 0 1 1 1 1 0 || (( p , (q), (r))) |- | f109 || f01101101 || 0 1 1 0 1 1 0 1 || (( p , (q), r )) |- | f107 || f01101011 || 0 1 1 0 1 0 1 1 || (( p , q , (r))) |- | f151 || f10010111 || 1 0 0 1 0 1 1 1 || (( p , q , r )) |} ==Charts and graphs== Two common ways of visualizing the space '''B'''''k'' of 2''k'' points are the [[hypercube]] picture and the [[venn diagram]] picture. Depending on how literally or figuratively one regards these pictures, each point of '''B'''''k'' 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'''''k'' is the unique point in the '''[[fiber (mathematics)|fiber]] of truth''' <math>[|s|]</math> of a '''singular proposition''' ''s'' : '''B'''''k'' → '''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 whose coordinates are all 1 is the unique point where the conjunction of all posited variables is 1, namely, the point where: :: ''x''1 ''x''2 … ''x''''n''–1 ''x''''n'' = 1. * The point whose coordinates are all 0 is the unique point where the conjunction of all negated variables is 1, namely, the point where: ::(''x''1)(''x''2)…(''x''''n''–1)(''x''''n'') = 1. To pass from these limiting examples to the general case, observe that a singular proposition ''s'' : '''B'''''k'' → '''B''' can be given canonical expression as a conjunction of literals, ''s'' = ''e''1 ''e''2 … ''e''''k''–1 ''e''''k''. Then the proposition ν(''e''1, ''e''2, …, ''e''''k''–1, ''e''''k'') 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 ν(p, q, r), when there is no risk of confusion written more simply as <math>(p, q, r)</math>, has the following venn diagram: 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) For a contrasting example, the boolean function expressed by the form <math>((p),(q),(r))</math> has the following Venn diagram: 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)) ==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'' ∈ '''B'''. * In situations where [[boolean value]]s are interpreted as [[logical value]]s, a [[boolean-valued function]] ''f'' : ''X'' → '''B''' or a [[boolean function]] ''g'' : '''B'''''k'' → '''B''' is frequently called a '''[[proposition]]'''. * Given a sequence of ''k'' boolean variables, ''x''1, …, ''x''''k'', each variable ''x''''j'' may be treated either as a [[basis element]] of the space '''B'''''k'' or as a [[coordinate projection]] ''x''''j'' : '''B'''''k'' → '''B'''. * This means that the ''k'' objects ''x''''j'' for ''j'' = 1 to ''k'' are just so many boolean functions ''x''''j'' : '''B'''''k'' → '''B''' , subject to logical interpretation as a set of ''basic propositions'' that generate the complete set of 22''k'' propositions over '''B'''''k''. * A '''literal''' is one of the 2''k'' propositions ''x''1, …, ''x''''k'', (''x''1), …, (''x''''k''), in other words, either a ''posited'' basic proposition ''x''''j'' or a ''negated'' basic proposition (''x''''j''), for some ''j'' = 1 to ''k''. * In mathematics generally, the '''[[fiber (mathematics)|fiber]]''' of a point ''y'' under a function ''f'' : ''X'' → ''Y'' is defined as the inverse image ''f''–1(''y''). * In the case of a boolean function ''f'' : '''B'''''k'' → '''B''', there are just two fibers: ** The fiber of 0 under ''f'', defined as ''f''–1(0), is the set of points where ''f'' is 0. ** The fiber of 1 under ''f'', defined as ''f''–1(1), is the set of points where ''f'' is 1. * When 1 is interpreted as the logical value ''true'', then ''f''–1(1) is called the '''fiber of 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 <nowiki>[|</nowiki>''f''<nowiki>|]</nowiki> = ''f''–1(1) for the fiber of truth in the proposition ''f''. * A '''singular boolean function''' ''s'' : '''B'''''k'' → '''B''' is a boolean function whose fiber of 1 is a single point of '''B'''''k''. * 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'''''k''. * A '''singular conjunction''' in '''B'''''k'' → '''B''' is a conjunction of ''k'' literals that includes just one conjunct of the pair {''x''''j'', ν(''x''''j'')} for each ''j'' = 1 to ''k''. * A singular proposition ''s'' : '''B'''''k'' → '''B''' can be expressed as a singular conjunction: {| style="width:50%" | width="10%" |   | width="10%" |   | width="5%" | ''s'' | width="5%" | = | width="20%" | ''e''1 ''e''2 … ''e''''k''–1 ''e''''k'', |- |   | where | ''e''''j'' | = | ''x''''j'' |- |   | or | ''e''''j'' | = | ν(''x''''j''), |- |   | for | ''j'' | = | 1 to ''k''. |} ==References== ==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] [[Image:Minimal negation operator 1.png|thumb|none|Figure 1. Region indicated by (p, q, r) is shaded]] [[Image:Minimal negation operator 2.png|thumb|none|Figure 2. Region indicated by ((p),(q),(r)) is shaded]]  ---- ''Some content adapted from the [[Wikinfo]] article "[http://getwiki.net/url.php?wikinfo=Minimal_negation_operator Minimal negation operator]" under the [[GNU Free Documentation License]].''