Boolean algebra and logic

Thanks to Von Neumann et. al. our present day idea of computers is that of binary digital devices which perform Boolean logical operations. Such a device can simulate any computational process in principle. What remains in order to create systems which compute the results of mathematical or logical problems is the ability to combine information streams into functions which are things we want to evaluate.

Modern computers are based on the use of binary data and Boolean algebra or logic. It is straightforward to show that a simple set of linearly independent operations on bits can be used to perform simple binary arithmetic, and thus more complex calculations in combination. The commonly referred to operations in Boolean algebra are the unary (1:1) operator

NOT ${\neg}$
In	Out
1	0
0	1

and the binary (2:1) operators

AND $\;{\cap}\;$
In1	In2	Out
0	0	0
0	1	0
1	0	0
1	1	1

        

OR $\;{\cup}\;$
In1	In2	Out
0	0	0
0	1	1
1	0	1
1	1	1

        

XOR $\;{\oplus}\;$
In1	In2	Out
0	0	0
0	1	1
1	0	1
1	1	0

In digital electronics, these are simulated using multi-transistor circuit blocks.

It is easy to show that any Boolean logic operation can be constructed from the two operations $\;{\cap}\;$ ( AND ) and ${\neg}$ ( NOT). This may be seen from the following identities:

$$P \;{\cup}\;Q {\neg}({\neg}P \;{\cap}\;{\neg}Q)$$ =

$$P \rightarrow Q {\neg}P\;{\cap}\;Q$$ =

$$P \leftrightarrow Q (P\rightarrow Q) \;{\cap}\;(Q\rightarrow P)$$ =

$$P \;{\oplus}\;Q {\neg}(P \leftrightarrow Q).$$ = (5)

or, in modern programming notation

                  P | Q  =  !(!P & !Q)
                 P -> Q  =  !P & Q
                 P == Q  =  (P -> Q) & (Q -> P)
                  P ^ Q  =  ! (P == Q).

or, again, in more common notation

$$P ~{\rm\bf OR}~Q ~{\rm\bf NOT}\,(~{\rm\bf NOT}\,P ~{\rm\bf AND}~~{\rm\bf NOT}\,Q)$$ =

$$P \rightarrow Q ~{\rm\bf NOT}\,P~{\rm\bf AND}~Q$$ =

$$P ~{\rm\bf EQUALS}~Q (P\rightarrow Q) ~{\rm\bf AND}~(Q\rightarrow P)$$ =

$$P ~{\rm\bf XOR}~Q ~{\rm\bf NOT}\,(P ~{\rm\bf EQUALS}~Q).$$ = (6)

The `implication' symbol is defined by the truth table

$$0 \rightarrow 0$$ = 1

$$0 \rightarrow 1$$ = 1

$$1 \rightarrow 0$$ = 0

$$1 \rightarrow 1$$ = 1. (7)