\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{In Expert Systems, Even If We Fix AND/OR Operations, 
A Natural Answer To A Composite Query Is The
Interval Of Possible Degrees of Belief}

\author{Qiang Zuo$^1$, I. Burhan Turksen$^2$, Hung T. Nguyen$^3$, and 
Vladik Kreinovich$^4$}

\maketitle

\begin{abstract} 
In expert systems, even if we fix AND and OR operations, the degree of
belief $d(Q)$ 
in a composite query $Q$ can take different values depending on how
exactly we represent the query in terms of AND, OR, and NOT. In this paper, we
compute the interval of possible values of $d(Q)$.
\end{abstract}

\auffil{The authors are with
$^1$Department of Mathematics,
        The University of Texas at El Paso, El Paso, Texas 79968, 
   with $^2$Department of Industrial Engineering, 
        University of Toronto, Toronto, Ontario, M5S 1A4, Canada,
with $^3$Department of Mathematical Sciences, New Mexico State
University, Las Cruces, NM, 88003, and with 
$^4$Department of Computer science,
        The University of Texas at El Paso, El Paso, Texas 79968. 
This work was partially 
supported by NSF grant No. CDA-9015006 and NASA Research Grant No.
NAG 9-757.}

\section{Introduction}

\subsection{Uncertainty Must Be Represented In Expert Systems}
The goal of an expert system is to answer queries. To be able to do
that, the expert system must contain the experts' knowledge about the
domain of interest (be it medicine, physics, etc). 
Experts can usually formulate this knowledge as a set of statements. 

Experts are often uncertain about their statements. The degree of
expert's belief in his statement $A$ 
is usually described by a number $d(A)$ from the interval $[0,1]$ (1
corresponds to complete belief, 0 to complete disbelief). 

\subsection{Degree Of Belief In A Query: The Simplest Case}
The simplest case for an expert system is when the query $Q$ coincides
with one of the statements that is already in the knowledge base.
Then, as an answer to that query, we can return the degree of belief
$d(Q)$ that is stored in this expert system. 

\subsection{Degree of Belief In Composite Queries: A Problem}
A more complicated case is when we want to find the degree of belief
$d(Q)$ in a query $Q$ that is a  
logical combination of the
statements from the knowledge base (or for a query $Q$ that 
can be shown to be
equivalent to such a combination). 

Even in the simplest of these cases,
when, e.g., a query $Q$ is a formula of the type $A\& B$ with $A$ and
$B$ both in the knowledge base, we already have a problem:
Indeed, if we know the degrees of
belief (subjective probabilities) $a=d(A)$ and $b=t(B)$ 
of the statements $A$ and $B$, then the actual degree of belief in
$A\& B$ can be $d(A)\cdot d(B)$ (if $A$ and $B$ are random and
uncorrelated), or $\min(d(A),d(B))$ (if one of the statements $A$ and
$B$ is a corollary of the other one), etc. The 
only thing that we know for sure about
the degree of belief of $A\& B$ is that it lies between
$\min(a+b-1,0)$ and $\min(a,b)$. Therefore, even if we start with precise
values, e.g., $a=0.3$ and $b=0.4$, we get an {\it interval}
$[0,0.3]$ of possible values of $d(A\& B)$. 

\subsection{AND/OR operations}
To avoid the above-described ambiguity,
usually, in expert systems, a {\it single} value from the interval of
the possible values of $d(A\& B)$ is chosen as an answer to the query
``$A\& B$?''. 
This chosen value depends only on the values of $d(A)$ and $d(B)$, so,
from the mathematical viewpoint, it is a {\it function} of $d(A)$ and
$d(B)$. This function $f_\&$ is called an {\it AND operation}. 

Similarly, in expert systems, two other functions are defined: 
\begin{itemize}
\item A
function $f_\vee(a,b)$ 
called an {\it OR operation} that transforms the values of
$d(A)$ and $d(B)$ into a single value $f_\vee(d(A),d(B))$ 
that is produced as $d(A\vee B)$.
\item A function $f_\neg(a)$ called a {\it NOT operation} that transforms the
value of $d(A)$ into a degree of belief $f_\neg(d(A))=d(\neg A)$ 
in ``not $A$''. 
\end{itemize}
The simplest possible AND, OR, and NOT operations are $\min$, $\max$,
and $f_\neg(a)=1-a$ (for which $d(A)\to d(\neg A)=1-d(A)$). 
 
\subsection{Even If AND and OR Operations Are Fixed, For 
More Complicated Queries, We Still Have Several Possible Degrees of
Belief}
If we fix AND, OR, and NOT operations, then we can in principle,
knowing the degree of belief in the basic statements, determine the
degree of belief in their logical combination $Q$. 
To do that, we represent the given formula $Q$ as a combination of
$\&$, $\vee$, and $\neg$, and then consequently 
use our chosen operations with degrees of
belief instead of
these logical symbols. 

For example, a formula $Q$ of the type 
$A\to B$ can be represented as $B\vee
\neg A$, and therefore, as a degree of belief in $Q$, we can take 
$f_\vee(d(B),f_\neg(d(A))$.

The problem with this idea is that 
for a complicated formula $Q$, e.g., $A\to B$, there
exists several methods of representing $A\to B$ in terms of $\&$,
$\vee$, and $\neg$: $B\vee\neg A$, $(A\&B)\vee \neg A$ etc. These
formulas are equivalent in classical logic, but they lead to different
numerical values for $d(Q)$. 

\subsection{What We Are Going To Do: Main Result}
In this paper, we describe the interval of possible values of $d(Q)$
for a given formula $Q$. Namely, we give a description for the case
when $f_\&=\min$ and $f_\vee=\max$, and we show that for other choices
of AND and OR operations, for practically any formula $Q$, the
corresponding interval simply coincides with $[0,1]$ (and therefore,
makes no sense).

\subsection{What We Are Going To Do: Additional Result}
The assumption that we can describe the initial degrees of belief by
numbers is an idealization. In reality, an expert cannot describe his
degree of belief beyond a certain accuracy. No one is able to say: ``I
believe in this with probability 83.4\%''. Therefore, a more realistic
description of the initial degrees of belief is by {\it intervals}. 

For this case, similar bounds on $d(Q)$ are obtained.

\subsection{Methods}
The methods that we use are a generalization if the methods used in
\cite{1} for formulas with two variables.

\section{Definitions and The Main Results}

Let us start with the basic definitions of propositional logic. 
\smallskip

\noindent{\bf Definition 1.}
Assume that a finite set $$V=\{v_1,...,v_n\}$$ 
is given. Its elements $v_i$ will be called {\it fuzzy variables}. By
a {\it literal}, we will mean either
a variable $v_i$ or its negation $\neg v_i$. A {\it propositional formula} 
with $n$ variables $v_i$ is then defined as follows:
\begin{itemize}
\item every variable $v_i$ is a formula;
\item if $A$ is a formula, then $\neg A$ (called {\it ``not $A$''})
is also a formula;
\item if $A$ and $B$ are formulas, then the following are formulas:
\begin{itemize}
\item[$\bullet$] $A\& B$ (called {\it ``$A$ and $B$''});
\item[$\bullet$] $A\vee B$ (called {\it ``$A$ or $B$''});
\end{itemize}
\item nothing else is a formula.
\end{itemize}
Formulas that have been used in the construction of a
formula $A$ are called its {\it subformulas.} Formulas different from
variables are called {\it composite} formulas.
\smallskip

\noindent{\bf Definition 2.} By a {\it Boolean vector}, we mean a
mapping $t:V\to \{T,F\}$, where $T$ and $F$ are special symbols that
stand for ``true'' and ``false''. In the following text, we will
identify $T$ with 1, and $F$ with 0. If $t$ is given, then we can
define $t(A)$ for an arbitrary composite propositional formula $A$ as follows:
\begin{itemize}
\item $t(\neg A)=\neg (t(A))$;
\item $t(A\& B)=t(A)\& t(B)$;
\item $t(A\vee B)=t(A)\vee t(B)$.
\end{itemize}
We say that formulas $A$ and $B$ are {\it equivalent} in propositional
logic if $t(A)=t(B)$ for every Boolean vector $t$.
\smallskip

\noindent {\it Comment.} 
For degrees of belief, we can have similar definitions.
\smallskip

\noindent{\bf Definition 3.} By the {\it initial degrees of belief}, we
mean a function $d:V\to [0,1]$. 
\smallskip

\noindent{\bf Definition 4.} Assume that we are given three functions:
\begin{itemize} 
\item $f_\&:[0,1]\times [0,1]\to [0,1]$,  
\item $f_\vee:[0,1]\times [0,1]\to [0,1]$, and 
\item $f_\neg:[0,1]\to [0,1]$.
\end{itemize}
Suppose that the initial degrees of belief $d$ are given. 
Then, we can define $d(A)$ for an arbitrary 
composite propositional formula $A$ as follows:
\begin{itemize}
\item $d(\neg A)=f_\neg (d(A))$;
\item $d(A\& B)=f_\&(d(A),d(B))$;
\item $d(A\vee B)=f_\vee(d(A),d(B))$.
\end{itemize}

\noindent{\bf Definition 5.} Let $A$ be a propositional formula, and
let $d$ be the initial degrees of belief. By $S$, we denote the set of
values of $d(B)$ for all formulas $B$ that are equivalent
to $A$ in propositional logic. Let us denote $\sup S$ by $d^+(A)$ and 
$\inf S$ by $d^-(A)$. 
\smallskip

\noindent{\it Comment.} Our goal is to describe the interval
$[d^-(A),d^+(A)]$. In order to describe this interval for $\min$ and
$\max$, we will need the following definition:
\smallskip

\noindent{\bf Definition 6.} Let $A$ be a propositional formula. 
\begin{itemize}
\item We
say that a Boolean vector {\it satisfies} the formula $A$ if $t(A)=T$.
\item For every Boolean vector $t$, we define a formula $C(t)$ as 
$a_1\& ...\& a_n$, where:
\begin{itemize}
\item[$\bullet$]$a_i=v_i$ if $t(v_i)=T$, and
\item[$\bullet$]$a_i=\neg v_i$ if $t(v_i)=F$.
\end{itemize}
\item By a {\it complete disjunctive normal form} of the formula $A$ 
(or, cDNF($A$), for
short), we mean the formula $C(t_1)\vee C(t_2)\vee ...$, where $t_1,
t_2,...$ are all Boolean vectors that satisfy the formula $A$. 
\end{itemize}

\noindent{\it Comment.} The formula cDNF($A$) means that the variables
$v_1,...,v_n$ take one of the tuples of values that make the formula
$A$ true. Therefore, this formula cDNF($A$) is equivalent to $A$
in propositional logic. 
\smallskip

\noindent{\bf Definition 7.} 
Let $A$ be a propositional formula. 
\begin{itemize}
\item We 
say that a Boolean vector {\it does not satisfy} the formula $A$ if $t(A)=F$.
\item For every Boolean vector $t$, we define a formula $D(t)$ as 
$a_1\vee ...\vee a_n$, where:
\begin{itemize}
\item[$\bullet$]$a_i=\neg v_i$ if $t(v_i)=T$, and
\item[$\bullet$]$a_i=v_i$ if $t(v_i)=F$.
\end{itemize}
\item By a {\it complete conjunctive normal form} of the formula $A$ 
(or, cCNF($A$), for
short), we mean the formula $D(t_1)\& D(t_2)\& ...$, where $t_1,
t_2,...$ are all Boolean vectors that satisfy the formula $A$. 
\end{itemize}

\noindent{\it Comment.} The formula cCNF($A$) means that the variables
$v_1,...,v_n$ do not take one of the tuples of values that make the formula
$A$ false. This formula is therefore equivalent to $A$
in propositional logic. 
\smallskip

\noindent{\bf THEOREM 1.} {\it Assume that $f_\&=\min$, $f_\vee=\max$,
and $f_\neg(a)=1-a$. Then, for an arbitrary propositional formula $A$,
$d^-(A)=d({\rm cDNF}(A))$ and $d^+(A)=d({\rm cCNF}(A))$.}
\smallskip

\noindent{\it Comments.}

1. All the proofs are given in the last section.

2. For operations different from $\&$ and $\vee$, the interval
$[d^-(A),d^+(A)]$ becomes trivial. To formulate the corresponding
result in precise terms, let is recall the following definitions and
results \cite{3,5}:
\smallskip

\noindent{\bf Definition 8.} \cite{5}
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 9.} \cite{5}
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{\bf CLASSIFICATION THEOREM FOR AND OPERATIONS.} 
\cite{5} {\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{\bf CLASSIFICATION THEOREM FOR OR OPERATIONS.} 
\cite{5} {\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$.}
\smallskip

\noindent{\bf Definition 10.} Let $d$ be the initial degrees of belief. We
say that a propositional formula $A$ is {\it not completely certain}
if $d(A)\in (0,1)$ (i.e., if $d(A)\ne 0$ and $d(A)\ne 1$).
\smallskip

\noindent{\it Comment.} In the following text, we will assume
that a negation operation $f_\neg$ is a continuous strictly decreasing
function $[0,1]\to [0,1]$ that maps 0 into 1 and 1 into 0. 
\smallskip

\noindent{\bf THEOREM 2.} {\it Let $f_\&$ is a continuous, strictly
monotonic t-norm, and let $d$ be the initial degrees of belief for
which a formula $A$ is not completely certain. Then
$[d^-(A),d^+(A)]=[0,1]$.}
\smallskip

\noindent{\bf THEOREM 3.} {\it Let $f_\vee$ is a continuous, strictly
monotonic t-conorm, and let $d$ be the initial degrees of belief for
which a formula $A$ is not completely certain. Then 
$[d^-(A),d^+(A)]=[0,1]$.}

\section{Additional Result: Case When Initial Degrees of Belief Are
Intervals}

In view of Theorems 2 and 3, in this Section, we will only consider
the case when $f_\&=\min$, $f_\vee=\max$, and $f_\neg(a)=1-a$. These
operations can be naturally extended to intervals in the following
way:
\smallskip

\noindent{\bf Definition 11.} Let $f:[0,1]\times [0,1]\to [0,1]$ be a
continuous function, and
let $I$ denote the set of all subintervals of the interval $[0,1]$.
Then, for ${\bf a}\in I$ and ${\bf b}\in I$, we define $f({\bf a},{\bf
b})$ as the the interval $\{f(a,b)\,|\,a\in {\bf a}, b\in{\bf b}\}$. 
\smallskip

\noindent{\it Comment.} For the above operations, this extension is
easy to describe:
\smallskip

\noindent{\bf PROPOSITION.}
{\it For all $a^-\le a^+$ and $b^-\le b^+$, the following formulas are
true:}
$$\min([a^-,a^+],[b^-,b^+])=[\min(a^-,b^-),\min(b^-,b^+)];$$
$$\max([a^-,a^+],[b^-,b^+])=[\max(a^-,b^-),\max(b^-,b^+)];$$
$$1-[a^-,a^+]=[1-a^+,1-a^-].$$

\noindent{\bf Definition 12.} By the {\it initial interval 
degrees of belief}, we
mean a function ${\bf d}:V\to I$. 
\smallskip

\noindent{\bf Definition 13.} 
Suppose that the initial interval degrees of belief $\bf d$ are given. 
Then, we can define ${\bf d}(A)$ for an arbitrary 
composite propositional formula $A$ as follows:
\begin{itemize}
\item ${\bf d}(\neg A)=1-{\bf d}(A)$;
\item ${\bf d}(A\& B)=\min({\bf d}(A),{\bf d}(B))$;
\item ${\bf d}(A\vee B)=\max({\bf d}(A),{\bf d}(B))$.
\end{itemize}

\noindent{\bf Definition 14.} 
\begin{itemize}
\item We say that a degree of belief $[a^-,a^+]$ is {\it smaller} that
the degree of belief $[b^-,b^+]$ (and denote it by $[a^-,a^+]\le
[b^-,b^+]$) if $a^-\le b^-$ and $a^+\le b^+$. 
\item We say that a formula $A$ is {\it weaker} than a formula $B$
(and that $B$ is {\it stronger} than $A$) if
for every initial interval degrees of belief $\bf d$, we have 
${\bf d}(A)\le {\bf d}(B)$. 
\end{itemize}

\noindent{\bf THEOREM 4.} {\it Every propositional formula $A$ is
stronger than cDNF($A$) and weaker than cCNF($A$).} 
\smallskip

\noindent{\it Comment.} If formulas $A$ and $B$ are equivalent in
propositional logic, then cCNF($A$)=cCNF($B$) and cDNF($A$)=cDNF($B$).
So, if $A$ and $B$ are equivalent, then the degree of belief in $B$ is
always bounded by the degrees of belief in cDNF($A$) and in cCNF($A$).
This theorem is therefore, a direct interval analogue of Theorem 1.

\section{Proofs} 

\subsection{Proof of Theorem 1} 

\subsubsection{Main Idea}
The main idea of our proof is as follows: to every formula $A$, we
will apply some transformations that leave $d(A)$ unchanged. As a result of
these transformations, we will be able to reduce $A$ to a special
form \cite{2}, and in that form, comparison with cCNF or cDNF will be easy. 

We will only describe the proof for cDNF. The proof for cCNF is
similar. 

\subsubsection{Moving Negations Inside}
For $\min$ and $\max$, the following Lemma can be easily proven:
\smallskip

\noindent{\bf LEMMA 1.} 
{\it For arbitrary propositional formulas $A$ and $B$, 
\begin{itemize}
\item $d(\neg(A\& B))=d((\neg A)\vee (\neg B))$;
\item $d(\neg(A\vee B))=d((\neg A)\& (\neg B))$;
\item $d(\neg(\neg A))=d(A)$.
\end{itemize}}

\noindent{\it Comment.} 
Indeed, e.g., the first statement easily follows from the 
statement that for all $a$ and $b$, 
$1-\min(a,b)=\min(1-a,1-b)$, if we take $a=d(A)$ and $b=d(B)$. This
statement, in its turn, 
can be easily proven by considering two possible cases: $a\le b$
and $a>b$. 
\smallskip

Using this Lemma, we can move all negations inside the formula until
we have a formula with the same values of $d$ in which negations are
only applied to variables. 

\subsubsection{Moving ANDs Inside}

\noindent{\bf LEMMA 2.} 
{\it For arbitrary propositional formulas $A$, $B$, and $C$, 
$d(A\&(B\vee C))=d((A\& B)\vee(A\& C))$.} 
\smallskip

The proof of this Lemma can be reduced to a statement 
that for all $a$, $b$, and $c$, 
we have $$\min(a,\max(b,c))=\max(\min(a,b),\min(a,c)).$$ This
statement can be proven
by considering all possible orderings of $a$, $b$, and $c$. 

Due to this lemma, whenever we have AND outside a composite formula, we
can move this AND inside. We can repeat this operation every time when
there is an AND outside the composite formula, thus moving AND further
and further inside. As a result, we can get a formula $B$ that is
equivalent to $A$, and in which AND is applied only to the variables
or to their negations. 

In other words, we get a formula $B$ 
of the type $C_1\vee ...\vee C_k$, where each of the subformulas $C_j$
is of the type $a\& ...\& b$, and $a, ..., b$ are {\it literals}
(i.e., variables or their negations). Such a form is called a {\it
Disjunctive Normal Form} (or, {\it DNF}, for short). Subformulas $C_j$
are called {\it conjunctions}. 

Due to Lemmas 1
and 2, we have $d(A)=d(B)$ for all initial degrees of belief $d$.

\subsubsection{Final Proof}
Let us now prove the Theorem. Since $d(A)=d(B)$, in order to prove
that $d(A)\ge d({\rm cDNF}(A))$, it is now sufficient to prove that 
$d(B)\ge d({\rm cDNF}(A))$. Here, 
${\rm cDNF}(A)=C(t_1)\vee C(t_2)\vee ...$, 
therefore, $d({\rm cDNF}(A))=\max(d(C(t_1)),d(C(t_2)),...).$
So, to prove that 
$d(B)\ge d({\rm cDNF}(A))=\max(d(C(t_1)),d(C(t_2)),...),$ 
it is sufficient to prove that 
$d(C(t_j))\le d(B)$ for all $j$.

The proof that $d(C(t_j))\le d(B)$
can be obtained via the following sequence of logical steps:
\begin{itemize}
\item By definition of cDNF, each $t_j$ 
is a satisfying vector for a formula $A$ (i.e., $t_j(A)=T$). 
\item Transformations from Lemmas 1 and 2 are equivalent in propositional
logic. So, $B$ is equivalent to $A$ in propositional logic, and hence, 
$t_j(B)=t_j(A)=T$. So, for the Boolean vector $t_j$, the formula $B= 
C_1\vee ...\vee C_k$ is true. 
\item By definition of OR, 
the fact that $C_1\vee ...\vee C_k$ is true 
 means that one of the
subformulas $C_l=a\& ...\& b$ is true. 
\item By definition of AND, the fact that $a\& ...\& b$ is true
means that all the literals $a, ..., b$ from the subformula $C_l$ are
true in $t_j$. 
\item By definition of $C(t_j)$, if a literal is true in $t_j$, then
it is an element of $C(t_j)$. So, all literals $a,...,b$ from $C_l$
are elements of $C(t_j)$. 
Hence, $C(t_j)$ contains all literals from
$C_l$ (and, maybe, some other literals), i.e., either $C(t_j)=C_l$, or
$C(t_j)=C_l\& c\& ...$. 
\item In the first case, $$d(C(t_j))=d(C_l)\le \max(...,
d(C_l),...)=d(B).$$
\item In the second case, $$d(C(t_j))=\min(d(C_l), d(c),...)\le
d(C_l)\le$$ $$ \max(..., d(C_l),...)\le d(B).$$ 
\item In both cases, $d(C(t_j))\le d(B)$. 
\end{itemize}
Hence, $$d({\rm cDNF}(A))=\max(d(C(t_1)),d(C(t_2)),...)\le $$ $$d(B)=d(A),$$
and $d({\rm cDNF}(A))\le d(A)$. Q.E.D.

\subsection{Proof of Theorem 2} 
Since $A$ is not completely certain, we have $d(A)\ne 0$ and $d(A)\ne
1$. For every $k$, the formula $A\& ...\& A$ ($k$ times) is equivalent
to $A$ in propositional logic. According to the Classification Theorem
for AND operations, the degree of belief in this formula is equal to
$\varphi ^{-1}((\varphi (a))^k)$ for the monotonic continuous function
$\varphi$ that corresponds to the chosen t-norm. When $k\to\infty$, we
have $(\varphi(a))^k\to 0$, and therefore, $d(A\& ...\& A)=
\varphi ^{-1}((\varphi (a))^k)\to 0$. Therefore, the set $S$ includes
values that are arbitrarily close to 0, and its infimum $d^-(A)$ is 0.

Let us now prove that it supremum is 1. Indeed, for each $k$, the
formula $\neg((\neg A)\& ...\& (\neg A))$ ($k$ times) is also
equivalent to $A$. Since $d(A)\in (0,1)$, and $f_\neg$ is strictly
decreasing, we have $d(\neg A)\in (0,1)$ and therefore, 
$d((\neg A)\& ...\& (\neg A))\to 0$. Hence, 
$d(\neg((\neg A)\& ...\& (\neg A)))\to 1$, and $d^+(A)=1$. Q.E.D.

\subsection{Proof of Theorem 3} This proof is similar to the proof of
Theorem 2.

\subsection{Proof of Theorem 4}
This proof is similar to the proof of Theorem 1, with the only
difference that instead of the relation $\le$ between numbers, we will
have to use the above-defined relation $\le$ between intervals, 
and instead Lemmas 1 and 2, we will have to use their interval analogues
\cite{2}:
\smallskip

\noindent{\bf LEMMA 3.} 
{\it For arbitrary propositional formulas $A$ and $B$, 
\begin{itemize}
\item ${\bf d}(\neg(A\& B))={\bf d}((\neg A)\vee (\neg B))$;
\item ${\bf d}(\neg(A\vee B))={\bf d}((\neg A)\& (\neg B))$;
\item $d(\neg(\neg A))=d(A)$.
\end{itemize}}

\noindent{\bf LEMMA 4.} 
{\it For arbitrary propositional formulas $A$, $B$, and $C$, 
${\bf d}(A\&(B\vee C))={\bf d}((A\& B)\vee(A\& C))$.} 
\smallskip

These Lemmas can also be proven by considering all possible cases of
relationship between $a^\pm$, $b^\pm$, and $c^\pm$, where:
\begin{itemize}
\item by $a^\pm$, we denoted the endpoints of the interval 
${\bf d}(A)=[a^-,a^+]$;
\item similarly, ${\bf d}(B)=[b^-,b^+]$; and
\item ${\bf d}(C)=[c^-,c^+]$.
\end{itemize}
Q.E.D.

\begin{thebibliography}{99}

\bibitem{2} H. T. Nguyen, O. Kosheleva and V. Kreinovich, 
{\bf Is The Success of Fuzzy Logic
Really Paradoxical? Or What is The Actual Logic Behind Expert
Systems?}, University of Texas at El Paso, Department of Computer
Science, Technical Report UTEP-CS-94-23, November 1994.

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

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

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

\bibitem{3} Q. Zuo, ``Description of Strictly Monotonic Interval 
AND/OR Operations'', {\it These Proceedings}.

\end{thebibliography}
\end{document}