Digital Logic Basics & Boolean Algebra Foundations

Core Concepts of Digital Logic Design

What is Digital Logic?

Digital logic is the foundation of all digital systems, including computers, smartphones, and embedded systems. Unlike analog systems that deal with continuous signals, digital systems use discrete values (typically binary: 0 and 1) to represent data and perform operations.

Why Binary?

• Simplicity: Binary is easy to implement using electronic switches (transistors).
• Reliability: Digital signals are less susceptible to noise compared to analog signals.
• Scalability: Complex operations can be broken down into simple binary operations.

mindmap
  root((Digital Logic))
    Binary System
      Base-2
      Discrete Values (0, 1)
    Analog vs Digital
      Analog: Continuous Signals
      Digital: Discrete Signals
    Applications
      Computers
      Smartphones
      Embedded Systems

Binary Number System

Binary Basics

Binary numbers are the backbone of digital systems. Each digit in a binary number is called a bit (binary digit). The value of each bit is determined by its position (weight), which is a power of 2.

Example: Convert 1101 to decimal.

• $1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0=8+4+0+1=13$

Boolean Algebra

Introduction to Boolean Algebra

Boolean algebra is a mathematical system used to analyze and simplify digital logic circuits. It was developed by George Boole and is based on three fundamental operations:

1. AND (· or ∧)
2. OR (+ or ∨)
3. NOT (' or ¬)

Basic Laws of Boolean Algebra

Logic Gates

Logic gates are the building blocks of digital circuits. They perform basic logical operations on one or more binary inputs to produce a single binary output.

Basic Logic Gates

1. AND Gate

   • Output is 1 only if all inputs are 1.
   • Symbol:

   • Truth Table:

     A	B	Y = A · B
     0	0	0
     0	1	0
     1	0	0
     1	1	1

2. OR Gate

   • Output is 1 if at least one input is 1.
   • Symbol:

   • Truth Table:

     A	B	Y = A + B
     0	0	0
     0	1	1
     1	0	1
     1	1	1

3. NOT Gate (Inverter)

   • Output is the inverse of the input.
   • Symbol:

   • Truth Table:

     A	Y = A'
     0	1
     1	0

4. NAND and NOR Gates

   • NAND Gate: AND followed by NOT.
     • Truth Table:

       A	B	Y = (A · B)'
       0	0	1
       0	1	1
       1	0	1
       1	1	0

   • NOR Gate: OR followed by NOT.
     • Truth Table:

       A	B	Y = (A + B)'
       0	0	1
       0	1	0
       1	0	0
       1	1	0

5. XOR and XNOR Gates

   • XOR Gate: Output is 1 if inputs are different.
     • Truth Table:

       A	B	Y = A ⊕ B
       0	0	0
       0	1	1
       1	0	1
       1	1	0

   • XNOR Gate: Output is 1 if inputs are same.
     • Truth Table:

       A	B	Y = A ⊙ B
       0	0	1
       0	1	0
       1	0	0
       1	1	1

Universal Gates

NAND and NOR gates are called universal gates because they can be used to construct any other logic gate.

Constructing AND Gate using NAND Gates

![AND gate using NAND gates](/media/b41f461191d8d5e795d4.png "AND gate implemented with two NAND gates (Image: A09, CC BY-SA 4.0, via Wikimedia Commons)")

• Circuit:
  • Connect the outputs of two NAND gates to a third NAND gate.
  • The output of the third NAND gate is the AND of the inputs.

Constructing OR Gate using NOR Gates

![OR gate using NOR gates](/media/0e22a5b38e081c961297.png "OR gate implemented with two NOR gates (Image: XZise, Public domain, via Wikimedia Commons)")

• Circuit:
  • Connect the outputs of two NOR gates to a third NOR gate.
  • The output of the third NOR gate is the OR of the inputs.

In the Real World

1. eSewa and Digital Payments

• Concept Used: Boolean logic and binary operations.
• How? eSewa processes transactions using digital logic to validate inputs (e.g., PIN, amount) and authorize payments. For example, an AND gate ensures that both the correct PIN and sufficient balance are verified before processing a transaction.

2. Khalti’s Fraud Detection

• Concept Used: Logic gates in decision-making.
• How? Khalti uses XOR gates to detect anomalies in transaction patterns. If a transaction’s details (e.g., location, time, amount) do not match expected patterns (stored as binary flags), the system flags it for review.

3. NTC’s Traffic Light Control

• Concept Used: Sequential logic and state machines.
• How? Traffic lights in Kathmandu use flip-flops (covered in Unit 4) to cycle through states (red → green → yellow). Boolean logic determines when to switch states based on sensor inputs (e.g., pedestrian buttons, vehicle detectors).

Worked Example: Traffic Light Controller Logic

Scenario: Design a simple logic circuit for a traffic light that cycles between red, yellow, and green based on a timer input.

Step 1: Define States

• Red: 1 0 0 (binary)
• Yellow: 0 1 0
• Green: 0 0 1

Step 2: Use a Decoder

A 3-to-8 decoder can be used to select the appropriate state based on a 2-bit input (since $2^2=4$ states, but we only need 3). The unused state (1 1) can be ignored or set to 0 0 0 (off).

• Input 00: Red (1 0 0)
• Input 01: Yellow (0 1 0)
• Input 10: Green (0 0 1)
• Input 11: Off (0 0 0)

Step 3: Connect to Traffic Lights

• Use the decoder outputs to drive the traffic lights:
  • Red light connected to Y0
  • Yellow light connected to Y1
  • Green light connected to Y2

Boolean Algebra Applications

Simplifying Logic Circuits

Boolean algebra is used to simplify complex logic expressions to reduce the number of gates and components in a circuit, saving cost and improving efficiency.

Example: Simplify $Y=A\cdot B+A\cdot C+B\cdot C$

1. Factor out $A$ from the first two terms: $Y=A\cdot (B+C)+B\cdot C$
2. This is already simplified, but it can be implemented using fewer gates than the original expression.

Exam Tip

1. Memorize Truth Tables: Be able to write truth tables for all basic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR) from memory.
2. Practice Simplification: Use Boolean algebra laws to simplify expressions. Always check your work by expanding back to the original form.
3. Understand Universal Gates: Know how to construct AND, OR, and NOT gates using only NAND or NOR gates.
4. Real-World Connections: Relate logic gates to everyday devices (e.g., traffic lights, payment systems). Examiners often ask for practical applications.
5. Diagrams: Always draw circuit diagrams for logic gates and combinational circuits. Label inputs, outputs, and gate types clearly.
6. Binary Conversions: Be quick with converting between binary, decimal, and hexadecimal. Practice converting 8-bit binary numbers to decimal and vice versa.

Visual Summary:

flowchart LR
    A["Binary System"] --> B["Boolean Algebra"]
    B --> C["Logic Gates"]
    C --> D["Combinational Circuits"]
    C --> E["Sequential Circuits"]
    D --> F["Simplification Techniques"]
    E --> G["Flip-Flops & Registers"]
    G --> H["Finite State Machines"]