foundations of computational agents
The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).
The preceding section gave a semantic definition of probability. An axiomatic definition specifies axioms. These are axioms one may want for a calculus of belief, and we show they are satisfied by probability.
Suppose $P$ is a function from propositions into real numbers that satisfies the following three axioms of probability:
$0\le P(\alpha )$ for any proposition $\alpha $. That is, the belief in any proposition cannot be negative.
$P(\tau )=1$ if $\tau $ is a tautology. That is, if $\tau $ is true in all possible worlds, its probability is 1.
$P(\alpha \vee \beta )=P(\alpha )+P(\beta )$ if $\alpha $ and $\beta $ are contradictory propositions; that is, if $\mathrm{\neg}(\alpha \wedge \beta )$ is a tautology. In other words, if two propositions cannot both be true (they are mutually exclusive), the probability of their disjunction is the sum of their probabilities.
These axioms are meant to be intuitive properties that we would like to have of any reasonable measure of belief. If a measure of belief follows these intuitive axioms, it is covered by probability theory. Note that empirical frequencies – propositions about the proportion of examples in a data set – obey these axioms, and so follow the rules of probability, but that does not mean that all probabilities are empirical frequencies (or obtained from them).
These axioms form a sound and complete axiomatization of the meaning of probability. Soundness means that probability, as defined by the possible-worlds semantics, follows these axioms. Completeness means that any system of beliefs that obeys these axioms has a probabilistic semantics.
If there are a finite number of finite discrete random variables, Axioms $\mathrm{1}$, $\mathrm{2}$, and $\mathrm{3}$ are sound and complete with respect to the semantics.
It is easy to check that these axioms are true of the semantics. Conversely, the axioms can be used to compute any probability from the probability of worlds, because the descriptions of two worlds are mutually exclusive. The full proof is left as an exercise. (See Exercise 2.)
The following hold for all propositions $\alpha $ and $\beta $
Negation of a proposition:
$$P(\mathrm{\neg}\alpha )=1-P(\alpha ).$$ |
If $\alpha \leftrightarrow \beta $, then $P(\alpha )=P(\beta )$. That is, logically equivalent propositions have the same probability.
Reasoning by cases:
$$P(\alpha )=P(\alpha \wedge \beta )+P(\alpha \wedge \mathrm{\neg}\beta ).$$ |
If $V$ is a random variable with domain $D$, then, for all propositions $\alpha $,
$$P(\alpha )=\sum _{d\in D}P(\alpha \wedge V=d).$$ |
Disjunction for non-exclusive propositions:
$$P(\alpha \vee \beta )=P(\alpha )+P(\beta )-P(\alpha \wedge \beta ).$$ |
The propositions $\alpha \vee \mathrm{\neg}\alpha $ and $\mathrm{\neg}(\alpha \wedge \mathrm{\neg}\alpha )$ are
tautologies. Therefore,
$1=P(\alpha \vee \mathrm{\neg}\alpha )=P(\alpha )+P(\mathrm{\neg}\alpha )$. Rearranging gives the desired result.
If $\alpha \leftrightarrow \beta $, then $\alpha \vee \mathrm{\neg}\beta $ is a tautology, so $P(\alpha \vee \mathrm{\neg}\beta )=1$. $\alpha $ and $\mathrm{\neg}\beta $ are contradictory statements, so Axiom 3 gives $P(\alpha \vee \mathrm{\neg}\beta )=P(\alpha )+P(\mathrm{\neg}\beta )$. Using part (a), $P(\mathrm{\neg}\beta )=1-P(\beta )$. Thus, $P(\alpha )+1-P(\beta )=1$, and so $P(\alpha )=P(\beta )$.
The proposition $\alpha \iff ((\alpha \wedge \beta )\vee (\alpha \wedge \mathrm{\neg}\beta ))$ and $\mathrm{\neg}((\alpha \wedge \beta )\wedge (\alpha \wedge \mathrm{\neg}\beta ))$ are tautologies. Thus, $P(\alpha )=P((\alpha \wedge \beta )\vee (\alpha \wedge \mathrm{\neg}\beta ))=P(\alpha \wedge \beta )+P(\alpha \wedge \mathrm{\neg}\beta ).$
The proof is analogous to the proof of part (c).
$(\alpha \vee \beta )\iff ((\alpha \wedge \mathrm{\neg}\beta )\vee \beta )$ is a tautology. Thus,
$P(\alpha \vee \beta )$ | $=P((\alpha \wedge \mathrm{\neg}\beta )\vee \beta )$ | ||
$=P(\alpha \wedge \mathrm{\neg}\beta )+P(\beta ).$ |
Part (c) shows $P(\alpha \wedge \mathrm{\neg}\beta )=P(\alpha )-P(\alpha \wedge \beta )$. Thus,
$$P(\alpha \vee \beta )=P(\alpha )+P(\beta )-P(\alpha \wedge \beta ).$$ |
∎