The Central Idea
Boolean algebra studies expressions built from Boolean variables and operations such as
\[ \land,\qquad \lor,\qquad \neg. \]The variables take values in the two-element set
\[ \boxed{\{F,T\}} \]or, equivalently in many digital settings,
\[ \boxed{\{0,1\}}. \]Boolean algebra provides laws that let us rewrite expressions without changing their truth behavior.
Boolean Algebra as an Algebraic Structure
Boolean algebra resembles ordinary algebra because expressions can be transformed using general laws.
However, Boolean algebra is not ordinary arithmetic.
For example,
\[ 1\lor1=1, \]not \(2\).
The symbols \(0\) and \(1\) represent Boolean states rather than unrestricted real numbers.
Common Boolean Notations
Boolean AND may be written
\[ p\land q \]or sometimes
\[ pq. \]Boolean OR may be written
\[ p\lor q \]or sometimes
\[ p+q. \]Boolean NOT may be written
\[ \neg p, \]\(p'\), or an overbar in some technical settings.
This lesson will primarily use logical notation.
The Identity Laws
Boolean identity elements leave a variable unchanged:
\[ \boxed{p\land T\equiv p} \]and
\[ \boxed{p\lor F\equiv p}. \]In \(0/1\) notation,
\[ p\land1=p, \] \[ p\lor0=p. \]Why the Identity Laws Work
AND requires both inputs to be true.
Therefore, if one input is already \(T\), the result depends entirely on \(p\):
\[ p\land T=p. \]OR requires at least one true input.
If one input is \(F\), the result again depends entirely on \(p\):
\[ p\lor F=p. \]The Domination Laws
Some constants determine the result completely:
\[ \boxed{p\lor T\equiv T} \]and
\[ \boxed{p\land F\equiv F}. \]These are sometimes called null or domination laws.
The Idempotent Laws
Repeating the same Boolean variable does not change the result:
\[ \boxed{p\lor p\equiv p} \]and
\[ \boxed{p\land p\equiv p}. \]This differs from ordinary arithmetic, where \(x+x=2x\).
The Complement Laws
A Boolean variable and its complement satisfy
\[ \boxed{p\lor\neg p\equiv T} \]and
\[ \boxed{p\land\neg p\equiv F}. \]One of \(p\) and \(\neg p\) must be true, but they cannot both be true.
The Double-Complement Law
Applying NOT twice restores the original value:
\[ \boxed{\neg\neg p\equiv p}. \]In Boolean-algebra notation, this is the involution law.
The Commutative Laws
The order of operands does not matter for AND or OR:
\[ \boxed{p\land q\equiv q\land p} \]and
\[ \boxed{p\lor q\equiv q\lor p}. \]The Associative Laws
Grouping does not matter when the same Boolean operation is repeated:
\[ \boxed{(p\land q)\land r\equiv p\land(q\land r)} \]and
\[ \boxed{(p\lor q)\lor r\equiv p\lor(q\lor r)}. \]Therefore, expressions such as
\[ p\land q\land r \]can be interpreted without ambiguity.
The Distributive Laws
AND distributes over OR:
\[ \boxed{p\land(q\lor r)\equiv(p\land q)\lor(p\land r)}. \]OR also distributes over AND:
\[ \boxed{p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)}. \]The second law is distinctive because ordinary arithmetic does not have an analogous distribution of addition over multiplication.
The Absorption Laws
Boolean algebra contains two important absorption identities:
\[ \boxed{p\lor(p\land q)\equiv p} \]and
\[ \boxed{p\land(p\lor q)\equiv p}. \]These laws eliminate redundant structure.
Why Absorption Works
Consider
\[ p\lor(p\land q). \]If \(p=T\), the entire OR expression is already true.
If \(p=F\), then
\[ p\land q=F. \]Thus the expression always has exactly the same truth value as \(p\).
De Morgan’s Laws
Negation reverses the operation inside a grouped expression:
\[ \boxed{\neg(p\land q)\equiv\neg p\lor\neg q} \]and
\[ \boxed{\neg(p\lor q)\equiv\neg p\land\neg q}. \]These identities are fundamental for simplification and conversion between Boolean forms.
De Morgan with Several Variables
The same pattern extends to longer expressions:
\[ \neg(p\land q\land r) \equiv \neg p\lor\neg q\lor\neg r \]and
\[ \neg(p\lor q\lor r) \equiv \neg p\land\neg q\land\neg r. \]Negation moves inward while AND and OR switch roles.
A Compact Law Table
| Law | AND Form | OR Form |
|---|---|---|
| Identity | \(p\land T\equiv p\) | \(p\lor F\equiv p\) |
| Domination | \(p\land F\equiv F\) | \(p\lor T\equiv T\) |
| Idempotent | \(p\land p\equiv p\) | \(p\lor p\equiv p\) |
| Complement | \(p\land\neg p\equiv F\) | \(p\lor\neg p\equiv T\) |
| Absorption | \(p\land(p\lor q)\equiv p\) | \(p\lor(p\land q)\equiv p\) |
Boolean Duality
Boolean algebra has a structural symmetry called duality.
To form the dual of an expression or identity:
- exchange AND and OR;
- exchange \(T\) and \(F\);
- leave variables and complements unchanged.
Valid Boolean identities have valid dual identities.
Example of Duality
Start with the identity law
\[ p\land T\equiv p. \]Exchange AND with OR and \(T\) with \(F\):
\[ p\lor F\equiv p. \]The two identity laws are duals.
Another Dual Pair
Start with
\[ p\land F\equiv F. \]Its dual is
\[ p\lor T\equiv T. \]Thus the domination laws form another dual pair.
Duality Does Not Mean Negation
The dual of a Boolean expression is not obtained by simply placing a NOT around it.
Duality exchanges operations and constants.
Negation changes truth behavior according to complement rules.
These are different transformations.
Simplification by Algebraic Laws
Boolean expressions can often be shortened by applying the laws one step at a time.
For example,
\[ (p\land T)\lor F \]simplifies to
\[ p\lor F \]and then to
\[ \boxed{p}. \]Example: Simplifying a Complement
Simplify
\[ (p\land\neg p)\lor q. \]Use the complement law:
\[ F\lor q. \]Use the identity law:
\[ \boxed{q}. \]Example: Simplifying an Absorption Pattern
Simplify
\[ p\lor(p\land q). \]Apply absorption:
\[ \boxed{p}. \]Example: A Less Obvious Absorption Pattern
Simplify
\[ p\land(\neg p\lor q). \]Distribute:
\[ (p\land\neg p)\lor(p\land q). \]Apply complement:
\[ F\lor(p\land q). \]Apply identity:
\[ \boxed{p\land q}. \]Example: Distribution Followed by Complement
Simplify
\[ p\lor(\neg p\land q). \]Distribute OR over AND:
\[ (p\lor\neg p)\land(p\lor q). \]Apply complement:
\[ T\land(p\lor q). \]Apply identity:
\[ \boxed{p\lor q}. \]Consensus-Type Simplification
Consider
\[ (p\land q)\lor(\neg p\land r)\lor(q\land r). \]The term
\[ q\land r \]is redundant.
Whenever \(q\land r\) is true, either \(p\) is true or \(p\) is false.
If \(p\) is true, then \(p\land q\) is true.
If \(p\) is false, then \(\neg p\land r\) is true.
Therefore,
\[ \boxed{ (p\land q)\lor(\neg p\land r)\lor(q\land r) \equiv (p\land q)\lor(\neg p\land r) }. \]This is a preview of the consensus theorem.
The Consensus Theorem
A standard Boolean identity is
\[ \boxed{ (p\land q)\lor(\neg p\land r)\lor(q\land r) \equiv (p\land q)\lor(\neg p\land r) }. \]The third term is called the consensus term.
Its information is already covered by the first two terms.
The Dual Consensus Form
By duality,
\[ \boxed{ (p\lor q)\land(\neg p\lor r)\land(q\lor r) \equiv (p\lor q)\land(\neg p\lor r) }. \]The same redundancy principle appears in conjunctive form.
Factoring Boolean Expressions
Boolean expressions can sometimes be factored using distributivity.
For example,
\[ (p\land q)\lor(p\land r) \]factors as
\[ \boxed{p\land(q\lor r)}. \]Factoring can expose structure and shorten an expression.
Boolean Factoring Is Structural
Although Boolean factoring resembles ordinary algebraic factoring, its meaning is logical.
The identity
\[ (p\land q)\lor(p\land r) \equiv p\land(q\lor r) \]follows from Boolean distributivity.
Expanding Boolean Expressions
The reverse process is expansion.
For example,
\[ p\land(q\lor r) \]expands to
\[ \boxed{(p\land q)\lor(p\land r)}. \]Expansion is useful when converting expressions into normal forms.
Using De Morgan to Remove Outer Negation
Simplify
\[ \neg(p\lor q)\lor r. \]Apply De Morgan:
\[ (\neg p\land\neg q)\lor r. \]The negation now applies only to individual variables.
Removing Double Negation
Consider
\[ \neg(\neg p\lor q). \]Apply De Morgan:
\[ \neg\neg p\land\neg q. \]Then apply double complement:
\[ \boxed{p\land\neg q}. \]Implication Inside Boolean Algebra
Although implication is not usually taken as a primitive Boolean-algebra operation, it can be represented using NOT and OR:
\[ \boxed{p\to q\equiv\neg p\lor q}. \]This lets conditional statements be manipulated with ordinary Boolean laws.
Biconditional Inside Boolean Algebra
A biconditional can be rewritten as
\[ \boxed{ p\leftrightarrow q \equiv (p\land q)\lor(\neg p\land\neg q) }. \]The expression is true exactly when the two inputs agree.
XOR Inside Boolean Algebra
Exclusive OR can be represented as
\[ \boxed{ p\oplus q \equiv (p\land\neg q)\lor(\neg p\land q) }. \]It is true exactly when the inputs differ.
NAND and NOR
NAND is
\[ \boxed{\neg(p\land q)}. \]NOR is
\[ \boxed{\neg(p\lor q)}. \]Using De Morgan,
\[ \neg(p\land q) \equiv \neg p\lor\neg q \]and
\[ \neg(p\lor q) \equiv \neg p\land\neg q. \]Functional Completeness
A collection of Boolean operations is functionally complete if every Boolean function can be expressed using only operations from that collection.
The set
\[ \{\neg,\land,\lor\} \]is functionally complete.
Remarkably, NAND alone is functionally complete, and NOR alone is also functionally complete.
Building NOT from NAND
If both NAND inputs are the same,
\[ p\uparrow p = \neg(p\land p). \]Since
\[ p\land p\equiv p, \]we obtain
\[ \boxed{p\uparrow p\equiv\neg p}. \]Thus NAND can construct NOT.
Building AND from NAND
First form
\[ p\uparrow q=\neg(p\land q). \]Then NAND that result with itself:
\[ (p\uparrow q)\uparrow(p\uparrow q). \]This negates the NAND output:
\[ \boxed{ (p\uparrow q)\uparrow(p\uparrow q) \equiv p\land q }. \]Building OR from NAND
By De Morgan,
\[ p\lor q \equiv \neg(\neg p\land\neg q). \]Since NAND can produce negation,
\[ \boxed{ (p\uparrow p)\uparrow(q\uparrow q) \equiv p\lor q }. \]NAND alone can therefore reproduce the standard Boolean operations.
Truth Tables and Algebraic Proof
Boolean identities can be verified in at least two major ways:
- compare truth tables;
- transform one side algebraically into the other.
Truth tables are exhaustive.
Algebraic transformations are often faster and reveal more structure.
Example: Verify Absorption Algebraically
Start with
\[ p\lor(p\land q). \]Use the identity
\[ p\equiv p\land T: \] \[ (p\land T)\lor(p\land q). \]Factor \(p\):
\[ p\land(T\lor q). \]Apply domination:
\[ p\land T. \]Apply identity:
\[ \boxed{p}. \]Example: Simplify a Larger Expression
Simplify
\[ (p\land q)\lor(p\land\neg q). \]Factor \(p\):
\[ p\land(q\lor\neg q). \]Apply complement:
\[ p\land T. \]Apply identity:
\[ \boxed{p}. \]Example: Simplify with De Morgan and Complement
Simplify
\[ \neg(p\lor\neg p). \]Apply the complement law inside:
\[ \neg T. \]Therefore,
\[ \boxed{F}. \]Alternatively, De Morgan gives
\[ \neg p\land\neg\neg p = \neg p\land p = F. \]Example: Simplify a CNF Expression
Simplify
\[ (p\lor q)\land(p\lor\neg q). \]Use distributivity in the form
\[ (a\lor b)\land(a\lor c) \equiv a\lor(b\land c). \]Then
\[ (p\lor q)\land(p\lor\neg q) \equiv p\lor(q\land\neg q). \]Apply complement:
\[ p\lor F. \]Apply identity:
\[ \boxed{p}. \]Example: Simplify a DNF Expression
Simplify
\[ (p\land q)\lor(p\land r). \]Factor \(p\):
\[ \boxed{p\land(q\lor r)}. \]The factored form is shorter but logically equivalent.
Minimality and Simplification
A simplified Boolean expression usually has fewer variables, literals, or operations than the original.
However, there may be several equally compact equivalent forms.
Boolean algebra provides the identities needed to search for simpler representations.
Equivalent Forms Can Serve Different Purposes
The expression
\[ p\land(q\lor r) \]is compact.
The equivalent expression
\[ (p\land q)\lor(p\land r) \]may be more useful when a disjunctive normal form is needed.
The best form depends on the task.
Boolean Algebra and Normal Forms
Boolean algebra provides the laws used to convert between normal forms.
Distribution creates expanded CNF or DNF structures.
Absorption, complement, and idempotence can remove redundant pieces.
Normalization and simplification therefore work together.
Boolean Algebra and Logic Gates
Every Boolean expression can be interpreted as a network of logical operations.
For example,
\[ (p\land q)\lor\neg r \]can be read as:
- AND \(p\) and \(q\);
- NOT \(r\);
- OR the two results.
The next lesson will translate expressions like this into circuit structure.
Common Error: Treating Boolean OR as Arithmetic Addition
In Boolean notation,
\[ 1\lor1=1. \]Ordinary arithmetic would give \(1+1=2\), but Boolean OR asks only whether at least one input is true.
Common Error: Applying Ordinary Algebra Automatically
Boolean algebra has its own identities.
For example,
\[ p\lor p=p, \]not \(2p\).
Similar-looking symbols do not imply identical algebraic rules.
Common Error: Forgetting the Dual Distributive Law
AND distributes over OR:
\[ p\land(q\lor r) \equiv (p\land q)\lor(p\land r). \]But Boolean algebra also has
\[ p\lor(q\land r) \equiv (p\lor q)\land(p\lor r). \]Common Error: Misusing De Morgan’s Laws
The incorrect form
\[ \neg(p\land q) \equiv \neg p\land\neg q \]fails because AND must switch to OR.
The correct identity is
\[ \boxed{\neg(p\land q)\equiv\neg p\lor\neg q}. \]Common Error: Stopping Before Applying Identity
Suppose simplification reaches
\[ p\land T. \]The expression can still be reduced:
\[ \boxed{p\land T\equiv p}. \]Always inspect the result for another applicable law.
Common Error: Changing Several Structures at Once
A reliable Boolean derivation should make one justified transformation at a time.
This makes errors easier to detect and each equivalence easier to verify.
A Reliable Procedure for Simplifying Boolean Expressions
- Identify the main operation and grouped subexpressions.
- Remove double negations when present.
- Apply complement, identity, domination, or idempotent laws when possible.
- Look for absorption patterns.
- Factor or distribute when doing so exposes simpler structure.
- Apply De Morgan’s laws when negations surround compound expressions.
- Repeat until no useful reduction is apparent.
- Verify by truth table when needed.
A Reliable Procedure for Proving an Identity
- Start from one side of the proposed identity.
- Apply one valid Boolean law at a time.
- Preserve parentheses and complement scope carefully.
- Continue transforming until the other side is reached.
- If algebraic transformation becomes unclear, verify with a truth table.
A Reliable Procedure for Finding a Dual
- Replace every AND with OR.
- Replace every OR with AND.
- Replace every \(T\) with \(F\).
- Replace every \(F\) with \(T\).
- Leave variables and complements unchanged.
Example: Full Simplification Workflow
Simplify
\[ (p\land q)\lor(p\land\neg q)\lor(\neg p\land q). \]Combine the first two terms:
\[ p\land(q\lor\neg q)\lor(\neg p\land q). \]Apply complement:
\[ p\land T\lor(\neg p\land q). \]Apply identity:
\[ p\lor(\neg p\land q). \]Use the derived absorption-style identity
\[ p\lor(\neg p\land q) \equiv p\lor q. \]Therefore,
\[ \boxed{ (p\land q)\lor(p\land\neg q)\lor(\neg p\land q) \equiv p\lor q }. \]Practice 1: Identity
Simplify
\[ p\land T. \]Practice 2: Domination
Simplify
\[ p\lor T. \]Practice 3: Idempotence
Simplify
\[ p\land p. \]Practice 4: Complement
Simplify
\[ p\lor\neg p. \]Practice 5: Absorption
Simplify
\[ p\land(p\lor q). \]Practice 6: De Morgan
Rewrite
\[ \neg(p\land q) \]without a negation outside parentheses.
Practice 7: Factor
Factor
\[ (p\land q)\lor(p\land r). \]Practice 8: Simplify
Simplify
\[ (p\land q)\lor(p\land\neg q). \]Practice 9: Find the Dual
Find the dual of
\[ p\land T\equiv p. \]Practice 10: Functional Completeness
Explain briefly why NAND can produce NOT.
Practice Answers
Practice 1
\[ \boxed{p\land T\equiv p}. \]Practice 2
\[ \boxed{p\lor T\equiv T}. \]Practice 3
\[ \boxed{p\land p\equiv p}. \]Practice 4
\[ \boxed{p\lor\neg p\equiv T}. \]Practice 5
\[ \boxed{p\land(p\lor q)\equiv p}. \]Practice 6
\[ \boxed{\neg p\lor\neg q}. \]Practice 7
\[ \boxed{p\land(q\lor r)}. \]Practice 8
Factor \(p\):
\[ p\land(q\lor\neg q). \]Apply complement:
\[ p\land T. \]Apply identity:
\[ \boxed{p}. \]Practice 9
Exchange AND with OR and \(T\) with \(F\):
\[ \boxed{p\lor F\equiv p}. \]Practice 10
Use the same input twice:
\[ p\uparrow p = \neg(p\land p). \]Since \(p\land p\equiv p\),
\[ \boxed{p\uparrow p\equiv\neg p}. \]What to Remember
- Boolean algebra manipulates two-valued expressions using algebraic laws.
- Identity, domination, idempotent, complement, and double-negation laws provide basic simplifications.
- AND and OR are commutative and associative.
- AND distributes over OR, and OR distributes over AND.
- Absorption removes redundant Boolean structure.
- De Morgan’s laws move negation through AND and OR while switching the operation.
- Duality exchanges AND with OR and \(T\) with \(F\).
- Equivalent Boolean expressions can be factored, expanded, or simplified without changing their truth behavior.
- NAND alone and NOR alone are functionally complete.
- Algebraic simplification and truth-table verification are complementary methods.
The central habit is to transform one justified step at a time while preserving Boolean equivalence.
Where We Go Next
Boolean algebra gives us a symbolic language for simplifying and reorganizing logical operations. Those same operations can be implemented physically as digital components.
The next lesson, Logic Gates and Circuits, translates Boolean expressions into gates, circuit diagrams, input-output behavior, and basic digital design.