Unit III: Ordering Relations, Lattices and Boolean Algebra

Course: Discrete Mathematics
Code: CADSC102

Table of Contents

Partial Ordering and Equivalence Relations
Lattices and Their Properties
Bounded, Distributive, and Complemented Lattices
Introduction to Boolean Algebra
Boolean Functions and Minimization
Exam Focus: Tips & FAQs

Ordering Relations

Ordering relations define how elements in a set are compared or ranked.

Partial Ordering Relations

A relation R on a set A is a Partial Ordering if it is Reflexive, Anti-symmetric, and Transitive.

Reflexive: a R a for all a in A.
Anti-symmetric: If a R b and b R a, then a = b.
Transitive: If a R b and b R c, then a R c.

Equivalence Relations

A relation is an Equivalence Relation if it is Reflexive, Symmetric, and Transitive. It partitions a set into disjoint equivalence classes.

Lattices and Their Properties

Definition: A Lattice is a partially ordered set in which every pair of elements has a unique Least Upper Bound (LUB or Join) and a unique Greatest Lower Bound (GLB or Meet).

Lattice Operations

Join (v): The Least Upper Bound (LUB).
Meet (^): The Greatest Lower Bound (GLB).

Special Types of Lattices

Bounded Lattices: A lattice that has both a greatest element (represented as 1) and a least element (represented as 0).
Distributive Lattices: A lattice in which the meet and join operations distribute over each other (e.g., a ^ (b v c) = (a ^ b) v (a ^ c)).
Complemented Lattices: A bounded lattice where every element has a complement (an element b such that a v b = 1 and a ^ b = 0).

Introduction to Boolean Algebra

Boolean algebra is a complemented distributive lattice. It provides the mathematical foundation for digital logic and computer circuitry.

Properties of Boolean Algebra

Identity Laws: a v 0 = a and a ^ 1 = a.
Commutative Laws: a v b = b v a and a ^ b = b ^ a.
Complement Laws: a v a' = 1 and a ^ a' = 0.

Boolean Functions and Minimization

Boolean functions represent logical operations on binary variables.

Representation and Minimization

Representation: Boolean functions can be represented using Truth Tables or algebraic expressions.
Minimization: The process of simplifying a Boolean expression to its simplest form to reduce the number of logic gates in a circuit.

Exam Focus & Tips

Exam Tip: Be ready to prove whether a given Hasse diagram represents a Lattice by checking if every pair has a LUB and GLB.
Common Pitfall: Do not assume every Poset is a Lattice. Look for "dangling" pairs that lack a common upper or lower bound.
Formula Tip: Memorize the Distributive Law as it is central to Boolean algebra proofs.

Frequently Asked Questions

Q: What is a Complement in a Lattice?
A: It is an element that, when joined with the original, gives the top (1), and when met, gives the bottom (0).

Q: When is a Lattice called "Bounded"?
A: When it contains both a global maximum and a global minimum.