Boolean Algebra
Of course, one of the major goals of George Boole’s work was not only to create a system of logic that looked like math, but also to be able to apply some of the same techniques from math within that system. Boolean Algebra is a form of algebra that can be done on boolean expressions, and it contains many of the same laws and operations that we’ve already learned from algebra.
Boolean Expressions
A Boolean expression is any expression that results in a Boolean value. They consist of the values True and False, sometimes denoted as
$ T $ and
$ F $, literal values, and variables which are usually lower-case letters, combined using the operations discussed on the previous page. Here are a few examples:
$$ T \land x $$ $$ (\neg x \land y) \oplus z $$ $$ (5 < x) \land (y > 8) $$
Laws of Boolean Algebra
Boolean algebra contains many of the same laws found in algebra. Here is a table listing some of these laws with an example for each. If the law does not list a specific operation, then in general it will work for all operations.
| Name | Example |
|---|---|
| Associative | $ x \land (y \land z) \iff (x \land y) \land z $ |
| Commutative | $ x \land y \iff y \land x $ |
| Idempotence | $ x \land x \iff x $ |
| Distributive $ \land $ over $ \lor $ | $ x \land (y \lor z) \iff (x \land y) \lor (x \land z) $ |
| Distributive $ \lor $ over $ \land $ | $ x \lor (y \land z) \iff (x \lor y) \land (x \lor z) $ |
| Identity $ \land $ | $ x \land T \iff x $ |
| Identity $ \lor $ | $ x \lor F \iff x $ |
| Eliminate $ \land $ | $ x \land F \iff F $ |
| Eliminate $ \lor $ | $ x \lor T \iff T $ |
| Complement $ \land $ | $ x \land \neg x \iff F $ |
| Complement $ \lor $ | $ x \lor \neg x \iff T $ |
| Double Negative | $ \neg(\neg x) \iff x $ |
| Or Absorption | $ x \lor (x \land y) \iff x $ |
| And Absorption | $ x \land (x \lor y) \iff x $ |
De Morgan’s Laws
YouTube Video
There is one rule, not listed above, where Boolean Algebra differs greatly from other forms of algebra. That is how it deals with the negation, or inverse, of an entire statement. For this, we refer to the work of Augustus De Morgan, pictured above. De Morgan was expanding upon the work of George Boole, and published some additional laws for Boolean Algebra, which we collectively refer to as De Morgan’s Laws.
In Algebra, when we negate an entire statement, we must change the signs of each number in the statement. Consider the example below:
$$ -(x + y) \iff -x + -y $$However, in Boolean Algebra, the same rules does not quite work:
$$ \neg(x \land y) \neq (\neg x) \land (\neg y) $$For example, if we assign the value True to
$ x $ and False to
$ y $, we would be able to reduce the expression in this way:
$$ \neg(x \land y) \neq (\neg x) \land (\neg y) $$ $$ \neg(T \land F) \neq (\neg T) \land (\neg F) $$ $$ \neg(F) \neq F \land T $$ $$ T \neq F $$
As we can see, the two statements are not equal. Instead, De Morgan’s Laws tell us that we must also invert the operation, changing $ \land $ to $ \lor $ and vice-versa. Let’s look at a corrected version of the above example:
$$ \neg(x \land y) \iff (\neg x) \lor (\neg y) $$ $$ \neg(T \land F) \iff (\neg T) \lor (\neg F) $$ $$ \neg(F) \iff (F) \lor (T) $$ $$ T \iff T $$
So, we must add the following two laws to our table above:
| Name | Example |
|---|---|
| De Morgan’s Law $ \land $ | $ \neg(x \land y) \iff (\neg x) \lor (\neg y) $ |
| De Morgan’s Law $ \lor $ | $ \neg(x \lor y) \iff (\neg x) \land (\neg y) $ |
That gives us a full suite of laws we can use when working in Boolean algebra.
We use DeMorgan’s all the time. When we say x is between 1 and 10, we can state that as either $ x \geq 1 \land x \leq 10 $ or $ \neg(x < 1 \lor x > 10) $. DeMorgan’s law provides the mathematical proof of this.
-
File:De Morgan Augustus.jpg. (2018, January 1). Wikimedia Commons, the free media repository. Retrieved 19:51, January 10, 2019 from https://commons.wikimedia.org/w/index.php?title=File:De_Morgan_Augustus.jpg&oldid=275794962. ↩︎