## 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.

Questions

1. Prove that $pq = qp$.
2. Prove that the remaining axioms are also true.

Next page - Content - Gates