1.4.3 - Boolean laws and simplification

1.4.3 - Boolean laws and simplification

A shorter Boolean expression can implement exactly the same decision with fewer operations. You will justify each transformation using a valid law, handle negated groups carefully, and check that simplification preserves every input outcome.

Equivalence and basic identities

Simplification changes the form of an expression while preserving its output for every input combination.

Boolean equivalence

Two expressions are equivalent when they give the same output for every possible input combination. The equivalence sign ≡\equiv, or the accepted alternative ↔\leftrightarrow, expresses that whole-input agreement.

An expression that works for one input is not necessarily equivalent. For example, A∨BA\lor B and A∧BA\land B agree for 00 and 11, but differ for 01 and 10.

This lesson uses ∧\land, ∨\lor and ¬\neg; Boolean dot, plus and overbar are recognised alternatives. XOR is ⊕\oplus, or OCR's underlined vee ∨‾\underline{\lor}. Do not replace OR with XOR when applying a law. A Boolean 1 is true and 0 is false, rather than an arbitrary numerical value.

Several basic identities explain why terms can disappear:

MeaningAND identityOR identity
IdentityA∧1≡AA\land1\equiv AA∨0≡AA\lor0\equiv A
Dominating valueA∧0≡0A\land0\equiv0A∨1≡1A\lor1\equiv1
Repeating a conditionA∧A≡AA\land A\equiv AA∨A≡AA\lor A\equiv A
Condition and its complementA∧¬A≡0A\land\neg A\equiv0A∨¬A≡1A\lor\neg A\equiv1

The complement identities follow from the two cases. If A=0A=0, then ¬A=1\neg A=1; if A=1A=1, then ¬A=0\neg A=0. They can never both be true, but at least one is always true. This is why A∨¬AA\lor\neg A becomes 1 rather than 0.

For example, (A∧1)∨(B∧0)≡A∨0≡A(A\land1)\lor(B\land0)\equiv A\lor0\equiv A. The variable BB has no effect on the output because its entire AND term is forced to 0. A simplification may remove a redundant input without changing the system's decision.

Commutation and association

Commutation changes the order of operands, while association changes the grouping of repeated instances of the same operator.

A∧B≡B∧A,A∨B≡B∨A.A\land B\equiv B\land A,\qquad A\lor B\equiv B\lor A. (A∧B)∧C≡A∧(B∧C),(A∨B)∨C≡A∨(B∨C).(A\land B)\land C\equiv A\land(B\land C),\qquad (A\lor B)\lor C\equiv A\lor(B\lor C).

An AND chain is true only if all its conditions are true, regardless of their order or grouping. An OR chain is true if at least one condition is true. These laws let you bring repeated or complementary conditions together so that another identity can simplify them.

For example,

(A∧B)∧¬A≡B∧(A∧¬A)≡B∧0≡0.(A\land B)\land\neg A \equiv B\land(A\land\neg A) \equiv B\land0 \equiv0.

The first step combines commutation and association to expose the complementary pair. It does not introduce a new condition or distribute NOT.

Association requires the same operator

Association applies to the same repeated operator. It does not licence changing (A∨B)∧C(A\lor B)\land C to A∨(B∧C)A\lor(B\land C). For A=1,B=0,C=0A=1,B=0,C=0, the first expression gives 0 and the second gives 1. Similarly, moving a NOT across a bracket requires a different law, rather than a rearrangement of terms.

Distribution and factoring

Distribution expands an expression across a bracket, and its reverse factors out a shared condition.

Boolean algebra has both of these distributive forms:

A∧(B∨C)≡(A∧B)∨(A∧C),A\land(B\lor C)\equiv(A\land B)\lor(A\land C), A∨(B∧C)≡(A∨B)∧(A∨C).A\lor(B\land C)\equiv(A\lor B)\land(A\lor C).

The first resembles familiar algebraic expansion. The second is also valid in Boolean logic, even though ordinary arithmetic addition does not distribute over multiplication in that way. Use the meaning of the operators, rather than importing an arithmetic rule.

Factoring often shortens a circuit. Suppose two AND gates feed OR and implement (A∧B)∨(A∧¬B)(A\land B)\lor(A\land\neg B). The common AA can be factored:

(A∧B)∨(A∧¬B)≡A∧(B∨¬B)≡A∧1≡A.(A\land B)\lor(A\land\neg B) \equiv A\land(B\lor\neg B) \equiv A\land1 \equiv A.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account