Generalization of the Dempster-Shafer Theory

1 Introduction

Uncertainty is a feature of our experience and observa­ tion of the world. Finding suitable means of represen­ tation and manipulation of uncertainty of information and knowledge [Bell 1992] is a challenge which will have to be met if computerized decision-making based on im­ perfect input is to be contemplated. An understanding of the effect of uncertainty on evidence appraisal, and ultimately on the behavior and properties of agents is essential. This paper contributes to this understanding and to the practical handling of evidence. It addresses the extension, in both practical and theoretical terms, of a numerical system which enables computer applications to reflect some aspects of uncertainty.

The theory of evidence which originated with Demp­ ster and Shafer underpins a method which has been shown to be a promising tool for making judgements when confronted with uncertainty in numerical evidence. It generalizes Bayesian theory which is itself a popular theory of uncertainty.

The generalization of evidence theory in turn is the subject of this paper. It involves moving away from the standard finite set based derivation of theoretical and computational results underpinning the Dempster­ Shafer approach. Conventionally propositions are rep­ resented as subsets of a collection of all possible values of a target variable. This particular representation of the hypothe!i! !pace is not the only way to represent propositions. Most obviously we can think of leaving the propositions as they are, avoiding their transformation into subsets. This is of immediate interest in reasoning applications, because propositions are familiar and can be used to represent arguments, hypotheses, etc.

If this were done we would still be dealing with a struc­ ture which has an important similarity to the previous space - both are Boolean algebras. This leads to the question: can we generalize evidence theory to general Boolean algebras ? If we can, this allows us to choose a representation - we can use subsets, propositions, and other means to represent hypotheses and their relation­ ships, as appropriate, in the hypothesis space. It can also allow us to establish a theory which covers infinite hypothesis spaces and evidence spaces by this extension.

This representational and theoretical advantage of the generalization is our focus of attention in this paper. However we have argued elsewhere [Guan & Bell 1993a], and supported our arguments by defining operations, that many applications can achieve improved perfor­ mance through using more appropriate representations. We demonstrated that by generalizing the orthogonal !Um operation so that hypotheses could be represented directly as propositions, such a performance enhance­ ment could accrue. Using this representation, all the subsets of the hypothesis space e, i.e., 21el subsets, need not be considered (as they would in standard Dempster­ Shafer theory). By focusing on relevant propositions only, the time complexity may be reduced to well be­ low the previous 0(21e1) time.

To these advantages of representational and manipu­ lative flexibility and efficiency for applications, we can add the advantage of developing a theory which covers infinite hypothesis spaces and evidence spaces, and ex­ tending our understanding of the Dempster-Shafer tech­ nique.

In section 2 we define evidential functions which are based on Boolean algebras. In particular we introduce weak versions of Bayesian functions, belief functions, and other evidential functions. We establish relationships be­ tween these weak functions and the familiar correspond­ ing functions from evidence theory, showing that the re­ sults for power sets do not carry over to Boolean algebras in the general case. In section 3 we discuss nested eviden­ tial functions. We show in section 4 that we can obtain familiar relations for the particular case of the power set. The well-known inversions between the most conspicu­ ous evidential functions are derived. Then we complete the paper by summarizing the relationships between the weak evidential functions obtained.

2 Evidential functions

In evidence theory, evidence is described in terms of evi­ dential functions. There are several functions commonly used in the theory - mass functions, belief functions, commonality functions, doubt functions, and plausibil­ ity functions. Normally they are defined over finite sets. Here we generalize evidential functions to Boolean alge­ bras. The significance of this is that conventional eviden­ tial functions are defined over the power set of a frame of discernment, but Boolean algebras include other in­ teresting spaces, such as the space of propositions.

Let< X, u, n,', ~. llf >be a Boolean algebra, where X is the &pace of di&cernment; U is the union operation; n is the intersection operation; 1 is the negation operation; ~ is the zero element, the least element in X under the partial ordering relation ~; llf is the identity element, the greatest element in X under ~·

Let [0, 1) denote the unit interval of real numbers.

A function bay : X -+ [0, 1) is called a weak Baye&ian (probabili&tic) function if y1) bay(~)= 0, y2) bay(llf) = 1, y3) bay(AuB) = bay(A)+bay(B) whenever AnB = ~.

THEOREM 1. Let bay be a weak Bayesian function. Then (1) bay(A) + bay(A') = 1. (2) bay(A) ~ bay(B) when A~ B; i.e., bay is non-decreasing.

A function bay : X 1 -+ [0, 1) is called a Baye&ian func­ tion ify1) bay(~)= 0, y2) bay(llf) = 1, y3' bay(AUB) = bay( A) +bay( B) - bay( An B).

A Bayesian function is a weak Bayesian function since y1), y2), and y3' imply y1), y2), and y3) .

THEOREM 2. Suppose bay is a function bay: X -+ [0, 1) and it satisfies y1) bay(~) = 0, y2) bay(llf) = 1.

Then the following assertions are all equivalent: y3. bay is a Bayesian function. y3' bay(A U B) = bay(A) + bay(B) - bay(A n B). y3" For any collection A1. A2, ... ,An (n ~ 1) of subsets of llf, bay(A1 U A2 U ... U An) = 'Er~{l,2, ... ,n},I;tt( -1)1II+1bay(niEIAi).

A function bel : X -+ [0, 1) is called a weak belief function if it satisfies b1) bel(~) = 0, b2) bel(llf) = 1, b3) for any collection A11 A2, .. . ,An ( n ~ 1 ) of subsets of llf, bel(A1 U A2 U ... U An) > 'Er~{l,2, ... ,n},r;te( -1 )III+lbel(niEI Ai ).

THEOREM 3. Let bel be a weak belief function . Then (1) We have bel(AuB) ~ bel(A)+bel(B)-bel(An B) for all A, B E ,l'. (2) bel is non-decreasing; i.e., bel(A) ~bel( B) when A~ B. (3) bel(X) + bel(X ') S 1.

Given a weak belief function bel, the function dou(A) = bel(A') is called a doubt function and the function pls(A) = 1 - dou(A) = 1 - bel(A') is called a plau&ibility function. It is easy to see that dou( ~) = 1,dou(llf) = O;pls(~) = O,pls(llf) = 1.

THEOREM 4. A doubt function dou is non­ increasing; i.e., A ~ B implies dou(A) ~ dou(B) .

THEOREM 5. (1) A plausibilityfunctionpls is non­ decreasing; i.e., A ~ B implies pls(A) ~ pls(B) . (2) pls(X) + pls(X') ~ 1, bel(X) ~ pls(X) for all X E .l'.

A function m: X-+ [0, 1) is called a mas& function if it has non-zero value only at a finite number F of elements A1, A2, ... , AF in X (i .e., subsets ~ llf) and it satisfies m1) m(~) = 0, m2) 'Exc~ m(X) = I:{=1 m(Ai) = 1.

Notice that X ~ llf if and only if X E ,l'. Also, notice that m has non-zero value only at a finite number of subsets X~ llf, so 'Exc~ makes sense.

A subset A of a frame X is called a focal element of a mass function mover X if m(A) > 0. Thus, the number of focal elements of a mass function is finite. The union C of all the focal elements of a mass function is called its core: C = UxeX,m(X)>oX, where Uxex makes sense as the number of focal elements of a mass function is finite.

A function bel on X is called a belief function if it can be expressed in terms of a mass function m: bel(A) = 'EAcx m(X) for all A EX.

THEOREM 6. Let m be a mass function . Then the function bel defined by the following expression bel( A) = 'ExcA m(X) for all A ~ llf is a weak belief function .

A -function com : X -+ [0, 1) is a commonality func­ tion if there is a mass function m such that com( A) = 'EA~X m(X) for all A~ llf.

3 The nested evidential functions

A function ben on X such that ben : X -+ [0, 1) is said to be a weak ne&ted belief function if it satisfies n1) ben(~) = 0; n2) ben(llf) = 1; n3) ben(A n B) = min{ben(A), ben( B)} for all A, B ~ llf.

THEOREM 7. Let ben be a weak nested belieffunc­ tion on < X, u, n,', ~. llf >; i.e., ben is a function such that ben : X -+ [0, 1) satisfying n1) ben(~) = 0; n2) ben(llf) = 1; n3) ben( An B) = min{ben(A), ben( B)} for all A, B ~ llf. Then ben is a weak belief function .

THEOREM 8. Let< ,l', u, n,', ~. llf >be a Boolean algebra. Let ben, pls, dou be functions X -+ [0, 1), and let pls(A) = 1- ben( A'), ben( A)= 1-pls(A'); dou(A) = ben( A'), ben( A) = dou(A') for all A ~ llf. Suppose ben satisfies n1) ben(~) = 0; n2) ben(llf) = 1. Then the following assertions are equivalent.

n3. ben is a weakly nested belief function .

n3) ben( An B) = min{ben(A), ben( B)} for all A, B ~ llf.

p3) pls(A U B)= max{pls(A),pl.!(B)} for all A, B C llf.

d3) dou(Xu B) = min{dou(A), dou(B)} for all A, B ~ llf.

THEOREM 9. Let< X, u, n,', ct, 1lT >be a Boolean algebra.

Let ben be a weak nested belief function on ;t', and let pls be its plausibility function on .r: pls(A) = 1 - ben( A'), ben(A) = 1- pls(A') for all A~ llf .

Then we have the following.

1. min{ ben( A), ben( A')}= 0 for all A~ llf .
2. max{pls(A),pls(A')} = 1 for all A~ W.
3. pls(A) < 1 implies ben(A) = 0 for all A ~ llf; i.e.,

when pls(A) < 1;

when pls(A) < 1 for all A~ W.

(4) ben(A) > 0 implies pls(A) = 1 for all A~ llf; i.e.,

when ben(A) > 0;

when ben(A) > 0 for all A~ llf.

Define bel(XIB) = hel(XuB')-bel(B') £ ll X C 1lT 1-hei(B') or a - and all B ~ llf, bel(B') < 1. Also, define pls(XIB) = 1 - bel(X'IB), bel(XIB) = 1 - pls(X'IB) for all X ~ w and all B ~ llf,bel(B') < 1,pls(B) > 0.

THEOREM 10. Let < X, u, n,', ct, 1lT > be a Boolean algebra. Let bel,pls be functions ;t' --+ [0, 1], and pls(A) = 1 -bel( A'), bel( A) = 1- pls(A') for all A ~ W. Supposl" bel satisfies nl) bel(<t) = 0; n2) bel(llf) = 1; i3) bel is non-decreasing; i.e., A ~ B implies bel(A) :::; bel( B) for all A, B ~ W. Then, the following assertions are all equivalent.

1. For function bel, min{bel(AIB), bel(A'IB)} = 0 for all A ~ 1lT and all B ~ 1lT such that bel( B') < 1.
2. For function pls, max{pls(AIB),pls(A'IB)} = 1 for all A ~ 1lT and all B ~ 1lT such that pls(B) > 0.
3. Again max{pls(A n B), pls(A' n B)} = pls(B) for all A~ 1lT and all B ~ 1lT such that pls(B) > 0.
4. And, max{pls(A n B), pls(A' n B)} = pls(B) for all A, B C llf .
5. Al;o, pls(D U E) = max{pls(D),pls(E)} for all D,E C llf.
6. bel is a weak nested belief function.

Suppose m is a mass function on the Boolean al­ gebra < X, U, n,', ct, 1lT >. m is said to be nested if its focal elements Ai; i = 1, 2, .. . , F; F > 0 can be ar­ ranged into an increasing chain of supersets: ct C A1 C A2 C ... C AF ~ llf , where m(A1),m(A.), ... ,m(AF) > 0; Lr=1 m(Ai) = 1.

We also say the belief function , plausibility function, and doubt function bel, pls, dou are nested when the mass function m is nested.

THEOREM 11. Let < X , u, n,', ct, 1lT > be a Boolean algebra. Let m be a mass function on X, and let bel be its belief function: bel( A)= LxcA m(X) for all A ~ 1lT . Suppose m is nested. -

Then bel is a weak nested belief function. That is, (by definition) bel satisfies n1) bel(<t) = 0; n2) bel(llf) = 1; n3) bel(A n B)= min{bel(A), bel( B)} for all A, B ~ w.

4 THE SPECIAL CASE WHERE SETS ARE FINITE

In this Sl"d.ion we show that thl" generali1.ecl t.hl"nrv pre­ sented in earlier sections reduces to familiar results when we are dealing with finite sets and subsets.

Let < X, U, n,', ct, 1lT > be a Boolean algebra as before. Earlier, we showed that

{ Bayesian functions } ~ { Weak Bayesian functions };

{ Bayesian functions }, { Weak nested belief functions },

{ Belief functions } ~ { Weak belief functions };

{ Nested belief functions }

In this section we will prove that for finite set 2 9 these ~ relations become equalities:

{ Belief functions } = { Weak belief functions },

{ Nested belief functions }

= { Weak nested belief functions }.

4.1 BAYESIAN FUNCTIONS

This subsection shows that Bayesian functions and weak Bayesian functions are identical for finite sets.

THEOREM 12. Let < X, u, n,', ct, 1lT >=< 2 9 , u, n,~ 0, e >, where e is a finite set. Then all weak Bayesian functions are Bayesian functions.

PROOF.Suppose bay is a function bay: 2 9 --+ [0, 1] and it satisfies y1) bay(0) = 0, y2) bay(e) = 1. Consider the following assertions:

• y3) bay is weak Bayesian; i.e., bay( AU B)= bay( A)+ bay( B) whenever An B = 0.
• y3} bay(A) = Lo:EA bay({:z:}) for all A~· e.

y3' bay is Bayesian; i.e., bay(A U B) = bay(A) + bay( B)- bay(A n B).

We prove this theorem as follows: y3) implies y3} , y3} implies y3'.

(i) y3) implies y3}. If A = 0, then y3} bay(0) = Lo:Ee bay({:z:}) is true from y1) bay(0) = 0 and from

If A =/= 0, then we may write A = { a1, a2, ... , an}, where a1, a2, ... , an are distinct and n ~ 1. Applying y3) re­ peatedly, we find that bay(A) = bay({a1,a2, ... , an})= bay( {a!})+ bay( { a2, .. . , an}) = bay( { a1}) +bay( { a2}) + bay( {a3, ... , an}) = ...... = bay( {a1}) +bay( {a2}) + ... + bay({an}) = Lo:EA bay({:z:}) since {a1} n {a2, ... ,an}= 0, {a2} n {a3, ... , an}= 0, .. .... , {an-1} n {an}= 0. Thus, y3) implies y3}.

(ii) y3} implies y3'. From y3}, bay(A U B) = Lo:EAUB bay({:z:}) = Lo:EA bay({:z:})+ Lo:EB bay({x})­ Lo:EAnB bay({:z:}) = bay(A) + bay(B)- bay(A n B). So y3} implies y3'. I QED I

4.2 BELIEF FUNCTIONS

In order to prove that in the case where X is the power set of a finite set e, all weak belief functions are belief functions, we need the following Mobius inversion.

MOBIUS INVERSION. Supjose e is a finite set, f and g are functions on 2 ·. Then f(A) = LxcA g(X) for all A ~ e if and only if g(A) = Lx~A(-1)1A-Xlf(X) for all A~ e.

As usual, if m is a mass function, then the function bel defined by (BM) bel(A) = LXCA m(X) for all A ~ e is said to be the belief function or m.

THEOREM 13. When e is a finite set, all weak belief functions are belief functions. That is, if bel is a weak belief function, then there exists a mass function m such that the function bel can be given by m as follows: (BM) bel(A) = LXCA m(X) for all A ~ e.

PROOF. Suppose bel is a weak belief function; i.e., bel is a function bel : 2° -+ [0, 1] satisfying the three conditions b1), b2), b3) .

Define a function m on 2° by (MB) m(A) LxcA(-1)1A-XIbel(X) for all A~ e.

Then we have (BM) bel(A) = LxcA m(X)

for all A ~ e and bel can be expressed in terms of m by Mobius inversion.

In order to prove that m is a mass function, we need to establish m1), m2), and m : 2° -+ [0, 1], i.e., 0 ~ m(A) ~ 1 for all A ~ e.

From (MB) and b1) we have m1) m(0) Lxce( -1)1°-XIbel(X) = ( -1) 0 bel(0) = 0, and from (BM) and b2) we have m2) Lxc0 m(X) =bel( e)= 1.

Now we only need to show- that 0 ~ m( A) ~ 1 for all A ~ e. Let us prove first that m{A) ~ 0 for all A # 0, A ~ e .

If !AI > 1, then let A = {al!a2, ... ,an}, where n > 1 and a1, a2, ... , an are distinct. Denote Ai = A- {ai} fori= 1, 2, ... , n, so that All A:~, ... , An are precisely the subsets of A that omit exactly one respective element all a:~, ... , an of A and A = A1 U A2 U ... U An· Then every proper subset X of A can be uniquely ex­ pressed as an intersection of the Ai. That is, for every X C A, there is an I ~ {1, 2, .. . , n}, I # 0 such that X= nierAi and A- X= {aili E I}.

Conversely, for every I~ {1, 2, .. . , n}, I# 0 there is an XC A such that X= nierAi and A- X= {aili E I}.

In other words, there is a one-to-one correspondence between the proper subsets X of e and the non-empty subsets I of {1, 2, ... , n} such that X= nierAi and A­ X= {a;li E I}.

Thus by b3) m(A) = LxcA(-1)1A-XIbel(X) LX=A ( -1)1A-XIbel(X) + Lx~A ( -1)1A-XIbel(X) ( -1)101bel(A) + Lr~{ 1, 2, . . . ,n},r;te( -1 )I{ "·liE I} I bel(niei Ai) = bel(A) + Lr~{ 1 , 2 , ... ,n},r;te( -1)1 1 1bel(nierAi) = bel(A1 U A2 U ... U An)- Lr~{ 1 , 2 , ... ,n},I;te( -1)1II+lbel(nierAi) ~ 0.

And if A= {a}, then from (MB) m({a}) = Lx~{<>}( -1)1{<>}-XIbel(X) ( -1)1{<>}1bel(0) + (-1)1°1bel({a}) = bel({a}) ~ 0 ( because bel(0) = 0

by b1) and bel is a function bel : 2° -+ [0, 1] therefore bel({a}) ~ 0 ).

Summarizing, we have m(A) ~ 0 for all A# 0, A<;; e and from m1), we have m(A) ~ 0 for all A~ e.

Also from m2), we have Lxc0 m(X) = 1. So m(X) ~ 1 for all subsets X ~ e,- and 0 ~ m(X) ~ 1 for all subsets X ~ e, which is what we set out to show. I QED I

4.3 NESTED BELIEF FUNCTIONS

Let < ,f, u, n,', <I>, "Ill >=< 2°, u, n,~ 0, e > as before. We can prove that weak nested belief functions are nested belief functions.

We have pls(A) = LxnA;t0 m(X) for all A ~ e: pls(A) = 1 - bel( A) = 1 - LxcA m(X) = 1 - LxnA=· m(X) = Lxc0 m(X) - ExnA=0 m(X) = LxnA;te m(X) . -

Also, we have the following pls-com inversion ( theo­ rem 2.4.5, p.59, Vol.l, Guan & Bell, 1991): pls(0) = O,pls(A) = Lx~A,X;te(-1)1XI+lcom(X) for all nonempty A ~ e, and com(0) 1, com( A) Lx~A,X;t0 ( -1)1XI+lpls(X) for all non-empty A ~ e. Now we can prove the following.

THEOREM 14. Let < X, u, n,', <I>, "Ill >=< 2°, u, n,-, 0, e >,where e is a finite set. Let m be a mass function on 2° and let bel, pls, com be its corresponding belief function, plausibility function, and commonality function, respectively. Then the following assertions are all equivalent.

• ( 1) bel is nested.
• bel is weakly nested; i.e.,

for all A, B ~ e.

1. pls(A U B)= max{pls(A),pls(B)} for all A, B ~ e.
2. pls(A) = max.:eA{pls({:z:})} for all non-empty ACe.

(5) com(A) = min:z:eA{com({:z:})} for all non-empty A~e.

PROOF. We proceed as follows: (1) implies (2), (2) implies (3), (3) implies (4), (4) implies (5), (5) implies ( 1 ).

(i) We prove (1) implies (2). Since m is a nested mass function on 2°, its F focal elements can be arranged into an increasing chain of supersets: 0 C A1 C A2 C ... C AF ~ e, F > 0 where m(Al), m(A2 ) , . .. , m(AF) > 0; 2:[= 1 m(Ai) = 1. We want to prove that bel( An B) = mint bel( A), bel( B)} for all A, B ~ e.

Denote Ao = 0. Given two subsets A, B ~ e, let l ~ 0 be the maximum integer such that A1 ~ A: A0 C A1 C A2 C ... C A1 ~ A, A1+1 C£. A; i.e., l = max{iiO ~ i ~ F, Ai ~A}; and let n ~ 0 be the maximum integer such that An ~ B: Ao C A1 C A:~ C .. . C An ~ B, An+l C£. B; i.e., n = max{iiO ~ i ~ F, Ai ~A}. Then

1. Ai ~ A for i = 0, 1, 2, ... , F if and only if 0 ~ i ~ l.
2. Ai ~ B fori= O, 1, 2, ... , F if and only if 0 ~ i ~ n .
3. Ai ~ An B for i = 0, 1, 2, ... , F if and only if 0 ~ i ~ min{l, n}.

Therefore we find that bel(AnB) = LxcAnB m(X) = LA,CAnB;i=l,:I, ... ,F m(Ai) since Aii i = 1, 2, ... ,Fare all the focal elements of m at which m has positive values, so bel(A n B)

again since Ai; i = 1, 2, ... ,Fare all the focal elements of m at which m has positive values.

• (ii) (2) implies (3). Suppose bel(A n B) min{bel(A), bel( B)} for all A, B ~ e. We want to prove that pls(AUB) = max{pls(A), pls(B)} for all A, B ~ e.

Indeed, we find that pls(A U B) = 1- bel( AU B) = 1 - bel(A n B) = 1- min{bel(A), bel( B)} = max{1bel( A), 1- bel(B)} = max{pls(A), pls(B)} for all A, B ~ e.

(iii) (3) implies (4). Suppose (3) holds: pls(A U B)= max{pls(A),pls(B)} for all A, B ~e. We want to prove the assertion pls(X) = max.,Ex{pl.!({x})} for all non­ empty X~ e.

Use mathematical induction on lXI. When lXI = 1 : X = {X}, X E e the assertion is true since pl.!( {X}) = max.,E{z}ipl.!({x})} = max{pls({x})} = pls({x}) for all x E e.

Suppose the assertion is true when lXI = n and now lXI = n + 1, X = {x1, x:;~, ... , Xn, Xn+I}· Then we find that pls(X) = max{pl.!({xl!x2,····xn}),pl.!({xn+l})} from (3), max{max{pls({xi}),pl.!({x2}), ··· , pls( {xn} )}, pls( {xn+l})} by induction hypothesis since l{xl, x2, ... , Xn}l = n,

= max.,Ex{pls({x})}. That is, the assertion is true when IX I = n + 1 and the mathematical induction is com­ pleted. The assertion is proved.

(iv) (4) implies (5). Suppose assertion (4) holds: pls(X) = max.,Ex{pls({x})} for all non-empty X~ e. We want to prove that com(X) = min.,Ex{com({x})} for all non-empty X ~ e.

Notice that the plausibility function pl.! and the commonality function com are equal at all singletons: com( { x}) = pl.!( { x}) for all x E e sine~ com( { :r. t) = L{z}I:;X m(X) = L{z}nX~t m(X) = pl.!({x}).

Let X = {XI, x:;~, ... , :Z:n} and let pl.!( { :z:I}) ~ pl.!({:z::~}) ~ ... ~ pl.!({:z:n}). Then

1. Non-empty subsets Y of X are in one-to-one corre­ spondence to non-empty subsets I of {1, 2, .. . , n} : Y ~ X, Y f. 0,Y = {:z:ili E I}+--+ I~ {1,2, ... ,n},I :f 0.
2. We have

1. We have i = max{ili E I} if and only if I C {1,2, ... ,i} and i E /.

4. We have pls({:z:1}) = min.,Ex{pls({:z:})}. So we find that com(X)

• = LY!:;X, Y~e(-1)1YI+lpl.!(Y) by the pls-com inversion,

by the subset formula (formula 1.2.1, p.ll, Vol.l, Guan & Bell, 1991),

Thereby we conclude that assertion (5) holds: com( X) pl.!( {xi}) min.,Ex{pl.!( {x})} = min.,Ex{com({x})} for all non-empty X~ e.

(v) (5) implies (1). We want to prove that com(X) = min.,Ex{com({x})} for all non-empty X ~ e implies that m is nested; i.e., its F focal elements can be ar­ ranged into an increasing chain of supersets: 0 C A1 C A:~ C ... CAp, F > 0 where m(A1), m(A:;~), ... , m(AF) > 0; I:[=1 m(Ai) = 1.

Suppose m is not nested; i.e., there exist two focal ele­ ments A, B ~ e such that A~ B, B ~A; m(A), m(B) > 0. So there exist two elements a, b E e such that a E A, a fl. B; b E B, b fl. A. We want to prove that as­ sertion (5) does not hold; i.e., there exists a non-empty D ~ e such that com(D) :f minzED{com({:z:})}.

Let D = {a, b}. It suffices to prove that com( {a, b}) < com( {a}), com( {b} ).

Indeed, we find that com( {a})

= Lx~e.x~{<>} m(X) ~ m(A) + Lx~e,x~{<>,b} m(X) since {X ~ 9jX 2 {a}} 2 {X ~ 8jX 2 {a,b}},A 2 {a}, A~ {a,b} Thus, we have com({a}) ~ m(A) + Lx~e,x~{<>,b} m(X) > Lx~e.x~{<>,b} m(X) = com( {a, b}) since the focal element A makes m( A) > 0.

Also, we find that com( {b}) = Lx~e.x~{b} m(X) ~ m(B) + Lx~e.x~{<>,b} m(X) since {X~ ejx 2 {b}} 2 {X ~ 8jX 2 {a,b}},B 2 {b},B ~ {a,b}. Thus, we have com({b}) ~ m(B) + Lx~e,x~{<>,b} m(X) > Lx~e.x~{<>,b} m(X) = com({a,b}) since the focal element B makes m(B) > 0. ~

5 SUMMARY

Most important spaces in artificial intelligence are Boolean algebras, for example, power sets and propo­ sition sets. The Dempster-Shafer theory originally ad­ dressed only the power sets. This paper generalizes the theory to Boolean algebras.

We investigate all the most important kinds of belief functions on an algebra to enable us to choose the most suitable belief function to represent evidence, according to the particular situation presented. The generaliza­ tion enables us to choose the most suitable algebra to represent knowledge and reason efficiently.

We introduce weak Bayesian (probabilistic) functions, Bayesian (probabilistic) functions, weak belief functions, and belief functions. We show that Bayesian functions are weak Bayesian functions; and Bayesian functions and belief functions are weak belief functions.

Mass functions, commonality functions, plausibility functions, and doubt functions are also introduced.

In the case where X = 2° and e is a finite set, we show that weak Bayesian functions are Bayesian func­ tions and vice versa. Moreover, weak belief functions are then belief functions and vice versa, and weak nested be­ lief functions are nested belief functions and vice versa.