Mathematics.

logic and set algebra

Boolean Algebra

Discrete Mathematics20 minDifficulty3 out of 10

You should know: propositional logic

Overview

Boolean algebra is a branch of algebra in which the values of the variables are the truth values true and false, usually written 1 and 0, rather than numbers. It differs from elementary algebra in its operators: instead of addition, multiplication, subtraction, and division, Boolean algebra uses the logical operators conjunction (∧, 'and'), disjunction (∨, 'or'), and negation (¬, 'not'). Boolean algebra is therefore a formal way of describing logical operations, the same way elementary algebra describes numerical operations — and it is the mathematical backbone of digital logic circuits.

Formal Definition

Definition

The core Boolean operations are ∧, ∨, and ¬ on the two-element set {0, 1}. Other connectives are definable from these three:

x→y=¬x∨yx \rightarrow y = \lnot x \lor y
Material implication
x↔y=(x∧y)∨(¬x∧¬y)x \leftrightarrow y = (x \land y) \lor (\lnot x \land \lnot y)
Biconditional (equivalence)
x⊕y=(x∨y)∧¬(x∧y)x \oplus y = (x \lor y) \land \lnot(x \land y)
Exclusive or (XOR)
x∨(y∨z)=(x∨y)∨z,x∧(y∧z)=(x∧y)∧zx \lor (y \lor z) = (x \lor y) \lor z, \quad x \land (y \land z) = (x \land y) \land z
Associativity of ∨ and ∧
x∧(y∨z)=(x∧y)∨(x∧z)x \land (y \lor z) = (x \land y) \lor (x \land z)
Distributivity of ∧ over ∨
¬(x∧y)=¬x∨¬y,¬(x∨y)=¬x∧¬y\lnot(x \land y) = \lnot x \lor \lnot y, \quad \lnot(x \lor y) = \lnot x \land \lnot y
De Morgan's laws

Worked Examples

  1. Factor out x using distributivity.

    (x∧y)∨(x∧¬y)=x∧(y∨¬y)(x \land y) \lor (x \land \lnot y) = x \land (y \lor \lnot y)

  2. y ∨ ¬y is always true (the law of excluded middle), so it acts as the identity 1 for ∧.

    x∧(y∨¬y)=x∧1=xx \land (y \lor \lnot y) = x \land 1 = x

Answer: (x ∧ y) ∨ (x ∧ ¬y) simplifies to x.

Practice Problems

Difficulty 3/10

Use De Morgan's laws to write ¬(x ∨ y) ∨ z in a form with the negation only over single variables.

Summary

  • Boolean algebra operates on truth values {0,1} using ∧ (and), ∨ (or), and ¬ (not) instead of arithmetic operators.
  • Implication, biconditional, and XOR are all definable from ∧, ∨, and ¬.
  • ∧ and ∨ are each associative and distribute over one another, mirroring — but not identical to — ordinary arithmetic.
  • De Morgan's laws let negation be pushed through ∧ and ∨, swapping one operator for the other.

References

  1. WebsiteWikipedia — Boolean algebra