Cyclic Negations and Four-valuedness

Oleg Grigoriev Dmitry Zaitsev Oleg Grigoriev is supported by RFBR grant

\mathcal{N}

^o 20-011-00698.Dmitry Zaitsev’s research is conducted as a part of “Brain, cognitive systems and artificial intelligence” Lomonosov Moscow University scientific school project.Lomonosov Moscow State University
Faculty of Philosophy, Department of Logic,
Moscow, Russia [email protected] [email protected]

Abstract

We consider an example of four valued semantics partially inspired by quantum computations and negation-like operations occurred therein. In particular we consider a representation of so called square root of negation within this four valued semantics as an operation which acts like a cycling negation. We define two variants of logical matrices performing different orders over the set of truth values. Purely formal logical result of our study consists in axiomatizing the logics of defined matrices as the systems of binary consequence relation and proving correctness and completeness theorems for these deductive systems.

1 Introduction

The study of properties of negation-like connectives constitutes nowadays is a well established area of interdisciplinary research activity, including purely logical investigations (consult collective monographs [10, 19]). Negation often expresses the characteristic features of logical systems acting thereby as a mean for distinguishing and systematizing them (see, for instance, [13] for the treatment of different types of paraconsistent logics in accordance with the properties of negations introduced there). In the literature one can find examples of hierarchic structures over the sets of negations, aimed to reflect their logical properties. Probably the best known is the “kite of negations” proposed by M. Dunn in [7] and refined in the subsequent articles.

In this paper, we are not intent on providing a complete picture of some big family of negation-like operations, instead we concentrate on a particular type of negation which may be characterized as a cyclic operation over certain set of truth values. Specifically we are interested in its behaviour in the context of four-valued semantics, the breeding ground of many well known non-classical logics.

Occasionally our research was brought to life with an interest to the problematics of quantum computation and its possible representations within the semantic framework of non-classical logic. In particular the reflections on one of the most unusual quantum gates, the square root of negation, induced a unary operation on the four-element set of truth values. On the syntactic level, we defined two logical systems considerably differing from each other with respect to the set of deductive postulates but sharing “classicality” of double negation. This particular feature is inherent in some other non-classical logics ([11, 12, 15, 20, 21]).

2 Cyclic Negation in the Generalized Truth Values Setting

Our interest to studies of cyclic negation stems from the different sources. This kind of negation is primarily known in the field of Post algebras and their logics (see [16, 17]). Another origin can be found in the context of four valued semantics and corresponding logics. According to [14], the first appearance of a cyclic negation in four valued framework can be found in [18], while [14] itself deals with the property of functional completeness for the expansions of Belnap-Dunn logic. In particular Belnap-Dunn logic equipped with cyclic negation in [18] is proved to be functionally complete. In [20], two versions of cycling negation appeared under the names left and right turns as the specific operations over the set of two-component generalized truth values¹¹1For the detailed account of this kind of compound truth values see [21]., but they had not been studied there at any extent. Four-valued systems with a cyclic negation are investigated in [12] and [15]. One of the features of the negation operations studied there consists in their ability to simulate the properties of classical (as well as intuitionistic) negation via composition. It is worth noting that [11] addresses the problem of simulating conventional negations via other unary operations touching upon a cyclic negation.

2.1 Four-Valuedness and Cyclic Negation from Quantum Computations

Although this paper does not concern with quantum computations or their logic at all, some concepts from the field of quantum computational logic have inspired the four-valued semantics underlying the logics discussed below and, specifically, the choice of the unary operation acting over there. This section clarifies the origins of the family of truth values used below.

One of the ideas that motivated this paper, namely, to merge generalized truth values approach and quantum computation in a joint logical framework, was prompted by seminal writings of prominent logicians of past and present, and after all is connected with the search of answers to the question, what (modern) logic is.

The first one was proposed by G. Frege and J. Łukasiewicz many years ago and now enjoys a new lease on life within the project of generalized truth values. The core idea may be expressed in Łukasiewicz’s words – logic is the science of objects of a special kind, namely a science of logical values. Though seems strange, this understanding of logic is coherent with standard conception of logic, because the search for criteria of correct reasoning and argument immediately leads one to truth-(or, designated value-) preserving interpretation of logical inference.

Another conception of logic is due to J. van Benthem, who in [2] develops a program of Logical Dynamics, which presupposes the interpretation of logic as a theory of information-driven agency, being thus the study of explicit informational processes (inference, observation, communication). The latter interpretation may be seen as the other side of the same coin – in words of J. van Benthem, “inference is just one way of producing information, at best on a par, even for logic itself, with others” [3, p. 183], so it is little wonder that “inference and information update are intertwined” [3, p. 189].

One step away from here and just a moment to go, there is an idea to consider quantum logic as logic of quantum computation, where the latter offers a new possibility opened up by quantum gates to deal with information processing procedures being generalizations of reasoning and argument. An additional interest is connected with logical formalization of so called genuine quantum gates “that transform classical registers into quregisters that are superpositions: the square root of the negation and the square root of the identity” [5, p. 298]. According to [6] “logicians are now entitled to propose a new logical operation $\sqrt{\mathtt{NOT}}$ . Why? Because a faithful physical model for it exists in nature”.

Let us remind some key concepts of quantum computational logic (for more details see, for example, [4]). The unit of representation of quantum information is a qubit (from English “quantum bit”), $a|0\rangle+b|1\rangle$ , where $|0\rangle$ and $|1\rangle$ are vectors $\begin{pmatrix}1\\ 0\end{pmatrix}$ and $\begin{pmatrix}0\\ 1\end{pmatrix}$ , respectively, written in so called Dirac notation, while $a$ and $b$ are complex numbers, the amplitudes, expressing the probabilities.

Quantum computational logic offers a broad family of operators, quantum logic gates²²2Well known examples are cnot, toffoli, fredkin, swap gates which perform reversible computation using some qubits as control registers for governing the actions on target bit. For example, cnot negates its target bit if and only if the control bit is recognized as 1., which in some cases can be rendered as the counterparts of classical logic gates and thus give rise to a family of propositional connectives in formal languages of quantum logical systems. But quantum computations provide also examples of non-classical gates. The square root of negation is of the special interest for us. For a qubit $|\varphi\rangle=a|0\rangle+b|1\rangle$ , $\sqrt{\mathtt{NOT}}(|\varphi\rangle)=\frac{1}{2}[(1+i)a+(1-i)b]|0\rangle+\frac{1}{2}[(1-i)a+(1+i)b]|1\rangle$ , where $i$ is an imaginary unit. While $\mathtt{NOT}$ gate transforms $|1\rangle$ into $|0\rangle$ and vice versa, $\sqrt{\mathtt{NOT}}$ does only half of the work.

The key observation here is that the square root of the negation is a kind of “connective with memory”. In particular, when applied twice to Truth, it returns Falsity and vice versa. At the same time, the first application to True or False gives intermediate value. Thus, to understand where to go after the first application of the square root of the negation, one should somehow remember the point of departure. The complex nature of generalized truth values allows to yield this peculiarity by preserving the component of the initial value. For example, starting with $\bf T$ , the first application of the square root of the negation “adds” uncertainty thus producing $\bf{TU}$ ; the second application transforms it to $\bf F$ ; the third again adds $\bf U$ to $\bf F$ resulting in $\bf{FU}$ ; and finally after the fourth application we arrive at $\bf T$ . So we can see that our representation of the square root of negation within four-valued framework is nothing more then a cyclic negation.

Thus we have new set of truth values, $\{\mathbf{T},\mathbf{TU},\mathbf{FU},\mathbf{F}\}$ , and an open choice of order relation and subset of the designated values. Below we consider two natural variants of partial order over this set with the same two-element subset of designated values, $\{\mathbf{T},\mathbf{TU}\}$ . The choice of this subset seems reasonable for several reasons. It contains Truth itself (T) and the the other value (TU), having something that we would call a trace of truth. Moreover, this subset is one of the two prime filters in lattice $4\mathcal{Q}$ described below.

In this paper, we consider two propositional logics, $\mathbf{CNL_{4}^{2}}$ and $\mathbf{CNLL_{4}^{2}}$ , of four-valued matrices (with two-valued matrix filters) constructed over the set of generalized truth values inspired by quantum computations as explained above. Though these logics have much in common, they differ essentially with respect to the properties of negations and their interrelation with conjunction and disjunction.

2.2 Four-Valued Matrices

For both logics, $\mathbf{CNL_{4}^{2}}$ and $\mathbf{CNLL_{4}^{2}}$ , we subsume the same propositional language $\mathcal{L}$ of signature $\{\wedge,\vee,\neg\}$ over denumerable set of variables $PV$ with the set of complex formulas $FM$ constructed according to the standard inductive definition.

On the basis of the set $\mathscr{U}=\{\mathbf{T},\mathbf{TU},\mathbf{FU},\mathbf{F}\}$ we define two distinct matrices, $\mathcal{M}^{\mathbf{CNL_{4}^{2}}}$ and $\mathcal{M}^{\mathbf{CNLL_{4}^{2}}}$ , over this set with the same subset of designated values $\mathcal{D}=\{\mathbf{T},\mathbf{TU}\}$ and the same definition of unary operation $\mathcal{O}=\{{\sim},\wedge,\vee\}$ differing with respect to meet and join in the lattice reducts of these matrices.

Tableau definitions for the binary operations $\wedge$ and $\vee$ can be easily imported from the order relations over the set of truth values represented via Hasse diagrams, depicted in Figure 1. Evidently these ordered sets of truth values constitute two simple lattices, $4\mathcal{Q}$ (left diagram) and $4\mathcal{LQ}$ .

Definition 2.1.

$\mathcal{M}^{\mathbf{CNL_{4}^{2}}}$ matrix is a structure $\langle\mathscr{U},\{f_{\_}{c}\}_{\_}{c\in\mathcal{O}},\mathcal{D}\rangle$ , where the operations $f_{\_}{\wedge}$ and $f_{\_}{\vee}$ are defined as meet and join in $4\mathcal{Q}$ , $f_{\_}{\sim}$ is defined via the following table:

$x$	$f_{\_}{\sim}(x)$
$\mathbf{T}$	$\mathbf{TU}$
$\mathbf{TU}$	$\mathbf{F}$
$\mathbf{F}$	$\mathbf{FU}$
$\mathbf{FU}$	$\mathbf{T}$

Definition 2.2.

$\mathcal{M}^{\mathbf{CNLL_{4}^{2}}}$ matrix is a structure $\langle\mathscr{U},\{g_{\_}c\}_{\_}{c\in\mathcal{O}},\mathcal{D}\rangle$ , where the operations $g_{\_}{\wedge}$ and $g_{\_}{\vee}$ are defined as meet and join in $4\mathcal{LQ}$ , $g_{\_}{\sim}$ is defined via the same table as $f_{\_}{\sim}$ .

A valuation $v$ is a mapping $PV\mapsto\mathscr{U}$ . An extension of $v$ to the set $FM$ depends on a matrix assumed. For example, in case of $\mathcal{M}^{\mathbf{CNL_{4}^{2}}}$ we have the following expressions for all $A,B\in FM$ : $v(A\wedge B)=f_{\_}{\wedge}(v(A),v(B))$ , $v(A\vee B)=f_{\_}{\vee}(v(A),v(B))$ , $v(\neg A)=f_{\_}{\sim}(v(A))$ . Thus we have to distinguish $\mathbf{CNL_{4}^{2}}$ - and $\mathbf{CNLL_{4}^{2}}$ -valuations³³3We will avoid cumbersome subscripts like in $v_{\_}{\mathbf{CNL_{4}^{2}}}$ when possible..

The semantic consequence relation is defined via preservation of a designated truth value and again relies on a matrix assumed:

Definition 2.3.

For all $A,B\in FM$ ,

1.

$A\vDash_{\_}{\mathbf{CNL_{4}^{2}}}B\Leftrightarrow v(A)\in D\Rightarrow v(B)\in D$ , for each $\mathbf{CNL_{4}^{2}}$ -valuation $v$ ,
2.

$A\vDash_{\_}{\mathbf{CNLL_{4}^{2}}}B\Leftrightarrow v(A)\in D\Rightarrow v(B)\in D$ , for each $\mathbf{CNLL_{4}^{2}}$ -valuation $v$ .

Figure 1: Lattices

4\mathcal{Q}

and

4\mathcal{LQ}

It is instructive to examine set $\mathscr{U}$ from the generalized truth values perspective. A common way to construct a set of generalized truth values is to get powerset over some semantic basis. So, let us choose the basic set $\{\mathbf{T},\mathbf{U}\}$ , consisting of Truth and Uncertainty values, obtaining thereby the set of generalized truth values $\{\{\mathbf{T,U}\},\{\mathbf{T}\},\{\mathbf{U}\},\varnothing\}$ . It is natural to think of $\{\mathbf{T}\}$ as just $\mathbf{T}$ , while $\{\mathbf{T,U}\}$ as our $\mathbf{TU}$ . Then $\mathbf{U}$ is just “uncertainty without being true”. Recall that the absence of truth can be understood as just being false. This suggests that $\mathbf{U}$ can be thought as $\mathbf{FU}$ ; likewise $\varnothing$ is just $\mathbf{F}$ .

3 Binary consequence systems for $\mathbf{CNL_{4}^{2}}$ and $\mathbf{CNLL_{4}^{2}}$

To formalize semantically defined consequence relation we will use a specific variant of a logical calculus, “a binary consequence system”⁴⁴4See [9, Chapter 6] for a discussion of terminology concerning to different presentations of logical systems. In particular our approach is called “binary implicational system” there., which is typical of all FDE-related logics. The term “binary” means that a sequent⁵⁵5We use the term ‘sequent’ in a broad sense, not reffering here to the apparatus of Gentzen calculi. is an expression of a form $A\vdash B$ which contains exactly one formula in the antecedent or consequent position. We take some schemata of sequents regarded as the axiomatic schemata. A sequent is an axiom if it is a particular instance of a schema. To make the presentation succinct we abbreviate ${\sim}{\sim}$ as ${\sim}^{\emph{\tiny 2}}$ , ${\sim}{\sim}{\sim}$ as ${\sim}^{\emph{\tiny 3}}$ and so on.

Definition 3.1.

A sequent $A\vdash B$ is called $\mathbf{CNL_{4}^{2}}$ -valid ( $\mathbf{CNLL_{4}^{2}}$ -valid) $\Leftrightarrow$

A\vDash_{\_}{\mathbf{CNL_{4}^{2}}}B\quad(A\vDash_{\_}{\mathbf{CNLL_{4}^{2}}}B).

Definition 3.2.

A $\mathbf{CNL_{4}^{2}}$ -proof (a $\mathbf{CNLL_{4}^{2}}$ -proof) as a list of sequents each of them is whether an axiom of $\mathbf{CNL_{4}^{2}}$ (an axiom of $\mathbf{CNLL_{4}^{2}}$ ) or derived from the previous items of the list using some rule of inference. A $\mathbf{CNL_{4}^{2}}$ -proof ( $\mathbf{CNLL_{4}^{2}}$ -proof) for a sequent $A\vdash B$ is a $\mathbf{CNL_{4}^{2}}$ -proof ( $\mathbf{CNLL_{4}^{2}}$ -proof) the last item of which coincides with $A\vdash B$ . A sequent $A\vdash B$ is called $\mathbf{CNL_{4}^{2}}$ -provable ( $\mathbf{CNLL_{4}^{2}}$ -provable) if there is a $\mathbf{CNL_{4}^{2}}$ -proof ( $\mathbf{CNLL_{4}^{2}}$ -proof) for $A\vdash B$ .

To indicate that a sequent $A\vdash B$ is $\mathbf{CNL_{4}^{2}}$ -provable ( $\mathbf{CNLL_{4}^{2}}$ -provable) we also adopt the expression $A\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B$ ( $A\vdash_{\_}{\mathbf{CNLL_{4}^{2}}}B$ ).

$\mathbf{CNL_{4}^{2}}$ & $\mathbf{CNLL_{4}^{2}}$ common axiomatic schemata and rules of inference:

(a1)

$A\wedge B\vdash A$ ,
(a2)

$A\wedge B\vdash B$ ,
(a3)

$B\vdash A\vee B$ ,
(a4)

$A\vdash A\vee B$ ,
(a5)

$A\vdash{\sim}^{\emph{\tiny 4}}A$ ,
(a6)

${\sim}^{\emph{\tiny 4}}A\vdash A$ ,
(a7)

${\sim}A\wedge{\sim}B\vdash{\sim}(A\wedge B)$ ,
(a8)

${\sim}(A\vee B)\vdash{\sim}A\vee{\sim}B$ ,
(a9)

$A\wedge{\sim}^{\emph{\tiny 2}}A\vdash B$ ,
(a10)

$A\wedge(B\vee C)\vdash(A\wedge B)\vee(A\wedge C)$ .

(r1)

$A\vdash B$ , $B\vdash C$ / $A\vdash C$ ,
(r2)

$A\vdash B$ , $A\vdash C$ / $A\vdash B\wedge C$ ,
(r3)

$A\vdash C$ , $B\vdash C$ / $A\vee B\vdash C$ ,
(r4)

$A\vdash B$ / ${\sim}^{\emph{\tiny 2}}B\vdash{\sim}^{\emph{\tiny 2}}A$ .

$\mathbf{CNL_{4}^{2}}$ additional axiomatic schemata:

(b1)

${\sim}(A\wedge B)\vdash{\sim}A\wedge{\sim}B$ ,
(b2)

${\sim}A\vee{\sim}B\vdash{\sim}(A\vee B)$ .

$\mathbf{CNLL_{4}^{2}}$ additional axiomatic schemata:

(c1)

${\sim}A\wedge{\sim}B\vdash{\sim}(A\vee B)$ ,
(c2)

${\sim}(A\wedge B)\vdash{\sim}A\vee{\sim}B$ ,
(c3)

${\sim}A\wedge{\sim^{\emph{\tiny 2}}}A\vdash{\sim}(A\wedge B)$
(c4)

$A\wedge{\sim}A\vdash{\sim}(A\vee B)$ ,
(c5)

${\sim}(A\vee B)\vdash{\sim}A\vee B$ ,
(c6)

${\sim}(A\vee B)\vdash{\sim}(B\vee A)$ ,
(c7)

${\sim}(A\wedge B)\vdash{\sim}(B\wedge A)$ ,
(c8)

$({\sim}(A\vee B)\wedge{\sim}(A\wedge B))\vdash{\sim}A\wedge{\sim}B$ ,

Proposition 3.3.

The following sequents are provable in $\mathbf{CNL_{4}^{2}}$ :

(1)

${\sim}A\wedge{\sim}B\vdash{\sim}(A\vee B)$ ,
(2)

${\sim}(A\wedge B)\vdash{\sim}A\vee{\sim}B$ .

Proposition 3.4.

The following sequents are provable in both $\mathbf{CNL_{4}^{2}}$ and $\mathbf{CNLL_{4}^{2}}$ .

(De1)

{\sim}^{\emph{\tiny 2}}A\wedge{\sim}^{\emph{\tiny 2}}B\dashv\vdash{\sim^{\emph{\tiny 2}}}(A\vee B)

(De2)

{\sim}^{\emph{\tiny 2}}A\vee{\sim}^{\emph{\tiny 2}}B\dashv\vdash{\sim^{\emph{\tiny 2}}}(A\wedge B)

(T)

B\vdash A\vee{\sim}^{\emph{\tiny 2}}A

Systems $\mathbf{CNL_{4}^{2}}$ and $\mathbf{CNLL_{4}^{2}}$ have much in common with classical logic. Indeed, if we were intended to represent classical logic as a binary consequence system, we would take (a1)–(a6), (a10) and (r1)–(r4), adding paradoxical postulates like (A9) (then, of course, a pair ${\sim\sim}$ should be treated as classical $\neg$ ). Is is well known that an alternative formulation of classical system is obtained by replacing contraposition rule with a full collection of De Morgan laws (but then both $A\wedge{\neg}A\vdash_{\_}CB$ and $A\vdash_{\_}CB\vee{\neg}B$ are needed, where $\vdash_{\_}C$ stands for classical binary consequence relation) as axiomatic schemas. For further references we will denote this system as $C$ .

As mentioned above, double $\sim$ have all these features of classical negation. Thus a kind of intrinsic classicality present in both our systems. More precisely we can represent this fact via translation function $\Phi$ from the language of classical logic $\mathcal{LC}$ (over the signature $\{\wedge,\vee,\neg\}$ ) to the language of the present systems (both sharing the same set of variables $PV$ ):

	$\displaystyle\Phi(p)$	$\displaystyle=p,\quad p\in PV,$
	$\displaystyle\Phi(A\circ B)$	$\displaystyle=\Phi(A)\circ\Phi(B),\quad\circ\in\{\wedge,\vee\},$
	$\displaystyle\Phi(\neg A)$	$\displaystyle={\sim}{\sim}\Phi(A).$

We would like to show, that $\Phi$ is not only a translation, but an embedding function as well. We prove this statement via semantic argument. Let us consider an expression $A\vDash_{\_}CB$ as an assertion about classical consequence relation with respect to four-valued boolean algebra based on the lattice $4\mathcal{Q}$ .

Lemma 3.5.

For all formulas $A$ , $B$ of the language $\mathcal{LC}$ :

A\vDash_{\_}CB\Leftrightarrow\Phi(A)\vDash_{\_}{\mathbf{CNL_{4}^{2}}}\Phi(B)\Leftrightarrow\Phi(A)\vDash_{\_}{\mathbf{CNLL_{4}^{2}}}\Phi(B).

Proof.

Recall that a valuation is a mapping $PV\mapsto\mathscr{U}$ , but for the extended valuations we should distinguish mappings depending on the languages and underlying semantic structures. Let us suppose for the purposes of this lemma that given a valuation $v$ , we denote by $v_{\_}1$ , $v_{\_}2$ and $v_{\_}3$ its classical, $\mathbf{CNL_{4}^{2}}$ - and $\mathbf{CNLL_{4}^{2}}$ -extensions respectively.

Induction on the structure of a formula shows that for all valuation $v$ and all its extensions $v_{\_}1$ , $v_{\_}2$ , $v_{\_}3$ and any formula $A$ of the language $\mathcal{LC}$ ,

v_{\_}1(A)=v_{\_}2(\Phi(A))=v_{\_}3(\Phi(A)).

(1)

Next we define partial clockwise ( $v^{+}$ ) and counter-clockwise ( $v^{-}$ ) rotation of a valuation $v$ for an arbitrary $p\in PV$ :

$v(p)$	$v^{+}(p)$	$v^{-}(p)$
$\mathbf{T}$	$\mathbf{T}$	$\mathbf{T}$
$\mathbf{TU}$	$\mathbf{T}$	$\mathbf{F}$
$\mathbf{F}$	$\mathbf{F}$	$\mathbf{F}$
$\mathbf{FU}$	$\mathbf{F}$	$\mathbf{T}$

Routine check proves the following key fact, namely that for a valuation $v$ , partial clockwise rotation $v^{+}$ induces corresponding rotations $v_{\_}i^{+}$ , $i\in\{1,2,3\}$ , while $v^{-}$ induces $v_{\_}i^{-}$ , $i\in\{1,2,3\}$ , answering the description given in the table below for each formula $A\in\mathcal{LC}$ :

$v_{\_}1(A)$ , $v_{\_}2(\Phi(A))$ , $v_{\_}3(\Phi(A))$	$v^{+}_{\_}1(A)$ , $v^{+}_{\_}2(\Phi(A))$ , $v^{+}_{\_}3(\Phi(A))$	$v^{-}_{\_}1(A)$ , $v^{-}_{\_}2(\Phi(A))$ , $v^{-}_{\_}3(\Phi(A))$
$\mathbf{T}$	$\mathbf{T}$	$\mathbf{T}$
$\mathbf{TU}$	$\mathbf{T}$	$\mathbf{F}$
$\mathbf{F}$	$\mathbf{F}$	$\mathbf{F}$
$\mathbf{FU}$	$\mathbf{F}$	$\mathbf{T}$

( $\star$ )

Now suppose $A\vDash_{\_}CB$ , but $\Phi(A)\nvDash_{\_}{\mathbf{CNL_{4}^{2}}}\Phi(B)$ . This means that there is some valuation $v_{\_}2$ such that $v_{\_}2(\Phi(A))\in D$ , $v_{\_}2(\Phi(B))\notin D$ . Assume $v_{\_}2(\Phi(A))=\mathbf{T}$ , $v_{\_}2(\Phi(B))\neq\mathbf{T}$ . Then, by (1), $v_{\_}1(A)=\mathbf{T}$ , $v_{\_}1(B)\neq\mathbf{T}$ . Hence $A\nvDash_{\_}{C}B$ .

Next assume $v_{\_}2(\Phi(A))=\mathbf{TU}$ , but $v_{\_}2(\Phi(B))=\mathbf{FU}$ or $v_{\_}2(\Phi(B))=\mathbf{F}$ . Then, according to table ( $\star$ ), $v_{\_}2^{+}(\Phi(A))=v^{+}_{\_}1(A)=\mathbf{T}$ , but $v_{\_}2^{+}(\Phi(B))=v^{+}_{\_}1(B)\neq\mathbf{T}$ , so $A\nvDash_{\_}{C}B$ .

For the other direction assume $A\nvDash_{\_}{C}B$ , that is $v_{\_}1(A)=\mathbf{T}$ , $v_{\_}1(B)\neq\mathbf{T}$ . According to (1), this means that $v_{\_}2(\Phi(A))=\mathbf{T}$ , $v_{\_}2(\Phi(B))\neq\mathbf{T}$ . If $v_{\_}2(\Phi(B))\neq\mathbf{TU}$ , then $\Phi(A)\nvDash_{\_}{\mathbf{CNL_{4}^{2}}}\Phi(B)$ . Consider, however, the case $v_{\_}2(\Phi(B))=\mathbf{TU}$ . According to ( $\star$ ) we can take the rotation $v_{\_}2^{-}$ such that $v_{\_}2^{-}(\Phi(A))=\mathbf{T}$ and $v_{\_}2^{-}(\Phi(B))=\mathbf{F}$ . Hence, again, $\Phi(A)\nvDash_{\_}{\mathbf{CNL_{4}^{2}}}\Phi(B)$ .

An analogues provides the proof in case of $\vDash_{\_}{\mathbf{CNLL_{4}^{2}}}$ relation. ∎

Corollary 3.6.

$\Phi$ is an embedding function.

4 Soundness and Completeness of $\mathbf{CNL_{4}^{2}}$

4.1 Soundness

Lemma 4.1 (Local Soundness for $\mathbf{CNL_{4}^{2}}$ ).

All axiomatic schemata of $\mathbf{CNL_{4}^{2}}$ represent $\mathbf{CNL_{4}^{2}}$ -valid sequents and the rules of inference preserve $\mathbf{CNL_{4}^{2}}$ -validity.

Proof.

We need to check each item from the list of axiomatic schemata and inference rules. Let us provide a couple of cases as an illustration.

Suppose that axiomatic schemata (a9) is invalid, i. e. there a $\mathbf{CNL_{4}^{2}}$ -valuation $\upsilon$ that $\upsilon(A\wedge{\sim}^{\emph{\tiny 2}}A)\in\{\textbf{T},\textbf{TU}\}$ and $\upsilon(B)\not\in\{\textbf{T},\textbf{TU}\}$ that is $\upsilon(B)\in\{\textbf{F},\textbf{FU}\}$ . We immediately derive a contradiction since $A\wedge{\sim}^{\emph{\tiny 2}}A$ cannot take its value from the set $\{\mathbf{T},\mathbf{TU}\}$ at all.

Suppose that the rule (r4) does not preserve validity. This means that there is such valuation that $A\vDash_{\_}{\mathbf{CNL_{4}^{2}}}B$ , but ${\sim}^{\emph{\tiny 2}}B\not\vDash_{\_}{\mathbf{CNL_{4}^{2}}}{\sim}^{\emph{\tiny 2}}A$ . From the latter it follows that there is a $\mathbf{CNL_{4}^{2}}$ -valuation $\upsilon$ such that $\upsilon({\sim}^{\emph{\tiny 2}}B)\in\{\textbf{T},\textbf{TU}\}$ and $\upsilon({\sim}^{\emph{\tiny 2}}A)\not\in\{\textbf{T},\textbf{TU}\}$ which means that $\upsilon({\sim}^{\emph{\tiny 2}}A)\in\{\textbf{F},\textbf{FU}\}$ . It is easy to note that it leads us to $\upsilon(A)\in\{\textbf{T},\textbf{TU}\}$ and $\upsilon(B)\in\{\textbf{F},\textbf{FU}\}$ , but this contradicts with $A\vDash_{\_}{\mathbf{CNL_{4}^{2}}}B$ , because this must be that $\upsilon(B)\in\{\textbf{T},\textbf{TU}\}$ . Therefore, (r4) preserves validity.

The other cases are similar. ∎

Theorem 4.2 (Soundness for $\mathbf{CNL_{4}^{2}}$ ).

For any formulas $A$ and $B$ , the following holds

$A\vdash B\text{ is $\mathbf{CNL_{4}^{2}}$-provable }\Rightarrow A\vDash_{\_}{\mathbf{CNL_{4}^{2}}}B$ .

Proof.

By induction on the length of the proof, using Lemma 4.1. ∎

4.2 Completeness

The idea of the completeness proof is based on a technique elaborated by J. M. Dunn for the system of $\mathbf{FDE}$ (see [8]). This method essentially relies on the notion of a prime theory which is presented by the following definition.

Definition 4.3.

A $\mathbf{CNL_{4}^{2}}$ -theory is the set of formulas $\alpha$ such that for all formulas $A$ and $B$ ,

1.

$A\wedge B\in\alpha$ whenever $A\in\alpha$ and $B\in\alpha$ ,
2.

$B\in\alpha$ whenever $A\in\alpha$ and $A\vdash B$ is $\mathbf{CNL_{4}^{2}}$ -provable.

A $\mathbf{CNL_{4}^{2}}$ -theory is prime if $A\vee B\in\alpha$ implies $A\in\alpha$ or $B\in\alpha$ . We call a $\mathbf{CNL_{4}^{2}}$ -theory $\alpha$ c-normal when for each formula $A$ it holds that $A\in\alpha$ if and only if ${\sim}^{\emph{\tiny 2}}A\notin\alpha$ .

As a first step toward completeness theorems for $\mathbf{CNL_{4}^{2}}$ we prove the Extension Lemma. Note that we use this lemma uniformly for both completeness theorems. So we prove it for the case of $\mathbf{CNL_{4}^{2}}$ , while proof for another system is the same.

Lemma 4.4 (Extension Lemma).

For all formulas $A$ and $B$ , if $A\vdash B$ is not $\mathbf{CNL_{4}^{2}}$ -provable, then there is a c-normal prime theory $\alpha$ such that $A\in\alpha$ , $B\not\in\alpha$ .

Proof.

Suppose that for some formulas $A$ and $B$ , $A\vdash B$ is not $\mathbf{CNL_{4}^{2}}$ -provable. Let us define $\alpha_{\_}{0}=\{C\mid A\vdash_{\_}{\mathbf{CNL_{4}^{2}}}C\}$ . $\alpha_{\_}0$ is a theory as it is closed under $\vdash_{\_}{\mathbf{CNL_{4}^{2}}}$ and $\wedge$ (using the rule (r2)). Next we construct the sequence of theories taking some enumeration of the set $FM$ ( $A_{\_}1,A_{\_}2,\ldots$ ) and define

\alpha_{\_}{n+1}=\begin{cases}\alpha_{\_}n,\text{ if }\alpha_{\_}{n}\cup\{A_{\_}{n+1}\}\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B,\\ \alpha_{\_}{n}\cup\{A_{\_}{n+1}\},\text{ if }\alpha_{\_}{n}\cup\{A_{\_}{n+1}\}\not\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B.\end{cases}

Let $\alpha$ be the union of all $\alpha_{\_}n$ ’s. First we show that $\alpha$ is a prime theory such that $A\in\alpha$ and $B\not\in\alpha$ . $A\in\alpha$ by the construction of $\alpha$ . Assume $B\in\alpha$ , hence $B$ was added to $\alpha_{\_}i$ on $i$ -th stage of construction of the sequence, which is impossible. For the primeness suppose that $\alpha$ is not prime, i. e. $C\vee D\in\alpha$ , but $C\not\in\alpha$ and $D\not\in\alpha$ . This means that both extensions $\alpha\cup\{C\}$ and $\alpha\cup\{D\}$ contain $B$ . Then there is a conjunctions of formulas form $\alpha$ , say $E$ , such that $E\wedge C\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B$ and $E\wedge D\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B$ . From this, using $(r3)$ , we derive $(E\wedge C)\vee(E\wedge D)\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B$ . Then, using (a10) and $(r1)$ , we have $E\wedge(C\vee D)\vdash_{\_}{\mathbf{CNL_{4}^{2}}}B$ , so $B\in\alpha$ .

Finally, $\alpha$ is also c-normal. Indeed, if for some $k$ , $A_{\_}k\in\alpha$ and ${\sim}^{\emph{\tiny 2}}A_{\_}k\in\alpha$ , then there is an $\alpha_{\_}i$ which contains $A_{\_}k\wedge{\sim}^{\emph{\tiny 2}}A_{\_}k$ as well as $B$ , due to axiom schema $A\wedge{\sim}^{\emph{\tiny 2}}A\vdash B$ and the rules (r1) and (r2), contrary to the assumption. On the other hand, primeness of $\alpha$ and derivable schema $B\vdash_{\_}{\mathbf{CNL_{4}^{2}}}A\vee{\sim}^{\emph{\tiny 2}}A$ guarantee that for each $A_{\_}k$ , one of two formulas, $A_{\_}k$ and ${\sim}^{\emph{\tiny 2}}A_{\_}k$ , belongs to $\alpha$ . ∎

4.3 Completeness for $\mathbf{CNL_{4}^{2}}$

Let $\mathcal{A}$ denote the set $\{\textbf{TU},\textbf{F}\}$ . We can express our truth-values in terms of $\mathcal{A}$ and $\mathcal{D}$ sets via the following expressions:

	$\displaystyle v(A)=\textbf{T}\text{ iff }v(A)\in\mathcal{D}\text{ and }v(A)\notin\mathcal{A},$
	$\displaystyle v(A)=\textbf{TU}\text{ iff }v(A)\in\mathcal{D}\text{ and }v(A)\in\mathcal{A},$
	$\displaystyle v(A)=\textbf{F}\text{ iff }v(A)\notin\mathcal{D}\text{ and }v(A)\in\mathcal{A},$
	$\displaystyle v(A)=\textbf{FU}\text{ iff }v(A)\notin\mathcal{D}\text{ and }v(A)\notin\mathcal{A}.$

It is not difficult to see the next lemma, having in mind the interpretations of propositional connectives.

Lemma 4.5.

Let $A,B\in FM$ , and $v$ be a $\mathbf{CNL_{4}^{2}}$ -valuation. Then, the following expressions hold:

(1)

$v({\sim}A)\in\mathcal{D}$ iff $v(A)\notin\mathcal{A}$ ;
(2)

$v({\sim}A)\in\mathcal{A}$ iff $v(A)\in\mathcal{D}$ ;
(3)

$v(A\wedge B)\in\mathcal{D}$ iff $v(A)\in\mathcal{D}$ and $v(B)\in\mathcal{D}$ ;
(4)

$v(A\wedge B)\in\mathcal{A}$ iff $v(A)\in\mathcal{A}$ or $v(B)\in\mathcal{A}$ ;
(5)

$v(A\vee B)\in\mathcal{D}$ iff $v(A)\in\mathcal{D}$ or $v(B)\in\mathcal{D}$ ;
(6)

$v(A\vee B)\in\mathcal{A}$ iff $v(A)\in\mathcal{A}$ and $v(B)\in\mathcal{A}$ ;

Now we turn to the definition of a $\mathbf{CNL_{4}^{2}}$ -canonical valuation.

Definition 4.6.

For each $c$ -normal prime theory $\alpha$ and propositional variable $p$ we define a $\mathbf{CNL_{4}^{2}}$ -canonical valuation $v^{c}$ as a mapping $PV\mapsto 4\mathcal{Q}$ satisfying the following expressions:

(1)

$v^{c}(p)\in\mathcal{D}\Leftrightarrow p\in\alpha$ ;
(2)

$v^{c}(p)\in\mathcal{A}\Leftrightarrow{\sim^{3}}p\in\alpha$ ;

Define a unique extension of $v^{c}$ to the set of all formulas in the usual way and denote this extension by $v^{c}$ as well and prove that extended valuation behaves as expected with respect to the c-normal prime theories.

Lemma 4.7 (Canonical Valuation Lemma for $\mathbf{CNL_{4}^{2}}$ ).

For each $c$ -normal prime theory $\alpha$ , formula $A$ and extended canonical $\mathbf{CNL_{4}^{2}}$ -valuation $v^{c}$ the following statements hold:

(1)

$v^{c}(A)\in\mathcal{D}\Leftrightarrow A\in\alpha$ ,
(2)

$v^{c}(A)\in\mathcal{A}\Leftrightarrow{\sim^{3}}A\in\alpha$ .

Proof.

By induction on the structure of a formula $A$ . The base case when $A$ is a propositional variable follows from the definition 4.6. Consider the cases for the complex formulas. The induction hypothesis (‘IH’ in the sequel) claims that lemma is true for their proper subformulas. We will tacitly use the two basic properties of theories, namely, their closure under conjunction and the relation $\vdash_{\_}{\mathbf{CNL_{4}^{2}}}$ throughout the proof.

Case $A={\sim}B$ .

$v^{c}({\sim}B)\in\mathcal{D}\Leftrightarrow\text{(by Lemma \ref{eq}) }v^{c}(B)\notin\mathcal{A}\Leftrightarrow\text{(by IH) }{\sim^{\emph{\tiny 3}}}B\notin\alpha\Leftrightarrow$ (by c-normality) ${\sim}B\in\alpha.$

$v^{c}({\sim}B)\in\mathcal{A}\Leftrightarrow v^{c}(B)\in\mathcal{D}\text{ (by Lemma \ref{eq})}\Leftrightarrow B\in\alpha$ (by IH) $\Leftrightarrow{\sim^{\emph{\tiny 4}}}B\in\alpha$ (by (a5), (a6)).

Case $A=B\wedge C$ .

$v^{c}(B\wedge C)\in\mathcal{D}\Leftrightarrow\text{(by Lemma \ref{eq}) }v^{c}(B)\in\mathcal{D}\text{ and }v^{c}(C)\in\mathcal{D}\Leftrightarrow$ (by IH) $B\in\alpha\text{ and }C\in\alpha\Leftrightarrow$

$\text{(by (a1), (a2)) }B\wedge C\in\alpha.$

$v^{c}(B\wedge C)\in\mathcal{A}\Leftrightarrow\text{(by Lemma \ref{eq}) }v^{c}(B)\in\mathcal{A}\text{ or }v^{c}(C)\in\mathcal{A}\Leftrightarrow$ (by IH) ${\sim^{\emph{\tiny 3}}}B\in\alpha\text{ or }{\sim^{\emph{\tiny 3}}}C\in\alpha\Leftrightarrow$

(by c-normality) ${\sim}B\notin\alpha\text{ or }{\sim}C\notin\alpha$ $\Leftrightarrow$ (by (b1), (a7)) ${\sim}(B\wedge C)\notin\alpha\Leftrightarrow$

$\text{(by {c}-normality) }{\sim^{\emph{\tiny 3}}}(B\wedge C)\in\alpha$ .

Case $A=B\vee C$ .

$v^{c}(B\vee C)\in\mathcal{D}\Leftrightarrow\text{(by Lemma \ref{eq}) }v^{c}(B)\in\mathcal{D}\text{ or }v^{c}(C)\in\mathcal{D}\Leftrightarrow$ (by IH) $B\in\alpha\text{ or }C\in\alpha\Leftrightarrow$

$\text{(by (a3), (a4), primeness) }B\vee C\in\alpha.$

$v^{c}(B\vee C)\in\mathcal{A}\Leftrightarrow\text{(by Lemma \ref{eq}) }v^{c}(B)\in\mathcal{A}\text{ and }v^{c}(C)\in\mathcal{A}\Leftrightarrow$ (by IH) ${\sim^{\emph{\tiny 3}}}B\in\alpha\text{ and }{\sim^{\emph{\tiny 3}}}C\in\alpha\Leftrightarrow$

(by c-normality) ${\sim}B\notin\alpha\text{ and }{\sim}C\notin\alpha\Leftrightarrow$ (by (a3), (a4), (a8), (b2), primeness) ${\sim}(B\vee C)\notin\alpha\Leftrightarrow$

$\text{(by {c}-norm.) }{\sim^{\emph{\tiny 3}}}(B\vee C)\in\alpha.$ ∎

Theorem 4.8 (Completeness for $\mathbf{CNL_{4}^{2}}$ ).

For any formulas $A$ and $B$ , the following holds:

A\vDash_{\_}{\mathbf{CNL_{4}^{2}}}B\Rightarrow A\vdash B\text{ is $\mathbf{CNL_{4}^{2}}$-provable}.

Proof.

Suppose $A\vdash B$ is not $\mathbf{CNL_{4}^{2}}$ -provable. Then, by Lemma 4.4, there is prime theory $\alpha$ such that $A\in\alpha$ and $B\not\in\alpha$ . Then, by Lemma 4.7, we have that $v^{c}(A)\in\mathcal{D}$ but $v^{c}(B)\notin\mathcal{D}$ , so $A\not\vDash_{\_}{\mathbf{CNLL_{4}^{2}}}B$ . ∎

5 Conclusion

Although we have studied probably the most natural logics of paired cyclic negations, the whole picture is still waiting to be explored. Even the framework of the four-valued semantics gives some possible directions for the further investigations. Specifically, one can choose other sets of the designated truth values or combine the different collections of designated and anti-designated truth values. On the other hand, alternative definitions of the consequence relation are also possible. To obtain the more abstract results, paired cyclic negations could be put into more general lattice structures, even not necessary finitely based. Having in mind ability to simulate the other negation-like operations, the potential relationships between logical systems appear to be of the main interest.

References

[1]
[2] Johan van Benthem (2011): Logical dynamics of information and interaction. Cambridge University Press, 10.1017/cbo9780511974533.
[3] Johan Van Benthem (2008): Logical dynamics meets logical pluralism? The Australasian Journal of Logic 6, pp. 182–209, 10.26686/ajl.v6i0.1801.
[4] Maria Luisa Dalla Chiara, Roberto Giuntini & Richard Greechie (2013): Reasoning in quantum theory: sharp and unsharp quantum logics. 22, Springer Science & Business Media, 10.1007/978-94-017-0526-4.
[5] Maria Luisa Dalla Chiara, Roberto Giuntini & Roberto Leporini (2005): Logics from quantum computation. International Journal of Quantum Information 03(02), pp. 293–337, 10.1142/s0219749905000943.
[6] David Deutsch, Artur Ekert & Rossella Lupacchini (2000): Machines, logic and quantum physics. Bulletin of Symbolic Logic 6(3), pp. 265–283, 10.2307/421056.
[7] J. Michael Dunn (1993): Star and perp: two treatments of negation. Philosophical Perspectives 7, pp. 331–357, 10.2307/2214128.
[8] J. Michael Dunn (2000): Partiality and its dual. Studia Logica 66, pp. 5–40, 10.1023/A:1026740726955.
[9] J. Michael Dunn & Gary Hardegree (2001): Algebraic Methods in Philosophical Logic. Oxford University Press.
[10] Dov M. Gabbay & Heinrich Wansing, editors (1999): What is a negation? Applied Logic Series 13, Springer Netherlands, 10.1007/978-94-015-9309-0.
[11] Lloyd Humberstone (1995): Negation by iteration. Theoria 61(1), pp. 1–24, 10.1111/j.1755-2567.1995.tb00489.x.
[12] Norihiro Kamide (2017): Paraconsistent double negations as classical and intuitionistic negations. Studia Logica 105(6), pp. 1167–1191, 10.1007/s11225-017-9731-2.
[13] Sergei P. Odintsov (2008): Constructive Negations and Paraconsistency. Springer Netherlands, 10.1007/978-1-4020-6867-6.
[14] Hitoshi Omori & Katsuhiko Sano (2015): Generalizing functional completeness in Belnap-Dunn logic. Studia Logica 103(5), pp. 883–917, 10.1007/s11225-014-9597-5.
[15] Hitoshi Omori & Heinrich Wansing (2018): On contra-classical variants of Nelson logic N4 and its classical extension. The Review of Symbolic Logic 11, pp. 805–820, 10.1017/s1755020318000308.
[16] Emil Post (1921): Introduction to a general theory of elementary propositions. American Journal of Mathematics 43, pp. 163–185, 10.2307/2370324.
[17] Helena Rasiowa (1974): An algebraic approach to non-classical logics. Studies in Logic and Foundations of Mathematics 78, North-Holland, Amsterdam, 10.1016/S0049-237X(09)70074-6.
[18] Paul Ruet (1996): Complete set of connectives and complete sequent calculus for Belnap’s logic. Technical Report, École Normale Supérieure. Logic Colloquium 96, Document LIENS-96–28.
[19] Heinrich Wansing, editor (1996): Negation: A notion in focus. W. De Gruyter, 10.1515/9783110876802.
[20] Dmitry Zaitsev & Oleg Grigoriev (2011): Two kinds of truth – one logic. Logical Investigations 17, pp. 121–139, 10.21146/2074-1472-2011-17-0-121-139. (in Russian).
[21] Dmitry Zaitsev & Yaroslav Shramko (2013): Bi-facial truth: a case for generalized truth values. Studia Logica 101(6), pp. 1299–1318, 10.1007/s11225-013-9534-z.

Cyclic Negations and Four-valuedness

Abstract

1 Introduction

2 Cyclic Negation in the Generalized Truth Values Setting

2.1 Four-Valuedness and Cyclic Negation from Quantum Computations

2.2 Four-Valued Matrices

Definition 2.1.

Definition 2.2.

Definition 2.3.

3 Binary consequence systems for 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}} and 𝐂𝐍𝐋𝐋𝟒𝟐\mathbf{CNLL_{4}^{2}}

Definition 3.1.

Definition 3.2.

Proposition 3.3.

Proposition 3.4.

Lemma 3.5.

Proof.

Corollary 3.6.

4 Soundness and Completeness of 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}}

4.1 Soundness

Lemma 4.1 (Local Soundness for 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}}).

Proof.

Theorem 4.2 (Soundness for 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}}).

Proof.

4.2 Completeness

Definition 4.3.

Lemma 4.4 (Extension Lemma).

Proof.

4.3 Completeness for 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}}

Lemma 4.5.

Definition 4.6.

Lemma 4.7 (Canonical Valuation Lemma for 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}}).

Proof.

Theorem 4.8 (Completeness for 𝐂𝐍𝐋𝟒𝟐\mathbf{CNL_{4}^{2}}).

Proof.

5 Conclusion

References

3 Binary consequence systems for $\mathbf{CNL_{4}^{2}}$ and $\mathbf{CNLL_{4}^{2}}$

4 Soundness and Completeness of $\mathbf{CNL_{4}^{2}}$

Lemma 4.1 (Local Soundness for $\mathbf{CNL_{4}^{2}}$ ).

Theorem 4.2 (Soundness for $\mathbf{CNL_{4}^{2}}$ ).

4.3 Completeness for $\mathbf{CNL_{4}^{2}}$

Lemma 4.7 (Canonical Valuation Lemma for $\mathbf{CNL_{4}^{2}}$ ).

Theorem 4.8 (Completeness for $\mathbf{CNL_{4}^{2}}$ ).