数理解析研究所講究録
第 1846 巻 2013 年 94-112

94

A Consideration on Functions Preserving Set Inclusion Relation
富山県立大学工学部 高木昇 (Noboru Takagi)
Department of Electronics and Informatics,
Toyama Prefectural University$Abstract-This$ paper discusses functions over the set of non-empty subsets of $\{0,1, \ldots, r-1\}$
that are monotonic in the set inclusion relation.
and Liteml opemtions play animportant role in multiple-valued logic design/circuits because they can realize any function${\rm Min},$${\rm Max}$over $\{0,1, \ldots, r-1\}$ . Opemtions over the set of non-empty subsets of $\{0,1, \ldots, r-1\}$ that
preserve the set inclusion relation are introduced fromand Liteml opemtions over$\{0,1, \ldots, r-1\}$ . Then, this paper proves someof mathematical properties offunctions over theset of non-empty subsets of $\{0,1, \ldots, r-1\}$ that are composed of the operations introduced.
${\rm Min},$${\rm Max}$

Keywords: Multiple-Valued Logic Design/Circuits, Set Inclusion Relation, Clone Theory

1

Introduction

S. C. Kleene [1] first introduced regularity into temary operations over the set of truth values$\{0,1, u\}$ in the following way.

A truth table for a temary operation is regular if it satisfies the condition thatgiven column (row) contains 1 in the row (column), only if the column (row)
(

$A$

$u$

consists entirely of $1’ s$ ; and likewise for$0$”

Kleene’s regularity is one of the ways how binary operations can be expanded into temary
operations. Table 1 is the truth tables of regular temary operations, which are given from thetraditional binary operations AND, $OR$ and NOT.
It is worth to notice that M. Goto [2] independently introduced temary operations thatare identical with the Kleene’s ternary operations in Table 1. He showed that the ternary
operations can be a model for analyzing undetermined behavior existing in binary systems,
such as hazards in binary logic circuits. After Goto’s work, M. Mukaidono studied mathematical properties of functions over $\{0,1, u\}$ that can be expressed by a formula composed of
the three ternary operations (He called the ternary functions regular ternary logic functions).
One of Mukaidono’s main results[3] is that a function over $\{0,1, u\}$ is a regular ternary logic
function if and only if the function is monotonic in the partial ordered relation, defined by
Figure 1. I. G. Rosenberg [8] indicated that the set of regular temary logic functions is thisclone generated by the Kleene’s temary logic, i.e., the clone is identical with the clone overthe 3-element universe $\{\{0\}, \{1\}, \{0,1\}\}$ that preserves the set inclusion relation
This paper discusses functions over the set of non-empty subsets of $\{0,1, \ldots, r-1\}$ whenis more than 2. In the following, E. anddenote the -valued set $\{0,1, \ldots, r-1\}$ and theset of non-empty subsets of E., respectively.
$f$

$f$

$\subseteq.$$r$$P_{r}$$r$

Table 1: Truth Tables of Regular Ternary Operations NOT, AND and $OR$
NOT
AND
OR

95
$u$

1

$0$

Figure 1: Partial Ordered Relation on $\{0,1, u\}$First, this paper shows a definition for expanding operations over
into operations over
. This definition is identical with the Kleene’s regularity when is equal to 2, and it has
already been shown by M. Mukaidono [4] and I. G. Rosenberg [8]. Min, Max, and Literal
operations play an important role in multiple-valued logic design/circuits, because they canrealize any multiple-valued logic function over . Therefore, Min, Max, and Literal operations
are focused on in this paper. This paper then clarifies mathematical properties of functions
over , which are expressed by formulas composed of the operations given from Min, Max,and Literal operations overThis paper is organized below. Section 2 is for preliminaries. This section shows thedefinition for expanding operations over
into operations over , and then gives some of
their mathematical properties. Section 3 focuses on Min, Max, and Delta Literal operations
over . They are expanded into operations over , and then this section proves a necessary
and sufficient condition for a function overto be expressed by a formula composed ofthese operations. Section 4 shows examples for the results obtained in Section 3. Section
5 discusses mathematical properties of functions overwhen we selected Min, Max, andUniversal Literal operations over . Then, Section 6 gives examples for the results appearedin Section 5 Section 7 concludes the paper.
$E_{r}$$P_{r}$$r$$E_{r}$$P_{r}$$E_{r}.$$E_{r}$$P_{r}$$E_{r}$$P_{r}$$P_{r}$$P_{r}$$E_{r}$

2

Preliminaries

Let
be the -valued set $\{0, \ldots, r-1\}$ , and let
be the set of all non-empty subsets of, i.e.,, where 2 is the power set of . If a subset of
consists of only
one element, then it is called a singleton. The set of all singletons ofis denoted byi.e., $S_{r}=\{\{0\}, \ldots, \{r-1\}\}$ . It is evident that the set
is a partial ordered set in the set
inclusion . In this paper, elements of the set
are denoted by small letters such as, etc., while elements of the set$(i.e., non-$ empyt subsets $of E_{r})$ are denoted by capitalletters such as $A,$ $B,$ $C,$ $X,$ $Y$ etc.
$E_{r}$$r$$P_{r}$$E_{r}$$P_{r}=2^{E_{r}}-\{\emptyset\}$$E_{r}$$E_{r}$$E_{r}$$E_{r}$$S_{r},$$P_{r}$$E_{r}$$\subseteq$

$x,$

$a,$

$b,$

$c,$

$P_{r}$$y$Definition 1 Let be an -ary operation on
respect to is defined by setting
$0$

$n$

$E_{r}$. Then, an -ary operation$n$$\hat{o}$on$P_{r}$

with$0$$\hat{o}(A_{1}, \ldots, A_{n})=\{o(a_{1}, \ldots, a_{n})|a_{1}\in A_{1}, \ldots,a_{n}\in A_{n}\}$for any element$(A_{1}, \ldots, A_{n})\in P_{r}^{n}$.

(End of Definition)

The following three operations play an important role in multiple-valued logic design because -valued functions consisting of these operations and the constants$r-1$ are
$r$

$0,$

$\ldots,$

96
Table 3: Truth Table ofTable 4: Truth Table of$\sqcup$$X^{S}$

functionally complete on the set $E_{r}[5].$$a \cdot b=\min(a, b)$ ,$a+b= \max(a, b)$ ,$x^{S}$$=$$\{\begin{array}{ll}r-1 if x\in S0 otherwise\end{array}$where $b\in E_{r}$ and. The unary operations
are often called the universal literals.
However, when is a singleton,
is sometimes called a delta literal.
For simplicity, in writing elements of , we will remove brackets and put an underline if$\{0,2\}$ and $\{0,1,2\},$no confusion arises. That is, for example,
and 012 stand forrespectively. Tables 2, 3 and 4 are truth tables of operations onwith respect toand, respectively. Because this paper focuses on the operations on $P$ with respect toand, respectively. 1, they are denoted byandThis paper does not allow any kinds of compositions of the operations
andonCompositions are restricted by the form of the formulas defined below.
$x^{S}$$S\subseteq E_{r}$$a,$$x^{s}$$S$$P_{r}$$\underline{0},$$\{0\},$$\underline{02}$.

$P_{3}$$x^{S}$$x^{s}$$\wedge,$$\sqcup$$X^{S}$.,$\cdot,$$\wedge,$$\sqcup$$+$$+$$X^{S}$$P_{r}.$

Definition 2 Formulas are defined inductively in the following way.
(1) Constants $\{0\},$(2) If$G$$\ldots,$$\{r-1\}$ and literals $X_{i}^{S}(i=1, \ldots, n and S\in P_{r})$are formulas.

and $H$ are formulas, then $(G\wedge H)$ and $(G\sqcup H)$ are also formulae.

(3) It is a formula if and only if we get it from (1) and (2) in a finite number of steps.
(End of Definition)

lThe operations
system$(P_{r}, \wedge, \sqcup)$and do not satisfy the absorption laws and the distributive laws. Thus, the algebraic
do not form a lattice.
$\wedge$$\sqcup$

97
In writing formulas, we sometimes omit the operation for simplicity.
It is evident that every formula expresses a function onwhen each variable
takes
an element of . Furthermore, it is easy to verify that the formulas can not express all of
the functions on , i.e., the functions on
expressed by the formulas are not functionallycomplete on . Thus, one of the main subjects of the paper is to clear what functions on
can be expressed by the formulas.
In the following, for any elements $(A_{1}, \ldots, A_{n})$ and $(B_{1}, \ldots, B_{n})$ of$(B_{1}, \ldots, B_{n})$ stands forfor all $i’ s$ . Moreover, $(A_{1}, \ldots, A_{n})\cap(B_{1}, \ldots , B_{n})=\emptyset$ stands
forfor some$\wedge$$P_{r}$$X_{i}$$P_{r}$$P_{r}$$P_{r}$$P_{r}$$P_{r}$$(A_{1}, \ldots , A_{n})\subseteq$$P_{r}^{n},$$A_{i}\subseteq B_{i}$$A_{i}\cap B_{i}=\emptyset$$i.$

Theorem 12 Suppose a function on
holds for any element$f$

Theorem 2 Suppose a function on
holds for any elements$(B_{1}, \ldots, B_{n})$ .
$f$$f(B_{1}, \ldots, B_{n})$3can be expressed by a formula. Then,$P_{r}$$f(A_{1}, \ldots, A_{n})\in$$(A_{1}, \ldots, A_{n})\in S_{r}^{n}.$$S_{r}$$P_{r}$

can be expressed by a formula. Then,andofsuch that$f(A_{1}, \ldots, A_{n})\subseteq$$(B_{1}, \ldots, B_{n})$$(A_{1}, \ldots , A_{n})$$P_{r}^{n}$$(A_{1}, \ldots, A_{n})\subseteq$

Functions Expressed by Formulas Composed ofand Delta Literals

This section shows a necessary and sufficient condition for functions onpressed by formulas with the operations
and delta literals.
$\wedge,$

Theorem 3 Let$A_{1},$$\ldots,$$A_{i-1},$ $A_{i+1},$$\ldots,$$P_{r}$$\wedge,$$u,$that can be ex-$u$$A_{n}$

be elements of$P_{r}$. If a function

$f$

on

$P_{r}$

is ex-

pressed by a formula, then the least element of $f(A_{1)}\ldots, A_{i-1}, A, A_{i+1}, \ldots, A_{n})$ (which is asubset of ) is equal to the least element of $f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$ for any elements$A$
and $B$ of $P_{r}-S_{r}$ , i.e.,$E_{r}$$\min f(a_{1}, \ldots, A_{i-1}, A, A_{i+1}, \ldots, A_{n})=\min f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$holds for any elements

$A$

and

$B$

of $P_{r}-S_{r}.$From Theorems 1, 2 and 3, any function
following Condition A.
Condition $A$ : Let(1) If$f$

be a function on$(A_{1}, \ldots, A_{n})\in S_{r}^{n}$

$f$

on

$P_{r}$

expressed by a formula satisfies the$P_{r}.$, then $f(A_{1}, \ldots, A_{n})\in S_{r}.$(2) For any elements $(A_{1}, \ldots, A_{n})$ andimplies $f(A_{1}, \ldots, A_{n})\subseteq f(B_{1}, \ldots, B_{n})$ .

$(B_{1}, \ldots , B_{n})$(3) Letof$P_{r}^{n},$$(A_{1}, \ldots, A_{n})\subseteq(B_{1}, \ldots, B_{n})$be elements of . Then, the least element ofis equal to the least element of$f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$ for any elements
and of $P_{r}-S_{r}$ , i.e.,$A_{1},$$\ldots,$$A_{i-1},$ $A_{i+1},$$\ldots,$$A_{n}$$P_{r}$$f(A_{1}, \ldots, A_{i-1}, A, A_{i+1}, \ldots, A_{n})$

$A$

$B$

$\min f(A_{1}, \ldots, A_{i-1}, A, A_{i+1}, \ldots, A_{n})=\min f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$holds for any elements$A$

and $B$ of $P_{r}-S_{r}.$2All of the proofs in this paper are omitted because of the limitation of the space.

98
In the remainder of this section, it is proven that Condition A is a necessary and sufficient
to be expressed by a formula with the operations
condition for a function on, anddelta literals.
$P_{r}$$\wedge,$$\sqcup$Definition 3 Let be a function on $P$., and let $A=(A_{1}, \ldots, A_{i-1}, A_{i+1}, \ldots, A_{n})$ be an. Then, we define one-variable functions
element ofand $\hat{f}_{A}^{i}(X)(i=1, \ldots, n)$expressed by the following formulas.
$f$$S_{f}^{n-1}$$\check{f}_{A}^{:}(X)$

where

(1)

,

$\check{f}_{A}^{i}(X)=\sqcup s\in E_{r}\{\{s\}\bigwedge_{B\in P_{A}^{+}(s)}\sqcup X^{B}\}$is the set of all maximal elements of the set$\check{P}_{A}^{i}(s)$$P_{A}^{i}(s)= \{B\in P_{r}|\min f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})=s\}$

,

(2)

and
$\hat{f}_{A}^{i}(X)=\sqcup S\in P_{r}-S, (u[\{t\}\wedge\{_{B\in\hat{Q}}\sqcup_{\dot{A}(S)}(\bigwedge_{e\in B}X^{\{e\}})\}])$

where$\hat{Q}_{A}^{i}(S)$(3),

is the set of all minimal elements of.

(4)$Q_{A}^{i}(S)=\{B\in P_{r}-S_{r}|f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})=S\}$In the formulae (1) and (3), if$\check{P}_{A}^{i}(s)$and$\prod_{B\in\check{P}_{A}^{i}(s)}X^{B}$

are defined asand$\hat{Q}_{A}^{i}(S)$are the empty set, then$B \in\hat{Q}_{A}^{j}(S)\sqcup(\bigwedge_{k\in B}X^{\{k\}})$, respectively. Moreover, in the formula (1), when $B=E_{r}$ , thenis theconstant $\{r-1\}$ .
(End of Definition)$X^{B}$$\{0\}$In the formula (1), if is a function satisfying Condition , then any subset
is asubset of , or it is equal to. Now, let us show this property. Suppose an element of. Then, by Condition $A(3)$ , it follows thatis a member ofis also a member of. Therefore, when an element of, thenis a member ofis also a member. This fact implies thatofis a subset of ., or it is equal to. So, the formula(1) is well-defined when is a function satisfying Condition A.
$A$

$f$

$P_{r}-S_{f}$$\check{P}_{A}^{i}(s)$$B$$\{E_{r}\}$$S_{r}$$P_{A}^{i}(s)$$E_{r}$$P_{r}-S_{f}$$P_{A}^{i}(s)$$P_{A}^{i}(s)$$\check{P}_{A}^{i}(s)$$P_{A}^{i}(s)$$E_{r}$$S$$\{E_{r}\}$$f$

Lemma 1 Let $A=$ $(A_{1}, \ldots , A_{i-1}, A_{i+1}, \ldots, A_{n})$ be an element ofsatisfying Condition $A,$

$S_{r}^{n-1}$. Then, for a function$f$$\check{f}_{A}^{i}(B)=$$\{\begin{array}{ll}f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n}) if f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})\in S_{r}K otherwise\end{array}$holds for any element

$B$

of

$P_{r}$, where $K$ is an element of$P_{r}$

such that$\{f_{0}\}\subseteq K\subseteq f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$and$f_{0}$

is the least element of $f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$ .

(End of Lemma)

99Lemma 2 Let $A=(A_{1}, \ldots, A_{i-1}, A_{i+1}, \ldots, A_{n})$ be an element ofsatisfying Condition $A,$

$S_{r}^{n-1}$. Then, for a function$f$$\hat{f}_{A}^{i}(B)=$$\{\begin{array}{ll}\{0\} if f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})\in S_{r}\{0\}\cup f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n}) otherwise\end{array}$holds for any element $B\in P_{r}$ .

(End of Lemma)

Lemma 3 Let $A=(A_{1}, \ldots, A_{i-1}, A_{i+1}, \ldots, A_{n})$ be an element ofsatisfying Condition $A,$

$S_{r}^{n-1}$. Then, for a function$f$$\check{f}_{A}^{i}(B)\sqcup\hat{f}_{A}^{i}(B)=f(A_{1}, \ldots, A_{i-1}, B, A_{i+1}, \ldots, A_{n})$holds for any element $B\in P_{r}.$In the following, this section proves that any function satisfying Condition A can be expressed by a formula, and also shows a method how a formula can be formulated by a function
satisfying Condition A.

Definition 4 Let be a function on
by the following formula.
$f$$P_{r}$. Then,$f_{1}$

is defined as a function on$f_{1}(X_{1}, \ldots, X_{n})=\sqcup f^{i}(X_{1}, \ldots, X_{n})i=1n$$P_{r}$

expressed

,

(5)

where

$f^{i}(X_{1}, \ldots, X_{n})=\sqcup A=(A_{1},\ldots,A_{i-1},A_{i+1},\ldots,A_{n})\in S_{r}^{n-1}(\bigwedge_{j=1(j\neq i)}^{n}X_{j}^{A_{j}}\wedge(\check{f}_{A}^{i}(X_{i})\sqcup\hat{f}_{A}^{i}(X_{i})))$(End of Definition)
Here, let us introduce a subset of$P_{r}^{n}$, which will be denoted by $I(r, n)$ , below.

$I(r, n)= \bigcup_{i=1}^{n}\{(A_{1}, \ldots, A_{n})\in P_{r}^{n}|A_{i}\in P_{r}-S_{r}$That is, each element$(A_{1}, \ldots, A_{n})$and$A_{1},$$\ldots,$$A_{i-1},$ $A_{i+1},$

of $I(r, n)$ consists of elements of$S_{r}$$\ldots,$$A_{n}\in S_{r}\}$, but except for one.

Lemma 4 Let $F$ be a function satisfying Condition A. Then,$f_{1}(A_{1}, \ldots, A_{n})=\{\begin{array}{ll}f(A_{1}, \ldots, A_{n}) if f(A_{1}, \ldots, A_{n})\in S_{r}\cup I(r, n)K otherwise\end{array}$holds for any element$\{0\}\cup f(A_{1}, \ldots, A_{n})$ .

$(A_{1}, \ldots, A_{n})\in P_{r}^{n}$, where $K$ is an element of$P_{r}$

such that(End of Lemma)$\{0\}\subseteq K\subseteq$

100
Definition 5 Let be a function on , let be an element of $P_{r}-S_{r}$ , and let
the set of all minimal elements of the following subset of$f$$P_{f}$$S$$\hat{T}(f, S)$

is$P_{r}^{n}.$$T(f, S)=\{(A_{1}, \ldots, A_{n})\in P_{r}^{n}|f(A_{1}, \ldots, A_{n})=S$

Then,$f_{2}$

is defined as a function on$P_{r}$

and$(A_{1}, \ldots, A_{n})\not\in S_{r}^{n}\cup I(r, n)\}$(6)expressed by the following formula.

$f_{2}(X_{1}, \ldots, X_{n})=\{s_{0}\}U[u\{\sqcup\{t\}Af_{S}(X_{1}, \ldots, X_{n})\}]$

,

(7)

where

$f_{S}(X_{1}, \ldots, X_{n})=\{\begin{array}{ll}(A_{1},\ldots,A_{n})\in\hat{T}(f,S)\sqcup\{\bigwedge_{b\in A_{1}}X_{1}^{\{b\}}\wedge\cdots\wedge\bigwedge_{b\in A_{n}}X_{n}^{\{b\}}\} if \hat{T}(f, S)\neq\emptyset\{0\} otherwise\end{array}$and$s_{0}$

is the least element ofLemma 5 Let$f$$\bigcup_{(A_{1},\ldots,A_{n})\in P_{r}^{n}}f(A_{1}, \ldots, A_{n})$be a function on$P_{r}$.

(8)(End of Definition)satisfying Condition A. Then,$f_{2}(A_{1}, \ldots, A_{n})=\{\begin{array}{ll}\{s_{0}\} if (A_{1}, \ldots, A_{n})\in S_{r}^{n}\cup I(r, n)f(A_{1}, \ldots, A_{n}) otherwise,\end{array}$holds for any element$(A_{1}, \ldots, A_{n})\in P_{r}^{n}$$\bigcup_{(A_{1},\ldots,A_{n})\in P_{r}^{n}}f(A_{1}, \ldots, A_{n})$Theorem 4 Let$f$, where$s_{0}$.

be a function on$P_{r}$

is the least element of the union(End of Lemma)

satisfying Condition A. Then,$f(A_{1}, \ldots, A_{n})=f_{1}(A_{1}, \ldots, A_{n})\sqcup f_{2}(A_{1}, \ldots, A_{n})$holds for any element
respectively.

4$(A_{1}, \ldots, A_{n})\in P_{r}^{n}$, where$f_{1}$

and$f_{2}$

are the formulae (5) and (7),(End of Theorem)

Examples of Functions Satisfying Condition A

whose truth table is given in Table 5. It is not difficult to verify
Consider the function onthat satisfies Condition A. Then, this section illustrates how we can form the formula that
expresses the function $f.$$f$

$P_{3}$$f$

Example 1 Let us first consider the formulas (1) and (3). It follows by Eq. (2) that we havethe following three subsets of$P_{3}.$$P_{\underline{0}}^{1}(0) = \{B\in P_{3}|\min f(B, \underline{0})=0\}=\{\underline{0}, \underline{2},\underline{01}, \underline{02}, \underline{12}, \underline{012}\}$$P_{\underline{0}}^{1}(1) = \{B\in P_{3}|\min f(B, \underline{0})=1\}=\{\underline{1}\}$$P_{\underline{0}}^{1}(2) = \{B\in P_{3}|\min f(B, \underline{0})=2\}=\emptyset$

101
Table 5: Example of Function

Thus, since(1).

$\check{P}_{\underline{0}}^{1}(0)=\{\underline{012}\},\check{P}_{\underline{0}}^{1}(1)=\{\underline{1}\}$

, and

$f$

Satisfying Condition A$\check{P}_{\underline{0}}^{1}(2)=\emptyset$, we have the formula$\check{f}_{\underline{0}}^{1}(X)$by Eq.

$\check{f}_{\underline{0}}^{1}(X) = (\underline{0}\wedge\underline{012})\sqcup(\underline{1} A X^{\underline{1}})\sqcup(\underline{2}\wedge\underline{0})$(9)$= \underline{1}\wedge X^{\underline{1}}$In a similar way, we have the formulas$\check{f}_{\underline{1}}^{1}(X),\check{f}_{\underline{2}}^{1}(X),\check{f}_{\underline{0}}^{2}(Y),\check{f}_{\underline{1}}^{2}(Y)$, and$\check{f}_{\underline{2}}^{2}(Y)$, below.

$\check{f}_{\underline{1}}^{1}(X)=\underline{1}X^{\underline{1}}\sqcup X^{\underline{2}}$$\check{f}_{\underline{2}}^{1}(X)=X^{\underline{1}}$(10)$\check{f}_{\underline{0}}^{2}(Y)=\underline{0}$$\check{f}_{\underline{1}}^{2}(Y)=\underline{1}\sqcup Y^{\underline{2}}$$\check{f}_{\underline{2}}^{2}(Y)=Y^{\underline{1}}$Moreover, it follows by Eq. (4) that we have
$Q_{\underline{0}}^{1}(\underline{01}) = \{B\in P_{3}-S_{3}|f(B,\underline{0})=\underline{01}\}=\{\underline{01}\},$$Q_{\underline{0}}^{1}(\underline{02}) = \{B\in P_{3}-S_{3}|f(B, \underline{0})=\underline{02}\}=\emptyset,$$Q_{\underline{0}}^{1}(\underline{12})$$=$$\{B\in P_{3}-S_{3}|f(B,\underline{0})=\underline{12}\}=\emptyset$, and$Q_{\underline{0}}^{1}(\underline{012}) = \{B\in P_{1}-S_{3}|f(B, \underline{0})=\underline{012}\}=\{\underline{12}, \underline{012}\}.$

Thus, sinceby Eq. (3).

$\hat{Q}_{\underline{0}}^{1}(\underline{01})=\{\underline{01}\},\hat{Q}_{\underline{0}}^{1}(\underline{02})=\hat{Q}_{\underline{0}}^{1}(\underline{12})=\emptyset$

and$\hat{Q}_{\underline{0}}^{1}(\underline{012})=\{\underline{12}\}$, we have the formula$\hat{f}_{\underline{0}}^{1}(X)$$\hat{f}_{\underline{0}}^{1}(X) = (\underline{0}X^{\underline{0}}X^{\underline{1}}\sqcup\underline{1}X^{\underline{0}}X^{\underline{1}})\sqcup\underline{0}\sqcup\underline{o}u(\underline{0}X^{\underline{2}}X^{\underline{2}}u\underline{1}X^{\underline{2}}X^{\underline{2}}\sqcup\underline{2}X^{\underline{2}}X^{\underline{2}})$$= \underline{1}X^{\underline{0}}X^{\underline{1}}\sqcup\underline{1}X^{\underline{1}}X^{\underline{2}}\sqcup X^{\underline{1}}X^{\underline{2}}$In a similar way, we have the formulas.

$\hat{f}_{\underline{1}}^{1}(X),\hat{f}_{\underline{2}}^{1}(X),\hat{f}_{\underline{0}}^{2}(Y),\hat{f}_{\underline{1}}^{2}(Y)$

(11)
, and

$\hat{f}_{\underline{2}}^{2}(Y)$, below.

$\hat{f}_{\underline{1}}^{1}(X)=\underline{1}X^{\underline{0}}X^{\underline{1}}\sqcup X^{\underline{0}}Y^{\underline{2}}\sqcup\underline{1}X^{\underline{1}}X^{\underline{2}}uX^{\underline{1}}X^{\underline{2}},$$\hat{f}_{\underline{2}}^{1}(X)=X^{\underline{0}}X^{\underline{1}}uX^{\underline{1}}X^{\underline{2}},$,$\hat{f}_{\underline{0}}^{2}(Y)=Y^{\underline{1}}Y^{\underline{2}}$$\hat{f}_{\underline{1}}^{2}(Y)=\underline{1}Y^{\underline{0}}Y^{\underline{2}}\sqcup X^{\underline{0}}Y^{\underline{2}}\sqcup\underline{1}Y^{\underline{1}}Y^{\underline{2}}uY^{\underline{1}}Y^{\underline{2}},$$\hat{f}_{\underline{2}}^{2}(Y)=Y^{\underline{0}}Y^{\underline{1}}\sqcup Y^{\underline{1}}Y^{\underline{2}}.$

(12)

102
Table 6: ‘Ruth Tables of$\check{f}_{A}^{1}(X)$and$\hat{f}_{A}^{1}(X)$

Table 7: Truth Tables ofTable 8: Truth Table ofTables 6 and 7 show the truth tables of$\check{f}_{A}^{i}$and$\hat{f}_{A}^{i}$$\check{f}_{A}^{2}(Y)$and$\hat{f}_{A}^{2}(Y)$$f_{A}^{i}=\check{f}_{A}^{i}u\hat{f}_{A}^{i}$for which $i=1,2$ and$A\in\{\underline{0},\underline{1}, \underline{2}\}.$(End of Example)
It follows by Lemma 3 that$f(X, B)=\check{f}_{A}^{1}(X)\sqcup\hat{f}_{A}^{1}(X)$and$f(B, Y)=\check{f}_{A}^{2}(Y)\sqcup\hat{f}_{A}^{2}(Y)$hold for every
and every $B\in P_{3}$ , where
andbeen obtained in Eqs. (9), (10), (11) and (12). Table 8 shows the truth tables of$\check{f}_{A}^{1}(X),\hat{f}_{A}^{1}(X),\check{f}_{A}^{2}(Y)$$A\in\{\underline{0}, \underline{1}, \underline{2}\}$where $i=1,2$ and$\hat{f}_{A}^{2}(Y)$have$\check{f}_{A}^{i}\sqcup\hat{f}_{A}^{i},$$A\in\{\underline{0},\underline{1},\underline{2}\}.$

Example 2 Let us next consider the formula (5) in Definition 4. It follows by Eqs. (9) and(11) that we have the formula
below.
$\check{f}_{\underline{0}}^{1}(X)\sqcup\hat{f}_{\underline{0}}^{1}(X)$$\check{f}_{\underline{0}}^{1}(X)\sqcup\hat{f}_{\underline{0}}^{1}(X) =\underline{1}X^{\underline{1}}\sqcup\underline{1}X^{\underline{0}}X^{\underline{1}}\sqcup\underline{1}X^{\underline{1}}X^{\underline{2}}\sqcup X^{\underline{1}}X^{\underline{2}}$$=\underline{1}X^{\underline{1}}\sqcup X^{\underline{1}}X^{\underline{2}}$In a similar way, by Eqs. (10), (11) and (12), we have the formulae$\check{f}_{\underline{1}}^{1}(X)\sqcup\hat{f}_{\underline{1}}^{1}(X) =\underline{1}X^{\underline{1}}\sqcup X^{\underline{2}},$$\check{f}_{\underline{2}}^{1}(X)\sqcup\hat{f}_{\underline{2}}^{1}(X) = X^{\underline{1}},$$\dot{f}_{\underline{0}}^{2}(Y)\sqcup\hat{f}_{\underline{0}}^{2}(Y) = Y^{\underline{1}}Y^{\underline{2}},$$\check{f}_{\underline{1}}^{2}(Y)\sqcup\hat{f}_{\underline{1}}^{2}(Y) =\underline{1}\sqcup Y^{\underline{2}},$$\check{f}_{\underline{2}}^{2}(Y)\sqcup\hat{f}_{\underline{2}}^{2}(Y) = Y^{\underline{1}}.$

Therefore, the formula $f_{1}(X, Y)$ of (5) in Definition 4 is given ae$f_{1}(X, Y)=f^{1}(X, Y)\sqcup f^{2}(X, Y)$ ,

(13)

103
Table 9: Ruth Table of $f_{1}(X, Y)$

where$f^{1}(X, Y)$$=$$Y^{\underline{0}}(\check{f}_{\underline{0}}^{1}(X)u\hat{f}_{\underline{0}}^{1}(X))\sqcup Y^{\underline{1}}(\check{f}_{\underline{1}}^{1}(X)\sqcup\hat{f}_{\underline{1}}^{1}(X))\sqcup Y^{\underline{2}}(\check{f}_{\underline{2}}^{1}(X)\sqcup\hat{f}_{\underline{2}}^{1}(X))$$f^{2}(X, Y)$$=$$X^{\underline{0}}(\check{f}_{\underline{0}}^{2}(Y)\sqcup\hat{f}_{\underline{0}}^{2}(Y))\sqcup X^{\underline{1}}(\check{f}_{\underline{1}}^{2}(Y)\sqcup\hat{f}_{\underline{1}}^{2}(Y))\sqcup X^{\underline{2}}(\check{f}_{\underline{2}}^{2}(Y)\sqcup\hat{f}_{\underline{2}}^{2}(Y))$

Table 9 is the truth table of $f_{1}(X, Y)$ .

and.

(End of Example)

Example 3 In this example, let us consider the formula (7) in Definition 5. It follows by Eq.
(6) that we have the following subsets of$P_{3}^{2}.$$T(f,\underline{01}) = \emptyset$$T(f, \underline{02}) = \{(\underline{02}, \underline{01}), (\underline{02}, \underline{12}), (\underline{02}, \underline{012})\}$$T(f, \underline{12}) = \emptyset$$T(f,\underline{012})$$=$$\{(A, B)|A\in\{\underline{01},$ $\underline{12},012\}$and $B\in P_{3}-S_{3}\}$

Therefore, since we have$\hat{T}(f, \underline{01}) = \emptyset,$$\hat{T}(f, \underline{02}) = \{(\underline{02}, \underline{01}), (\underline{02}, \underline{12})\},$$\hat{T}(f, \underline{12})$$=$$\emptyset$, and$\hat{T}(f, \underline{012}) = \{(\underline{01}, \underline{01}), (\underline{01}, \underline{02}), (\underline{01}, \underline{12}), (\underline{12}, \underline{01}), (\underline{12},\underline{02}), (\underline{12}, \underline{12})\},$

it follows by Eq. (8) that we have the following formulas.
$f_{\underline{01}}(X, Y) =\underline{0}$$f_{\underline{02}}(X, Y) = X^{\underline{0}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{1}}uX^{\underline{0}}X^{\underline{2}}Y^{\underline{1}}Y^{\underline{2}}$$f_{\underline{12}}(X, Y) =\underline{0}$$f_{\underline{012}}(X, Y) = X^{\underline{0}}X^{\underline{1}}Y^{\underline{0}}Y^{\underline{1}}\sqcup X^{\underline{0}}X^{\underline{1}}Y^{\underline{0}}Y^{\underline{2}}\sqcup X^{\underline{0}}X^{\underline{1}}Y^{\underline{1}}Y^{\underline{2}}\sqcup$$X^{\underline{1}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{1}}uX^{\underline{1}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{2}}\sqcup X^{\underline{1}}X^{\underline{2}}Y^{\underline{1}}Y^{\underline{2}}$Thus, the formula $f_{2}(X, Y)$ of (7) in Definition 5 is obtained as the formula below.
$f_{2}(X, Y)$$=\underline{0}\sqcup\{0f_{\underline{02}}(X, Y)\sqcup\underline{2}f_{\underline{02}}(X, Y)\}\sqcup\{\underline{O}f_{\underline{012}}(X, Y)u1J_{\underline{012}}(X, Y)\sqcup\underline{2}f_{\underline{012}}(X, Y)\}$$= f_{\underline{02}}(X, Y)\sqcup\underline{1}f_{\underline{012}}(X, Y)\sqcup f_{\underline{012}}(X, Y)$

Table 10 is the truth table of $f_{2}(X, Y)$ .

(14)(End of Example)

It follows by Theorem 4 that the function of Table 5 can be expressed by the formula, where $f_{1}(X, Y)$ and $f_{2}(X, Y)$ are the formulas given in (13) and (14),respectively.
$f$$f_{1}(X, Y)\sqcup f_{2}(X, Y)$

104Functions Expressed by Formulas Composed ofand Universal Literals

5$\wedge,$$\sqcup$

expressed by formulae, which are composed of theThis section discusses functions on
operations
and universal literals. Then, a necessary and sufficient condition for a function
to be expressed by a formula when is equal to 3.
on$P_{r}$$\wedge,$$\sqcup$$P_{r}$$r$

Theorem 5 Let$f$

be a function on$P_{r}$. If$f$can be expressed by a formula, then$\bigcap_{A\in P_{r}-S_{r}}f(A_{1}, \ldots, A_{i-1}, A, A_{i+1}, \ldots, A_{n})\neq\emptyset$

holds for any elements$A_{1},$$\ldots,$$A_{t-1},$ $A_{i+1},$

By Theorems 1, 2 and 5, any function
Condition B.

Condition$B$(1) If: Let$f$

be a function on$(A_{1}, \ldots, A_{n})\in S_{r}^{n}$$\ldots,$$f$on$A_{n}$$P_{r}$

of$P_{r}$.

(End of Theorem)

expressed by a formula satisfies the following$P_{r}.$, then $f(A_{1}, \ldots, A_{n})\in S_{r}.$(2) For any elements $(A_{1}, \ldots, A_{n})$ and $(B_{1}, \ldots, B_{n})$ ofimplies $f(A_{1}, \ldots, A_{n})\subseteq f(B_{1}, \ldots, B_{n})$ .
(3)$\bigcap_{A\in P_{r}-S_{r}}f(A_{1}, \ldots, A_{i-1}, A, A_{i+1}, \ldots, A_{n})\neq\emptyset$$A_{i+1},$$\ldots,$$A_{n}$

of$P_{r}^{n},$$(A_{1}, \ldots, A_{n})\subseteq(B_{1}, \ldots, B_{n})$holds for any elements$A_{1},$$\ldots,$$A_{i-1},$$P_{r}.$In the following, this section proves that Condition is a necessary and sufficient condition
for a function on
to be expressed by a formula with the operations, and universal
literals.
$B$$P_{3}$$\wedge,$$\sqcup$Definition 6 Let
be any element of . Then,is said tobe the type-l term corresponding to. Next, letbe any element of. Then,is said to be the type-2 term corresponding to$(A_{1}, \ldots, A_{n})$$\alpha=X_{1}^{A_{1}}\wedge\cdots\wedge X_{n}^{A_{n}}$$P_{r}^{n}$$(B_{1}, \ldots, B_{n})$$(A_{1}, \ldots, A_{n})$$P_{r}^{n}-S_{r}^{n}$$\beta=\bigwedge_{e\in B_{1}}X_{1}^{\{e\}}\wedge\cdots\wedge\bigwedge_{e\in B_{n}}X_{n}^{\{e\}}$$(B_{1}, \ldots, B_{n})$.

(End of Definition)

Let be an element of , and let be an element of $P.$ $-S_{r}$ . Then, it is eaey to verify
that the following two equations are valid.
$S$

$T$

$P_{r}$$X^{S}$$=$(15)$\{\begin{array}{ll}\{r-1\} if X\subseteq S\{0\} if X\cap S=\emptyset\{0, r-1\} otherwise\end{array}$(16)$\bigwedge_{e\in T}X^{\{e\}} = \{\begin{array}{ll}\{0, r-1\} if T\subseteq X\{0\} otherwise\end{array}$$\alpha(A_{1}, \ldots, A_{n})=\{r-1\},$ $\{0, r-1\},$
Therefore, for any type-l term and any type-2 term
, and $\beta(A_{1}, \ldots, A_{n})=\{0, r-1\}$ ororhold for any element$\beta,$$\alpha$$\{0\}$

Lemma 6 For any type-l term$\{0\}$$\alpha$corresponding to$(A_{1}, \ldots, A_{n})\in P_{r}^{n}.$$(A_{1}, \ldots, A_{n})\in P_{r}^{n},$105(1) $(B_{1}, \ldots, B_{n})\subseteq(A_{1}, \ldots, A_{n})$ iff $\alpha(B_{1}, \ldots, B_{n})=\{r-1\},$(2) $(A_{1}, \ldots, A_{n})\cap(B_{1}, \ldots, B_{n})=\emptyset$ iff $\alpha(B_{1}, \ldots, B_{n})=\{0\},$(3) $(B_{1}, \ldots, B_{n})\not\in(A_{1)}\ldots, A_{n})$ and $(A_{1}, \ldots, A_{n})\cap(B_{1}, \ldots, B_{n})=\emptyset iff\alpha(B_{1}, \ldots, B_{n})=$$\{0, r-1\}$

hold for any$(B_{1}, \ldots , B_{n})\in P_{r}^{n}$.

Lemma 7 For any type-2 term(End of Lemma)$\alpha$corresponding to $(A_{1}, \ldots, A_{n})\in P_{r}^{n}-S_{r}^{n},$(1)$(A_{1}, \ldots, A_{n})\subseteq(B_{1}, \ldots, B_{n})$iff $\alpha(B_{1}, \ldots, B_{n})=\{0, r-1\},$(2)$(A_{1}, \ldots, A_{n})\not\subset(B_{1}, \ldots, B_{n})$iff $\alpha(B_{1}, \ldots, B_{n})=\{0\}$hold for any$(B_{1}, \ldots, B_{n})\in P_{r}^{n}$.

(End of Lemma)

be a function satisfying Condition , and let be an element of
two subsets of, denoted by $L(f, S)$ and $U(f, S)$ , below.
Let

$B$

$f$

$S$

$P_{r}$. Then, define$P_{r}^{n}$$L(f, S)$$=$$\{(A_{1}, \ldots, A_{n})\in P_{r}^{n}|f(A_{1}, \ldots, A_{n})\subseteq S\}$and$U(f, S) = \{(A_{1}, \ldots, A_{n})\in P_{r}^{n}|f(A_{1}, \ldots, A_{n})\cap S\neq\emptyset\}.$Let
and $U’(f, S)$ be the sets of all maximal elements of $L(f, S)$ and of all minimal$U(f,S)$ , respectively. Rrther, let $\hat{U}(f, S)=U’(f, S)-S_{r}^{n}.$elements of$\check{L}(f, S)$

Lemma 8 Let be a function satisfying Condition
can be expressed by the following formula.
$f$

$B$

, and let$S$

be an element of$P_{r}$. Then,$(f)^{S}$$(f)^{s}=\{\begin{array}{ll}A\in\check{L}(fS)\sqcup,\alpha_{A}\sqcup\sqcup,\beta_{A}A\in\hat{U}(fS) if \check{L}(f, S)\neq\emptyset or \hat{U}(f, S)\neq\emptyset\{0\} otherwise\end{array}$where$\alpha_{A}$and$\beta_{A}$are the type-l and type-2 terms corresponding to

$A$

(17)

, respectively.
(End of Lemma)

Now, let us consider formulas of one-variable functions satisfying Condition B. Any onevariable function satisfying Condition is in at least one of the following three cases 3.
$B$

$f$

(B-1)

$f(A)\neq\underline{01}$holds for any element $A\in P_{3}-S_{3}.$(B-2)$f(A)\neq\underline{02}$holds for any element $A\in P_{3}-S_{3}.$(B-3)$f(A)\neq\underline{12}$holds for any element $A\in P_{3}-S_{3}.$is in neither one of the cases( -1), ( -2), ( -3), then it implies that we have three distinct elements$\overline{3Iff}$insuch that
, and
.
$B$

$A,$

$B,$ $C$

that

$f$

$P_{3}-S_{3}$$f(A)=\underline{01},$

satisfies Condition $B(3)$ .

$B$

$B$

$f(B)=\mathscr{Q}$$f(C)=\underline{12}$However, this contradicts to the fact

106
Table 11: Example of ( -4)

Table 12: Example of ( -5)

$B$

$B$

Table 13: Example of ( -6)$B$

Property 1 Any one-variable function
following formula.

$f$satisfying Condition$f^{\underline{12}}(X)\wedge(\underline{1}\sqcup f^{\underline{02}}(X))$$f(X)=$$\{$$(\underline{1}\wedge f^{\underline{1}}(X))\sqcup f^{\underline{2}}(X)\sqcup(\underline{1}\wedge f^{\underline{12}}(X))$$(\underline{1}\wedge f^{\underline{1}}(X))\sqcup f^{\underline{2}}(X)$

if
if
if

$f$
$f$
$f$

$B$

can be expressed by theis in the caee ( -1)
is in the caee ( -2)
is in the caee ( -3)
$B$

(18)

$B$

$B$

(End of Property)

By Property 1, every one-variable function satisfying Condition can be expressed by aformula.
Next, let us consider the caee where functions satisfying Condition depend more than
one variable. Then, any function satisfying Condition is in at leaet one of the three caees
below.
$B$

$B$

$B$

$f$

(B-4)

$f(A_{1}, \ldots, A_{n})\neq\underline{01}$holds for any element $(A_{1}, \ldots A_{n})\in(P_{3}-S_{3})^{n}.$(B-5)$f(A_{1}, \ldots, A_{n})\neq\underline{12}$holds for any element $(A_{1}, \ldots A_{n})\in(P_{3}-S_{3})^{n}.$(B-6)$\bigcap_{(A_{1},\ldots,A_{n})\in(P_{3}-S_{3})^{n}}f(A_{1}, \ldots, A_{n})=\underline{1}.$Tables 11, 12 and 13 are examples of two-variable functions being in the caees ( -4), ( -5),and ( -6), respectively.
Then, we can prove Properties $1\sim 6$ , which show a way for constructing formulae of-variable functions satisfying Condition B.
. Then, denote the one-variable
Let be an element $(A_{1}, \ldots, A_{i-1}, A_{i+1}, \ldots, A_{n})$ of.
function $f(A_{1}, \ldots, A_{i-1}, X, A_{i+1}, \ldots, A_{n})$ by
$B$

$B$

$n$

$A$

$P_{f}^{n-1}$$f_{A}^{i}(X)$

$B$

107
Property 2 Suppose a function satisfying Condition
function expressed by the formula$f$$f’=p^{1}\sqcup\cdots up^{n}$$B$

is in the case ( -5). Let $f’$ be a
$B$

(19)

,

where
$p^{i}(X_{1}, \ldots, X_{n})=$$A=(A_{1},\ldots,A_{i}-1^{\sqcup(f_{A}^{i}(X_{i})\wedge X_{1}^{A_{1}}\wedge\cdots\wedge X_{i-1}^{A_{i-1}}\wedge X_{i+1}^{A_{i+1}}\wedge\cdots\wedge X_{n}^{A_{n}})}A_{i+1},\ldots,A_{n})\in S_{3}^{n-1}$

.

(20)

Then, for any element $(A_{1}, \ldots, A_{n})\in P_{3}^{n},$$f’(A_{1}, \ldots, A_{n})=\{\begin{array}{ll}f(A_{1}, \ldots, A_{n}) if (A_{1}, \ldots, A_{n})\not\in(P_{3}-S_{3})^{n}K otherwise\end{array}$where $K$ is an element of$P_{r}$

such that $\{0\}\subseteq K\subseteq\{0\}\cup F(A_{1}, \ldots, A_{n})$ .

Property 3 Suppose a function satisfying Condition
function expressed by the formula
$f$

$B$

is in the case ( -5). Let $f”$ be a$B$$f”(X_{1}, \ldots, X_{n})=s\in P_{3}-s_{3}\lfloor\rfloor\{\prod_{t\in S}(\{t\} A f_{\hat{T}(S)}(X_{1}, \ldots, X_{n}))\}$

where$\hat{T}(S)$(End of Property)

(21)

,

is the set of all minimal elements of the set$T(S)=\{(A_{1}, \ldots, A_{n})\in(P_{3}-S_{3})^{n}|f(A_{1}, \ldots, A_{n})=S\}$and$f_{\hat{T}(S)}(X_{1}, \ldots, X_{n})=\sqcup\{\bigwedge_{e(A_{1},\ldots,A_{n})\in\hat{T}(S)\in A_{1}}X^{\{e\}}\wedge\cdots\wedge\bigwedge_{e\in A_{n}}X^{\{e\}}\}$

Then, for any element

.

(22)

$(A_{1}, \ldots , A_{n})\in P_{3}^{n},$$f”(A_{1}, \ldots, A_{n})=\{\begin{array}{ll}\{0\} if (A_{1}, \ldots, A_{n})\not\in(P_{3}-S_{3})^{n}f(A_{1}, \ldots, A_{n}) otherwise\end{array}$(End of Property)

Property 4 Any functionin the case ( -5).

$f$satisfying Condition$B$

can be expressed by $f=f’\sqcup f"$ , if

is(End of Property)

$B$

$f$

Property 5 Suppose a function satisfying Condition
is in the case ( -4). Let $A=$$(A_{1}, \ldots, A_{i-1}, A_{i+1}, \ldots, A_{n})$ be an element of. Then, define
and as functions on
expressed by the following formulas.
$B$

$B$

$f$

$S_{3}^{n-1}$$g_{A}^{i}$$h$$g_{A}^{i}(X_{1}, \ldots, X_{n})=f_{A}^{i}(X_{i})\sqcup(X_{1}^{A_{1}’}\wedge\cdots\wedge X_{i-1}^{A_{i-1}’}\wedge X_{i+1}^{A_{i+1}’}\wedge\cdots\wedgeX_{n}^{A_{n}’})$$P_{r}$,(23)

where $A_{j}’=E_{3}-A_{j}(j=1, \ldots, i-1, i+1, \ldots, n)$ .
$h(X_{1}, \ldots, X_{n})=$$\{(\sqcup^{n}\sqcup X_{i}^{A})\sqcup f^{\underline{12}}(X_{1}, \ldots, X_{n})\}\wedge\{(_{i=1A\in S_{3}}\sqcup^{n}\sqcup X_{i}^{A})\sqcup f^{\underline{02}}(X_{1}, \ldots, X_{n})\sqcup\underline{1}\}(24)$

108
Then,

$f$

can be expressed by the following formula.
$f(X_{1}, \ldots, X_{n})=G(X_{1}, \ldots, X_{n})\wedge h(X_{1}, \ldots, X_{n})$whereis -ing of all the$G$$\wedge$$g_{A}^{i}s$

,

(25)

of Eq. (23), i.e.,(26)$G(X_{1}, \ldots, X_{n})=\bigwedge_{i=1}^{n}(\bigwedge_{A\in S_{3}^{n-1}}g_{A}^{i}(X_{1}, \ldots, X_{n}))$(End of Property)

Property 6 Suppose a function satisfying Condition
either one of the following two caees.
$f$

(1)

$f(A)\neq\underline{02}$holds for any element$A\in P_{3}^{n}$(2) $f(A)=\underline{02}$ holds for some element

If

$f$

is in the caee (1), then

$f$

$B$

is in the caee ( -6). Then,$B$$A\in P_{3}^{n}.$can be expressed by

.

$w$

(27)

be a function expressed by the following formula.
$w(X_{1}, \ldots, X_{n})=\sqcup\xi_{1}(A_{1})\sqcup\cdots\sqcup\xi_{n}(A_{n})(A_{1},\ldots,A_{n})\in Q_{\underline{02}}$

where

is in

, or

$f(X_{1}, \ldots, X_{n})=(\underline{1}\wedge f^{\underline{1}}(X_{1}, \ldots, X_{n}))\sqcup f^{\underline{2}}(X_{1}, \ldots, X_{n})\sqcup(\underline{1}\wedge f^{\underline{12}}(X_{1}, \ldots, X_{n}))$

Let

$f$

$Q_{\underline{02}}=\{(A_{1}, \ldots, A_{n})\in P_{3}^{n}|f(A_{1}, \ldots, A_{n})=\underline{02}\}4$

(28)

’

, and

$\xi_{i}(A)=\{\begin{array}{ll}X_{i}^{A} if A\in S_{3}\underline{0} otherwise.\end{array}$

Then,

$f$

can be expressed by the following formula, if$f$

is in the caee (2).

$f(X_{1}, \ldots, X_{n})=G(X_{1}, \ldots, X_{n})\wedge w(X_{1}, \ldots, X_{n})$

,

(29)

where $G(X_{1}, \ldots, X_{n})$ is given by Eq. (26).

6(End of Property)

Examples of ffinction Satisfying Condition $B$

This section shows examples of 2-variable functions satisfying Condition
how they can be expressed by formulae.

$B$, and illustrates

Example 4 Consider the function defined by Table 12, which is in the caee ( -5). The
formula expressing is given by Properties 2, 3, and 4. First, consider the formulae, which appear in Eq. (20). Table 14 shows the truth tables of the six one-variableandfunctionsand. Sinceandare in ( -2)(or ( -3)),
is in
is in ( -1), it follows by. (17)
that theseone-variablefunctions- are expresse by the following formulae.
$f$

$B$

$f$

$f_{A}^{1}(X)$$f_{A}^{2}(Y)$$f_{0}^{1}(X),$$B$$-f_{1}^{1}(X)$$f_{\underline{1}}^{1}(X),$$f_{2}^{1}(X),$$f_{\underline{0}}^{2}(Y),$$f_{\underline{1}}^{1}(Y)$$(B_{-3)}^{-}, and f_{2}^{2}(Y)$$f_{\underline{2}}^{2}(Y)$$B$$\overline{d}$holds, since

is in the case ( -6).

$\overline{4Q_{\underline{02}}\cap(P_{3}-S_{3})^{n}=\emptyset}$
$f$

$B$

$f_{2}^{1}(X)$$\overline{E}q$$f_{1}^{2}(Y)$$an\overline{d}(18)$

$B$

109
Table 14: One-Variable Functions$f_{A}^{1}$

and$f_{A}^{2}$of Example 4

Table 16: Truth Table of $f”$ of Example 4$f_{\underline{0}}^{1}(X)=\underline{O}, f_{\underline{1}}^{1}(X)=\underline{1}X^{\underline{1}}\sqcup X^{\underline{2}}, f_{\underline{2}}^{1}(X)=\underline{1}X^{\underline{2}}$$f_{\underline{0}}^{2}(Y)=\underline{0}, f_{\underline{1}}^{2}(Y)=\underline{1}Y^{\underline{1}}, f_{\underline{2}}^{2}(Y)=Y^{\underline{12}}(\underline{1}uY^{\underline{01}})$

Therefore, it follows by Eq. (19) that $f’$ is expressed by the following formula.
$f’=X^{\underline{0}}f_{\underline{0}}^{2}(Y)\sqcup X^{\underline{1}}f_{\underline{1}}^{2}(Y)\sqcup X^{\underline{2}}f_{\underline{2}}^{2}(Y)\sqcup f_{\underline{0}}^{1}(X)Y^{\underline{0}}\sqcup f_{\underline{1}}^{1}(X)Y^{\underline{1}}\sqcup f_{\underline{2}}^{1}(X)Y^{\underline{2}}$(30)

Table 15 is the truth table of $f’$ . Next, consider $f”$ in Eq. (21). Since$\hat{T}(\underline{01}) = \{(\underline{01}, \underline{01}), (\underline{01}, \underline{12})\},$$\hat{T}(\underline{02})$$=$$\hat{T}(\underline{12})=\emptyset$, and$\hat{T}(\underline{012}) = \{(\underline{02}, \underline{01}), (\underline{02},\underline{02}), (\underline{02},\underline{12}), (\underline{12}, \underline{01}), (\underline{12}, \underline{02}), (\underline{12}, \underline{12})\},$

it follows by Eq. (22) that we have the following formulas.
$f_{\hat{T}(\underline{01})}(X, Y) = X^{\underline{0}}X^{\underline{1}}Y^{\underline{0}}Y^{\underline{1}}\sqcup X^{\underline{0}}X^{\underline{1}}Y^{\underline{1}}Y^{\underline{2}}$$f_{\hat{T}(\underline{012})}(X, Y) = X^{\underline{0}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{1}}\sqcup X^{\underline{0}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{2}}\sqcup X^{\underline{0}}X^{\underline{2}}Y^{\underline{1}}Y^{\underline{2}}\sqcup X^{\underline{1}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{1}}\sqcup$$X^{\underline{1}}X^{\underline{2}}Y^{\underline{0}}Y^{\underline{2}}\sqcup X^{\underline{1}}X^{\underline{2}}Y^{\underline{1}}Y^{\underline{2}}$We then have $f”(X, Y)$ below by Eq. (21).
$f”(X, Y)=1J_{\hat{T}(\underline{01})}(X, Y)\sqcup\underline{1}f_{\hat{T}(\underline{012})}(X, Y)uf_{\hat{T}(\underline{012})}(X, Y)$(31)

Table 16 is the truth table of $f”$ . It follows by Property 4 that $f(X, Y)=f’(X, Y)\sqcup f"(X, Y)$ .
(End of Example)

110
Table 17: Truth Table of$G$of Example 5

Table 18: Truth Table of$h$of Example 5

Example 5 Consider the function defined by Table 11, which is in ( -4). The formulaexpressing is given by Property 5. First, consider the formulaandof Eq. (23).
It follows by Eq. (17) and (18) that the one-variable functions
andare obtained
$B$

$f$

$g_{A}^{1}(X)$$f$$f_{A}^{1}(X)$$g_{A}^{2}(Y)$$f_{A}^{2}(Y)$bel $ow.$$f_{\underline{0}}^{1}(X)=X^{\underline{1}}, f_{\underline{1}}^{1}(X)=\underline{1}\sqcup X^{\underline{12}}, f_{\underline{2}}^{1}(X)=\underline{1}\sqcup X^{\underline{01}},$$f_{\underline{0}}^{2}(Y)=\underline{1}Y^{\underline{1}}\sqcup Y^{\underline{2}}, f_{\underline{1}}^{2}(Y)=\underline{2}, f_{\underline{2}}^{2}(Y)=Y^{\underline{12}}(\underline{1}\sqcup Y^{\underline{01}})$

Then, by Eq. (23), we have$g_{\underline{0}}^{1}(X, Y)=X^{\underline{1}}\sqcup Y^{\underline{12}},$$g_{\underline{1}}^{1}(X, Y)=\underline{1}\sqcup X^{\underline{12}}\sqcup Y^{\underline{02}},$$g_{\underline{2}}^{1}(X, Y)=\underline{1}uX^{\underline{01}}\sqcup Y^{\underline{01}},$$g_{\underline{0}}^{2}(X, Y)=X^{\underline{12}}\sqcup\underline{1}Y^{\underline{1}}\sqcup Y^{\underline{2}},$$g_{\underline{1}}^{2}(X, Y)=\underline{2},$$g_{\underline{2}}^{2}(X, Y)=X^{\underline{01}}\sqcup Y^{\underline{12}}(\underline{1}\sqcup Y^{\underline{01}})$.

By Eq. (26), we have the function $G(X, Y)$ expressed by -ing of all the above $g_{A}^{i}(X, Y)’ s.$
Table 17 is the truth table of $G(X, Y)$ . Next, consider in Eq. (24). It follows by Eq. (17)that the functions
andare expressed by the following formulae.
$\wedge$$h$$f^{\underline{12}}(X, Y)$$f^{\underline{02}}(X, Y)$$f^{\underline{12}}(X, Y) = X^{\underline{1}}\sqcup X^{\underline{12}}Y^{\underline{12}}\sqcup Y^{\underline{1}}\sqcup Y^{\underline{2}}\sqcup X^{\underline{0}}X^{\underline{1}}Y^{\underline{0}}\sqcup X^{\underline{1}}X^{\underline{2}}Y^{\underline{0}}$$f^{\underline{02}}(X, Y) = X^{\underline{0}}Y^{\underline{02}}\sqcup X^{\underline{1}}\sqcup X^{\underline{01}}Y^{\underline{2}}\sqcup X^{\underline{12}}Y^{\underline{01}}\sqcup Y^{\underline{1}}$Thus, by Eq. (24), we have$h(X, Y)=(v(X, Y)\sqcup f^{\underline{12}}(X, Y))\wedge(v(X, Y)\sqcup f^{\underline{02}}(X, Y)\sqcup\underline{1})$,. Table 18 is the truth table of $h(X, Y)$ . Lastly,
where
by Eq. (25), $f(X, Y)$ are expressed by the following formula.
$v(X, Y)=X^{\underline{0}}\sqcup X^{\underline{1}}\sqcup X^{\underline{2}}\sqcupY^{\underline{0}}\sqcup Y^{\underline{1}}\sqcup Y^{\underline{2}}$$f(X, Y)$$=$

$G(X, Y)\wedge h(X, Y)$$=g_{\underline{0}}^{1}(X, Y)\wedge g_{\underline{1}}^{1}(X, Y)\wedge g_{\underline{2}}^{1}(X, Y)\wedge g_{\underline{0}}^{2}(X, Y)\wedge g_{\underline{1}}^{2}(X, Y)\wedge g_{\underline{2}}^{2}(X, Y)\wedge h(X, Y)$(End of Example)

Example 6 Consider the function define by Table 13, which is in ( -6). The formulaexpressing is given by Property 6. Since is in the caee (2) of Property 6, is expressedby the formula given in Eq. (29).
First, consider the formula $G(X, Y)$ . It follows by Eq. (17) and (18) that one-variable
functionsare obtained below.
and
$B$

$f$

$f$

$f$

$f_{A}^{1}(X)$$f_{A}^{2}(Y)$

$f$

111

$f_{\underline{0}}^{1}(X)=\underline{O} f_{\underline{1}}^{1}(X)=(\underline{1}\wedge X^{\underline{12}})\sqcup X^{\underline{2}} f_{\underline{2}}^{1}(X)=X^{\underline{12}}\wedge(\underline{1}\sqcup X^{\underline{02}})$$f_{\underline{0}}^{2}(Y)=\underline{O}, f_{\underline{1}}^{2}(Y)=\underline{1}\wedge Y^{\underline{12}} f_{\underline{2}}^{2}(Y)=Y^{\underline{12}}$Thus, we obtain $g_{A}^{1}(X, Y)$ and $g_{A}^{2}(X, Y)$ of Eq. (23) below.
$g_{\underline{0}}^{1}(X, Y)=Y^{\underline{12}}$$g_{\underline{1}}^{1}(X, Y)=(\underline{1}\wedge X^{\underline{12}})\sqcup X^{\underline{2}}\sqcup Y^{\underline{02}}$$g_{\underline{2}}^{1}(X, Y)=X^{\underline{12}}\wedge(\underline{1}\sqcup X^{\underline{02}})\sqcup Y^{\underline{01}}$$g_{\underline{0}}^{2}(X, Y)=X^{\underline{12}}$$g_{\underline{1}}^{2}(X, Y)=X^{\underline{02}}\sqcup(\underline{1}\wedge Y^{\underline{12}})$$g_{\underline{2}}^{2}(X, Y)=X^{\underline{01}}\sqcup Y^{\underline{12}}$By Eq. (26), we have the function $G(X, Y)$ expressed by
Table 19 is the truth table of $G.$
Next, consider $w(X, Y)$ of Eq. (28). Because$\wedge$-ing of all the above $g_{A}^{i}(X, Y)’ s.$$Q_{\underline{02}}=\{(\underline{2}, \underline{01}), (\underline{2}, \underline{02}), (\underline{2},\underline{012}), (\underline{02}, \underline{02})\},$

it follow by Eq. (28) that the formula$w$

is obtained below.

$w(X, Y)=\underline{1}\sqcup X^{\underline{2}}\sqcup Y^{\underline{2}}$Table 20 is the truth table ofexpresses the function $f.$$f(X, Y)$

$=$

$w$

. Lastly, it follows by Eq. (29) that the following formula$G(X, Y)\wedge w(X, Y)$.

$= g_{\underline{0}}^{1}(X, Y)\wedge g_{\underline{1}}^{1}(X, Y)\wedge g_{\underline{2}}^{1}(X, Y)\wedge g_{\underline{0}}^{2}(X, Y)\wedge g_{\underline{1}}^{2}(X, Y)\wedge g_{\underline{2}}^{2}(X, Y)\wedge w(X, Y)$(End of Example)

7

Conclusions

This paper discussed functions over that preserves the set inclusion relation . We referred
the three kinds of operations Min, Max, and Literals over, because they are functionallycomplete on the -valued set . This paper then proved some of the mathematical propertiesof functions overthat can be expressed by formulas. It is one of the open problems thatwhich set of operations
over
can realize any function overpreserving theset inclusion relation$P_{r}$$\subseteq$$E_{r}$$E_{r}$$r$$P_{r}$$\hat{o}_{1},\hat{o}_{2},$$\subseteq.$$\ldots,\hat{o}_{m}$$P_{r}$$P_{r}$

112
References[1] S. C. Kleene, Introduction to metamathematics, North-Holland Pub., pp. 332-340, 1952.
[2] M. Goto, “Application of three-valued logic to construct the theory of relay networks,” (inJapanese), Proc. Joint Meeting IEE, IECE, and I. of Illum. E. of Japan, 1948.

[3] M. Mukaidono, “Regular ternary logic functions –Ternary logic functions suitable fortreating ambiguity,” IEEE Trans. on Computers, vol. c-35, no. 2, pp. 179-183, 1986.

[4] M. Mukaidono, “On the -ternary logical function,” IECE Trans., vol. 55-D, no. 6, pp.
355-362, 1972 (in Japanese)$B$[5] J. C. Muzio and T. C. Wesselkamper, Multiple-Valued Switching Theory.
[6] M. Mukaidono: “The -temary logic and its applications to the detection of hazards in
combinational switching circuits,” Proc. of the 8th ISMVL, pp. 269-275, 1978.
$B$[7] N. Takagi, Y. Nakamura and K. Nakaehima: “Set-valued functions and regularity,” Proc.
of the 27th ISMVL, pp. 89-94, 1997.
[8] I. G. Rosenberg, “Multiple-valued hyperstructures,” Proc. of the 28th ISMVL, pp. 326333, 1998.