✅ UNIT 4 — POSET, LATTICES & BOOLEAN ALGEBRA (DISCRETE MATHEMATICS)

 

✅ UNIT 4 — POSET, LATTICES & BOOLEAN ALGEBRA

1. Poset

Partially Ordered Set
A pair (A, ≤) where relation is:

• Reflexive

• Anti-symmetric

• Transitive

Toset: Totally ordered set

Every pair comparable.

Woset: Well-ordered set

Totally ordered + every non-empty subset has least element.

---

2. Topological Sorting

Linear ordering of vertices of a DAG respecting dependencies.

---

3. Hasse Diagram

Graphical representation of a poset showing cover relations (without loops or direction).

---

4. Extremal Elements

• Minimum element

• Maximum element

• Minimal elements

• Maximal elements

---

5. Lattices

A poset where every pair has:

• Least Upper Bound (LUB / join ∨)

• Greatest Lower Bound (GLB / meet ∧)

Semi-lattice

Only meet or only join exists.

Properties

• Idempotent

• Commutative

• Associative

• Absorption laws

---

6. Types of Lattices

• Distributive lattice

• Modular lattice

• Boolean lattice (special case)

---

7. Boolean Algebra

Defined with two operations:

• AND (·)

• OR (+)

• NOT (')

Elements usually {0,1}.

Important Laws

• Identity

• Complement

• Idempotent

• Associative

• Distributive

• De Morgan’s laws

  $$(A+B)' = A'B' \quad ;\quad (AB)' = A' + B'$$

✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS (DISCRETE MATHEMATICS)

 

✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS

A. Relations

Definition

A relation R from A to B is a subset of A×B.

Representation

• List of ordered pairs

• Matrix representation

• Directed graph

Operations

• Union

• Intersection

• Composition (R ∘ S)

• Inverse relation (R⁻¹)

Types of Relations

1. Reflexive: (a,a) ∈ R for all a

2. Symmetric: (a,b) ⇒ (b,a)

3. Transitive: (a,b) & (b,c) ⇒ (a,c)

4. Anti-symmetric

---

Counting Relations

If A has n elements:

Total possible relations =

$$2^{n^2}$$

---

Closure of Relations

• Reflexive closure = R ∪ {(a,a)}

• Symmetric closure = R ∪ R⁻¹

• Transitive closure = Add pairs until transitivity satisfied (Warshall)

---

Equivalence Relation

When R is:

• Reflexive

• Symmetric

• Transitive

Then A is partitioned into equivalence classes.

---

Partial Order Relation

R is:

• Reflexive

• Anti-symmetric

• Transitive

Forms a poset.

---

Power of a Relation

Rⁿ = R composed with itself n times.

---

Functions

Definition

A function f: A → B assigns each element in A to exactly one element in B.

Terms

• Domain

• Co-domain

• Range

Types

• One-one (Injective)

• Onto (Surjective)

• Bijective

• Constant

• Identity function

---

Counting Functions

From set A (m elements) to B (n elements):

$$n^m \text{ functions}$$

---

Inverse Function

Exists only for bijective functions.

---

Composition

If f: A→B and g: B→C
Then g∘f: A→C.

---

Group Theory (Basics)

A set G with binary operation * is a group if:

1. Closure

2. Associativity

3. Identity element

4. Inverse exists for all elements

If operation is commutative → Abelian group.

✅ UNIT 2 — COMBINATORICS (DISCRETE MATHEMATICS)

 

✅ UNIT 2 — COMBINATORICS

1. Permutations & Combinations

Permutation

Arrangement of objects where order matters.

• Formula:

  $$^nP_r = \frac{n!}{(n-r)!}$$

Example:
Number of ways to arrange 3 letters from ABCD
= $^4P_3 = 24$

Combination

Selection of objects where order does NOT matter.

• Formula:

  $$^nC_r = \frac{n!}{r!(n-r)!}$$

Example:
Choose 2 students from 5
= $^5C_2 = 10$

---

2. Summation

Properties of Σ:

• Linearity:
  $\sum (a_i + b_i) = \sum a_i + \sum b_i$

• Constant factor:
  $\sum c\cdot a_i = c\sum a_i$

---

3. Binomial Function

Binomial Theorem:

$$(a + b)^n = \sum_{k=0}^{n} {^nC_k a^{n-k} b^k}$$

Properties:

• Number of terms = n+1

• Middle term depends on n (odd/even)

• Coefficients symmetric:

  $$^nC_k = ^nC_{n-k}$$

---

4. Generating Functions

Used in recurrence and combinatorics.

Basic idea:

If we have sequence {a₀, a₁, a₂, …}
Generating function is:

$$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$$

Example: For sequence 1,1,1,1,…

$$G(x) = \frac{1}{1 - x}$$

---

5. Recurrence Relation

Example: Fibonacci

$$f(n) = f(n-1) + f(n-2)$$

Solving Linear Recurrences

General form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2}$$

Steps:

1. Form characteristic equation

   $$r^2 - c_1 r - c_2 = 0$$

2. Find roots r₁, r₂

3. General solution:

   $$a_n = A r_1^n + B r_2^n$$

✅ 1. CACHE MAPPING NUMERICAL (Direct Mapping) NUMERICALS

 

✅ 1. CACHE MAPPING NUMERICAL (Direct Mapping)

Q1.

A computer has:

• Main memory = 4K words

• Cache = 128 words

• Block size = 4 words

Find:

1. No. of blocks in main memory

2. No. of lines in cache

3. Mapping of memory block 205 to cache line.

---

Solution

1) Blocks in main memory

Main memory size = 4K = 4096 words
Block size = 4 words

$$\text{No. of blocks} = \frac{4096}{4} = 1024$$

---

2) Cache lines

Cache size = 128 words
Block size = 4 words

$$\text{Cache lines} = \frac{128}{4} = 32$$

---

3) Mapping of block 205

Direct mapping:

$$\text{Cache line} = \text{Block number} \mod \text{No. of lines}$$ $$205 \mod 32 = 13$$

✔ Answer:

Block 205 maps to cache line 13.

---

✅ 2. SET-ASSOCIATIVE CACHE NUMERICAL

Q2.

8 KB cache, block size = 64 bytes, 4-way set associative.
Find number of sets.

---

Solution

Cache size = 8 KB = 8192 bytes
Block size = 64 bytes

1 set has 4 blocks (because 4-way).

Total blocks =

$$\frac{8192}{64} = 128$$

No. of sets =

$$\frac{128}{4} = 32$$

✔ Answer:

32 sets

---

✅ 3. MEMORY INTERLEAVING

Q3.

A system has 4 memory banks using lower-order interleaving.
Words are stored starting from address 0.
Find the bank number for address: 37.

---

Solution

Lower-order interleaving:

$$\text{Bank} = \text{Address} \mod \text{No. of banks}$$

Here:
37 mod 4 = 1

✔ Answer:

Address 37 is in Bank 1.

---

✅ 4. EFFECTIVE ACCESS TIME (EAT)

Q4.

Hit ratio = 90%
Cache access time = 10 ns
Main memory access = 100 ns

Find EAT.

---

Solution

$$EAT = (Hit\ Ratio \times Cache\ Time) + (Miss\ Ratio \times Memory\ Time)$$

Hit ratio = 0.9
Miss ratio = 1 – 0.9 = 0.1

$$EAT = (0.9 \times 10) + (0.1 \times 100)$$ $$= 9 + 10 = 19\ \text{ns}$$

✔ Answer:

19 ns

---

✅ 5. PIPELINE THROUGHPUT

Q5.

A pipeline has 5 stages, each taking 20 ns.
Calculate time to execute 10 instructions.

---

Solution

Pipeline time =

$$kT + (n - 1)T$$

k = stages = 5
T = 20 ns
n = instructions = 10

$$= 5(20) + 9(20)$$ $$= 100 + 180 = 280\ \text{ns}$$

✔ Answer:

280 ns

---

✅ 6. BINARY → EXCESS-3 NUMERICAL

Q6.

Convert 75 (decimal) into Excess-3 code.

---

Solution

Digits: 7 and 5

Step 1 → Convert to BCD:
7 → 0111
5 → 0101

Step 2 → Add 3 (0011) to each:

0111 + 0011 = 1010
0101 + 0011 = 1000

✔ Answer:

75 = 1010 1000 (Excess-3)

---

✅ 7. BINARY MULTIPLICATION (Booth’s Algorithm)

Q7.

Multiply: (+7) × (−3) using Booth’s algorithm.
(Short exam-style solution.)

---

Solution Summary

7 = 0111
−3 = 1101 (2’s complement)

Perform Booth steps → final answer:

✔ Answer:

(+7) × (−3) = −21
Binary result: 1010 1011

---

✅ 8. ADDRESSING MODE NUMERICAL

Q8.

Effective address = ?
Instruction: MOV A, M
HL register pair = 2050H

---

Solution

Indirect addressing:
Address = content of HL.

✔ Answer:

EA = 2050H

---

✅ 9. MEMORY SIZE CALCULATION

Q9.

How many bytes in a memory with 16-bit address bus?

---

Solution

No. of addressable locations =

$$2^{16} = 65536$$

Each location stores 1 byte.

✔ Answer:

64 KB

---

✅ 10. CACHE TAG CALCULATION

Q10.

Find tag, set, and block offset for:

• Cache = 4 KB

• Block size = 32 bytes

• 2-way associative

• 16-bit address

---

Solution Steps

1. Cache size = 4096 bytes
   Block size = 32 →
   Blocks = 4096 / 32 = 128 blocks

2. 2-way set associative →
   Sets = 128 / 2 = 64 sets

3. Set bits = log₂(64) = 6 bits

4. Offset bits = log₂(32) = 5 bits

5. Tag bits = 16 – (6 + 5) = 5 bits

---

✔ Final Answer:

• Tag = 5 bits

• Set = 6 bits

• Offset = 5 bits