What is idempotence theorem for a boolean expression?

Idempotency is a property that produces the same results when repeatedly applied to a value. In mathematical terms, this property can be expressed as follows:

where $f$ denotes the operation and $x$ is the value being operated upon.

Idempotence theorem in boolean algebra

The idempotence theorem in boolean algebra states that if a boolean expression is operated with itself, the resulting expression will be equivalent to the original expression. There are following two boolean operations, which are idempotent:

• $\textbf{OR}$ operation: This operation is denoted by $+$ and yields true ($1$) if one of its input values is true ($1$). Otherwise, it returns false (0). Following is the truth table for the $OR$ operation between two variables:

We can see in the above table that if $A$ and $B$ are similar, they will output the same value.

• $\textbf{AND}$ operation: This operation is denoted by $.$ and it yields true ($1$), only if all of its input values are true ($1$). Following is the truth table for $AND$ operation between two variables:

We can see in above table that if $A$ and $B$ both are similar, they output the same value.

Hence, mathematically:

and

Advantage of idempotence theorem

The idempotence theorem helps simplify extensive and complex boolean functions, reducing the cost and time complexity of the hardware implementation reliant on those functions.

Consider the following boolean expression:

If we are to make a circuit from it, seven logic gates (three $AND$ gates, two $OR$ gates, and two $NOT$ gates) will be used, which could be a pretty expensive solution. The idempotence theorem helps optimize the above circuit design and potentially save the cost as follows:

Since $OR$ is an idempotent operation, we can repeat a term:

Rearranging the terms:

Putting the common terms aside:

The negation theorem states that the $OR$ operation of any expression with its complement always returns true ($1$). Hence:

Since $1$ is the identity for $AND$ operation, the above expression would become:

This simplified expression would require only one logic gate, thereby reducing the overall cost of the circuit implementation. In this way, the idempotence theorem helps optimize the circuit design and potentially save costs.

Learn about the idempotence theorm's application in computer networking.