Mathwords logoReference LibraryMathwords

Boolean Logic

Boolean logic is a type of algebra where every variable is either True or False (often written as 1 or 0). It uses operations like AND, OR, and NOT to combine or modify these values, and it forms the foundation of how computers make decisions.

Boolean logic (also called Boolean algebra) is an algebraic system defined over the set {0,1}\{0, 1\}, where 0 represents False and 1 represents True. The three fundamental operations are conjunction (AND, written ∧\wedge), disjunction (OR, written ∨\vee), and negation (NOT, written ¬\neg). These operations obey specific laws—such as commutativity, associativity, distributivity, and De Morgan's laws—that govern how Boolean expressions can be simplified and evaluated.

Key Formula

\neg(A \wedge B) = (\neg A) \vee (\neg B)$$ $$\neg(A \vee B) = (\neg A) \wedge (\neg B)
Where:
  • A,BA, B = Boolean variables, each either True (1) or False (0)
  • ∧∧ = AND — result is True only when both inputs are True
  • ∨∨ = OR — result is True when at least one input is True
  • ¬¬ = NOT — flips True to False, or False to True

Worked Example

Problem: Given A = True and B = False, evaluate the expression ¬(A ∧ B) and verify it equals (¬A) ∨ (¬B) using De Morgan's first law.
Step 1: Evaluate the inner expression A ∧ B (A AND B). Since A is True and B is False, the AND of these is False.
A∧B=True∧False=FalseA \wedge B = \text{True} \wedge \text{False} = \text{False}
Step 2: Apply NOT to the result. The negation of False is True.
¬(A∧B)=¬(False)=True\neg(A \wedge B) = \neg(\text{False}) = \text{True}
Step 3: Now evaluate the right side of De Morgan's law. Find ¬A and ¬B separately.
¬A=False,¬B=True\neg A = \text{False}, \quad \neg B = \text{True}
Step 4: Combine with OR. Since at least one value is True, the result is True.
(¬A)∨(¬B)=False∨True=True(\neg A) \vee (\neg B) = \text{False} \vee \text{True} = \text{True}
Answer: Both sides give True, confirming De Morgan's law: ¬(A ∧ B) = (¬A) ∨ (¬B).

Why It Matters

Every digital circuit in a computer—from processors to memory—is built from Boolean logic gates. When you write an if-statement in code, such as `if (age >= 16 AND hasPermit)`, you are using Boolean logic to control which instructions run. Understanding Boolean algebra also helps in database queries, search engines, and designing efficient algorithms.

Common Mistakes

Mistake: Confusing AND with OR. Students sometimes think A AND B is True when at least one is True.
Correction: AND requires both inputs to be True. If you want "at least one," that's OR. A quick truth table can help you check.
Mistake: Applying De Morgan's laws incorrectly by negating the inputs but forgetting to switch the operator.
Correction: De Morgan's laws require two changes: negate each variable AND swap ∧ with ∨ (or vice versa). For example, ¬(A ∧ B) becomes (¬A) ∨ (¬B), not (¬A) ∧ (¬B).

Related Terms