1. Binary Logic
Definition – Binary Logic and Logic Variables
Binary logic works with variables that take exactly two discrete values, combined by operations that have a logical meaning.
- Two logic states: ≡ False / True ≡ Off / On.
- A logic variable is always either 0 or 1 and is named by a letter ().
Definition – The Three Basic Operations
| Operation | Notation | Read | Rule |
|---|---|---|---|
| AND | ”C equals A AND B” | 1 only if both inputs are 1 | |
| OR | ”D equals A OR B” | 1 if at least one input is 1 | |
| NOT | , , | “NOT A” | inverts: , |
(The dot for AND is usually omitted.)
Definition – Truth Table
A truth table lists every combination of the input variables together with the output. variables ⇒ rows.
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
| 0 | 1 |
| 1 | 0 |
Binary Logic vs. Binary Arithmetic
- An arithmetic variable is a number with possibly many digits: (“one plus one is two”).
- A logic variable is a single 0 or 1: (“one OR one is one”).
⚠️ The ”+” sign means OR in Boolean expressions. — there is no carry in logic.
Logic Gates
Logic gates are electronic circuits that take one or more input signals and produce an output signal implementing a logic operation.
Physically, voltages are analog (e.g. anywhere in 0 – 3 V), but a digital circuit interprets them as one of two levels: logic 1 (e.g. ≈ 3 V) or logic 0 (e.g. ≈ 0 V). Each level has an acceptable range; the region between them is only crossed during a transition.
2. Boolean Algebra – Motivation
Circuit cost matters. Finding a simpler but equivalent expression means fewer gates and fewer gate inputs, which cuts cost. The mathematical tool for this is Boolean algebra.
Example – Simplifying
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
The truth table is that of OR. Algebraically:
Four AND gates + one 4-input OR become a single 2-input OR gate.
3. Postulates of Boolean Algebra (Huntington, 1904)
History: George Boole (1854) created the algebra; Claude Shannon (1938) introduced the two-valued switching algebra for bistable electrical switching circuits; E. V. Huntington (1904) gave the formal postulates used here.
Definition – Boolean Algebra
A set with two binary operators and satisfying the following postulates. Here .
| # | Postulate | (a) for | (b) for |
|---|---|---|---|
| P1 | Closure | ||
| P2 | Identity element | ||
| P3 | Commutativity | ||
| P4 | Distributivity | ||
| P5 | Complement | ||
| P6 | At least two distinct elements |
⚠️ P4(a), , has no equivalent in ordinary algebra — OR distributes over AND. It is very useful for factoring.
Example – Verifying P4(a) by Truth Table
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Columns 5 and 8 are identical ✓.
This two-valued algebra is exactly the binary logic of §1 (AND, OR, NOT); engineers call it switching algebra.
4. Basic Theorems
Principle – Duality
Every equality derivable from the postulates stays valid if you swap OR ↔ AND and 0 ↔ 1. That is why postulates and theorems come in pairs: each one is the dual of the other.
⚠️ Duality swaps operators and constants only — do not complement the variables. (Complementing them too is the procedure for the complement of a function, §6.)
Proof Method – Perfect Induction
With few variables, any theorem can be proven by checking every case (a truth table).
Theorem Table
| Name | (a) | (b) — dual |
|---|---|---|
| P2 – Identity | ||
| P5 – Complement | ||
| T1 – Idempotence | ||
| T2 – Absorbing elements | ||
| T3 – Involution | ||
| P3 – Commutativity | ||
| T4 – Associativity | ||
| P4 – Distributivity | ||
| T5 – De Morgan | ||
| T6 – Absorption | ||
| T7 – Consensus | ||
| T8 – Minimization (adjacency) | ||
| T9 – Simplification |
Operator Precedence
- Parentheses
- NOT (complement)
- AND
- OR
Put OR sub-expressions in parentheses when they are ANDed: .
⚠️ means , but complements the whole product. The prime binds tighter than AND.
Example – Proof of T1:
| Step | Justification |
|---|---|
| (P2) | |
| Distributive (P4) | |
| (OR) | |
| P2 |
Example – Proof of T6:
| Step | Justification |
|---|---|
| P2 | |
| P4 | |
| (T2) | |
| P2 |
Example – Duality in Action (T8)
Prove : .
Its dual then holds automatically — no new proof needed.
Theorem – De Morgan’s Laws
Proof by Truth Table
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
Generalization to Variables
Proof (induction): true for . Assume it for . Then
The second law follows by duality.
5. Algebraic Proofs (Exercises from the Slides)
Exercise –
| Step | Justification |
|---|---|
| Distributive | |
| Distributive | |
| Associative + distributive | |
Exercise – Consensus:
| Step | Justification |
|---|---|
| Distributive | |
| Commutative + distributive | |
| , |
Idea: the term is “covered” by (when ) and by (when ), so it is redundant.
Exercise –
| Step | Justification |
|---|---|
| De Morgan | |
| Commutative + distributive | |
| , commutative |
Exercise –
(This is — a variable ANDed with its complement, by De Morgan.)
6. Complement of a Boolean Expression
Method
Either apply De Morgan’s laws repeatedly, or in one step:
- Swap AND ↔ OR (keep the grouping — add parentheses!).
- Complement every literal and every constant.
Example –
Example –
⚠️ Keep the original structure: in , the OR is the outermost operation, so in it becomes the outermost AND . Forgetting parentheses is the most common mistake here.
7. Boolean Functions
Definition – Boolean Function
An -variable Boolean function maps each input combination to 0 or 1:
The inputs are independent variables with combinations. A logic gate implements one operation; a logic circuit implements a whole function.
Three Representations
- Algebraic expression — many possible.
- Truth table — unique for a given function.
- Circuit diagram (schematic) — many possible.
Example –
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Manipulating the expression with Boolean algebra can reduce the number of gates and gate inputs — and therefore the cost — while keeping the same truth table.
Exercises: solved in the slides — prove ; ; ; (§5).