minimal negation operator


\PMlinkescapephrase

primes \PMlinkescapephrasePrimes \PMlinkescapephrasesingular \PMlinkescapephraseSingular

The minimal negation operator ν is a multigrade operator (νk)k where each νk is a k-ary boolean functionMathworldPlanetmath defined in such a way that νk(x1,,xk)=1 in just those cases where exactly one of the arguments xj is 0.

In contexts where the initial letter ν is understood, the minimal negation operators can be indicated by argument lists in parentheses. In the following text a distinctive typeface will be used for logical expressions based on minimal negation operators, for example, (x, y, z) = ν(x,y,z).

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 negationMathworldPlanetmath.

()=ν0=0=false(x)=ν1(x)=x~=x(x, y)=ν2(x,y)=x~yxy~=xyxy(x, y, z)=ν3(x,y,z)=x~yzxy~zxyz~=xyzxyzxyz

To express the general case of νk in terms of familiar operationsMathworldPlanetmath, it helps to introduce an intermediary concept:

Definition. Let the function ¬j:𝔹k𝔹 be defined for each integer j in the interval [1,k] by the following equation:

¬j(x1,,xj,,xk)=x1xj-1¬xjxj+1xk.

Then νk:𝔹k𝔹 is defined by the following equation:

νk(x1,,xk)=¬1(x1,,xk)¬j(x1,,xk)¬k(x1,,xk).

If we think of the point x=(x1,,xk)𝔹k as indicated by the boolean productMathworldPlanetmathPlanetmathPlanetmath x1xk or the logical conjunction x1xk, then the minimalPlanetmathPlanetmath negation (x1,,xk) indicates the set of points in 𝔹k that differ from x in exactly one coordinate. This makes (x1,,xk) a discrete functionalMathworldPlanetmathPlanetmathPlanetmath analogue of a point omitted neighborhoodMathworldPlanetmath in analysis, more exactly, a point omitted distance one neighborhood. In this light, the minimal negation operator can be recognized as a differential construction, an observation that opens a very wide field. It also serves to explain a varietyMathworldPlanetmathPlanetmath of other names for the same concept, for example, logical boundary operatorMathworldPlanetmath, limen operator, least action operator, or hedge operator, to name but a few. The rationale for these names is visible in the venn diagramsMathworldPlanetmath of the corresponding operations on sets.

The remainder of this discussion proceeds on the algebraic boolean convention that the plus sign (+) and the summation symbol () both refer to addition modulo 2. Unless otherwise noted, the boolean domain 𝔹={0,1} is interpreted so that 0=false and 1=true. This has the following consequences:

The following properties of the minimal negation operators νk:𝔹k𝔹 may be noted:

  • The function (x, y) is the same as that associated with the operation x+y and the relation xy.

  • In contrast, (x, y, z) is not identical to x+y+z.

  • More generally, the function νk(x1,,xk) for k>2 is not identical to the boolean sum j=1kxj.

  • The inclusive disjunctions indicated for the νk of more than one argument may be replaced with exclusive disjunctions without affecting the meaning, since the terms disjoined are already disjoint.

1 Truth tables

Table 1 is a truth tableMathworldPlanetmath for the sixteen boolean functions of type f:𝔹3𝔹, each of which is either a boundary of a point in 𝔹3 or the complement of such a boundary.

Table 1. Logical Boundaries and Their Complements
L1 L2 L3 L4
Decimal Binary Sequential Parenthetical
p= 1 1 1 1 0 0 0 0
q= 1 1 0 0 1 1 0 0
r= 1 0 1 0 1 0 1 0
f104 f01101000 0 1 1 0 1 0 0 0 ( 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))
f233 f11101001 1 1 1 0 1 0 0 1 (((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 ))

2 Charts and graphs

This SectionPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath focuses on visual representations of minimal negation operators. A few bits of terminology are useful in describing the pictures, but the formal details are tedious reading, and may be familiar to many readers, so the full definitions of the terms marked in bold are relegated to a Glossary at the end of the article.

Two ways of visualizing the space 𝔹k of 2k points are the hypercube picture and the venn diagram picture. The hypercube picture associates each point of 𝔹k with a unique point of the k-dimensional hypercube. The venn diagram picture associates each point of 𝔹k with a unique ”cell” of the venn diagram on k ”circles”.

In addition, each point of 𝔹k is the unique point in the fiber of truth [|s|] of a singular propositionPlanetmathPlanetmathPlanetmath s:𝔹k𝔹, and thus it is the unique point where a singular conjunctionMathworldPlanetmath of k literalsMathworldPlanetmath is equal to 1.

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

  • The point (1,1,,1,1) with all 1’s as coordinates is the point where the conjunction of all posited variablesMathworldPlanetmath evaluates to 1, namely, the point where:

    x1x2xk-1xk=1
  • The point (0,0,,0,0) with all 0’s as coordinates is the point where the conjunction of all negated variables evaluates to 1, namely, the point where:

    (x1)(x2)(xk-1)(xk)=1

To pass from these limiting examples to the general case, observe that a singular proposition s:𝔹k𝔹 can be given canonical expression as a conjunction of literals, s=e1e2ek-1ek. Then the proposition ν(e1,e2,,ek-1,ek) 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) — written more simply as (p, q, r) — has the following venn diagram:

Figure 2.   (p, q, r)

For a contrasting example, the boolean function expressed by the form ((p),(q),(r)) has the following venn diagram:

Figure 3.   ((p),(q),(r))

3 Glossary of basic terms

  • A boolean domain 𝔹 is a generic 2-element set, say, 𝔹={0,1}, whose elements are interpreted as logical values, 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𝔹.

  • In situations where boolean values are interpreted as logical values, a boolean-valued function f:X𝔹 or a boolean function g:𝔹k𝔹 is frequently called a proposition.

  • Given a sequence of k boolean variables, x1,,xk, each variable xj may be treated either as a basis element of the space 𝔹k or as a coordinate projection xj:𝔹k𝔹.

  • This means that the k objects xj for j = 1 to k are just so many boolean functions xj:𝔹k𝔹, subject to logical interpretationMathworldPlanetmathPlanetmath as a set of basic propositions that generate the complete set of 22k propositions over 𝔹k.

  • A literal is one of the 2k propositions x1,,xk,(x1),,(xk), in other words, either a posited basic proposition xj or a negated basic proposition (xj), for some j = 1 to k.

  • In mathematics generally, the fiber of a point y under a function f:XY is defined as the inverse imagePlanetmathPlanetmath f-1(y).

  • In the case of a boolean-valued function f:X𝔹, 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 [|f|]=f-1(1) for the fiber of truth in the proposition f.

  • A singular boolean function s:𝔹k𝔹 is a boolean function whose fiber of 1 is a single point of 𝔹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 𝔹k.

  • A singular conjunction in (𝔹k𝔹) is a conjunction of k literals that includes just one conjunct of the pair {xj,ν(xj)} for each j = 1 to k.

  • A singular proposition s:𝔹k𝔹 can be expressed as a singular conjunction:

    s=e1e2ek-1ekwhereej=xjorej=ν(xj)forj=1tok

Title minimal negation operator
Canonical name MinimalNegationOperator
Date of creation 2013-03-22 17:48:13
Last modified on 2013-03-22 17:48:13
Owner Jon Awbrey (15246)
Last modified by Jon Awbrey (15246)
Numerical id 42
Author Jon Awbrey (15246)
Entry type Definition
Classification msc 08A70
Classification msc 08A40
Classification msc 39A70
Classification msc 39A12
Classification msc 03G05
Classification msc 03E20
Classification msc 03C05
Classification msc 03B05
Related topic DifferentialLogic
Related topic DifferentialPropositionalCalculus
Related topic DifferentialPropositionalCalculusAppendices
Related topic DifferentialPropositionalCalculusAppendix2
Related topic DifferentialPropositionalCalculusAppendix3
Related topic DifferentialPropositionalCalculusAppendix4
Related topic PropositionalCalculus
Related topic L