A summary of Boolean algebra
Given the following notations:
- a proposition is denoted as a lowercase letter, e.g. $p$, $q$
- the truth value of a proposition $p$ is denoted as $ B(p) \in \set{0, 1} $, where $B(p)=1$ if $p$ is true or $B(p)=0$ if $p$ is false
Negation (not, $¬$), conjunction (and, $∧$) and disjunction (or, $∨$) are defined by the truth tables below:
| $B(p)$ | $B(¬p)$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
| $B(p)$ | $B(q)$ | $B(p∧q)$ | $B(p∨q)$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Truth value allocation as an intuitive picture of Boolean algebra
Intuitively, we can derive the same truth tables by following the process of the truth value allocation with the two steps below:
- List all mutually exclusive results from propositions under consideration
- Allocate the truth value to them so that their truth-values sum up to $1$
Note that the second step actually requires only one of result has a truth value $1$, given $ B(p) \in \set{0, 1} $.
Negation
For a single proposition $p$, there are two mutually exclusive results $p$ (is true) or $¬p$ (is true), as follows:
| $¬p$ | $p$ |
|---|---|
| $B(¬p)$ | $B(p)$ |
Where we can allocate the truth value:
$$B(¬p) + B(p) = 1$$
Thus we get an equivalent equation to the negation truth table.
Conjunction
Now let’s consider two propositions $p$ and $q$ at the same time. There are four mutually exclusive results: $(p∧q)$, $(¬p∧q)$, $(p∧¬q)$ or $(¬p∧¬q)$. Thus we have the truth value allocation table:
| $¬p$ | $p$ | |
| $¬q$ | $B(¬p∧¬q)$ | $B(p∧¬q)$ |
| $q$ | $B(¬p∧q)$ | $B(p∧q)$ |
Where we can allocate the truth value:
$$ B(¬p∧¬q) + B(p∧¬q) + B(¬p∧q) + B(p∧q) = 1 $$
From the allocation we can easily get $B(p)$ as the sum of the second column:
$$ B(p) = B(p∧q) + B(p∧¬q) $$
And $B(q)$ as the sum of the second row:
$$ B(q) = B(p∧q) + B(¬p∧q) $$
Similar equations can be derived for $B(¬p)$ as the sum of the first column and $B(¬q)$ as the sum of the first row.
If we use the notation $B(q|p)$ as the ratio of truth value “q is true” given “p is true”, the conjunction $B(p∧q)$ can be expressed as:
$$ B(p∧q) = B(p) \times B(q|p) $$
This equation can be read from the allocation table as “the sum of the first column where $p$ is true” times “the ratio of $q$ is true given $p$ is true”.
Also, note that $B(q|p) = B(q)$, which can be easily derived from the allocation table. Thus we have the equivalent equation for the conjunction:
$$ B(p∧q) = B(p) \times B(q) $$
Disjunction
The disjunction $B(p∨q)$ can be calculated by summing up the second column (where $p$ is true) and the second row (where $q$ is true) but subtracting $B(p∧q)$ (which is summed twice):
$$ B(p∨q) = B(p) + B(q) - B(p∧q) $$
From Boolean algebra to probability
The probability can be generalised from the similar notations and intuitive allocation picture, by replacing the truth value with the probability value.
Given the following notations:
- a proposition is denoted as a lowercase letter, e.g. $p$, $q$
- the probability of a proposition $p$ is denoted as $ P(p) \in [0, 1] $, where $P(p)$ represents our belief in the truthfulness of the proposition $p$
If we enumerate all possible mutually exclusive outcomes and allocate the probability value $1$ to them. We will get similar equations as the Boolean algebra.
$$ P(p) + P(¬p) = 1 $$
The product (chain) rule:
$$ P(p∧q) = P(p) \times P(q|p) $$
Where $P(q|p)$ is called the conditional probability of $q$ given $p$.
And the sum rule:
$$ P(p∨q) = P(p) + P(q) - P(p∧q) $$
Then all the rest of the probability theory could be derived from the definitions above.
Also note that the notations above are equivalent to the Kolmogorov first and second axioms and the probability allocation is the third axiom, only expressed more intuitively but less formally.