Boolean Algebra – Hybrid-Learning Lecture (Topic 2)

Overview of Boolean Algebra

• Boolean Algebra (a.k.a. switching or logical algebra) is a mathematical system that works exclusively with two symbols: $0$ and $1$.
• Widely used for analysing electronic, optical and other switching circuits.
• Three fundamental operations:
  • Complement (NOT / negation)
  • Boolean Sum (OR / +)
  • Boolean Product (AND / ·)

Fundamental Elements & Notation

• Symbols allowed: $0,1$ only.
• Complement is written with a bar or over-line: $\overline{A}$.
  • $\overline{0}=1$
  • $\overline{1}=0$
• Alternative symbols you may encounter:
  • $+$ for OR
  • “blank” or $\cdot$ or bracket adjacency for AND
  • Small output-circle on gate diagrams indicates “invert/complement.”

Core Operations & Their Truth Tables

• Boolean Sum (OR):
  • $1+1=1$
  • $1+0=1$
  • $0+1=1$
  • $0+0=0$
• Boolean Product (AND):
  • $1\cdot1=1$
  • $1\cdot0=0$
  • $0\cdot1=0$
  • $0\cdot0=0$
• Complement rules already given above.

Example 1 – Proving the Distributive Law $X(Y+Z)=XY+XZ$

• Variables involved: $X, Y, Z\rightarrow 3$ variables $\Rightarrow 2^3=8$ possible input rows.
• Column plan for truth-table: $X, Y, Z, (Y+Z), X(Y+Z), XY, XZ, XY+XZ$.
• Row pattern (1-2-4 rule):
  • $X$: four $1$s then four $0$s
  • $Y$: two $1$s, two $0$s repeating
  • $Z$: alternate $1,0$
• Fill table step-by-step (extract reproduced figures):
  • $Y+Z$ column → $1,1,1,0,1,1,1,0$
  • $X(Y+Z)$ produced by ANDing $X$ with $Y+Z$ → $1,1,1,0,0,0,0,0$
  • $XY$ → $1,1,0,0,0,0,0,0$
  • $XZ$ → $1,0,1,0,0,0,0,0$
  • $XY+XZ$ (OR of previous two) → $1,1,1,0,0,0,0,0$
• Observation: The final two columns are identical, therefore distributive law holds.

Example 2 – Evaluating $XY + \overline{Z}$

• Again $X,Y,Z$ → $8$ rows.
• Compute $XY$ first, then complement of $Z$, finally OR them:
  • Resulting final column in lecture: $1,1,0,1,0,1,0,1$ (pattern $11010101$).
• Note: Instructor emphasised that only $0$ and $1$ ever appear in any intermediate or final column.

Translating Classical Logic to Boolean Form

• Truth ($T$) → $1$; False ($F$) → $0$.
• Conjunction ($\wedge$) → AND; Disjunction ($\vee$) → OR; Negation ($\lnot$) → Complement.
• Example from class:
  $(T \wedge T) \vee \lnot F$
  becomes
  $(1\cdot1) + \overline{0} = 1 + 1 = 1$.

Logic Gates & Their Boolean Behaviour

• NOT (Inverter) / “small circle”: $Y=\overline{A}$. Truth table: $0\rightarrow1,\;1\rightarrow0$.
• AND gate: $Y=A\cdot B$ (standard).
• OR gate: $Y=A+B$.
• NOR gate: OR followed by inversion. If input $A$ enters the bubble, output $\overline{A+B}$; single-input NOR behaves like simple NOT.
• NAND gate: AND followed by inversion. Truth table excerpt:
  • $0\cdot0=0 \Rightarrow \overline{0}=1$
  • $0\cdot1=0 \Rightarrow \overline{0}=1$
  • $1\cdot0=0 \Rightarrow \overline{0}=1$
  • $1\cdot1=1 \Rightarrow \overline{1}=0$
• NOT-OR (NOR) and NOT-AND (NAND) share rule: compute normal output, then complement.
• Exclusive OR (XOR): Outputs $1$ if and only if inputs differ.
  • Law emphasised: “Same truth values $\Rightarrow$ XOR gives $0$.”

Principle of Duality

• To obtain the dual of a Boolean expression:
  • Swap every $+$ (OR) with $\cdot$ (AND).
  • Swap every $\cdot$ with $+$.
  • Replace every $0$ with $1$ and every $1$ with $0$.
  • Variable symbols remain unchanged.

Worked Duality Examples from Lecture

1. $Y+Z \;\Rightarrow\; Y\cdot Z$ (only operator swapped).
2. $Z\cdot0 \;\Rightarrow\; Z+1$ (operator AND→OR, constant $0→1$).
3. $X\,(Y+0)$
   • Bracket signifies multiplication, so BOTH operator changes apply:
   $X(Y+0) \;\Rightarrow\; X + Y\cdot1$.
4. (Instructor’s spoken but ambiguous) “Y + 0 becomes 1” – flagged as a remark from the video; algebraically, strict dual of $Y+0$ should be $Y\cdot1$, but transcript claims it collapses to $1$.

Practical / Ethical Notes & Miscellaneous Remarks

• Instructor repeatedly stresses the binary nature: “Only two numbers are permitted—zeros and ones.”
• Truth-table construction tip: use the $1,2,4,8$ (powers of 2) counting pattern for columns when more than one variable is present.
• Real-world relevance: These algebraic laws underpin the design of digital circuits, optical switch networks, and logical control systems.
• Homework prompt (from video): Prepare and submit additional dual-form exercises for lecturer review.

Quick Reference – Identities & Laws Mentioned

• Complement: $\overline{\overline{A}} = A$ (double negation)
• Domination: $A + 1 = 1,\; A\cdot0 = 0$
• Identity: $A + 0 = A,\; A\cdot1 = A$
• Distributive: $A(B+C)=AB+AC$ and (dual) $A+(BC)=(A+B)(A+C)$
• De Morgan: $\overline{A\cdot B}=\overline{A}+\overline{B},\; \overline{A+B}=\overline{A}\cdot\overline{B}$ (implicitly touched via NAND/NOR discussion).

Study Pointers Moving Forward

• Practise drawing 2-, 3- and 4-variable truth tables quickly; the $2^n$ rule dictates row count.
• Memorise core gates, their symbols, and corresponding Boolean expressions (AND, OR, NOT, NAND, NOR, XOR).
• Use duality to check work: create dual, simplify, verify against expected forms.
• Anticipate continuation into Topic 3 covering “SETS and SUBMATION” (per lecturer announcement).