7. Logic Circuits: Complete Guide with Solved Exercises

Logic circuits are physical or abstract representations of propositional logic operators. When working with propositions, we typically assign values like true (T) or false (F). With circuits, however, we deal with on (1) and off (0) states.

This connection between mathematical logic and electrical circuits was discovered by Claude Shannon in 1938, who demonstrated that Boolean algebra could be applied to the design of switching circuits.

Fundamental Concepts

Logic-Circuit Correspondence

Propositional Logic	Electrical Circuit
True Proposition (T)	Closed Switch (1)
False Proposition (F)	Open Switch (0)
Conjunction (∧)	Series Circuit
Disjunction (∨)	Parallel Circuit
Negation (¬)	Inverse Switch

Basic Elements of a Circuit

1. Switch: Device that allows or prevents current flow
   • Open (0): No current flows
   • Closed (1): Current flows
2. Lamp/Bulb: Indicates the circuit result
   • Off (0): Open circuit
   • On (1): Closed circuit
3. Power source: Provides current to the circuit

Basic Circuits

Visual Symbols

Before diving into each circuit, let’s familiarize ourselves with the symbols we’ll be using:

Symbol	Meaning
──●── continuous line	Closed switch (1) – current flows
──○── broken line	Open switch (0) – no current flows
💡	Lamp/bulb on
──○ (at the end)	Lamp/bulb off

1. AND Circuit (Conjunction) – Series

The AND circuit corresponds to the logical conjunction (\( p \land q \)). It is built by connecting switches in series.

General representation:

──── p ───── q ───💡

Operation: The lamp turns on only if both switches are closed.

AND Circuit States

Case 1: p=0, q=0 → Lamp OFF

─── ○ ────── ○ ─────○
  (open)    (open)

Case 2: p=0, q=1 → Lamp OFF

──── ○ ────── ● ────○
  (open)   (closed)

Case 3: p=1, q=0 → Lamp OFF

─── ● ────── ○ ────○
 (closed)   (open)

Case 4: p=1, q=1 → Lamp ON ✓

──── ● ─────── ● ────💡
 (closed)   (closed)

Truth Table:

p	q	p ∧ q	Lamp
0	0	0	Off
0	1	0	Off
1	0	0	Off
1	1	1	On

Boolean Notation: \( S = p \cdot q \)

Note on Boolean Algebra: Boolean notation uses algebraic symbols to represent logical operations. The dot (·) or simple concatenation represents AND, the plus (+) represents OR, and the overline (\( \overline{p} \)) or prime (p’) represents NOT. This notation was developed by George Boole in the 19th century and is fundamental in digital circuit design.

2. OR Circuit (Disjunction) – Parallel

The OR circuit corresponds to the logical disjunction (\( p \lor q \)). It is built by connecting switches in parallel.

General representation:

       ┌─── p ───┐
       │         │
    ───┼         ┼───
       │         │
       └─── q ───┘

    ┌─── p ───┐
    │          │
───┤          ├───💡
    │          │
    └─── q ───┘

Operation: The lamp turns on if at least one of the switches is closed.

OR Circuit States

Case 1: p=0, q=0 → Lamp OFF

     ┌─── ○ ───┐
     │         │
  ───┼         ┼───○
     │         │
     └─── ○ ───┘
     (both open)

    ┌─── ○ ───┐
    │          │
───┤          ├───○
    │          │
    └─── ○ ───┘
    (both open)

Case 2: p=0, q=1 → Lamp ON ✓

       ┌─── ○ ───┐
       │         │
    ───┼         ┼───💡
       │         │
       └─── ● ───┘
       (q closed)

    ┌─── ○ ───┐
    │          │
───┤          ├───💡
    │          │
    └─── ● ───┘
    (q closed)

Case 3: p=1, q=0 → Lamp ON ✓

       ┌─── ● ───┐
       │         │
    ───┼         ┼───💡
       │         │
       └─── ○ ───┘
       (p closed)

    ┌─── ● ───┐
    │          │
───┤          ├───💡
    │          │
    └─── ○ ───┘
    (p closed)

Case 4: p=1, q=1 → Lamp ON ✓

       ┌─── ● ───┐
       │         │
    ───┼         ┼───💡
       │         │
       └─── ● ───┘
      (both closed)

    ┌─── ● ───┐
    │          │
───┤          ├───💡
    │          │
    └─── ● ───┘
   (both closed)

Truth Table:

p	q	p ∨ q	Lamp
0	0	0	Off
0	1	1	On
1	0	1	On
1	1	1	On

Boolean Notation: \( S = p + q \)

3. NOT Circuit (Negation) – Inverter

The NOT circuit corresponds to logical negation (\( \neg p \)). It uses a single switch representing a negated propositional variable.

General representation:

     ───── ¬p ─────

Operation: The lamp stays on while the switch is closed. Opening the switch turns the lamp off.

NOT Circuit States

Case 1: p=0 (not pressed) → Lamp ON ✓

   ────── ● ─────💡
     (p closed)

Case 2: p=1 (pressed) → Lamp OFF

   ────── ○ ─────○
     (p open)

Truth Table:

p	¬p	Lamp
0	1	On
1	0	Off

Boolean Notation: \( S = \overline{p} \) or \( S = p’ \)

Compound Circuits

Compound circuits are built by combining basic circuits (AND, OR, NOT). Their states are derived directly from basic operations.

4. NAND Circuit (Negation of AND)

The NAND circuit is the negation of AND: \( \neg(p \land q) \).

Conceptual representation:

The logical equivalence of \( \neg(p \land q) ≡ \neg p \lor \neg q \), for the schematic:

       ┌─── ¬p ───┐
       │          │
    ───┼          ┼───
       │          │
       └─── ¬q ───┘

       ┌─── ¬p ───┐
       │           │
   ───┼           ┼───
       │           │
       └─── ¬q ───┘

Operation: The lamp turns on only when at least one switch is open (i.e., it turns on in 3 of 4 cases).

NAND Circuit States

p	q	AND	NAND	State
0	0	○	💡	On
0	1	○	💡	On
1	0	○	💡	On
1	1	●	○	Off

Boolean Notation: \( S = \overline{p \cdot q} \)

Important note: The NAND gate is a universal gate, which means any other logic gate can be built using only NAND gates.

5. NOR Circuit (Negation of OR)

The NOR circuit is the negation of OR: \( \neg(p \lor q) \).

Conceptual representation:

The logical equivalence of \( \neg(p \lor q) ≡ \neg p \land \neg q \), for the schematic:

────── ¬p ─────── ¬q ─────

Operation: The lamp turns on only when neither is closed (only 1 of 4 cases).

NOR Circuit States

p	q	OR	NOR	State
0	0	○	💡	On
0	1	●	○	Off
1	0	●	○	Off
1	1	●	○	Off

Boolean Notation: \( S = \overline{p + q} \)

Important note: The NOR gate is also a universal gate.

6. XOR Circuit (Exclusive Disjunction)

The XOR circuit corresponds to the exclusive disjunction: \( p \oplus q \) or \( p \veebar q \).

Conceptual representation:

The logical equivalence of \( p \veebar q ≡ (p \land \neg q) \lor (\neg p \land q) \), for the schematic:

   ┌───── p ─────── ¬q ────┐
   │                       │
───┤                       ├───
   │                       │
   └───── ¬p ─────── q ────┘

    ┌─── p ──── ¬q ───┐
    │                   │
───┤                   ├───
    │                   │
    └─── ¬p ──── q ───┘

Operation: The lamp turns on only if the inputs are different (one on, the other off).

XOR Circuit States

p	q	Different?	XOR	State
0	0	No	○	Off
0	1	Yes	💡	On
1	0	Yes	💡	On
1	1	No	○	Off

Boolean Notation: \( S = p \oplus q = (p \cdot \overline{q}) + (\overline{p} \cdot q) \)

Logical equivalence: \( p \oplus q \equiv (p \lor q) \land \neg(p \land q) \)

Practical application: XOR is used in stairway switches, where either switch can change the state of the light.

7. XNOR Circuit (Equivalence)

The XNOR circuit is the negation of XOR, also called biconditional or equivalence: \( p \leftrightarrow q \).

Conceptual representation:

The logical equivalence of \( p \leftrightarrow q ≡ (p \land q) \lor (\neg p \land \neg q) \), for the schematic:

   ┌───── p ──────── q ────┐
   │                       │
───┤                       ├────💡
   │                       │
   └───── ¬p ────── ¬q ────┘

    ┌──── p ───── q ───┐
    │                    │
───┤                    ├────💡
    │                    │
    └──── ¬p ─── ¬q ───┘

Operation: The lamp turns on only if the inputs are equal (both on or both off).

XNOR Circuit States

p	q	Equal?	XNOR	State
0	0	Yes	💡	On
0	1	No	○	Off
1	0	No	○	Off
1	1	Yes	💡	On

Boolean Notation: \( S = \overline{p \oplus q} = (p \cdot q) + (\overline{p} \cdot \overline{q}) \)

Practical application: XNOR is used as an equality detector in digital circuits.

Circuits for Connectives Without Dedicated Gates

The seven gates discussed above (AND, OR, NOT, NAND, NOR, XOR, XNOR) are standard gates available as physical integrated circuits (74xx, 40xx series chips, etc.). However, some important logical connectives lack dedicated physical gates but can still be constructed by combining basic gates.

8. Conditional Circuit (Implication)

The conditional \( p \rightarrow q \) (“if p then q”) is fundamental in mathematical logic, but does not exist as a dedicated physical gate.

Why doesn’t it exist?

1. Redundancy: It is easily built combining NOT + OR
2. Low practical demand: In digital circuit design, AND, OR, and NOT are the most commonly used operations
3. Universality of NAND/NOR: Any logical function can be built with only NAND or NOR

Logical equivalence:

\[ p \rightarrow q \equiv \neg p \lor q \]

Conceptual representation:

   ┌──── ¬p ─────┐
   │             │
───┤             ├────💡
   │             │
   └───── q ─────┘

    ┌──── ¬p ─────┐
    │               │
───┤               ├────💡
    │               │
    └───── q ─────┘

Circuit reading: “If p is NOT closed, OR q is closed, then the lamp turns on.”

Conditional Circuit States

p	q	¬p	¬p ∨ q	State
0	0	1	💡	On
0	1	1	💡	On
1	0	0	○	Off
1	1	0	💡	On

Interpretation: The conditional is only false when the antecedent (p) is true and the consequent (q) is false. In all other cases it is true.

Boolean Notation: \( S = \overline{p} + q \)

9. Negation of Conditional Circuit

The negation of the conditional \( \neg(p \rightarrow q) \) can also be constructed, though it likewise has no dedicated physical gate.

Logical equivalence:

\[ \neg(p \rightarrow q) \equiv p \land \neg q \]

Conceptual representation:

────── p ─────── ¬q ─────💡

Circuit reading: “If p is closed, AND q is NOT closed, then the lamp turns on.”

¬(p → q) Circuit States

p	q	¬q	p ∧ ¬q	State
0	0	1	○	Off
0	1	0	○	Off
1	0	1	💡	On
1	1	0	○	Off

Interpretation: The negation of the conditional is true only when the antecedent is true and the consequent is false.

Boolean Notation: \( S = p \cdot \overline{q} \)

Note on Universal Gates

It’s worth emphasizing that NAND and NOR are universal gates. This means:

• Any logical function can be built using only NAND gates
• Any logical function can be built using only NOR gates

For example, the conditional \( p \rightarrow q \) using only NAND: \[ p \rightarrow q = p \text{ NAND } (q \text{ NAND } q) \]

This property is fundamental in integrated circuit design, as it allows chips to be manufactured using a single type of transistor.

---

Logic Gates Summary

Gate	Symbol	Expression	Description
AND	∧	\( p \cdot q \)	Output 1 if both inputs are 1
OR	∨	\( p + q \)	Output 1 if at least one input is 1
NOT	¬	\( \overline{p} \)	Inverts the input
NAND	⊼	\( \overline{p \cdot q} \)	Negation of AND
NOR	⊽	\( \overline{p + q} \)	Negation of OR
XOR	⊕	\( p \oplus q \)	Output 1 if inputs are different
XNOR	⊙	\( \overline{p \oplus q} \)	Output 1 if inputs are equal
IMPLY*	→	\( \overline{p} + q \)	Conditional: false only if p=1, q=0
NIMPLY*	↛	\( p \cdot \overline{q} \)	Negation of conditional

Note: Gates marked with an asterisk (*) do not exist as dedicated integrated circuits. They are built by combining basic gates (NOT + OR for IMPLY, and AND + NOT for NIMPLY).

Building Circuits from Expressions

Method for building circuits:

1. Identify the variables (propositions) involved
2. Analyze the logical expression from inside out
3. Connect the switches according to operations:
   • AND → Series
   • OR → Parallel
   • NOT → Inverse switch
4. Verify with the truth table

Example 1: Circuit for \( (p \land q) \lor r \)

Step 1: Identify operators

• First: \( p \land q \) (AND between p and q)
• Then: OR with r

Step 2: Build

┌──── p ─────── q ────┐
│                     │
│                     ┼───💡
│                     │
└───────── r ─────────┘

┌─── p ────── q ───┐
│                     │
│                     ┼───💡
│                     │
└─────── r ────────┘

Truth Table:

p	q	r	p ∧ q	(p ∧ q) ∨ r
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

Example 2: Circuit for \( (p \lor q) \land (p \lor r) \)

Analysis: Two parallel blocks, connected in series with each other.

       ┌──── p ─────┐     ┌──── p ────┐
       │            │     │           │
       │            ┼─────┼           ┼───💡
       │            │     │           │
       └──── q ─────┘     └──── r ────┘

┌── p ──┐    ┌── p ──┐
│        │    │        │
│        ├───┤        ├───💡
│        │    │        │
└── q ──┘    └── r ──┘

Example 3: Circuit for \( \neg p \land (q \lor r) \)

Analysis:

• \( \neg p \): Inverse switch of p
• \( q \lor r \): q and r in parallel
• Everything in series

                ┌──── q ────┐
                │           │
   ──── ¬p ─────┤           ┼───💡
                │           │  
                └──── r ────┘

          ┌── q ──┐
          │        │
 ── ¬p ──┤        ┼───💡
          │        │  
          └── r ──┘

Circuit Simplification

Logic circuits can be simplified using the laws of Boolean algebra:

Fundamental Laws

1. Identity Law:
   • \( p \land 1 = p \)
   • \( p \lor 0 = p \)
2. Domination Law:
   • \( p \land 0 = 0 \)
   • \( p \lor 1 = 1 \)
3. Idempotent Law:
   • \( p \land p = p \)
   • \( p \lor p = p \)
4. Complement Law:
   • \( p \land \neg p = 0 \)
   • \( p \lor \neg p = 1 \)
5. Double Negation Law:
   • \( \neg(\neg p) = p \)
6. De Morgan’s Laws:
   • \( \neg(p \land q) = \neg p \lor \neg q \)
   • \( \neg(p \lor q) = \neg p \land \neg q \)
7. Distributive Law:
   • \( p \land (q \lor r) = (p \land q) \lor (p \land r) \)
   • \( p \lor (q \land r) = (p \lor q) \land (p \lor r) \)
8. Absorption Law:
   • \( p \land (p \lor q) = p \)
   • \( p \lor (p \land q) = p \)

Practical Applications

1. Security System

Problem: An alarm should activate if the door is opened (p) AND the system is armed (a), OR if smoke is detected (h).

Expression: \( (p \land a) \lor h \)

Note: In alarm systems, “armed” means the system is activated and ready to detect intrusions. When the user leaves home, they “arm” the alarm (turn it on); when they enter, they “disarm” it (turn it off). If the alarm is not armed, opening the door does not trigger the siren.

2. Lighting Control

Problem: A stairway light should toggle whenever either switch (upstairs or downstairs) changes position.

Expression: \( p \oplus q \) (XOR)

3. Voting System

Problem: In a 3-person committee, a proposal is approved if at least 2 vote in favor.

Expression: \( (p \land q) \lor (p \land r) \lor (q \land r) \)

Solved Exercises

Exercise 1

Determine the logical expression for the following circuit:

  ┌──── A ────┐
  │           │
──┤           ┼───💡
  │           │  
  └──── B ────┘

   ┌─── A ────┐
   │            │
──┤            ┼───💡
   │            │  
   └─── B ────┘

Solution: Switches A and B are in parallel, therefore: \[ S = A \lor B \]

Exercise 2

Determine the logical expression for the following circuit:

──── A ──── B ──── C ────💡

Solution: Switches A, B, and C are in series, therefore: \[ S = A \land B \land C \]

Exercise 3

Build the circuit for the expression: \( (A \land B) \lor (C \land D) \)

Solution:

• A and B in series (first block)
• C and D in series (second block)
• Both blocks in parallel

   ┌───── A ──────── B ────┐
   │                       │
───┤                       ├────💡
   │                       │
   └───── C ──────── D ────┘

    ┌──── A ────── B ────┐
    │                       │
───┤                       ├────💡
    │                       │
    └──── C ────── D ────┘

Exercise 4

Simplify the expression: \( (A \land B) \lor (A \land \neg B) \)

Solution:

Step	Expression	Justification
1	\( (A \land B) \lor (A \land \neg B) \)	Original expression
2	\( A \land (B \lor \neg B) \)	Common factor (A)
3	\( A \land 1 \)	Complement law: \( B \lor \neg B = 1 \)
4	\( A \)	Identity law: \( A \land 1 = A \)

Result: The expression simplifies to \( A \)

Exercise 5

Complete the truth table for: \( (p \rightarrow q) \land (q \rightarrow p) \)

Solution:

p	q	p → q	q → p	(p → q) ∧ (q → p)
0	0	1	1	1
0	1	1	0	0
1	0	0	1	0
1	1	1	1	1

Observation: This expression is equivalent to the biconditional \( p \leftrightarrow q \).

Exercise 6

Apply De Morgan’s laws to simplify: \( \neg(\neg A \land \neg B) \)

Solution:

Step	Expression	Justification
1	\( \neg(\neg A \land \neg B) \)	Original expression
2	\( \neg(\neg A) \lor \neg(\neg B) \)	De Morgan’s Law
3	\( A \lor B \)	Double negation

Result: The expression simplifies to \( A \lor B \)

Proposed Exercises

Basic Level

1. Determine the logical expression for a circuit where three switches (A, B, C) are in series.
2. Build the circuit for the expression: \( A \lor (B \land C) \)
3. Complete the truth table for: \( \neg(A \lor B) \)
4. What is the result of the AND circuit when A=1 and B=0?
5. Draw the circuit that represents the expression: \( (A \lor B) \land C \)

Intermediate Level

6. Simplify using Boolean algebra: \( A \lor (A \land B) \)
7. Prove that \( \neg(A \land B) = \neg A \lor \neg B \) using truth tables.
8. Build a circuit with 3 variables that turns on the lamp only when exactly one variable is true.
9. Find the simplest equivalent expression for: \( (A \land B) \lor (\neg A \land B) \lor (A \land \neg B) \)
10. Design a circuit that detects if two bits are equal.

Advanced Level

11. Implement the expression \( A \rightarrow B \) using only NAND gates.
12. Simplify: \( (A \lor B) \land (\neg A \lor B) \land (A \lor \neg B) \)
13. Design a half adder circuit that has two outputs: sum (S) and carry (C).
14. Prove that NAND gates are universal by building AND, OR, and NOT using only NAND.
15. Given the circuit for \( (A \land B \land C) \lor (A \land B \land \neg C) \lor (A \land \neg B \land C) \), simplify it to the minimum.

Answers to Proposed Exercises

Basic Level

1. \( S = A \land B \land C \)

2.

       ┌──────── A ────────┐
       │                   ├──💡
       └─── B ─────── C ───┘

┌─────── A ───────┐
│                   ├──💡
└── B ────── C ───┘

3.

A	B	A ∨ B	¬(A ∨ B)
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

4. The result is 0 (off), because AND requires both inputs to be 1.

5.

       ┌──── A ─────┐
       │            ┼── C ───💡
       └──── B ─────┘

┌──── A ────┐
│             ├── C ───💡
└──── B ────┘

Intermediate Level

6. \( A \lor (A \land B) = A \) (Absorption law)

7. Truth table:

A	B	A ∧ B	¬(A ∧ B)	¬A	¬B	¬A ∨ ¬B
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Columns ¬(A ∧ B) and ¬A ∨ ¬B are identical. ✓

8. Expression: \( (A \land \neg B \land \neg C) \lor (\neg A \land B \land \neg C) \lor (\neg A \land \neg B \land C) \)

9.

Step	Expression	Justification
1	\( (A \land B) \lor (\neg A \land B) \lor (A \land \neg B) \)	Original expression
2	\( B \lor (A \land \neg B) \)	\( (A \land B) \lor (\neg A \land B) = B \)
3	\( B \lor A \)	Absorption
4	\( A \lor B \)	Commutativity

Result: \( A \lor B \)

10. Use XNOR: \( S = A \odot B = (A \land B) \lor (\neg A \land \neg B) \)

Advanced Level

11. Implement \( A \rightarrow B \) with NAND:

Equivalence	Expression
Definition	\( A \rightarrow B = \neg A \lor B \)
Alternative	\( = \neg(A \land \neg B) \)
With NAND	\( = A \text{ NAND } (B \text{ NAND } B) \)

12.

Step	Expression	Justification
1	\( (A \lor B) \land (\neg A \lor B) \land (A \lor \neg B) \)	Original expression
2	\( B \land (A \lor \neg B) \)	\( (A \lor B) \land (\neg A \lor B) = B \)
3	\( (B \land A) \lor (B \land \neg B) \)	Distributive
4	\( A \land B \)	\( B \land \neg B = 0 \)

Result: \( A \land B \)

13. Half Adder:

• Sum: \( S = A \oplus B \)
• Carry: \( C = A \land B \)

14. Construction with only NAND:

• NOT: \( \neg A = A \text{ NAND } A \)
• AND: \( A \land B = (A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B) \)
• OR: \( A \lor B = (A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B) \)

15.

Step	Expression	Justification
1	\( (A \land B \land C) \lor (A \land B \land \neg C) \lor (A \land \neg B \land C) \)	Original
2	\( A \land B \land (C \lor \neg C) \lor (A \land \neg B \land C) \)	Common factor
3	\( (A \land B) \lor (A \land C \land \neg B) \)	\( C \lor \neg C = 1 \)
4	\( A \land (B \lor (C \land \neg B)) \)	Common factor A
5	\( A \land (B \lor C) \)	Absorption

Result: \( A \land (B \lor C) \)

---

What’s Next?

In our next post, we’ll dive into a comprehensive set of exercises covering everything we’ve learned so far.

Was this guide helpful? Drop a comment below with your questions or feedback! And be sure to check out the next installment in this mathematical logic series.