\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }


\title{Description of Strictly Monotonic Interval 
AND/OR Operations}
\author{Qiang Zuo}

\maketitle

\begin{abstract}
In expert systems, AND and OR operations are usually defined for degrees of
belief that are real numbers.
Such AND/OR operations have been classified 
by B. Schweizer and A. Sklar \cite{1} and S. Weber \cite{2}.  

In practice, however, it is difficult to assign an exact numerical
value to the expert's degree of belief. At best, we can get an {\it
interval} of possible values. It is therefore necessary to define
AND/OR operations for intervals. 

In this paper, we classify such operations.
\end{abstract}

\auffil{The author is with the Department of Mathematics,
        The University of Texas at El Paso, El Paso, Texas 79968. 
The author is greatly thankful to 
Dr. Kreinovich for his teaching, important attention and help.}
 
\section{Degrees of Belief}
The goal of an expert system is to the experts' way of making
decisions. 
For that purpose, an
expert system includes a {\it knowledge base} that contains the
knowledge of the experts. Some statements from the knowledge base are
believed to be absolutely correct. However, in their decisions,
experts also use other statements, about which they are not 100\% sure
that they are correct. To describe the expert knowledge adequately, we
must therefore store in the knowledge base not only the statements
themselves, but also the indication of the extent to which the experts
believe in these statements.

This {\it degree of belief} is usually described by a number from the
interval [0,1]. An expert's degree of belief $d(A)$ in a statement $A$ can be
determined, if, e.g., we ask an expert to estimate his degree of
belief on a scale from 0 to 10. If he selects 8, then we take
$d(A)=8/10$.

\section{AND and OR Operations}
Suppose now that we know the degrees of belief $d(A)$ and $d(B)$ in
statements $A$ and $B$, and we know nothing else about $A$ and $B$.
Suppose also that we are interested in the degree of belief of the
composite statement $A\& B$. Since the 
only information available consists of the values $d(A)$ and $d(B)$,
we must compute $d(A\& B)$ based on these values. We must be able to
do that for arbitrary values $d(A)$ and $d(B)$. Therefore, we need a
{\it function} that transforms the values $d(A)$ and $d(B)$ into an
estimate for $d(A\& B)$. Such a function is called an {\it
AND-operation}. If an AND-operation $$T:[0,1]\times [0,1]\to[0,1]$$
is fixed, then we take
$T(d(A),d(B))$ as an estimate for $d(A\& B)$. 

Similarly, to estimate the degree of belief in $A\vee B$, we need an
{\it OR-operation} $S:[0,1]\times [0,1]\to[0,1]$. 

Histortically the first AND and OR operations were introduced by L.
Zadeh in \cite{3}: $T(x,y)=\min(x,y)$ and $S(x,y)=\max(x,y)$. Since
then, several other operations have been proposed:
\begin{itemize}
\item ``Soft AND'' by Bellman and Zadeh [4];
\item  ``Bold AND''
and ``Bold OR'' by Giles [5];
\item ``Compensatory AND'' by Zimmerman and 
Zesno [6];
\item Yager [7] studied a general class of fuzzy connectives.  
\end{itemize}

A complete classification of all AND and OR operations that satisfy
several natural conditions was given by Schweizer and
Sklar [1], and by Asina, Trillas and Valverde [8].
Since we will use their results, we will briefly recall them here (in
slightly different notations).

\section{Classification Of AND And OR Operations}

\noindent{\bf Definition 1.}
By a {\it continuous, strictly increasing t-norm}, we mean a function
$\&:[0,1]\times [0,1]\to [0,1]$ that satisfies the following
conditions:
\begin{itemize}
\item[(1)]{\it Boundary conditions:}
$x\& 0=0\& x=0$, $x\& 1=1\& x=x.$
\item[(2)]{\it Commutativity:}
$x\& y=y\& x.$
\item[(3)]{\it Associativity:}
$x\& (y\& z)=(x\& y)\& z.$
\item[(4)]{\it Monotonicity:}
if $a_1\le a_2$ and $b_1\le b_2$, then $a_1\& b_1\le a_2\& b_2.$
\item[(5)]{\it Strict monotonicity:}
if $a_1<a_2$ and $b_1<b_2$, then $a_1\& b_1<a_2\& b_2.$
\item[(6)]{\it Continuity:} the function $\&$ is continuous in both
variables.
\end{itemize}

\noindent{\bf Definition 2.}
By a {\it continuous, strictly increasing t-conorm}, we mean a function
$$\vee:[0,1]\times [0,1]\to [0,1]$$ that satisfies the following
conditions:
\begin{itemize}
\item[(1)]{\it Boundary conditions:}
$x\vee 0=0\vee x=x$, $x\vee 1=1\vee x=1.$
\item[(2)]{\it Commutativity:}
$x\vee y=y\vee x.$
\item[(3)]{\it Associativity:}
$x\vee (y\vee z)=(x\vee y)\vee z.$
\item[(4)]{\it Monotonicity:}
if $a_1\le a_2$ and $b_1\le b_2$, then $a_1\vee b_1\le a_2\vee b_2.$
\item[(5)]{\it Strict monotonicity:}
if $a_1<a_2$ and $b_1<b_2$, then $a_1\vee b_1<a_2\vee b_2.$
\item[(6)]{\it Continuity:} the function $\vee$ is continuous in both
variables.
\end{itemize}

\noindent{\it Comment.} These conditions are easy to justify: e.g.,
commutativity means that we want to assign equal estimate to
statements $A\& B$ and $B\& A$, etc. 
\smallskip

\noindent{\bf CLASSIFICATION THEOREM FOR AND OPERATIONS.} 
\cite{1} {\it Any continuous, strictly
monotonic t-norm can be represented as 
$a\& b=
\varphi ^{-1}(\varphi (a)\cdot \varphi (b))$
for some continuous and
strictly increasing function 
$\varphi:[0,1]\to
[0,1]$ 
for which $\varphi (0) = 0$ and $\varphi (1) = 1$.}
\smallskip

\noindent {\it Comment.} This result states that any continuous
strictly increasing t-norm $\&$ is equivalent to the algebraic
product.
\smallskip

\noindent{\bf CLASSIFICATION THEOREM FOR OR OPERATIONS.} 
\cite{1} {\it Any continuous, strictly
monotonic t-conorm $\vee$ can be represented as $a\vee
b=\psi^{-1}(\psi(a)\cdot\psi(b))$
for some continuous and
strictly decreasing function 
$\psi:[0,1]\to [0,1]$ 
for which $\psi(0) = 1$ and $\psi(1)=0$.}

\section{Intervals Are Necessary To Describe Degrees Of Belief}
Experts cannot describe their degrees of belief precisely. At best,
they can give an {\it interval} of possible values. For example, an
expert can point to 8 on a scale from 0 to 10, but this same expert
will hardly be able to pinpoint a value on a scale from 0 to 100. As a
result, the only thing that we know about the expert's degree of
belief is that it is closer to 8 than to 7 or to 9, i.e., that it is
in the interval $[0.75,0.85]$.  

So, to describe degrees of belief more adequately, we must use {\it
intervals} instead of real numbers.
This idea have been proposed by 
Turksen [9] and 
Bandler and Kohout [10].

Since we went from numbers to intervals, we need 
AND and OR operations as
functions from intervals to intervals. 
In this paper, we give a complete classification of such operations.
\newpage

\section{Main Results}

To formulate these results, we will need the following denotations:
\smallskip

\noindent{\bf Denotations.}
\begin{itemize} 
\item By $I$, we will denote the set of all intervals
${\bf a}=[a^-,a^+]\subseteq [0,1]$ (i.e., all intervals for which 
$0\le a^-\le a^+\le 1$).
\item We say that ${\bf a}=[a^-,a^+]\le [b^-,b^+]={\bf b}$ if $a^+\le
b^-$. 
\item We say that ${\bf a}=[a^-,a^+]<[b^-,b^+]={\bf b}$ if $a^+<b^-$.
\end{itemize}

\noindent{\it Comment.} The notation $[a^-,a^+]<[b^-,b^+]$ means the
following: if $d(A)=[a^-,a^+]$ and $d(B)=[b^-,b^+]$, then our belief
in $B$ is stronger than our belief in $A$. Since we do not know the
exact values of these degrees of belief, the only way to express this
``stronger'' is to require that $a<b$ for all $a\in [a^-,a^+]$ and
for all $b\in[b^-,b^+]$. This condition is equivalent to $a^+<b^-$.
\smallskip

\noindent{\bf Definition 3.}
By an {\it interval AND operation}, we 
mean a function
$\&:I\times I\to I$ that satisfies the following
conditions:
\begin{itemize}
\item[(1)]{\it Boundary conditions:}
${\bf x}\& [0,0]=[0,0]\& {\bf x}=[0,0]$,
${\bf x}\& [1,1]=[1,1]\& {\bf x}={\bf x}.$
\item[(2)]{\it Commutativity:}
${\bf x}\& {\bf y}={\bf y}\& {\bf x}.$
\item[(3)]{\it Associativity:}
${\bf x}\& ({\bf y}\& {\bf z})=({\bf x}\& {\bf y})\& {\bf z}.$
\item[(4)]{\it Monotonicity:}
if ${\bf a}_1\le {\bf a}_2$ and ${\bf b}_1\le {\bf b}_2$, then ${\bf
a}_1\& {\bf b}_1\le {\bf a}_2\& {\bf b}_2.$
\item[(5)]{\it Strict monotonicity:}
if ${\bf a}_1<{\bf a}_2$ and ${\bf b}_1<{\bf b}_2$, 
then ${\bf a}_1\& {\bf b}_1<{\bf a}_2\& {\bf b}_2.$
\item[(6)]{\it Continuity:} the function ${\bf a},{\bf b}\to {\bf
a}\&{\bf b}$ is continuous in both
variables (i.e., in all four variables $a^-,a^+,b^-,b^+$). 
\item[(7)]{\it Inclusion monotonicity:}
if ${\bf a}_1\subseteq {\bf a}_2$ and ${\bf b}_1\subseteq {\bf b}_2$, 
then ${\bf a}_1\& {\bf b}_1\subseteq {\bf a}_2\& {\bf b}_2.$
\end{itemize}

\noindent{\bf Definition 4.}
By an {\it interval OR operation}, we 
mean a function
$\vee:I\times I\to I$ that satisfies the following
conditions:
\begin{itemize}
\item[(1)]{\it Boundary conditions:}
${\bf x}\vee [0,0]=[0,0]\vee {\bf x}={\bf x},$
${\bf x}\vee [1,1]=[1,1]\vee {\bf x}=[1,1].$
\item[(2)]{\it Commutativity:}
${\bf x}\vee {\bf y}={\bf y}\vee {\bf x}.$
\item[(3)]{\it Associativity:}
${\bf x}\vee ({\bf y}\vee {\bf z})=({\bf x}\vee {\bf y})\vee {\bf z}.$
\item[(4)]{\it Monotonicity:}
if ${\bf a}_1\le {\bf a}_2$ and ${\bf b}_1\le {\bf b}_2$, then ${\bf
a}_1\vee {\bf b}_1\le {\bf a}_2\vee {\bf b}_2.$
\item[(5)]{\it Strict monotonicity:}
if ${\bf a}_1<{\bf a}_2$ and ${\bf b}_1<{\bf b}_2$, 
then ${\bf a}_1\vee {\bf b}_1<{\bf a}_2\vee {\bf b}_2.$
\item[(6)]{\it Continuity:} the function ${\bf a},{\bf b}\to {\bf
a}\vee{\bf b}$ is continuous in both
variables (i.e., in all four variables $a^-,a^+,b^-,b^+$). 
\item[(7)]{\it Inclusion monotonicity:}
if ${\bf a}_1\subseteq {\bf a}_2$ and ${\bf b}_1\subseteq {\bf b}_2$, 
then ${\bf a}_1\vee {\bf b}_1\subseteq {\bf a}_2\vee {\bf b}_2.$
\end{itemize}
\newpage

\noindent{\it Comment.} The motivation for inclusion monotonicty is as
follows: suppose that initially, we had ${\bf a}_2$ and ${\bf b}_2$ as
sets of possible values of degrees of belief in $A$ and $B$. Then, by
applying the interval AND operation $\&$, we can conclude that the degree of
belief in $A\& B$ is in ${\bf a}_2\& {\bf b}_2$. 

Suppose now that we have narrowed down our degrees of belief to ${\bf
a}_1\subseteq {\bf a}_2$ and ${\bf b}_1\subseteq {\bf b}_2$. If we
apply the same interval AND operation to the new degrees of belief, we
get a new interval ${\bf a}_1 \& {\bf b}_1$. Since we have narrowed
down our intervals of possible degrees of belief, it can happen that
some previously possible degrees of belief in $A\& B$ are not possible
any more. But it is reasonable to require that if a value is now
possible, then it was possible earlier as well (when we had even fewer
knowledge about degrees of belief). In other words, we require that
every number from ${\bf a}_1 \& {\bf b}_1$ belongs to ${\bf a}_2 \&
{\bf b}_2$. This is exactly inclusion monotonicity.
\smallskip

\noindent{\bf CLASSIFICATION THEOREM FOR INTERVAL AND OPERATIONS.} 
{\it For any 
interval AND operation $\&$, there exists a continuous and
strictly increasing function 
$\varphi:[0,1]\to
[0,1]$ 
such that $\varphi (0) = 0$, $\varphi (1) = 1$, and
$$[a^{-},a^{+}]\& [b^{-},b^{+}] = $$
$$[\varphi ^{-1}(\varphi (a^{-})\varphi (b^{-})),
\varphi ^{-1}(\varphi (a^{+})\varphi (b^{+}))].$$}

\noindent{\bf CLASSIFICATION THEOREM FOR INTERVAL OR OPERATIONS.} 
{\it For any 
interval OR operation $\vee$, there exists a continuous and
strictly decreasing function 
$\psi:[0,1]\to
[0,1]$ 
such that $\psi (0) = 1$, $\psi (1) = 0$, and
$$[a^{-},a^{+}]\vee [b^{-},b^{+}] = $$
$$[\psi ^{-1}(\psi (a^{-})\psi (b^{-})),
\psi ^{-1}(\psi (a^{+})\psi (b^{+}))].$$}
\smallskip

\noindent{\it Comment.} It is easy to check that 
the inverse if also true: if $\varphi$ (or
$\psi$) satisfies the given conditions, then the formula given in the
formulations of the corresponding theorem defines an interval AND 
(OR) operation.

\section{Proofs}
We will prove the result for AND operations. The result for OR
operations is proven similarly.

Let us denote the lower and upper bounds of the interval 
$[a^{-},a^{+}]\& [b^{-},b^{+}]$ by 
$f^-(a^{-},a^{+},b^{-},b^{+})$ and $f^+(a^{-},a^{+},b^{-},b^{+})]$. 
The proof will consist of the following two steps:
\begin{itemize}
\item First, we will prove the following three statements:
\begin{itemize}
\item[$\bullet$]
$f^-$ depends only on $a^-$ and $b^-$;
\item[$\bullet$]$f^+$ depends only on $a^+$ and $b^+$;
\item[$\bullet$]$f^-(x,y)=f^+(x,y)$.
\end{itemize}
\item Second, we will prove that $f^-$ is a continuous, strictly
increasing t-norm. The desired result will then follow from the
classification theorem for non-interval AND operations.
\end{itemize}

Let us first prove the desired three statements.
Since $\&$ is an interval AND operation, it is monotonic. So, 
from $[a^{-},a^{-}]\leq [a^{-},a^{+}]$
and $[b^{-},b^{-}]\leq [b^{-},b^{+}]$, we can conclude that 
$$f^+(a^-,a^-,b^-,b^-)\le f^-(a^-,a^+,b^-,b^+).\eqno{(1)}$$
Since $f^-$ and $f^+$ are endpoints of an interval, we have 
$$f^-(a^-,a^+,b^-,b^+)\le f^+(a^-,a^+,b^-,b^+)\eqno{(2)}$$
and
$$f^-(a^-,a^-,b^-,b^-)\le f^+(a^-,a^-,b^-,b^-).\eqno{(3)}$$
On the other hand, we can apply inclusion monotonicity:
since 
$[a^{-},a^{-}]\subseteq [a^{-},a^{+}]$ 
 and 
$[b^{-},b^{-}]\subseteq [b^{-},b^{+}]$, we have
$$[f^-(a^{-},a^{-},b^{-},b^{-}),f^+(a^{-},a^{-},b^{-},b^{-})]\subseteq $$
$$[f^-(a^{-},a^{+},b^{-},b^{+}),f^+(a^{-},a^{+},b^{-},b^{+})].$$
This interval inclusion means that 
$$f^-(a^{-},a^{+},b^{-},b^{+}) \le f^-(a^{-},a^{-},b^{-},b^{-})\eqno{(4)}$$
and 
$$f^+(a^{-},a^{+},b^{-},b^{+}) \ge f^+(a^{-},a^{-},b^{-},b^{-}).\eqno{(5)}$$
From (3), (1), and (4), we conclude that
$$f^-(a^-,a^-,b^-,b^-)\le f^+(a^-,a^-,b^-,b^-)\le $$
$$f^-(a^-,a^+,b^-,b^+)\le f^-(a^-,a^-,b^-,b^-).$$
Therefore, 
$$f^-(a^-,a^-,b^-,b^-)=f^+(a^-,a^-,b^-,b^-)=$$
$$f^-(a^-,a^+,b^-,b^+).\eqno{(6)}$$
Since $$f^-(a^-,a^-,b^-,b^-)=f^-(a^-,a^+,b^-,b^+),$$ we conclude that 
$f^-$ depends only on $a^-$ and $b^-$. Similarly, $f^+$ depends only
on $a^+$ and $b^+$, and from (6), it follows that $f^-(x,y)=f^+(x,y)$
for all $x$ and $y$.

So, for degenerate intervals $[x,x]$ and $[y,y]$, the result
$[f^-(x,y),f^+(x,y)]$ of
applying an interval AND operation is also a degenerate interval. Hence,
we have a function $[0,1]\times [0,1]\to [0,1]$. For this function,
conditions (1)--(6) lead to similar conditions in Defintion 1. So, due
to Classification Theorem for AND operations, we get the desired 
expression for
$f^-=f^+$ in terms of $\varphi$. Q.E.D. 

\begin{thebibliography}{99}

\bibitem{1} B. Schweizer and A. Sklar, ``Associative functions and 
statistical triangle inequalities'', {\it Publ. Math. Debrecen}, 1961,
Vol. 8, pp. 169--186.

\bibitem{2} S. Weber, ``A general concept of fuzzy connectives, 
negations, and implications based on t-norms and t-conorms'',
{\it Fuzzy Sets and Systems}, 1983, Vol. 11, pp. 115--134.

\bibitem{3} L. A. Zadeh, ``Fuzzy Sets'', {\it Inform. and Control},
1965, Vol. 8, pp. 338--353.

\bibitem{4} R. E. Bellman and L. A. Zadeh, ``Decision-making in 
a fuzzy environment,'' {\it Management Sci.}, 1970, Vol. 17, pp. B141--B164.

\bibitem{5} R. Giles, ``Lukasiewicz logic and fuzzy set theory'',
{\it Internat. J. Man-Machine Stud.}, 1976, Vol. 8, pp. 313--327.

\bibitem{6} H. H. Zimmerman and P. Zysno, ``Latent connectives in human
decision making'',  {\it Fuzzy Sets and Systems}, 1980, Vol. 4, pp. 37--51.

\bibitem{7} R. R. Yager, ``On general class of fuzzy connectives'',
{\it Fuzzy Sets and Systems}, 1980, Vol. 4, pp. 235--262. 

\bibitem{8} C. Alsina, E. Trillas, and L. Valverde, ``On 
non-distributive logical connectives for fuzzy set theory'',  
{\it Busefal}, 1980, Vol. 3, pp. 18--29.

\bibitem{9} I. B. Turksen, ``Interval valued fuzzy sets based on 
normal forms'',  {\it Fuzzy Sets and Systems}, 1986, Vol. 20, pp. 191--210.

\bibitem{10} W. Bandler and L. J. Kohout, ``Unified theory of
multi-valued logical operations in the light of the checklist
paradigm'',  {\it Proc of IEEE Conference on Systems, Man, and
Cybernetics}, Halifax, Nova Scotia, Oct. 1984.

\bibitem{11} R. Kruse and K. D. Meyer, {\bf Statistics with vague data}.
D. Reidel, 1987.

\end{thebibliography}
\end{document}