Unit III: Ordering Relations, Lattices and Boolean Algebra
Course: Discrete Mathematics
Code: CADSC102
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.