Boolean Algebra in a Nutshell

7 min readMay 29, 2018

Introduction

The usual approach to teaching logic is to start with Aristotelian logic. In today’s digital world, I think a more natural starting point for the topic is Boolean algebra. Not only does it flow more naturally into more modern logics such as propositional and first-order logic, it is also invaluable to both the computer programmer and computer engineer.

Let P be a proposition, for instance, “Roses are red,” “The sky is blue,” or “All dogs are mammals.” As such, P will take on a truth value. In Boolean logic, it may take on only one of two values: that is, it is either true or false, 0 or 1.

The purpose of Boolean algebra is to form conjunctive expressions with one or more of these propositions. On the basis of the truth values of the individual propositions, the truth of the entire expression may be evaluated.

Two of the most common conjunctions used in English to unite two or more statements (propositions) are AND and OR, for instance:

Roses are red AND the sky is blue.

These conjunctions are also used in Boolean logic as operators between two propositions, although OR is somewhat different than how it is used in English.

The two symbols for AND and OR are ˄ and ˅, respectively. Suppose we have two propositions, P and Q. We can use these operators to unite them, thereby turning them into a new proposition:

P ˄ Q

which is read, “P AND Q’’. Another useful operator is the NOT or negation operator, ¬. This is a unary rather than a binary operator, hence operates on only one argument:

¬P

An interesting feature of Boolean logic, is that unlike in older forms of logic, such as Aristotelian logic, the entire content of an elementary proposition, such as P, above, is abstracted away, leaving only the binary truth value.

Truth tables

As mentioned in the previous section, combining one or more propositions with an operator creates a new proposition. How do we determine the truth value of this new proposition? One way is using a truth table. A truth table tabulates the truth value of the whole expression for every possible truth value of each of the constituent propositions.

Here is the truth table for the AND operator:

X  Y  X AND Y0  0     0
0  1     0
1  0     0
1  1     1

Note that the logical OR is different from the English ‘or’. In English speech, ‘or’ is the equivalent to the exclusive OR (XOR) which will be discussed in next section.

X  Y  X OR Y0  0   0
0  1   1
1  0   1
1  1   1

NOT is logical negation:

X  NOT X0    1
1    0

Gates and logic circuits

Any Boolean expression can be written as a logical circuit network using gates. Table 2 lists the gates and their equivalent Boolean operations.

Consider the following pair of expressions:

( A ˄ B ˄ Cin ) ˅ { ( A ˅ B ˅ Cin ) ˄ ¬[ ( A ˄ B) ˅ ( B ˄ Cin ) ˅ ( A ˄ Cin ) ] }
( A ˄ B) ˅ ( B ˄ Cin ) ˅ ( A ˄ Cin )

This is a binary adder and the equivalent logic circuit is shown in the Figure. The first expression is the sum (S) and the second is the carry bit (Cout). Note how the circuit allows repeated expressions to be re-used without needing multiple versions. A set of adders lined up in series with each “carry out” bit (Cout) routed to the next “carry in” bit (Cin) can be used to add multiple digit binary numbers.

Tautologies and logical implication

A tautology is an expression that is always true. Consider for instance:

P ˅ ¬P

Now, consider these two new operators: logical implication or if-then (→)
and if-and-only-if ( ↔ ).

If X then Y (X → Y ) is defined:

X  Y  X -> Y0  0    0
0  1    1
1  0    1
1  1    1

This is equivalent to ¬X ˅ Y . To define if-and-only-if, we first define the exclusive OR or XOR which is as follows:

X  Y  X XOR Y0  0    0
0  1    1
1  0    1
1  1    0

If-and-only-if, ↔, is simply a negated XOR ( ¬(X XOR Y) )

Now consider two equivalent expressions, for instance X → Y and ¬X ˅ Y , above. We can write:

(X → Y ) ↔ (¬X ˅ Y )

This expression is a tautology It also encapsulates a rule-of-inference, that is you can substitute the expression on the left for the one on the right and vice versa. For the one way case, where you can substitute the expression on the left for the one on the right, but not the other way around, we use if-then. For example:

(X ↔ Y ) → (X → Y )

Boolean logic and computational complexity

Boolean algebra is important in computational complexity theory. Satisfying a Boolean expression is a prototypical NP-complete problem. The worst-case running time to find a set of inputs that returns a value of 1 increases exponentially with the number of inputs. Moreover, other NP problems are equivalent to this problem and all such equivalent problems are “NP-complete”.

Note, however, that NP does not mean “non-polynomial”, but rather,
“non-deterministic polynomial”. In other words, an NP problem will always run in polynomial time on a non-deterministic computer. A non-deterministic computer is a theoretical construct such that every time it encounters a branch, the computer takes both simultaneously, so it has the property of always finding the optimal path in any given algorithm.

The most discussed NP-complete problem is the travelling salesman problem, which is as follows: given a set of points, what is the shortest path that passes through all of them? Note that in this context, it must be formulated as a decision problem: that is, given a set of points and a distance threshold, find a path that is less than the threshold. Presumably, one could design a network that would accurately model any given travelling salement problem.

While any potential solution can be verified in polynomial time — the running time is directly proportional to the size of the network — finding a solution can currently only be achieved in NP time — the worst-case running time is proportional to the exponent of the size. It is currently an unsolved problem whether algorithms exist that can find a solution to NP-complete problems in polynomial time.

The most obvious way of testing a Boolean expression is by trying different combinations of inputs, but this is not the only way. It is also possible to reduce the expression using tautologies of the type discussed in the previous section to certain forms that make the non-zero outputs immediately apparent. Consider the following truth table, for example:

A  B  C  Output0  0  0    0
0  0  1    0
0  1  0    0
0  1  1    1
1  0  0    0
1  0  1    0
1  1  0    1
1  1  1    0

The following expression will generate this truth table:

(¬A ˄ B ˄ C) ˅ (A ˄ B ˄ ¬C)

Exercises

A.

Derive the truth tables for NOR and NAND.
Write all the gates and operators in terms of NOT and NOR.
Write all the gates and operators in terms of NOT and NAND

B.

Derive the truth table for the binary adder.
See if you can come up with your own formulation for the adder. In particular, try to minimize the number of gates. The example has a total of nine (9) gates. Can you invent an adder that needs fewer?

C.

Prove the following tautologies:

¬(A ˄ B) ↔ (¬A ˄ ¬B)
¬(A ˄ B) ↔ (¬A ˄ ¬B)
[A ˄ (B ˅ C)] ↔ [(A ˄ B) ˅ (A ˄ C)]
[A ˅ (B ˄ C) ] ↔ [(A ˅ B) ˄ (A ˅ C)]
[(A → B) ˄ (B → A) ] ↔ (A ↔ B)

D.

Find three Boolean expressions with at least three propositions in programs you’ve written. If you haven’t written any programs, find them in one or more programs from the internet. (Hint: the logic that decides an if-then or other control structure is Boolean.)
Using the tautologies, above, transform the Boolean expressions into the form described at the end of the last section.

Conclusion

The basis of all of math and science is logic. It is widely acknowledged that computers can solve just about any problem we can throw at them, so much so that humans may soon be obsolete. The basis of the logic inside of a computer is that created by Boole in 1847. Any serious student of math, physics, computer science or any other technical subject should know it inside and out.