Difference between revisions of "Minimal negation operator"

A minimal negation operator  is a logical connective that says “just one false” of its logical arguments.

If the list of arguments is empty, as expressed in the form  then it cannot be true that exactly one of the arguments is false, so 

If  is the only argument, then  says that  is false, so  expresses the logical negation of the proposition  Wrtten in several different notations, 

If  and  are the only two arguments, then  says that exactly one of  is false, so  says the same thing as  Expressing  in terms of ands  ors  and nots  gives the following form.

 

As usual, one drops the dots  in contexts where they are understood, giving the following form.

 

The venn diagram for  is shown in Figure 1.

 

The venn diagram for  is shown in Figure 2.

 

The center cell is the region where all three arguments  hold true, so  holds true in just the three neighboring cells. In other words, 

Initial definition

The minimal negation operator  is a multigrade operator  where each  is a -ary boolean function defined in such a way that  in just those cases where exactly one of the arguments  is 

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,  = 

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.

 

Formal definition

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

Definition. Let the function  be defined for each integer  in the interval  by the following equation:

 

Then  is defined by the following equation:

 

If we think of the point  as indicated by the boolean product  or the logical conjunction  then the minimal negation  indicates the set of points in  that differ from  in exactly one coordinate. This makes  a discrete functional analogue of a point omitted neighborhood 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 variety of other names for the same concept, for example, logical boundary operator, limen operator, least action operator, or hedge operator, to name but a few. The rationale for these names is visible in the venn diagrams 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  is interpreted so that  and  This has the following consequences:

 • The operation  is a function equivalent to the exclusive disjunction of  and  while its fiber of 1 is the relation of inequality between  and  • The operation  maps the bit sequence  to its parity.

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

 • The function  is the same as that associated with the operation  and the relation  • In contrast,  is not identical to  • More generally, the function  for  is not identical to the boolean sum  • The inclusive disjunctions indicated for the  of more than one argument may be replaced with exclusive disjunctions without affecting the meaning, since the terms disjoined are already disjoint.

Truth tables

Table 3 is a truth table for the sixteen boolean functions of type  whose fibers of 1 are either the boundaries of points in  or the complements of those boundaries.

                  

Charts and graphs

This Section 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 italics are relegated to a Glossary at the end of the article.

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

In addition, each point of  is the unique point in the fiber of truth  of a singular proposition  and thus it is the unique point where a singular conjunction of  literals is 

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

 • The point  with all 1's as coordinates is the point where the conjunction of all posited variables evaluates to  namely, the point where:  • The point  with all 0's as coordinates is the point where the conjunction of all negated variables evaluates to  namely, the point where: 

To pass from these limiting examples to the general case, observe that a singular proposition  can be given canonical expression as a conjunction of literals, . Then the proposition  is  on the points adjacent to the point where  is  and 0 everywhere else on the cube.

For example, consider the case where  Then the minimal negation operation  — written more simply as  — has the following venn diagram:

 

For a contrasting example, the boolean function expressed by the form  has the following venn diagram:

 

Glossary of basic terms

Boolean domain
A boolean domain  is a generic 2-element set, for example,  whose elements are interpreted as logical values, usually but not invariably with  and 
Boolean variable
A boolean variable  is a variable that takes its value from a boolean domain, as 
Proposition
In situations where boolean values are interpreted as logical values, a boolean-valued function  or a boolean function  is frequently called a proposition.
Basis element, Coordinate projection
Given a sequence of  boolean variables,  each variable  may be treated either as a basis element of the space  or as a coordinate projection 
Basic proposition
This means that the set of objects  is a set of boolean functions  subject to logical interpretation as a set of basic propositions that collectively generate the complete set of  propositions over 
Literal
A literal is one of the  propositions  in other words, either a posited basic proposition  or a negated basic proposition  for some 
Fiber
In mathematics generally, the fiber of a point  under a function  is defined as the inverse image 
In the case of a boolean function  there are just two fibers:
The fiber of  under  defined as  is the set of points where the value of  is 
The fiber of  under  defined as  is the set of points where the value of  is 
Fiber of truth
When  is interpreted as the logical value  then  is called the fiber of truth in the proposition  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  for the fiber of truth in the proposition 
Singular boolean function
A singular boolean function  is a boolean function whose fiber of  is a single point of 
Singular proposition
In the interpretation where  equals  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 
Singular conjunction
A singular conjunction in  is a conjunction of  literals that includes just one conjunct of the pair  for each 
A singular proposition  can be expressed as a singular conjunction:
 , 

Syllabus

Related topics

 Logical graph Minimal negation operator Multigrade operator Parametric operator Peirce's law

Document history

Portions of the above article were adapted from the following sources under the GNU Free Documentation License, under other applicable licenses, or by permission of the copyright holders.