数理解析研究所講究録
第 1846 巻 2013 年 46-52

46

Logic characterized by Boolean algebras with conjugate
情報環境学部

東京電機大学近藤通朗 (Michiro Kondo)

School of Information Environment
Tokyo Denki University

1Introduction

In [1], Jarvinen and Kortelainen considered properties of lower (upper) approximation operators in roughset theory by use of the algebras with conjugate pair of maps. Let be any Boolean algebra.
pair$(f, g)$ of maps $f,$ $g:Barrow B$ is called conjugate ([2]) if, for all$y\in B$ , the following condition is satisfied:
$B$

$A$

$x,$

$x\wedge f(y)=0\Leftrightarrow y\wedge g(x)=0$

Moreover if a pair $(f, f)$ is conjugate, then is called self-conjugate. If a Boolean algebra has a pair ofconjugate maps, then we say simply a Boolean algebra with conjugate.
By $B$ we mean the class of all Boolean algebras with conjugate. In this short note we show that $B$
characterizes a ceratin kind of tense logic, that is, for the class of all formulas of$f$$\Phi$$K_{t}^{*}$For any $B\in B$ and a maptense logic

2$\xi$: $\Phiarrow B$ , we have$K_{t}^{*},$$\xi(A)=1\Leftrightarrow\vdash_{K_{\ell}}^{*}A$$K_{t}^{*}$We define a certain kind of tense logic named
here. The logic is obtained from the minimal tenseby removing the axioms $(sym):Aarrow GPA,$ $Aarrow HFA$ and $(cl):GAarrow GGA,$ $HAarrow HHA.$
logic$G,$ $H$ are logicalLet
be a countable setof propositional variables andsymbols.
formula ofis defined as follows:$K_{t}^{*}$$K_{t}$$\Phi_{0}$$p_{0},p_{1},p_{2},$ $\cdots$$A$$\wedge,$$\vee,$$arrow,$$K \oint$(1) Every propositional variable is a formula;(2) IfLet$\Phi$$A$and $B$ are formulas, then so are $A\wedge B,$ $A\vee B,$ $Aarrow B,$

be the set of all formulas of$K_{t}^{*}$. We define symbols$F$and$P$$\urcorner A,$$GA,$ $HA.$

respectively by$FA\equiv\urcorner\urcorner, PA\equiv\urcorner H\urcorner A.$

A logical system
Axioms :$K_{t}^{*}$

has the following axioms and rules of inference ([3]):(1)$Aarrow(Barrow A)$(2)$(Aarrow(Barrow C))arrow((Aarrow B)arrow(Aarrow C))$(3)$(\neg Aarrow\neg B)arrow(Barrow A)$(4)$G(Aarrow B)arrow(GAarrow GB),$$H(Aarrow B)arrow(HAarrow HB)$

Rule of Inference :( $MP$ ) Deduce $B$ fromand $Aarrow B$ ;(Nec) Deduce $GA$ and $HA$ from $A.$$A$

We list typical axioms which chracterize some properties of conjugate:$\neg,$

47(ext) : $GAarrow A,$ $HAarrow A$(sym): $Aarrow GPA,$ $Aarrow HFA$(cl): $GAarrow GGA,$ $HAarrow HHA$A well-known tense logic$K_{t}$

that is,is an axiomatic extension of$K_{t}^{*}$, which has extra axioms $(sym)$ and $(cl)$ ,$K_{t}=K_{t}^{*}+(sym)+(d)$A formula is called provable when there is a finite sequencesuch that, for every $i(1\leq i\leq n)$ ,
$A$

(1)

$A_{i}$

is an axiom;(2)$A_{i}$

is deduced from(3)

$A_{i}$

is done from $A_{j}(j<i)$ by (Nec).

We denote that$A$

$A_{j},$$A_{1},$ $A_{2},$$\cdots,$$A_{n}(=A)(n\geq 1)$ of formulasby ( $MP$ );$A_{k}(j, k<i)$

is provable by$\vdash_{K_{\dot{\ell}}}A$(or simply$\vdash A$).

A relational structure
is called a Kripke frame, where $W$ is a non-empty set and is a binary
relation on it. valuation is a map from, that is, :to. It is easy to show thata valuation can be extended uniquely to the set of all formulas:$(W, R)$

$A$

$R$

$v$

$\Phi_{0}$$v$$\mathcal{P}(W)$$v$$\Phi_{0}arrow \mathcal{P}(W)$$\Phi$(1)$v(A\wedge B)=v(A)\cap v(B)$(2)$v(A\vee B)=v(A)\cup v(B)$(3)$v(Aarrow B)=v(A)^{c}\cup v(B)$(4) $v(\neg A)=v(A)^{c}$(5) $v(GA)=\{x\in W|\forall y((x, y)\in R\Rightarrow y\in v(A))\}$(6) $v(HA)=\{x\in W|\forall y((y, x)\in R\Rightarrow y\in v(A))\}$
Thus we call the extended valuation above simply a valuation and denote it by the same symbol
Since, for all formulas and $B$

$v.$

$A$

$\vdash_{K_{\dot{t}}}A\wedge\neg Aarrow B\wedge\neg B, \vdash_{K_{\dot{t}}}A\vee\neg Aarrow B\vee\urcorner B,$

We define symbols$\perp$and$T$

respectively by$\perp\equiv A\wedge\neg A, T\equiv A_{\urcorner}A.$

Then for every formula $A\in\Phi$ , we have$\vdash_{K_{\dot{p}}}\perparrow A, \vdash_{K\int}Aarrow T.$

A structure $\mathcal{M}=(W, R, v)$ is called a Kripke model, where $(W, R)$ is a Kripke frame and is avaluation on it. Given a Kripke model $\mathcal{M}=(W, R, v)$ , we can interpret the formulas on it as follows: For$x\in W$ , a formula
is said to be true at on the Kripke model
if$v$

$A$

$\mathcal{M}$$x$$x\in v(A)$,and denoted by$\mathcal{M}\models_{x}A.$

If $v(A)=W$ , that is,denoted by$A$

is true at ever $x\in W$ on the Kripke model$\mathcal{M}$, then$A$

is called true on$\mathcal{M}\models A.$

Moreover$A$is called valid if$A$is true on every Kripke model$\models A.$

It is easy to show the next result ([3]):$\mathcal{M}$and denoted by$\mathcal{M}$and48
Theorem 1. (Completeness Theorem) For every formula$\vdash_{K_{\dot{t}}}A\Leftrightarrow A$$A$, we have: valid

We can get the next result by use of filtmtion method ([3]):Theorem 2. For every fomula$A$, we have$\vdash_{K_{\dot{t}}}A\Leftrightarrow A$3: true for any finite Kripke model$\mathcal{M}.$

Boolean algebra with conjugate pair

Let $\mathcal{B}=(B, \wedge, ’, 0,1)$ be a Boolean algebra.
pair if, for all $y\in B,$

$A$

pair

$(\varphi, \psi)$of maps$\varphi,$: $Barrow B$ is called a conjugate$\psi$$x,$$x\wedge\varphi(y)=0\Leftrightarrow y\wedge\psi(x)=0.$

We define some properties about a map$\varphi$$\varphi$: extensive: symmetric: closed$\varphi$$\varphi$: $Barrow B$ as follows:$\Leftrightarrow x\leq\varphi(x)$$\Leftrightarrow x\leq\varphi(y)$$\Leftrightarrow y\leq\varphi(x)$$(\forall x\in B)$

implies $y\leq\varphi(x)(\forall x, y\in B)$
implies $\varphi(y)\leq\varphi(x)(\forall x, y\in B)$

It is clear that the following holds for a conjugate pair
: extensive: symmetric: closed$\varphi$$\varphi$$\varphi$

We introduce two operators$\varphi^{\partial},$$\psi^{\partial}$$\Leftrightarrow\psi$$\Leftrightarrow\varphi$$\Leftrightarrow\psi$$(\varphi, \psi)$([1]):: extensive: self–conjugate: closed

for the sake of simplicity$\varphi^{\partial}(x)=(\varphi(x’))’, \psi^{\partial}(x)=(\psi(x’))’(x\in B)$

A conjugate pair$(\varphi, \psi)$.

can be represented by$\varphi(x)\leq y\Leftrightarrow x\leq\psi^{\partial}(y)(x, y\in B)$.

It is obvious from definition that
Proposition 1. For every $x\in B$ we have$\varphi$$\varphi$: extensive: symmetric$\varphi$: closed$\Leftrightarrow\varphi^{\partial}(x)\leq x$$\Leftrightarrow x\leq\varphi^{\partial}(\varphi(x))$$\Leftrightarrow\varphi^{\partial}(x)\leq\varphi^{\partial}(\varphi^{\partial}(x))$

Let $B$ be a Boolean algebra with conjugate andon the algebra as follows:(1)$\xi(A\wedge B)=\xi(A)\wedge\xi(B)$(2)$\xi(A\vee B)=\xi(A)\vee\xi(B)$(3)$\xi(Aarrow B)=(\xi(A))’\vee\xi(B)$(4)$\xi(\neg A)=(\xi(A))’$(5)$\xi(GA)=(\varphi((\xi(A))’))’=\varphi^{\partial}(\xi(A))$(6)$\xi(HA)=(\psi(\xi(A)’))’=\psi^{\partial}(\xi(A))$$\xi$: $\Phiarrow B$ be a map. Each formula of$K_{t}^{*}$

is interpreted

49
Lemma 1. For every formula$A$, we have$\vdash_{K_{t}}.$$A\Rightarrow\xi(A)=1$

Proof. It is sufficient to verify that each axiom

is preserved, that is, for the case of ($MP$$\alpha$offor all$\xi$

: $\Phiarrow B$

has a value $\xi(\alpha)=1$ and each rule of inference$K_{t}^{*}$),$\xi(A)=\xi(Aarrow B)=1$ imply $\xi(B)=1$

and for the case of (Nec)$\xi(A)=1$ implies $\xi(GA)=\xi(HA)=1.$

We omit their proof.

$\square$We can show the converse direction of the above. In order to do that we prepare some lemmas. At
first we define a relation on the set of formulas of: For $A,$ $B\in\Phi,$$\Phi$$\equiv$$K_{t}^{*}$$A\equiv B\Leftrightarrow\vdash_{K_{t}}.$As to the relation$\equiv$$Aarrow B$

and$\vdash_{K_{t}}.$$Barrow A$

we can prove thatLemma $2.$a congruence on , that is, it is an equivalence relation and satisfies the compatible
property ; If $A\equiv B$ and $C\equiv D$ , then$\equiv is$$\Phi$$A\wedge C\equiv B\wedge D, A\vee C\equiv B\vee D,$$Aarrow D\equiv Barrow D,$$\neg A\equiv\neg B,$$GA\equiv GB, HA\equiv HB$

Proof. We only prove that if$A\equiv B$(Nec) we getthen $GA\equiv GB$ . It follows from assumption that $\vdash Aarrow B$ . From$\vdash G(Aarrow B)$.

On the other hand, since $\vdash G(Aarrow B)arrow(GAarrow GB)$ , we have from ( $MP$ )$\vdash GAarrow GB.$

Similarly, by $\vdash Barrow A$ , we get$\vdash GBarrow GA.$

This means that
$GA\equiv GB.$$\square$Since$\equiv$

is the congruence, we can define operations on$\Phi/\equiv:$

For $A,$ $B\in\Phi$ , we define$[A]n[B]=[A\wedge B],$$[A]\sqcup[B]=[A\vee B],$$[A]^{*}=[\neg A],$$\varphi([A])=[\neg G\neg A]=[FA],$$\psi([A])=[\neg H\neg A]=[PA],$$0=[\perp], 1=[T].$Lemma 3. $(\Phi/\equiv, \sqcap, u, *, o, 1)$ is a Boolean algebm with$(\varphi, \psi)$

as a conjugate pair.

50
Proof. We show that$(\varphi, \psi)$is the conjugate pair. Let $[A],$ $[B]\in\Phi/\equiv$ . We have to prove$[A]\lceil\rceil\varphi([B])=0\Leftrightarrow[B]n\psi([A])=0,$

that is,$[A\wedge FB]=0\Leftrightarrow[B\wedge PA]=0.$

Suppose that $[A\wedge FB]=0$ . Since $\vdash A\wedge FBarrow\perp$ , we have. From (Nec) we get. Since $\vdash Barrow HFB$ , we also have
. Thus we obtain$\vdash FBarrow\urcorner A$$\vdash HFBarrow H\neg A$$\vdash Barrow H_{\urcorner}A$$\vdash\urcorner(B\wedge PA)$,

that is,$[B\wedge PA]=0.$

It is similar the converse.

$\square$Lemma 4. For any formula $A\in\Phi,$$\vdash_{K_{\dot{t}}}A\Leftrightarrow[A]=1$

in$\Phi/\equiv$

Proof.
$\vdash_{K_{1}}A\Leftrightarrow\vdash_{K_{t}}Aarrow T$and$\vdash_{K_{t}}Tarrow A$$\Leftrightarrow[A]=[T]=1$$\square$Rom the above, we can prove the next theorem.
Theorem 3. Let $A\in\Phi.$
For any Boolean algebra $B$ with conjugate and a map$\xi$: $\Phiarrow B$ , we have $\xi(A)=1$$\Leftrightarrow\vdash_{K_{\dot{t}}}A$

Proof. We have already proved if part. To show the only if part, we assume that $\psi_{K;}A$ . Since
the Boolean algebra with conjugate, if we take a map$\Phi/\equiv$is$\xi:\Phiarrow\Phi/\equiv, \xi(A)=[A],$then on$\Phi/\equiv$

we get$\xi(A)\neq 1$

by$\mu_{K_{\dot{p}}}A.$$\square$We can characterize some logics by Boolean algebras with conjugate.

Theorem 4. Logical systems $K_{t}^{*}+(ext),$ $K_{t}^{*}+(sym),$ $K_{t}^{*}+(d)$ are charactenzed respectively by theBoolean algebras with extensive, symmetr , closed conjugate, that is, for any formula $A\in\Phi$$\dot{v}c$(1)for any Boolean algebra$B$with extensive conjugate and a map$B$with symmetric conjugate and a map$\xi$: $\Phiarrow B$ , we have$\xi(A)=1\Leftrightarrow\vdash_{K_{\dot{t}}+(ext)}A$(2)

for any Boolean algebra$\xi$: $\Phiarrow B$ , we have$\xi(A)=1\Leftrightarrow\vdash_{K_{\dot{t}}+(sym)}A$(3) for any Boolean algebra $B$ with closed conjugate and a map$\Leftrightarrow\vdash_{K_{\dot{t}}+(cl)}A$$\xi$: $\Phiarrow B$ , we have $\xi(A)=1$

51
Proof. We only show that, in any Boolean algebra with typical property, $\xi(A)=1$ for the correspondent
typical axioms in respective cases. Suppose that $\xi(A)=x\in B.$(1) For an extensive conjugate, we have to prove that $\xi(GAarrow A)=1$ . Since$A$$(\varphi, \psi)$$\xi(GAarrow A)=1\Leftrightarrow\xi(GA)\leq\xi(A)$$\Leftrightarrow(\varphi(x’))’\leq x$$\Leftrightarrow x’\leq\varphi(x’)$

andis extensive, we have $\xi(GAarrow A)=1.$(2) Letbe a symmetric conjugate. Since$\varphi$$(\varphi, \psi)$$\varphi=\psi$by assumption, we have$\xi(Aarrow GPA)=1\Leftrightarrow\xi(A)\leq\xi(GPA)$$\Leftrightarrow x\leq\varphi^{\partial}(\psi(x))$$\Leftrightarrow x\leq\psi^{\partial}(\psi(x))$$\Leftrightarrow\varphi(x)\leq\psi(x)$$\Leftrightarrow\varphi(x)\leq\varphi(x)$Thus, $\xi(Aarrow GPA)=1.$(3) Suppose thatis a closed conjugate.
and hence that$(\varphi, \psi)$.

It follows from the assumption that$\varphi^{\partial}(x)\leq$$\varphi^{\partial}(\varphi^{\partial}(x))(x\in B)$$\xi(GAarrow GGA)=1\Leftrightarrow\xi(GA)\leq\xi(GGA)$$\Leftrightarrow\varphi^{\partial}(x)\leq\varphi^{\partial}(\varphi^{\partial}(x))$.

This means that $\xi(Aarrow GPA)=1.$

4$\square$

Decidability

It is well-known that the minimal tense logic
can be characterized by the class of finite Kripke models.
Similarly we can show thatis characterized by the classof finite Boolean algebras with conjugate.
Suppose that. There is a finite Kripke model $\mathcal{M}^{*}=(W, R, v)$ such that $x\not\in v(A)$ for some$x\in W$ , that is, $v(A)\neq W$ . We construct a finite Boolean algebrawith conjugate from the finite
Kripke model
as follows:$K_{t}$$B^{*}$$K_{t}^{*}$$\mu_{K_{\ell}^{*}}A$$B^{*}$$\mathcal{M}^{*}$$B^{*}=\mathcal{P}(W)$$\varphi,$$\psi$: $Barrow B$ are defined respectively by$\varphi(X)=\{x\in B|R(x)\cap X\neq\emptyset\}$$\psi(X)=\{x\in B|R^{-1}(x)\cap X\neq\emptyset\},$where $R(x),$ $R^{-1}(x)$ are defined by$R(x)=\{y\in B|(x, y)\in R\}, R^{-1}(x)=\{y\in B|(y, x)\in R\}$We can prove the fundamental result.
Lemma 5.

$B^{*}$

is a finite Boolean algebra with a conjugate pair

Proof. It is sufficient to prove that
$X,$ $Y\subseteq W$$(i.e., X, Y\in B^{*})$ ,$\varphi,$$\psi$$\varphi,$$\psi$: $B^{*}arrow B^{*}.$: $B^{*}arrow B^{*}$ are conjugate. That is, we have to prove that for$X\cap\varphi(Y)=\emptyset\Leftrightarrow Y\cap\psi(X)=\emptyset.$

Suppose that

$Y\cap\psi(X)\neq\emptyset$. Since $y\in\psi(X)$ for some $y\in Y$ , it follows from definition of $\psi(X)$ that$\exists x\in Xs.t.

(x, y)\in R.$

52
We also have $(x, y)\in R$ and $y\in Y$ . This implies that
$R(x)\cap Y\neq\emptyset$

and $x\in\varphi(Y)$ . The fact that $x\in X$ means$x\in X\cap\varphi(Y)$The converse can be proved similarly. Thus

, that is,$B^{*}$$X\cap\varphi(Y)\neq\emptyset.$is the finite Boolean algebra with the conjugate pair$\varphi,\psi:B^{*}arrow B^{*}.$

Moreover if we take$\square$$\xi^{*}:\Phiarrow B^{*}$

as$\xi^{*}(A)=v(A)$,implies $\xi^{*}(A)\neq 1$ for some finite
then we have $\xi^{*}(A)\neq 1$ from $v(A)\neq W$ . This means that
. It is obvious the converse statement. We thus obtain
Boolean algebra with conjugate andthe next result.
$\psi_{K_{t}}\cdot$$A$$\xi^{*}:B^{*}arrow B^{*}$

Theorem 5. The logic$K_{t}^{*}$

can be chamcterized by the finite Boolean algebras with conjugate.

We can show the following similarly.
Theorem 6. The logics $K_{t}^{*}+(ext),$ $K_{t}^{*}+(sym),$ $K_{t}^{*}+(cl)$ are $chamcter^{l}ized$ by the class of all finite
Boolean algebras with extensive, symmetric, closed conjugate pair, respectively.

Thus we can conclude that our logical systems $K_{t}^{*}(+(ext), +(sym), +(cl))$ are decidable, that is, we
can determine whether a given formula is provable or not by finite steps.

References[1] J.Jarvinen and J.Kortelainen, A unifying study between modal-like operators, topologies, and fuzzysets, TUCS Technical report, 642 (2004)[2] B.Jonsson and A.Tarski, Boolean algebras with operators. Part 1., American Joumal of Mathematics,

vol.73 (1951), 891-939[3] Goldblatt, R., Logics of time and computation, CSLI Lecture Notes No.7 (1987)[4] Lemmon, E.J., New foundation for Lewis modal systems, Joumal of Symbolic Logic, vol.22 (1957),

176-186