Definition:Minimal Negation Operator

From ProofWiki
Jump to navigation Jump to search


Let $\Bbb B$ be a Boolean domain:

$\Bbb B = \set {\F, \T}$

The minimal negation operator $\nu$ is a multiary operator:

$\nu_k: \Bbb B^k \to \Bbb B$


$k \in \N$ is a natural number
$\nu_k$ is a boolean function defined as:
$\map {\nu_k} {x_1, x_2, \ldots, x_k} = \begin {cases}

\T & : \exists! x_j \in \set {x_1, x_2, \ldots, x_k}: x_j = \F \\ \F & : \text {otherwise} \end{cases}$

That is:

$\map {\nu_k} {x_1, x_2, \ldots, x_k}$ is true if and only if exactly one of its arguments is false.


The symbol $\nu$ used for this is the Greek letter nu.


Expressed in disjunctive normal form, the first few instances of $\nu_k$ are as follows:

\(\ds \nu_0\) \(=\) \(\ds \F\)
\(\ds \map {\nu_1} p\) \(=\) \(\ds \neg p\)
\(\ds \map {\nu_2} {p, q}\) \(=\) \(\ds \paren {\neg p \land q} \lor \paren {p \land \neg q}\)
\(\ds \map {\nu_3} {p, q, r}\) \(=\) \(\ds \paren {\neg p \land q \land r} \lor \paren {p \land \neg q \land r} \lor \paren {p \land q \land \neg r}\)
\(\ds \map {\nu_4} {p, q, r, s}\) \(=\) \(\ds \paren {\neg p \land q \land r \land s} \lor \paren {p \land \neg q \land r \land s} \lor \paren {p \land q \land \neg r \land s} \lor \paren {p \land q \land r \land \neg s}\)

Example: $\nu_0$

$\nu_0$ is the false constant, or the contradiction operator $\bot$:

$\nu_0 = \bot$

Example: $\nu_1$

$\nu_1$ is the same operator as the logical not operator $\neg$:

$\map {\nu_1} p = \neg p$

Example: $\nu_2$

$\nu_2$ is the same operator as the exclusive or operator $\oplus$:

$\map {\nu_2} {p, q} = p \oplus q$

For $k > 2$ there is no immediate correspondence between $\nu_k$ and conventional logical operators.

Also see

  • Results about the minimal negation operator can be found here.