Idempotent Laws

In discrete mathematics, the idempotent laws state that combining an element or statement with itself under certain binary operations leaves it unchanged. This property plays a central role in propositional logic, set theory, and Boolean algebra.

The term “idempotence” comes from the Latin idem (same) and potens (power), describing the idea that applying an operation repeatedly yields the same value as applying it once.

Idempotence in Propositional Logic

In propositional logic, the idempotent laws state that combining a proposition with itself using a conjunction (∧) or a disjunction (∨) yields a result logically equivalent to the original proposition. For any proposition p: 

p ∧ p ≡ p

p ∨ p ≡ p

That is, the conjunction of a proposition with itself is equivalent to the proposition; likewise, the disjunction of a proposition with itself is equivalent to the proposition. Redundancy does not alter the truth value.

Everyday examples help illustrate this concept. For conjunction, saying "it is raining and it is raining" provides no more information than simply stating "it is raining." For disjunction, the statement "I will eat pizza or I will eat pizza" presents a false choice, as it practically reduces to a single option: "I will eat pizza." 

Proof

The validity of the idempotent laws can be proved using truth tables, which allow us to verify logical equivalence by comparing the final truth values of each expression.

For the first law, p ∧ p ≡ p:

For the second law, p ∨ p ≡ p:

In both tables, the columns for the compound proposition (p ∧ p and p ∨ p) and the simple proposition (p) share identical truth values for every possible case. This match proves logical equivalence.

It is worth noting that conjunction and disjunction are the only idempotent logical connectives, as other operators do not satisfy this property. 

For instance, double negation, written as ¬(¬p) ≡ p, does produce a logical equivalence, but the result is the original proposition p, not the negated statement ¬p. In contrast, for the conditional (p → p) and the biconditional (p ↔ p), operating a proposition with itself yields a tautology (a statement that is always true), rather than the proposition p itself. 

Idempotence in Set Theory

The idempotent property also appears in set theory, specifically in the operations of union and intersection. These two fundamental operations share the characteristic that applying them to a set with itself yields the original set.

Formally, for any set A, the following equalities hold:

A ∪ A = A

A ∩ A = A

This means that the union of a set with itself adds no new elements; we simply obtain the exact same set. Similarly, the intersection of a set with itself results in the original set, as all elements are common to both operands.

Proof

To prove that A ∪ A = A, we use an element argument based on the definition of union and the idempotent law of logic:

1. By definition, x ∈ A ∪ A means x ∈ A ∨ x ∈ A.
2. Applying the idempotent law of disjunction, x ∈ A ∨ x ∈ A ⇔ x ∈ A.
3. Therefore, x ∈ A ∪ A if and only if x ∈ A, which proves that A ∪ A = A.

Similarly, for intersection:

1. By definition, x ∈ A ∩ A means x ∈ A ∧ x ∈ A.
2. Applying the idempotent law of conjunction, x ∈ A ∧ x ∈ A ⇔ x ∈ A.
3. Thus, x ∈ A ∩ A if and only if x ∈ A, proving that A ∩ A = A.

Idempotent Laws in Boolean Algebra

In Boolean algebra and digital circuit design, the idempotent laws represent the behavior of OR and AND operations using algebraic notation. For any Boolean variable A:

A + A = A (OR form)

A · A = A (AND form)

Expressed with binary values (0 and 1):

This property indicates that connecting the same digital input signal to both terminals of an AND gate or an OR gate produces an output identical to the original input signal.