Content

Boolean Algebra Again?

There has always been a hint in the air that what we have been doing with propositions mirrors what we did with Boolean algebras. Let's see what evidence we have so far on this connection.

• Propositional logic is based on 0 and 1
• There are operations $p + q$, $pq$ and $p'$
• $p + p' = 1; (p')' = p; (pq)'= p'+ q'; $and $(p + q)'= p'q'$;

All of these appear in Boolean algebra. To be sure that we have a Boolean algebra all we have to do is to make sure that the axioms of Boolean algebra hold for propositions (page 16). Let's look at a few for a start.

• Axiom 1

  $B$ contains at least two elements. Propositional logic contains at least true and false. These hover in the background just as on and off do for switching circuits.

• Axiom 2

  $B$ is closed under + and $\times$. That is for all $x$ and $y$ in $B, x + y$ and $x \times y$ are in $B$. For propositions $p$ and $q$, $p + q$ and $ pq$ are both propositions.

• Axiom 3

  + and $ \times$ are commutative. That is for all $x$ and $y$ in $B, x + y = y + x$ and $x \times y = y \times x$. So we have to show that $p + q = q + p$ and $pq = qp$ are tautologies. We do the first in Table 9.

Table 9: Towards a proof of commutativity

$p$	$q$	$p+q$	$p+q$
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

From here we can see that $(p + q) \to (q + p) $ and $(q + p) \to(p + q)$. So + (either or) in propositional logic are the same.

Next page - Content - Gates