Lab Work - Discrete Mathematics

Overview

This lab work covers practical exercises for all units of Discrete Mathematics (CT3). Each exercise helps understand theoretical concepts through hands-on problem solving.

Lab Exercise 1: Truth Tables

Topic: Propositional Logic

Objective: Construct truth tables for compound propositions

Problem: Create truth tables for:

1. p ∧ q
2. p ∨ q
3. p → q
4. p ↔ q
5. ¬p ∨ q

Example Solution for p → q:

Task: Complete truth tables for all five expressions.

Learning: Understand basic logical operators and conditional statements.

Lab Exercise 2: Logical Equivalences

Topic: Propositional Equivalences

Objective: Prove logical equivalences using laws

Problem: Prove these equivalences:

1. ¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan’s Law)
2. p → q ≡ ¬p ∨ q (Conditional Identity)
3. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (Distributive Law)

Example Solution:

Prove: p → q ≡ ¬p ∨ q

Last two columns identical → equivalence proved!

Task: Prove all three equivalences using truth tables.

Learning: Master logical equivalence laws and transformation techniques.

Lab Exercise 3: Predicates and Quantifiers

Topic: Predicates and Quantifiers

Objective: Work with quantified statements

Problem: Given domain {1, 2, 3, 4, 5}, determine truth value:

1. ∀x P(x) where P(x): “x² > x”
2. ∃x Q(x) where Q(x): “x + 2 = 5”
3. ∀x R(x) where R(x): “x is odd”
4. ∃x S(x) where S(x): “x is prime”

Example Solution:

∃x Q(x) where Q(x): “x + 2 = 5”

• Q(1): 1 + 2 = 3 ≠ 5 (False)
• Q(2): 2 + 2 = 4 ≠ 5 (False)
• Q(3): 3 + 2 = 5 ✓ (True)
• Q(4): 4 + 2 = 6 ≠ 5 (False)
• Q(5): 5 + 2 = 7 ≠ 5 (False)

At least one true → ∃x Q(x) is TRUE

Task: Evaluate all four quantified statements.

Learning: Understand universal and existential quantifiers.

Lab Exercise 4: Proof Techniques

Topic: Proof Methods

Objective: Apply different proof strategies

Problem: Prove using specified method:

1. Direct proof: If n is even, then n² is even
2. Contrapositive: If n² is odd, then n is odd
3. Contradiction: √2 is irrational
4. Induction: 1 + 2 + 3 + … + n = n(n+1)/2

Example Solution (Direct Proof):

Prove: If n is even, then n² is even

Proof:

• Assume n is even
• Then n = 2k for some integer k
• n² = (2k)² = 4k² = 2(2k²)
• Since 2k² is an integer, n² = 2m where m = 2k²
• Therefore n² is even ✓

Task: Complete all four proofs using appropriate methods.

Learning: Master various proof techniques.

Lab Exercise 5: Mathematical Induction

Topic: Proof by Induction

Objective: Prove formulas using induction

Problem: Prove by induction:

1. 1 + 3 + 5 + … + (2n-1) = n²
2. 1² + 2² + 3² + … + n² = n(n+1)(2n+1)/6
3. 2ⁿ > n for all n ≥ 1

Example Solution:

Prove: 1 + 3 + 5 + … + (2n-1) = n²

Base case (n=1):

• LHS = 1
• RHS = 1² = 1
• LHS = RHS ✓

Inductive step:

• Assume true for n = k: 1 + 3 + … + (2k-1) = k²
• Prove for n = k+1:
• LHS = 1 + 3 + … + (2k-1) + (2(k+1)-1)
• = k² + (2k+1) [by inductive hypothesis]
• = k² + 2k + 1
• = (k+1)²
• = RHS ✓

By induction, formula holds for all n ≥ 1.

Task: Complete all three induction proofs.

Learning: Master induction structure and application.

Lab Exercise 6: Divisibility and GCD

Topic: Number Theory

Objective: Compute GCD using Euclidean algorithm

Problem: Find GCD using Euclidean algorithm:

1. gcd(48, 18)
2. gcd(252, 198)
3. gcd(1071, 462)

Example Solution:

Find gcd(48, 18)

48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0

GCD = 6 (last non-zero remainder)

Verification:

• 48 = 6 × 8
• 18 = 6 × 3
• 6 divides both ✓

Task: Find GCD for all three pairs.

Learning: Master Euclidean algorithm for GCD computation.

Lab Exercise 7: Modular Arithmetic

Topic: Modular Arithmetic

Objective: Perform modular calculations

Problem: Compute:

1. 17 + 23 (mod 12)
2. 15 × 7 (mod 11)
3. 2⁸ (mod 5)
4. Solve: 3x ≡ 7 (mod 10)

Example Solution:

Compute: 15 × 7 (mod 11)

• 15 × 7 = 105
• 105 = 11 × 9 + 6
• 105 ≡ 6 (mod 11)

Alternative:

• 15 ≡ 4 (mod 11)
• 4 × 7 = 28
• 28 ≡ 6 (mod 11) ✓

Task: Complete all four modular arithmetic problems.

Learning: Understand modular arithmetic operations.

Lab Exercise 8: Boolean Functions

Topic: Boolean Algebra

Objective: Simplify Boolean expressions

Problem: Simplify using Boolean laws:

1. xy + x̄y
2. (x + y)(x + ȳ)
3. xy + xz + yz
4. x̄ȳz + xȳz + xyz̄ + xyz

Example Solution:

Simplify: xy + x̄y

• = y(x + x̄) [Distributive law]
• = y(1) [Complement law]
• = y [Identity law]

Simplified form: y

Task: Simplify all four Boolean expressions.

Learning: Apply Boolean algebra laws for simplification.

Lab Exercise 9: Logic Gates

Topic: Digital Logic Circuits

Objective: Design circuits using logic gates

Problem: Design logic circuit for:

1. F(x, y) = x ⊕ y (XOR)
2. F(x, y, z) = xy + z
3. Half adder (Sum and Carry)
4. Full adder

Example Solution (XOR):

F(x, y) = x ⊕ y = xȳ + x̄y

Circuit:

x ----[NOT]---[AND]---+
                       |----[OR]---- F
y ----[NOT]---[AND]---+
  \           /
   [AND]-----+

Components:

• 2 NOT gates
• 2 AND gates
• 1 OR gate

Task: Design circuits for all four functions.

Learning: Convert Boolean expressions to logic circuits.

Lab Exercise 10: Karnaugh Maps

Topic: Circuit Minimization

Objective: Minimize Boolean functions using K-maps

Problem: Minimize using 3-variable K-map:

1. F(x,y,z) = Σm(0,1,2,5,7)
2. F(x,y,z) = Σm(1,2,3,5,7)
3. F(x,y,z) = Σm(0,2,4,6) + d(1,3)

Example Solution:

F(x,y,z) = Σm(0,1,2,5,7)

K-map:

     yz
x   00  01  11  10
0    1   1   1   1
1    0   1   1   0

Groups:

• x̄ȳ covers (0,1)
• x̄z̄ covers (0,2)
• yz covers (5,7)

Minimized: F = x̄ȳ + x̄z̄ + yz

Task: Minimize all three functions.

Learning: Master K-map technique for minimization.

Lab Exercise 11: Graph Representation

Topic: Graph Models

Objective: Represent graphs using different methods

Problem: For this graph:

1 -- 2
|    |
3 -- 4

Create:

1. Adjacency matrix
2. Adjacency list
3. Edge list
4. Incidence matrix

Example Solution (Adjacency Matrix):

  1  2  3  4
1[0  1  1  0]
2[1  0  0  1]
3[1  0  0  1]
4[0  1  1  0]

Properties:

• Symmetric (undirected graph)
• Diagonal zeros (no self-loops)
• Space: O(V²)

Task: Create all four representations.

Learning: Understand different graph representation methods.

Lab Exercise 12: Graph Traversal

Topic: Graph Algorithms

Objective: Perform DFS and BFS traversals

Problem: Traverse this graph starting from vertex 1:

    1
   /|\
  2 3 4
  |   |
  5   6

1. DFS traversal
2. BFS traversal
3. Draw DFS tree
4. Draw BFS tree

Example Solution (BFS from 1):

Algorithm:

1. Start: Queue = [1], Visited = {}
2. Visit 1: Queue = [2,3,4], Visited = {1}
3. Visit 2: Queue = [3,4,5], Visited = {1,2}
4. Visit 3: Queue = [4,5], Visited = {1,2,3}
5. Visit 4: Queue = [5,6], Visited = {1,2,3,4}
6. Visit 5: Queue = [6], Visited = {1,2,3,4,5}
7. Visit 6: Queue = [], Visited = {1,2,3,4,5,6}

BFS order: 1, 2, 3, 4, 5, 6

Task: Perform both DFS and BFS, draw spanning trees.

Learning: Master graph traversal algorithms.

Lab Exercise 13: Shortest Path

Topic: Dijkstra’s Algorithm

Objective: Find shortest paths in weighted graph

Problem: Find shortest path from A to all vertices:

    A --1-- B
    |       |
    4       2
    |       |
    C --1-- D

Example Solution:

Dijkstra’s Algorithm:

Shortest paths:

• A → A: 0
• A → B: 1 (A-B)
• A → C: 4 (A-C)
• A → D: 3 (A-B-D)

Task: Find all shortest paths from source vertex.

Learning: Apply Dijkstra’s algorithm for shortest paths.

Lab Exercise 14: Minimum Spanning Tree

Topic: MST Algorithms

Objective: Find MST using Kruskal’s and Prim’s

Problem: Find MST for this weighted graph:

    1
   /|\
  1 2 3
 /  |  \
2   3   4

Use both:

1. Kruskal’s algorithm
2. Prim’s algorithm

Example Solution (Kruskal’s):

Steps:

1. Sort edges: 1-2(1), 1-3(2), 2-3(3), 1-4(3)
2. Add 1-2 (weight 1) - no cycle
3. Add 1-3 (weight 2) - no cycle
4. Skip 2-3 (would create cycle)
5. Add 1-4 (weight 3) - no cycle

MST edges: {1-2, 1-3, 1-4} Total weight: 1 + 2 + 3 = 6

Task: Find MST using both algorithms, verify same total weight.

Learning: Master MST algorithms and cycle detection.

Lab Exercise 15: Euler Paths and Circuits

Topic: Eulerian Graphs

Objective: Determine if Euler path/circuit exists

Problem: For each graph, determine:

1. Does Euler circuit exist?
2. Does Euler path exist?
3. If yes, find one

Graph 1:

1 -- 2
|    |
3 -- 4

Example Solution:

Check degrees:

• deg(1) = 2
• deg(2) = 2
• deg(3) = 2
• deg(4) = 2

All degrees even → Euler circuit exists!

One Euler circuit: 1-2-4-3-1

Task: Analyze all given graphs for Euler paths/circuits.

Learning: Apply Euler path/circuit theorems.

Lab Exercise 16: Hamiltonian Paths

Topic: Hamiltonian Graphs

Objective: Find Hamiltonian paths and circuits

Problem: For each graph, determine if Hamiltonian path/circuit exists:

Graph 1: Complete graph K₄ Graph 2: Cycle C₅ Graph 3: Path P₆

Example Solution (K₄):

K₄ is complete:

• Every vertex connected to every other
• Hamiltonian circuit exists: 1-2-3-4-1
• Many other Hamiltonian circuits possible

Total Hamiltonian circuits in Kₙ: (n-1)!/2

For K₄: (4-1)!/2 = 6/2 = 3 distinct circuits

Task: Find Hamiltonian paths/circuits for all graphs.

Learning: Understand Hamiltonian graph properties.

Lab Exercise 17: Tree Properties

Topic: Trees and Forests

Objective: Verify tree properties

Problem: For this tree:

      1
     /|\
    2 3 4
   /|   |
  5 6   7

Calculate:

1. Number of vertices (v)
2. Number of edges (e)
3. Height
4. Number of leaves
5. Verify: e = v - 1

Example Solution:

Count:

• Vertices: v = 7 {1,2,3,4,5,6,7}
• Edges: e = 6 {1-2,1-3,1-4,2-5,2-6,4-7}
• Height: 2 (root to leaf)
• Leaves: 4 {3,5,6,7}

Verify tree property:

• e = v - 1
• 6 = 7 - 1 ✓

Task: Calculate all properties and verify tree equation.

Learning: Understand fundamental tree properties.

Lab Exercise 18: Tree Traversals

Topic: Binary Tree Traversal

Objective: Perform all traversal methods

Problem: For this binary tree:

      1
     / \
    2   3
   / \
  4   5

Find:

1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
4. Level-order traversal

Example Solution:

Preorder (Root-Left-Right):

1. Visit 1
2. Visit left subtree: 2, 4, 5
3. Visit right subtree: 3 Result: 1, 2, 4, 5, 3

Inorder (Left-Root-Right):

1. Visit left subtree: 4, 2, 5
2. Visit root: 1
3. Visit right subtree: 3 Result: 4, 2, 5, 1, 3

Postorder (Left-Right-Root):

1. Visit left subtree: 4, 5, 2
2. Visit right subtree: 3
3. Visit root: 1 Result: 4, 5, 2, 3, 1

Level-order (BFS): Result: 1, 2, 3, 4, 5

Task: Perform all four traversals.

Learning: Master tree traversal algorithms.

Lab Exercise 19: Planar Graphs

Topic: Planarity Testing

Objective: Determine if graphs are planar

Problem: Check planarity of:

1. K₄ (complete graph with 4 vertices)
2. K₅ (complete graph with 5 vertices)
3. K₃,₃ (complete bipartite)

Use:

• Euler’s formula (v - e + f = 2)
• Inequality: e ≤ 3v - 6

Example Solution (K₅):

K₅ properties:

• v = 5 vertices
• e = 10 edges (complete graph)

Test inequality: e ≤ 3v - 6

• 10 ≤ 3(5) - 6
• 10 ≤ 15 - 6
• 10 ≤ 9
• False! ✗

Conclusion: K₅ is NOT planar

Task: Test planarity for all three graphs.

Learning: Apply planarity testing techniques.

Lab Exercise 20: Graph Coloring

Topic: Vertex Coloring

Objective: Color graphs with minimum colors

Problem: Find chromatic number χ(G) for:

Graph 1:

1 -- 2
|    |
3 -- 4

Graph 2: K₄

Graph 3: C₅ (5-cycle)

Example Solution (Graph 1):

Coloring:

• Vertex 1: Red
• Vertex 2: Blue (adjacent to 1)
• Vertex 3: Blue (adjacent to 1, not 2)
• Vertex 4: Red (adjacent to 2 and 3)

Colors used: 2

χ(C₄) = 2 (even cycle)

Task: Find minimum colors for all graphs.

Learning: Apply graph coloring techniques.

Lab Exercise 21: Greedy Coloring

Topic: Coloring Algorithms

Objective: Apply greedy coloring algorithm

Problem: Color this graph using greedy algorithm with order 1,2,3,4,5:

1 -- 2 -- 3
|         |
4 ------- 5

Example Solution:

Greedy algorithm:

1. Color vertex 1: Color 1
2. Color vertex 2: Color 2 (adjacent to 1)
3. Color vertex 3: Color 1 (not adjacent to 1)
4. Color vertex 4: Color 2 (adjacent to 1)
5. Color vertex 5: Color 3 (adjacent to 3 and 4)

Result: 3 colors used

Task: Apply greedy algorithm, try different orderings.

Learning: Understand greedy algorithm behavior and ordering effects.

Lab Exercise 22: Spanning Trees Count

Topic: Cayley’s Formula

Objective: Calculate number of spanning trees

Problem: Find number of labeled spanning trees for:

1. K₃ (complete graph, 3 vertices)
2. K₄ (complete graph, 4 vertices)
3. K₅ (complete graph, 5 vertices)

Example Solution:

Cayley’s Formula: Number of spanning trees in Kₙ = n^(n-2)

For K₄:

• n = 4
• Number = 4^(4-2) = 4² = 16 spanning trees

Verification: K₄ has 6 edges, spanning tree uses 3 edges.

• C(6,3) = 20 ways to choose 3 edges
• But not all form trees (some have cycles)
• Actual count: 16 ✓

Task: Calculate for all three complete graphs.

Learning: Apply Cayley’s formula and understand combinatorics.

Lab Exercise 23: Application Problems

Topic: Real-World Applications

Objective: Solve practical problems using graph theory

Problem 1: Exam Scheduling

5 exams: {A, B, C, D, E}

Student enrollments create conflicts:

• A conflicts with B, C
• B conflicts with A, D
• C conflicts with A, E
• D conflicts with B, E
• E conflicts with C, D

Find minimum time slots needed.

Solution:

Model as graph:

• Vertices = exams
• Edge if exams conflict
• Color = time slot

Graph:

    A
   / \
  B   C
  |   |
  D - E

Greedy coloring:

• A: Slot 1
• B: Slot 2
• C: Slot 2
• D: Slot 1
• E: Slot 3

Minimum slots: 3

Problem 2: Network Design

Connect 4 offices with minimum cable:

Distances:
A-B: 10km
A-C: 15km
A-D: 20km
B-C: 12km
B-D: 18km
C-D: 8km

Find minimum cable needed (MST).

Solution (Kruskal’s):

1. Sort: C-D(8), A-B(10), B-C(12), A-C(15), B-D(18), A-D(20)
2. Add C-D: 8km
3. Add A-B: 10km
4. Add B-C: 12km (connects all)

Total cable: 8 + 10 + 12 = 30km

Task: Solve both application problems.

Learning: Apply graph theory to real-world scenarios.

Summary

Completed 23 lab exercises covering:

Unit 1: Logic & Proofs

• Truth tables
• Logical equivalences
• Predicates and quantifiers
• Proof techniques
• Mathematical induction

Unit 2: Number Theory & Boolean

• GCD computation
• Modular arithmetic
• Boolean simplification
• Logic gates
• Karnaugh maps

Unit 3: Graph Theory

• Graph representation
• Graph traversal (DFS/BFS)
• Shortest paths
• MST algorithms
• Euler and Hamiltonian paths

Unit 4: Advanced Topics

• Tree properties and traversals
• Planar graphs
• Graph coloring
• Cayley’s formula
• Real-world applications

Skills Developed:

• Problem solving
• Algorithm implementation
• Mathematical reasoning
• Proof techniques
• Applied graph theory

Exam Preparation:

• Practice all exercises multiple times
• Understand underlying concepts
• Memorize key formulas and theorems
• Work through examples step-by-step
• Apply techniques to new problems

Good luck with your discrete mathematics studies!