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

OperationNotationReadRule
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.

0000
0110
1010
1111
01
10

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.

ABA·BABA+BAA’ANDORNOT

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

0000000
0110001
1001101
1100011

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
P1Closure
P2Identity element
P3Commutativity
P4Distributivity
P5Complement
P6At 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

00000000
00100010
01000100
01111111
10001111
10101111
11001111
11111111

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

  1. Parentheses
  2. NOT (complement)
  3. AND
  4. 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:

StepJustification
(P2)
Distributive (P4)
(OR)
P2

Example – Proof of T6:

StepJustification
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

00011011
01100011
10100011
11100100

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 –

StepJustification
Distributive
Distributive
Associative + distributive

Exercise – Consensus:

StepJustification
Distributive
Commutative + distributive
,

Idea: the term is “covered” by (when ) and by (when ), so it is redundant.

Exercise –

StepJustification
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:

  1. Swap AND ↔ OR (keep the grouping — add parentheses!).
  2. 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

  1. Algebraic expression — many possible.
  2. Truth table — unique for a given function.
  3. Circuit diagram (schematic) — many possible.

Example –

0000
0011
0100
0110
1001
1011
1101
1111

XYZF = X + Y’Z

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).