Boolean Identities

The main identities associated with Boolean algebra.

Recommended Level

Beginner

Prerequisite Reading

This article assumes that you have read and are comfortable with the Boolean Basics article (which also contains a list of links to other articles in this series). If you find yourself having difficulty following the concepts or notation used here, you might review that article.

Boolean Identities- Summary

Like normal algebra, Boolean algebra has a number of useful identities. An "identity" is merely a relation that is always true, regardless of the values that any variables involved might take on. Many of these are very analogous to normal multiplication and addition, particularly when the symbols {0,1} are used for {FALSE,TRUE}. But while this can be useful, there are some identities that are different and that cause confusion for many people -- we will highlight these as we encounter them. We begin with a table summarizing these identities and then proceed to examine each of them in detail.

Boolean Identities

IDENTITY	EXPRESSION
Logical Inverse	0¯¯¯=1;1¯¯¯=0
Involution	A¯¯¯¯¯¯¯¯=A
	OR	AND
Dominance	A+1=1	A⋅0=0
Identity	A+0=A	A⋅1=A
Idempotence	A+A=A	A⋅A=A
Complementarity	A+A¯¯¯¯=A	A⋅A¯¯¯¯=A
Commutativity	A+B=B+A	A⋅B=B⋅A
Associativity	(A+B)+C=A+(B+C)	(A⋅B)⋅C=A⋅(B⋅C)
Distributivity	A+(B⋅C)=(A+B)⋅(A+C)	A⋅(B+C)=(A⋅B)+(A⋅C)
Absorption	A⋅(A+B)=A	A⋅(A+B)=A
DeMorgan's	A+B=A¯¯¯¯⋅B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯	A⋅B=A¯¯¯¯+B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Each of these identities can be proven by simply creating a fully-enumerated truth table for the expression on the left (of the equality sign, not of the table) and another for the expression on the right and showing that they produce the same result for every possible input combination. This will be done for each identity. A more elegant way is to use previously proven identities to prove subsequent ones. In general we will not do this primarily because the ordering of the table above is intended to follow a largely intuitive progression and it is not optimized for supporting a chain of Boolean proofs.
Notice that for each identity involving the OR and/or the AND operator, there is a corresponding identity in which the roles of these two operators are reversed. This is due to the "duality" of AND and OR, a topic explored in detail in a separate article.
In all of the expressions in this article we make no assumption about either the precedence or the associativity of the operators, meaning that we will rely heavily on fully parenthesized expressions. Because we will use the overbar notation for logical negation (the NOT operator), we will use the natural convention that the expression underneath the bar is evaluated and the result of that is then inverted (NOTed).

Boolean Identities- Detailed Explanations

We will now work our way through the table of identities, in order, making observations about each, usually including a "common sense" informal proof. In addition to the Boolean expressions, each identity will also be depicted graphically using standard logic schematic symbols. The symbols for NOT, OR, and AND were introduced in the Boolean Basics article. In addition to these, we will use the BUF symbol to represent a non-inverting buffer. This gate merely copies its input to its output. Furthermore, while we use {0, 1} to represent {FALSE, TRUE} in the Boolean expressions, we will use {LO, HI} to represent them in the schematic diagrams.

Notice that the NOT symbol is simply a BUF symbol followed by a bubble. The bubble represents logical inversion and is the actual NOT gate. Anytime you see a bubble attached to a gate pin, you can detach it from the pin and insert a separate NOT gate in its place without affecting the resulting logic.
Each discussion is followed by a formal proof via fully-enumerated truth tables. For most of the identities, these proofs will not contain any suprises. But they are worthwhile including because some of the less-intuitive proofs might make more sense when you can see how the logic progresses through the tables.

Logical Inverse

This identity, which is actually two separate identities, is merely the definition of logical negation applied to each of the possible Boolean values.

0¯¯¯=1

1¯¯¯=0

Proof

Since this is our first identity, our proof must be based on the fundamental definitions of the signals and the operators (which will be true of several early identities). As the only operation involved here is negation, we simply site the definition of negation and note that these identities are simply the two rows in that definition.

PROOF: Logical Negation -

0¯¯¯=1

 

0	LHS 0¯¯¯	RHS 1
0	1	1

PROOF: Logical Negation -

1¯¯¯=0

1	LHS 0¯¯¯	RHS 0
1	0	0

Involution

In mathematics, a function is said to be involutive if it is its own inverse. In normal arithmetic, the reciprocal function is involutive since the reciprocal of a reciprocal yields the original value, as does multiplying a value twice by -1. In Boolean logic, negation is an involutive function because negating a value twice returns the original value. This is analogous to the "double negative" in normal conversation.

A¯¯¯¯¯¯¯¯=A

    or   

(A′)′=A

PROOF

PROOF: Involution

A	A¯¯¯¯	(A¯¯¯¯)¯¯¯¯¯¯¯¯¯¯=A¯¯¯¯¯¯¯¯	LHS A¯¯¯¯¯¯¯¯	RHS A
0	1	0	0	0
1	0	1	1	1

Dominance

In normal multiplication, we have the property that anything multiplied by zero yields zero. In a sense, this means that zero has the ability to suppress, mask, or dominate any other value under multiplication. The dominance identity -- also known the "suppression" or "masking" identity -- is similar and merely recognizes that anything that is OR'ed with a TRUE produces a TRUE while anything AND'ed with a FALSE produces a FALSE.

A+1=1

A⋅0=0

While the second property looks the same as normal multiplication, the first property is definitely NOT the same as normal addition. This is something to keep in mind until you are proficient with Boolean algebra because it is very easy to fall back on well-entrenched habits and apply rules from normal algebra to Boolean algebra when they simply aren't valid, or fail to exploit rules that are.

PROOF

PROOF: Dominance of 1 under OR

A	1	LHS A+1	RHS 1
0	1	1	1
1	1	1	1

PROOF: Dominance of 0 under AND

A	0	LHS A⋅0	RHS 0
0	0	0	0
1	0	0	0

Note that, technically, the proofs given here only apply to the case when the first input is the free variable and the second input is the dominant value for that operation. We could prove that the identity holds with the inputs are swapped, but once we prove that both OR and AND are commutative, those proofs become trivial and uninteresting.

Identity

Just as 0 is the identity element for normal addition and 1 is the identity element for multiplication, so too are 0 (FALSE) and 1 (TRUE) the identity elements for OR and AND respectively.

A+0=A

A⋅1=A

This property, more than anything else, is why the addition symbol is used for logical OR and the multiplication symbol is used for logical AND. But it is important to remember that, in Boolean algebra, we are NOT "adding" or "multiplying" two values to when we use these operators. Using this terminology is poor form and generally frowned upon (even though it is heard quite regularly). Having said that, the terms "sum" and "product" are widely used and accepted for the results of logical OR and logical AND, respectively. So while it is poor form to talk about "adding A and B," it is acceptable to talk about "the sum of A and B"; this may seem odd and even inconsistent, but it is simply the result of a compromise that has evolved between mathematically rigorous terminology and practical common parlance -- for instance, it is easier and cleaner to speak of "the sum of products" than is "the OR of ANDs".
The identity for OR comes directly from the definition of OR when the second input is constrained to be 0, while the identity for AND comes directly from it's definition when the second input is constrained to be 1.

PROOF

The identity for OR comes directly from the definition of OR when the second input is constrained to be 0, while the identity for AND comes directly from it's definition when the second input is constrained to be 1.

PROOF: Identity under OR

A	0	LHS A+0	RHS A
0	0	0	0
1	0	1	1

PROOF: Identity under AND

A	1	LHS A⋅1	RHS A
0	1	0	0
1	1	1	1

Note that, technically, the proofs given here only apply to the case when the first input is the free variable and the second input is the identity value for that operation. We could prove that the identity holds with the inputs are swapped, but once we prove that both OR and AND are commutative, those proofs become trivial and uninteresting.

Idempotence

The term "idempotent" describes an operation that can be carried out any number of times and the effect is the same as if it had only been carried out once. If we either AND a Boolean variable with itself or OR it with itself, we get the same result as the original variable. This means that both AND and OR are idempotent. This property is expressed as

A+A=A

A⋅A=A

Notice that this is VERY different than normal arithmetic.

PROOF

The proof of idempotence for both OR and AND follows from examining the definition of each operation under the constraint that both inputs have the same value.

PROOF: Idempotence under OR

A	A	LHS A+A	RHS A
0	0	0	0
1	1	1	1

PROOF: Idempotence under AND

A	A	LHS A⋅A	RHS A
0	0	0	0
1	1	1	1

Complementarity

A 'complement' (as opposed to a 'compliment') is the opposite of something. In fact, another name for the logical inverse is the complement. When we OR or AND a Boolean value with its complement we end up with the same result regardless of the value of the variable. In the case of AND, since we know that either the variable or its complement FALSE, the logical AND of a variable with its complement will always yield FALSE since the one that is FALSE will dominate. Similarly, since we know one of them is TRUE, the logical OR of a variable with its complement will always yield TRUE because the one that is TRUE will dominate.

A+A¯¯¯¯=1

A⋅A¯¯¯¯=0

To have the property of complementarity, all that is required of a Boolean binary operator is that it be symmetric, meaning that the two rows in its defining truth table that have dissimilar inputs produce the same result. This is a surprisingly powerful identity that often plays a part in reducing, or "simplifying" Boolean expressions.

PROOF

To have the property of complementarity, all that is required of a Boolean binary operator is that it be symmetric, meaning that the two rows in its defining truth table that have dissimilar inputs produce the same result.

PROOF: Complementarity under OR

A	A¯¯¯¯	LHS A+A¯¯¯¯	RHS 1
0	1	1	1
1	0	1	1

PROOF: Complementarity under AND

A	A¯¯¯¯	LHS A⋅A¯¯¯¯	RHS 0
0	1	0	0
1	0	0	0

Note that, technically, the proofs given here only apply to the case when the first input is the uncomplemented free variable and the second input is its complement. We could prove that the identity holds with the inputs are swapped, but once we prove that both OR and AND are commutative, those proofs become trivial and uninteresting.

Commutativity

As in normal arithmetic, the order of the operands for both OR and AND do not matter making them both commutative.

A+B=B+A

A⋅B=B⋅A

This is also described by saying that AND and OR are 'symmetric' functions.
Like complementarity, all that is required for a binary Boolean operator to be commutative is for the two rows in the defining truth table having dissimilar inputs produce the same output. The corollary to this is that any binary Boolean operator that is commutative is also complementary, and vice verse.

PROOF

Like complementarity, all that is required for a binary Boolean operator to be commutative is for the two rows in the defining truth table having dissimilar inputs produce the same ouput. The corollary to this is that any binary Boolean operator that is commutative is also complementary, and vice verse.

PROOF: Cummutativity under OR

A	B	LHS A + B	RHS B + A
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

PROOF: Commutativity under AND

A	B	LHS A⋅B	RHS A⋅B
0	0	0	0
0	1	0	0
1	0	0	0
1	1	1	1

Associativity

Again, as in normal arithmetic with addition and multiplication, the order in which we apply operations when two or more of the same operator are involved does not matter.

(A+B)+C=A+(B+C)

(A⋅B)⋅C=A⋅(B⋅C)

The associativity of OR and AND is not at all obvious. It is tempting to assume that because OR and AND are commutative that they must be associative also. This is not the case however and some Boolean operators, NAND and NOR (discussed in a later article), that are commutative are not associative.

PROOF

PROOF: Associativity under OR

A	B	C	(A + B)	(B + C)	LHS (A + B) + C	RHS A + (B + C)
0	0	0	0	0	0	0
0	0	1	0	1	1	1
0	1	0	1	1	1	1
0	1	1	1	1	1	1
1	0	0	1	0	1	1
1	0	1	1	1	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

PROOF: Associativity under AND

A	B	C	(A⋅B)	(B⋅C)	LHS (A⋅B)⋅C	RHS A⋅(B⋅C)
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	0	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	1	0	0	0
1	1	1	1	1	1	1

Distributivity

In normal arithmetic we often use the property that multiplication distributes over addition and are aware that addition does not distribute over multiplication. However, in Boolean algebra, either operator distributes over the other.

A⋅(B+C)=(A⋅B)+(A⋅C)

A+(B⋅C)=(A+B)⋅(A+C)

This last property, because it goes against our engrained understanding of the rules of arithmetic, seems very unnatural and many people are unaware that it is true or actively believe that it is not true. This is almost entirely an unintended consequence of using the plus-sign and multiplication-sign from normal arithmetic and failing to remember that logical operators and arithmetic operators are simply not the same thing and that they have absolutely no relation to each other regardless of whether we use the symbols to represent them.
Both of these properties are extremely useful and, not suprisingly, many people make their work much more difficult because they aren't adept at recognizing where applying the disitributivity of OR over AND would greatly streamline things.

PROOF

PROOF: Distributivity of AND over OR

A	B	C	(B + C)	(A⋅B)	(A⋅C)	LHS A⋅(B+C)	RHS (A⋅B)+(A⋅C)
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	0	1	1	1
1	1	0	1	1	0	1	1
1	1	1	1	1	1	1	1

PROOF: Distributivity of OR over AND

A	B	C	(B⋅C)	(A+B)	(A+C)	LHS A+(B⋅C)	RHS (A+B)⋅(A+C)
0	0	0	0	0	0	0	0
0	0	1	0	0	1	0	0
0	1	0	0	1	0	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

Absorption

One of the more useful Boolean identities is absorption because it allows use to remove unneeded variables. But, in addition, it also allows us to introduce variables that then frequently allow us to make even greater simplifications.

A+(A⋅B)=A

A⋅(A+B)=A

Informally, these identities make sense by considering the possible options. In the first case, if A is FALSE, then the entire expression is FALSE while if A is TRUE then then (A + B) is TRUE regardless of the value of B and the expression overall is TRUE. Thus, in either case, the overall expression is equal to the value of A alone. In the second case this is even more obvious. If A is TRUE then the overall expression is TRUE while if A is FALSE the second term is FALSE regardless of the value of B and the overall expression is FALSE. Again, the overall expression is equal to the value of A alone.
These two identities tend to be ones that are difficult for people to recall, therefore it is useful to see an algebraic proof because the manipulations involved are often easier for people to see and apply than the identities themselves.
In the first identity, we can either "factor out" the A using the distributive property of AND over OR or we can just distribute the OR over the AND. Let's use the first approach as this is the one that is usually easier to see in practice.

The second identity is actually more intuitive as see by first distributing the A using the distributive property of AND over OR and then, after applying idempotence, factoring it back out.

PROOF

PROOF: Absorption under OR

A	B	(A+B)	LHS A⋅(A+B)	RHS A
0	0	0	0	0
0	1	1	1	0
1	0	1	1	1
1	1	1	1	1

PROOF: Absorption under AND

A	B	(A⋅B)	LHS A+(A⋅B)	RHS A
0	0	0	0	0
0	1	0	0	0
1	0	0	1	1
1	1	1	1	1

With the previously proven identities, the absorption identities can be proven algebraically in very short order.

The above prove actually contains the proof for the absorption identity under AND beginning with the second line.

DeMorgan's

DeMorgan's identities, better known as DeMorgan's Theorems, are extremely powerful and heavily used properties of Boolean logic. In essence, they say that and OR gate can be swapped with an AND gate (and vice-versa) without changing the logic function being implemented provided that ALL of the inputs and outputs to the gate are inverted as well.

A+B=A¯¯¯¯⋅B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

A⋅B=A¯¯¯¯+B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Recalling that a bubble on either an input or an output of a gate represents logical inversion, DeMorgan's Theorems can be captured very compactly as follows:

 

PROOF

PROOF: DeMorgan's OR to AND

A	B	A + B	A¯¯¯¯	B¯¯¯¯	A¯¯¯¯⋅B¯¯¯¯	LHS A+B	RHS A¯¯¯¯⋅B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
0	0	0	1	1	1	0	0
0	1	1	1	0	0	1	1
1	0	1	0	1	0	1	1
1	1	1	0	0	0	1	1

PROOF: DeMorgan's AND to OR

A	B	A⋅B	A¯¯¯¯	B¯¯¯¯	A¯¯¯¯+B¯¯¯¯	LHS A⋅B	RHS A¯¯¯¯+B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
0	0	0	1	1	1	0	0
0	1	0	1	0	1	0	0
1	0	0	0	1	1	0	0
1	1	1	0	0	0	1	1

Conclusion

Armed with the identities presented here, you are in a position to manipulate Boolean logic expressions and logic diagrams. However, these identities are merely the most fundamental of tools available to you as a logic designer. To become truly proficient at the art, you must also learn some of the many powerful analysis and design techniques that are based upon these fundamentals.