CAEECentre for Automotive Embedded Engineering · HSR Layout, Bengaluru
Module 20 of 20 · Foundation

Discrete Mathematics, Boolean Algebra and Network Graphs

Discrete mathematics describes logic states, finite structures and interconnected networks. It supports digital electronics, switching systems, coding, circuit topology and communication networks.

Foundation55 min study timePrerequisite: Algebra
Module learning progress0 of 3 stages

1 · Why this mathematics matters

Model digital logic, finite states, switching networks and graph connectivity.

2 · Prerequisites and learning approach

Prerequisites: Algebra. Begin with the physical meaning, identify every symbol and unit, study the fixed-scale graph, then solve and verify the examples.

3 · Symbols and units

0, 1Boolean states
Vvertex set
Eedge set
⊕exclusive OR

4 · Concepts and textbook formulas

1. Sets and relations

Sets organise objects and relations describe allowed pairings. Functions are special relations with one output per input.

Sets and relations equation

How to read it: identify the output quantity first, then the variables, parameters, units and assumptions. Test zero, unity and limiting values before using the equation in a design.

2. Boolean algebra

Boolean variables take 0 or 1. Algebraic laws simplify logic while preserving the truth table.

Boolean algebra equation

How to read it: identify the output quantity first, then the variables, parameters, units and assumptions. Test zero, unity and limiting values before using the equation in a design.

3. Combinatorics

Counting rules quantify configurations, codewords and test cases.

Combinatorics equation

How to read it: identify the output quantity first, then the variables, parameters, units and assumptions. Test zero, unity and limiting values before using the equation in a design.

4. Graph theory

A graph consists of vertices and edges. Incidence matrices, paths, trees and loops formalise circuit and network topology.

Graph theory equation

How to read it: identify the output quantity first, then the variables, parameters, units and assumptions. Test zero, unity and limiting values before using the equation in a design.

5 · Step-by-step worked examples

Example 1: Foundation

A 3-input Boolean function has 2^3=8 input combinations in its complete truth table.

Verification: check the unit, sign, order of magnitude and physical trend.

Example 2: Logic simplification

Given: Simplify AB plus A B-bar.

Logic simplification solution equation

Engineering meaning: Factoring and the complement law remove the redundant variable.

Example 3: Spanning tree

Given: A connected graph has six vertices.

Spanning tree solution equation

Engineering meaning: Every spanning tree of the graph contains exactly five edges and no loop.

6 · EE/ECE applications

  • logic minimisation — use the governing equation to predict parameter sensitivity, confirm a simulation and interpret measured behaviour.
  • finite-state machines — use the governing equation to predict parameter sensitivity, confirm a simulation and interpret measured behaviour.
  • network topology — use the governing equation to predict parameter sensitivity, confirm a simulation and interpret measured behaviour.
  • coding and test coverage — use the governing equation to predict parameter sensitivity, confirm a simulation and interpret measured behaviour.

7 · Common mistakes

  • Using ordinary algebra where Boolean identities apply.
  • Confusing a directed graph with an undirected network.

8 · Practice problems

  1. Simplify a Boolean expression using identities.
  2. Represent a small electrical network as vertices and edges.
Verification habit: predict the direction of change before calculating, then check units, sign, limiting cases and engineering reasonableness.