Posets, Hasse Diagram and Lattices

The concepts of Partially Ordered Sets (Posets), Hasse Diagrams, and Lattices are important topics in discrete mathematics. These concepts are widely used in data structures, databases, operating systems, compiler design, and optimization problems. Questions from this unit are frequently asked in MCA semester examinations.

Partial Ordered Sets (Posets)

Let A be a non-empty set and R be a relation on A. The pair (A, R) is called a Partially Ordered Set (Poset) if the relation R satisfies the following three properties:

Reflexive: (a, a) ∈ R for all a ∈ A
Antisymmetric: If (a, b) ∈ R and (b, a) ∈ R, then a = b
Transitive: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R

The relation R is called a partial order relation.

Examples of Posets

(ℕ, ≤) – Natural numbers with less than or equal to relation
(P(S), ⊆) – Power set with subset relation
(A, |) – Set of integers with divisibility relation

Comparable and Incomparable Elements

Two elements a and b are comparable if aRb or bRa
If neither aRb nor bRa holds, then a and b are incomparable

Minimal, Maximal, Least and Greatest Elements

Minimal element: No element is strictly smaller than it
Maximal element: No element is strictly greater than it
Least element: Smaller than or equal to every element
Greatest element: Greater than or equal to every element

Exam Note: A poset may have more than one minimal or maximal element but only one least or greatest element.

Combination of Partial Ordered Sets

Product of Posets

If (A, R₁) and (B, R₂) are two posets, then their product poset is defined on A × B as:

(a₁, b₁) ≤ (a₂, b₂) if and only if:

a₁ R₁ a₂ and
b₁ R₂ b₂

This is also known as the Cartesian product of posets.

Subposet

A subposet is a subset of a poset that itself forms a poset under the same partial order relation.

Hasse Diagram

A Hasse diagram is a graphical representation of a finite poset. It simplifies the representation of a partial order relation.

Rules for Drawing Hasse Diagram

Do not show reflexive relations
Do not show transitive relations
Represent elements by points
Draw lines upward to show ordering

Example

For the set A = {1, 2, 3, 6} with relation "divides":

1 divides 2, 3, and 6 2 divides 6 3 divides 6

The Hasse diagram places 1 at the bottom and 6 at the top.

Advantages of Hasse Diagram

Easy visualization of posets
Helps identify minimal, maximal, least, and greatest elements
Useful in solving lattice-related problems

Introduction to Lattices

A lattice is a poset (L, ≤) in which every pair of elements has:

A least upper bound (LUB) or join (∨)
A greatest lower bound (GLB) or meet (∧)

Join and Meet

Join (a ∨ b): Smallest element greater than or equal to both a and b
Meet (a ∧ b): Greatest element less than or equal to both a and b

Example of Lattice

(P(S), ⊆) where:

Join = Union (∪)
Meet = Intersection (∩)

Properties of Lattices

(a) Bounded Lattice

A lattice is said to be bounded if it has:

A least element (0)
A greatest element (1)

Example: Power set lattice

(b) Complemented Lattice

A bounded lattice is complemented if for every element a, there exists an element b such that:

a ∧ b = 0
a ∨ b = 1

(c) Modular Lattice

A lattice is modular if it satisfies the modular law:

If a ≤ c, then: a ∨ (b ∧ c) = (a ∨ b) ∧ c

(d) Complete Lattice

A lattice is said to be complete if every subset of the lattice has:

A join (supremum)
A meet (infimum)

Example: Power set of any set is a complete lattice

Difference Between Poset and Lattice

Basis	Poset	Lattice
Meet and Join	Not necessary	Always exist
Structure	Partial order	Special poset
Example	(ℕ, ≤)	(P(S), ⊆)

Exam-Oriented Important Points

Definition of poset is a frequently asked question
Hasse diagram construction is important for numericals
Lattice properties often appear as long-answer questions
Difference between modular and complemented lattice is important

Conclusion

Posets, Hasse diagrams, and lattices form an important theoretical foundation for computer science. For MCA students, mastering these topics is essential for understanding advanced concepts in discrete structures and system design.

Boolean Algebra

Boolean Algebra is a mathematical structure used to analyze and simplify logical expressions. It deals with variables that take only two possible values: 0 (False) and 1 (True). Boolean algebra is the backbone of digital electronics, computer hardware, logic circuits, switching theory, and programming logic.

For MCA students, this topic is highly important from both theory and problem-solving (K-map, logic gates) perspectives.

Basic Elements of Boolean Algebra

Boolean Variables

Variables take values: 0 or 1
Common variables: A, B, C, X, Y

Boolean Operators

OR (+)
AND (·)
NOT (′ or ¯)

Axioms (Postulates) of Boolean Algebra

A Boolean algebra consists of a set B with two binary operations (+, ·) and one unary operation (′) satisfying the following axioms:

Axiom 1: Closure

For all a, b ∈ B:

a + b ∈ B
a · b ∈ B

Axiom 2: Identity Elements

a + 0 = a
a · 1 = a

Axiom 3: Commutative Laws

a + b = b + a
a · b = b · a

Axiom 4: Associative Laws

a + (b + c) = (a + b) + c
a · (b · c) = (a · b) · c

Axiom 5: Distributive Laws

a · (b + c) = (a · b) + (a · c)
a + (b · c) = (a + b) · (a + c)

Axiom 6: Complement Law

a + a′ = 1
a · a′ = 0

Theorems of Boolean Algebra

Identity Laws

A + 0 = A
A · 1 = A

Null Laws

A + 1 = 1
A · 0 = 0

Idempotent Laws

A + A = A
A · A = A

Complement Laws

A + A′ = 1
A · A′ = 0
(A′)′ = A

Absorption Laws

A + (A · B) = A
A · (A + B) = A

De Morgan’s Theorems (Very Important)

(A + B)′ = A′ · B′
(A · B)′ = A′ + B′

Boolean Functions

A Boolean function is an expression formed using Boolean variables, constants (0,1), and operators (+, ·, ′).

Example: F(A, B, C) = A′B + BC′ + AC

Types of Representation

Algebraic expression
Truth table
Logic circuit

Simplification of Boolean Functions

Need for Simplification

Reduces number of logic gates
Reduces cost and power consumption
Improves speed of circuits

Methods of Simplification

Algebraic Method
Karnaugh Map (K-map) Method

Algebraic Simplification Example

F = A + A·B Using absorption law: F = A

Karnaugh Maps (K-Maps)

A Karnaugh Map is a graphical method used to simplify Boolean functions with up to 4 or 5 variables easily.

Types of K-Maps

2-variable K-map (4 cells)
3-variable K-map (8 cells)
4-variable K-map (16 cells)

Steps to Solve K-Map

Draw the K-map
Enter 1s (minterms) or 0s (maxterms)
Make groups of 1s in powers of 2 (1,2,4,8)
Write simplified Boolean expression

Advantages of K-Maps

Simple and fast method
Reduces Boolean expressions to minimum form
Very useful in exam numericals

Logic Gates

Logic gates are electronic circuits that perform Boolean operations.

Basic Logic Gates

Gate	Symbol	Boolean Expression
AND	·	Y = A · B
OR	+	Y = A + B
NOT	′	Y = A′

Universal Gates

Gate	Expression
NAND	(A · B)′
NOR	(A + B)′

Exam Note: Any Boolean function can be implemented using only NAND or only NOR gates.

Other Gates

XOR: A′B + AB′
XNOR: AB + A′B′

Difference Between Logic Gates

Basis	AND Gate	OR Gate
Output	1 if all inputs are 1	1 if any input is 1

Exam-Oriented Important Points

Axioms and De Morgan’s laws are frequently asked
Boolean simplification is important for numericals
K-map questions carry high weightage
Universal gates are important for short notes

Conclusion

Boolean algebra is a core subject for MCA students as it forms the foundation of digital logic and computer hardware. Mastery of this topic helps in understanding circuit design and logical reasoning.

Posets, Hasse Diagram and Lattices