ExamFinch.com My Study

Study guide

9.2 Boolean Algebra, Logic Gates & Combinational Circuits

Practice this exam

PRC Electronics Engineering Licensure Examination Study Guide Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Introduction & Board Exam Strategy

1.1 PRC ECE Licensure Exam Overview & Regulation 1.2 Table of Specifications & Exam Strategy

2 Chapter 2: Mathematics Foundations

2.1 College & Advanced Algebra 2.2 Trigonometry & Solid Mensuration 2.3 Analytic Geometry & Differential Calculus 2.4 Integral Calculus & Applications

3 Chapter 3: Advanced Mathematics for ECE

3.1 Differential Equations & Circuit Transients 3.2 Complex Numbers & Laplace Transforms 3.3 Fourier Series, Fourier Transforms & Z-Transforms 3.4 Vector Analysis, Matrices & Probability

4 Chapter 4: GEAS - Engineering Sciences & Economics

4.1 Engineering Physics & Materials Chemistry 4.2 Engineering Mechanics & Strength of Materials 4.3 Engineering Economics & Financial Analysis 4.4 Computer Fundamentals & C/C++ Programming

5 Chapter 5: GEAS - Management, Materials, Environment & CAD

5.1 Engineering Management & Technopreneurship 101 5.2 Materials Science & Engineering 5.3 Environment Science & Engineering 5.4 Computer-Aided Drawing (CAD) & Engineering Graphics

6 Chapter 6: GEAS - ECE Laws, Ethics & Contracts

6.1 Republic Act No. 9292 (Electronics Engineering Law of 2004) 6.2 ECE Code of Ethics & Professional Conduct 6.3 Contracts, Specifications & National Building Code (PD 1096)

7 Chapter 7: Electronics Engineering - Circuits & Semiconductor Diodes

7.1 DC & AC Circuit Analysis & Network Theorems 7.2 Electromagnetics & Passive Components 7.3 Semiconductor Physics & Diode Circuits 7.4 Power Supply Design & Voltage Regulators

8 Chapter 8: Electronics Engineering - Transistors & Analog Circuits

8.1 BJT Operation, Biasing & Small-Signal Amplifiers 8.2 FET Characteristics, Biasing & Amplifier Circuits 8.3 Multistage Amplifiers, Frequency Response & Power Amplifiers 8.4 Operational Amplifiers & Active Filter Design

9 Chapter 9: Electronics Engineering - Digital Electronics & Control Systems

9.1 Feedback Topologies & Oscillator Circuits 9.2 Boolean Algebra, Logic Gates & Combinational Circuits 9.3 Sequential Logic, Flip-Flops & Microprocessor Architecture 9.4 Industrial Power Electronics & Control System Theory

10 Chapter 10: EST - Communications Fundamentals & Transmission Lines

10.1 Signal Fundamentals, Decibel Calculations & Noise Analysis 10.2 Amplitude Modulation (AM) Principles & Receivers 10.3 Frequency Modulation (FM), Phase Modulation & Discriminators 10.4 Transmission Line Parameters, SWR & Smith Chart

11 Chapter 11: EST - Digital Communications, Wireless & Optical Systems

11.1 Pulse & Digital Modulation Systems 11.2 Data Communications, OSI Model & Protocols 11.3 Antenna Principles & Electromagnetic Wave Propagation 11.4 Optical Fiber, Microwave, Satellite & Philippine NTC Regulations

9.2 Boolean Algebra, Logic Gates & Combinational Circuits

Key Takeaways Explain This Topic AI

De Morgan's laws (NOT(A · B) = NOT(A) + NOT(B) and NOT(A + B) = NOT(A) · NOT(B)) provide the algebraic rules for complementing product and sum terms in logic simplification.

Karnaugh maps (K-maps) group adjacent minterms in powers of two (1, 2, 4, 8, 16) using Gray code indexing to eliminate redundant variables and derive Minimal Sum-of-Products (SOP) expressions.

NAND and NOR logic gates are universal gates; any Boolean function or combinational logic system can be constructed exclusively using a single universal gate type.

Multiplexers (MUX) route one of 2ⁿ input signals to a single output using n select lines, serving as universal function generators for n-variable Boolean expressions.

Combinational circuits generate outputs solely based on the instantaneous combination of present inputs without memory, storage elements, or clock feedback loops.

Last updated: July 2026

9.2 Boolean Algebra, Logic Gates & Combinational Circuits

Quick Answer: Combinational logic circuits evaluate Boolean expressions where output states depend strictly on present inputs. Boolean algebra optimization leverages identity rules, consensus theorems, and De Morgan's laws (NOT(A · B) = NOT(A) + NOT(B)). Karnaugh mapping minimizes logic functions by grouping adjacent 1s in Gray-code p-subspaces of size 2ᵏ. NAND and NOR gates are universal building blocks capable of implementing any logic function. Standard modular combinational sub-systems include 2ⁿ-to-1 Multiplexers (MUX), n-to-2ⁿ Decoders, Priority Encoders, and binary Adders (Half Adder and Full Adder).

1. Boolean Algebra Theorems & Laws

Digital logic operates on binary variables restricted to two states: 0 (FALSE/LOW) and 1 (TRUE/HIGH). Boolean algebra establishes the formal mathematical rules for manipulating binary logic functions.

  • Core Axioms and Single-Variable Theorems
  • Identity Laws: A · 1 = A, A + 0 = A
  • Null (Nullity) Laws: A · 0 = 0, A + 1 = 1
  • Idempotent Laws: A · A = A, A + A = A
  • Complementarity Laws: A · NOT(A) = 0, A + NOT(A) = 1
  • Involution Law: NOT(NOT(A)) = A
  • Multi-Variable Theorems & De Morgan's Laws
  • Commutative Laws: A · B = B · A, A + B = B + A
  • Associative Laws: (A · B) · C = A · (B · C), (A + B) + C = A + (B + C)
  • Distributive Laws: A · (B + C) = AB + AC, A + (B · C) = (A + B)(A + C)
  • Absorption Laws: A + AB = A, A(A + B) = A, A + NOT(A)B = A + B
  • Consensus Theorem: AB + NOT(A)C + BC = AB + NOT(A)C

De Morgan's First Law: The complement of a product equals the sum of the complements: A ⋅ B ‾ = A ‾ + B ‾ \overline{A \cdot B} = \overline{A} + \overline{B} A ⋅ B = A + B

De Morgan's Second Law: The complement of a sum equals the product of the complements: A + B ‾ = A ‾ ⋅ B ‾ \overline{A + B} = \overline{A} \cdot \overline{B} A + B ​ = A ⋅ B

De Morgan's laws allow engineers to convert Sum-of-Products (SOP) expressions directly into all-NAND implementations and Product-of-Sums (POS) expressions into all-NOR implementations.

2. Logic Gate Truth Tables & Universal Logic

Logic gates are physical electronic hardware devices that execute primitive Boolean operations.

Standard Primitive Gates

The primitive logic gates and their governing truth table definitions are summarized below:

  • Input A Input B AND (A · B) OR (A + B) NAND (NOT(AB)) NOR (NOT(A+B)) XOR (A ⊕ B) XNOR (A ⊙ B)
  • 0 0 0 0 1 1 0 1
  • 0 1 0 1 1 0 1 0
  • 1 0 0 1 1 0 1 0
  • 1 1 1 1 0 0 0 1

Note: Exclusive-OR (XOR) output Y = A NOT(B) + NOT(A) B yields 1 if and only if an odd number of inputs are 1. XNOR Y = AB + NOT(A)NOT(B) acts as a 2-bit equality comparator.

Universal Gate Synthesis (NAND & NOR)

NAND and NOR gates are termed universal gates because any digital logic expression can be implemented using only one type of these gates.

NOT Function using NAND: Connect both inputs together: Y = NOT(A · A) = NOT(A).

AND Function using NAND: Cascade a NAND gate with an inverting NAND gate: Y = NOT(NOT(A · B)) = A · B.

OR Function using NAND: Invert inputs individually and apply to a NAND gate: Y = NOT(NOT(A) · NOT(B)) = A + B (via De Morgan).

3. Karnaugh Map (K-Map) Minimization & Quine-McCluskey Method

Graphical minimization of Boolean expressions up to 4 variables relies on Karnaugh Maps (K-maps) . A K-map organizes minterms into a multidimensional grid where adjacent cells differ by exactly one binary digit (Gray code ordering: 00, 01, 11, 10).

K-Map Grouping Rules

To minimize a Sum-of-Products (SOP) function F(A,B,C,D):

Plot 1s for each minterm in the function truth table.

Group adjacent 1s into rectangular blocks whose size is a power of 2 (1, 2, 4, 8, 16).

Groups must be as large as possible. Larger groups eliminate more variables.

Wrap-around grouping is valid: top and bottom edges are adjacent, as are left and right edges.

Don't Care (X) Conditions: Inputs that cannot occur or whose output is irrelevant can be treated as 1 if it aids in forming a larger group, or 0 otherwise.

Worked Example: 4-Variable K-Map Minimization

Consider the Boolean function: F ( A , B , C , D ) = ∑ m ( 2 , 3 , 6 , 7 , 8 , 10 , 12 , 14 ) F(A,B,C,D) = \sum m(2, 3, 6, 7, 8, 10, 12, 14) F ( A , B , C , D ) = ∑ m ( 2 , 3 , 6 , 7 , 8 , 10 , 12 , 14 )

Let's lay out the 4x4 grid with rows AB (00, 01, 11, 10) and columns CD (00, 01, 11, 10):

Minterms 2, 3, 6, 7 fill the 2nd row (AB=00,01 with CD=10,11), forming a quad group covering C=1, D=don't care, A=0. Group 1 yield: NOT(A)C.

Minterms 8, 10, 12, 14 occupy AB=10, 11 with D=0 (CD=00, 10). The 4 corners/column-10 form a quad group yielding: A NOT(D).

Combining these prime implicants results in the minimal SOP expression: F m i n = A ‾ C + A D ‾ F_{min} = \overline{A}C + A\overline{D} F min ​ = A C + A D

  • 4. Standard Combinational Logic Sub-systems
  • Multiplexers (Data Selectors)

A Multiplexer (MUX) routes data from one of N = 2ⁿ input lines to a single output line based on n select control lines.

4-to-1 MUX: Features 4 data inputs (I₀, I₁, I₂, I₃), 2 select lines (S₁, S₀), and output Y: Y = S 1 ‾ S 0 ‾ I 0 + S 1 ‾ S 0 I 1 + S 1 S 0 ‾ I 2 + S 1 S 0 I 3 Y = \overline{S_1}\overline{S_0}I_0 + \overline{S_1}S_0 I_1 + S_1\overline{S_0}I_2 + S_1 S_0 I_3 Y = S 1 ​ ​ S 0 ​ ​ I 0 ​ + S 1 ​ ​ S 0 ​ I 1 ​ + S 1 ​ S 0 ​ ​ I 2 ​ + S 1 ​ S 0 ​ I 3 ​

Universal Function Generator: An N-to-1 MUX can directly implement any n-variable Boolean function by applying the variables to the n select lines and tying the data inputs I_k to logic 0, logic 1, or the (n+1)-th variable.

Decoders & Encoders

Decoder (n-to-2ⁿ): Converts an n-bit binary input code into 2ⁿ unique output lines, where exactly one output line is activated at a time. A 3-to-8 decoder (e.g., IC 74LS138) with active-low enable lines generates all 8 canonical minterms for inputs (A, B, C).

Priority Encoder (2ⁿ-to-n): Performs the reverse operation of a decoder, converting the highest-order active input line into its corresponding binary representation (e.g., 8-to-3 priority encoder 74LS148).

Binary Arithmetic Circuits

Half Adder: Adds two 1-bit inputs (A, B) producing a Sum (S) and Carry-out (C): S = A ⊕ B , C = A ⋅ B S = A \oplus B, \quad C = A \cdot B S = A ⊕ B , C = A ⋅ B

Full Adder: Adds two 1-bit inputs (A, B) plus an incoming Carry-in (C_{in}): S = A ⊕ B ⊕ C i n S = A \oplus B \oplus C_{in} S = A ⊕ B ⊕ C in ​ C o u t = A B + C i n ( A ⊕ B ) = A B + B C i n + A C i n C_{out} = AB + C_{in}(A \oplus B) = AB + BC_{in} + AC_{in} C o u t ​ = A B + C in ​ ( A ⊕ B ) = A B + B C in ​ + A C in ​

Ripple-Carry Adder: Cascades n Full Adders in series to add n-bit binary numbers. The total propagation delay is limited by carry propagation through all n stages (t_{delay} = n · t_{carry}). Carry-Lookahead Adders (CLA) eliminate this bottleneck by calculating carry signals in parallel using generate (G_i = A_i B_i) and propagate (P_i = A_i ⊕ B_i) logic.