Partially Ordered Sets

Consider a relation R on a set S satisfying the following properties:

R is reflexive, i.e., xRx for every x ∈ S.

R is antisymmetric, i.e., if xRy and yRx, then x = y.
R is transitive, i.e., xRy and yRz, then xRz.
Then R is called a partial order relation, and the set S together with partial order is called a
partially order set or POSET and is denoted by (S, ≤).

Example:

1 The set N of natural numbers form a poset under the relation '≤' because firstly x ≤ x,
secondly, if x ≤ y and y ≤ x, then we have x = y and lastly if x ≤ y and y ≤ z, it implies x ≤ z for all
x, y, z ∈ N.

2 The set N of natural numbers under divisibility i.e., 'x divides y' forms a poset because x/x for
every x ∈ N. Also if x/y and y/x, we have x = y. Again if x/y, y/z we have x/z, for every x, y, z ∈
N.

3 Consider a set S = {1, 2} and power set of S is P(S). The relation of set inclusion ⊆ is a partial
order. Since, for any sets A, B, C in P (S), firstly we have A ⊆ A, secondly, if A ⊆B and B⊆A,
then we have A = B. Lastly, if A ⊆B and B ⊆C,then A⊆C. Hence, (P(S), ⊆) is a poset.

Elements of POSET:
Maximal Element: An element a ∈ A is called a maximal element of A if there is no element in c
in A such that a ≤ c.
Minimal Element: An element b ∈ A is called a minimal element of A if there is no element in c
in A such that c ≤ b.
Note: There can be more than one maximal or more than one minimal element.
Example: Determine all the maximal and minimal elements of the poset whose Hasse diagram
is shown in fig:

Partially Ordered Sets

Solution: The maximal elements are b and f.

The minimal elements are d and e.

Comparable Elements:
Consider an ordered set A. Two elements a and b of set A are called comparable if
 a≤b or b≤a
R R

Non-Comparable Elements:
Consider an ordered set A. Two elements a and b of set A are called non-comparable if neither
a ≤ b nor b ≤ a.

Example: Consider A = {1, 2, 3, 5, 6, 10, 15, 30} is ordered by divisibility. Determine all the
comparable and non-comparable pairs of elements of A.

Solution: The comparable pairs of elements of A are:

{1, 2}, {1, 3}, {1, 5}, {1, 6}, {1, 10}, {1, 15}, {1, 30}
{2, 6}, {2, 10}, {2, 30}
{3, 6}, {3, 15}, {3, 30}
{5, 10}, {5, 15}, {5, 30}
{6, 30}, {10, 30}, {15, 30}

The non-comparable pair of elements of A are:

{2, 3}, {2, 5}, {2, 15}
{3, 5}, {3, 10}, {5, 6}, {6, 10}, {6, 15}, {10, 15}

Linearly Ordered Set:

Consider an ordered set A. The set A is called linearly ordered set or totally ordered set, if every
pair of elements in A is comparable.

Example: The set of positive integers I+ with the usual order ≤ is a linearly ordered set.

Hasse Diagrams
It is a useful tool, which completely describes the associated partial order. Therefore, it is also
called an ordering diagram. It is very easy to convert a directed graph of a relation on a set A to
an equivalent Hasse diagram. Therefore, while drawing a Hasse diagram following points must
be remembered.

The vertices in the Hasse diagram are denoted by points rather than by circles.
Since a partial order is reflexive, hence each vertex of A must be related to itself, so the edges
from a vertex to itself are deleted in Hasse diagram.
Since a partial order is transitive, hence whenever aRb, bRc, we have aRc. Eliminate all edges
that are implied by the transitive property in Hasse diagram, i.e., Delete edge from a to c but
retain the other two edges.
If a vertex 'a' is connected to vertex 'b' by an edge, i.e., aRb, then the vertex 'b' appears above
vertex 'a'. Therefore, the arrow may be omitted from the edges in the Hasse diagram.
The Hasse diagram is much simpler than the directed graph of the partial order.
Example: Consider the set A = {4, 5, 6, 7}. Let R be the relation ≤ on A. Draw the directed graph
and the Hasse diagram of R.

Solution: The relation ≤ on the set A is given by

R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5}, {6, 6}, {7, 7}}

The directed graph of the relation R is as shown in fig:

Hasse Diagrams
To draw the Hasse diagram of partial order, apply the following points:

Delete all edges implied by reflexive property i.e.

(4, 4), (5, 5), (6, 6), (7, 7)
Delete all edges implied by transitive property i.e.
(4, 7), (5, 7), (4, 6)
Replace the circles representing the vertices by dots.
Omit the arrows.

The Hasse diagram is as shown in fig:

Hasse Diagrams
Upper Bound: Consider B be a subset of a partially ordered set A. An element x ∈ A is called
an upper bound of B if y ≤ x for every y ∈ B.

Lower Bound: Consider B be a subset of a partially ordered set A. An element z ∈ A is called a

lower bound of B if z ≤ x for every x ∈ B.

Example: Consider the poset A = {a, b, c, d, e, f, g} be ordered shown in fig. Also let B = {c, d,
e}. Determine the upper and lower bound of B.

Hasse Diagrams
Solution: The upper bound of B is e, f, and g because every element of B is '≤' e, f, and g.

The lower bounds of B are a and b because a and b are '≤' every elements of B.

Least Upper Bound (SUPREMUM):

Let A be a subset of a partially ordered set S. An element M in S is called an upper bound of A if
M succeeds every element of A, i.e. if, for every x in A, we have x <=M

If an upper bound of A precedes every other upper bound of A, then it is called the supremum of
A and is denoted by Sup (A)

Greatest Lower Bound (INFIMUM):

An element m in a poset S is called a lower bound of a subset A of S if m precedes every

element of A, i.e. if, for every y in A, we have m <=y

If a lower bound of A succeeds every other lower bound of A, then it is called the infimum of A
and is denoted by Inf (A)

Example: Determine the least upper bound and greatest lower bound of B = {a, b, c} if they
exist, of the poset whose Hasse diagram is shown in fig:

Hasse Diagrams

Solution: The least upper bound is c.

The greatest lower bound is k.

=====================

Lattices:
Let L be a non-empty set closed under two binary operations called meet and join, denoted by
∧ and ∨. Then L is called a lattice if the following axioms hold where a, b, c are elements in L:

1) Commutative Law: -
(a) a ∧ b = b ∧ a (b) a ∨ b = b ∨ a

2) Associative Law:-
(a) (a ∧ b)∧ c = a ∧(b∧ c) (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) Absorption Law: -
(a) a ∧ ( a ∨ b) = a (b) a ∨ ( a ∧ b) = a

Duality:

The dual of any statement in a lattice (L,∧ ,∨ ) is defined to be a statement that is obtained by
interchanging ∧ an ∨.

For example, the dual of a ∧ (b ∨ a) = a ∨ a is a ∨ (b ∧ a )= a ∧ a

Bounded Lattices:

A lattice L is called a bounded lattice if it has greatest element 1 and a least element 0.

Example:

The power set P(S) of the set S under the operations of intersection and union is a bounded
lattice since ∅ is the least element of P(S) and the set S is the greatest element of P(S).
The set of +ve integer I+ under the usual order of ≤ is not a bounded lattice since it has a least
element 1 but the greatest element does not exist.
Properties of Bounded Lattices:

If L is a bounded lattice, then for any element a ∈ L, we have the following identities:

a∨1=1
a ∧1= a
a ∨0=a
a ∧0=0
Theorem: Prove that every finite lattice L = {a1,a2,a3....an} is bounded.

Proof: We have given the finite lattice:

L = {a1,a2,a3....an}
Thus, the greatest element of Lattices L is a1∨ a2∨ a3∨....∨an.

Also, the least element of lattice L is a1∧ a2∧a3∧....∧an.

Since, the greatest and least elements exist for every finite lattice. Hence, L is bounded.

Sub-Lattices:
Consider a non-empty subset L1 of a lattice L. Then L1 is called a sub-lattice of L if L1 itself is a
lattice i.e., the operation of L i.e., a ∨ b ∈ L1 and a ∧ b ∈ L1 whenever a ∈ L1 and b ∈ L1.

Example: Consider the lattice of all +ve integers I+ under the operation of divisibility. The lattice
Dn of all divisors of n > 1 is a sub-lattice of I+.

Determine all the sub-lattices of D30 that contain at least four elements,
D30={1,2,3,5,6,10,15,30}.

Solution: The sub-lattices of D30 that contain at least four elements are as follows:

1. {1, 2, 6, 30} 2. {1, 2, 3, 30}

3. {1, 5, 15, 30} 4. {1, 3, 6, 30}
5. {1, 5, 10, 30} 6. {1, 3, 15, 30}
7. {2, 6, 10, 30}

Isomorphic Lattices:
Two lattices L1 and L2 are called isomorphic lattices if there is a bijection from L1 to L2 i.e., f:
L1⟶ L2, such that f (a ∧ b) =f(a)∧ f(b) and f (a ∨ b) = f (a) ∨ f (b)

Example: Determine whether the lattices shown in fig are isomorphic.

Solution: The lattices shown in fig are isomorphic. Consider the mapping f = {(a, 1), (b, 2), (c, 3),
(d, 4)}.For example f (b ∧ c) = f (a) = 1. Also, we have f (b) ∧ f(c) = 2 ∧ 3 = 1

Lattices

Distributive Lattice:
A lattice L is called distributive lattice if for any elements a, b and c of L,it satisfies following
distributive properties:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
If the lattice L does not satisfies the above properties, it is called a non-distributive lattice.
Example:
The power set P (S) of the set S under the operation of intersection and union is a distributive
function. Since,
a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
and, also a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) for any sets a, b and c of P(S).
The lattice shown in fig II is a distributive. Since, it satisfies the distributive properties for all
ordered triples which are taken from 1, 2, 3, and 4.
Lattices

Complements and complemented lattices:

Let L be a bounded lattice with lower bound o and upper bound I. Let a be an element if L. An
element x in L is called a complement of a if a ∨ x = I and a ∧ x = 0

A lattice L is said to be complemented if L is bounded and every element in L has a

complement.

Example: Determine the complement of a and c in fig:

Lattices

Solution: The complement of a is d. Since, a ∨ d = 1 and a ∧ d = 0

The complement of c does not exist. Since, there does not exist any element c such that c ∨
c'=1 and c ∧ c'= 0.

Modular Lattice:
A lattice (L, ∧,∨) is called a modular lattice if a ∨ (b ∧ c) = (a ∨ b) ∧ c whenever a ≤ c.

Direct Product of Lattices:

Let (L1 ∨1 ∧1)and (L2 ∨2 ∧2) be two lattices. Then (L, ∧,∨) is the direct product of lattices,
where L = L1 x L2 in which the binary operation ∨(join) and ∧(meet) on L are such that for any
(a1,b1)and (a2,b2) in L.

(a1,b1)∨( a2,b2 )=(a1 ∨1 a2,b1 ∨2 b2)

and (a1,b1) ∧ ( a2,b2 )=(a1 ∧1 a2,b1 ∧2 b2).
Example: Consider a lattice (L, ≤) as shown in fig. where L = {1, 2}. Determine the lattices (L2,
≤), where L2=L x L.

Solution: The lattice (L2, ≤) is shown in fig:

===================

Boolean Algebra:
A complemented distributive lattice is known as a Boolean Algebra. It is denoted by (B,
∧,∨,',0,1), where B is a set on which two binary operations ∧ (*) and ∨(+) and a unary
operation (complement) are defined. Here 0 and 1 are two distinct elements of B.

Since (B,∧,∨) is a complemented distributive lattice, therefore each element of B has a unique
complement.

Properties of Boolean Algebra:

1. Commutative Properties:

(i)a+b = b+a
(ii)a*b=b *a

2. Distributive Properties

(i) a+(b*c)=(a+b)*(a+c)
(ii)a*(b+c)=(a*b)+(a*c)

3. Identity Properties

(i) a+0=a
(ii) a *1=a

4. Complemented Laws:

(i) a+a'=1
 (ii)a * a'=0

Sub-Algebra:
Consider a Boolean-Algebra (B, *, +,', 0,1) and let A ⊆ B. Then (A,*, +,', 0,1) is called a
sub-algebra or Sub-Boolean Algebra of B if A itself is a Boolean Algebra i.e., A contains the
elements 0 and 1 and is closed under the operations *, + and '.

Example: Consider the Boolean algebra D70 whose Hasse diagram is shown in fig:

Clearly, A= {1, 7, 10, 70} and B = {1, 2, 35, 70} is a sub-algebra of D70. Since both A and B are
closed under operation ∧,∨and '.

Note: A subset of a Boolean Algebra can be a Boolean algebra, but it may or may not be
sub-algebra as it may not close the operation on B.
Isomorphic-Boolean Algebras:
Two Boolean algebras B and B1 are called isomorphic if there is a one to one correspondence f:
B⟶B1 which preserves the three operations +,* and ' for any elements a, b in B i.e.,
f (a+b)=f(a)+f(b)
f (a*b)=f(a)*f(b) and f(a')=f(a)'.

Example: The following are two distinct Boolean algebras with two elements which are
isomorphic.

1.The first one is a Boolean Algebra that is derived from a power set P(S) under ⊆ (set
inclusion),i.e., let S = {a}, then B = {P(S), ∪,∩,'} is a Boolean algebra with two elements P(S) =
{∅,{a}}.

2. The second one is a Boolean algebra {B, ∨,∧,'} with two elements 1 and p {here p is a prime
number} under operation divides i.e., let B = {1, p}. So, we have 1 ∧ p = 1 and 1 ∨ p = p also
1'=p and p'=1.

The table shows all the basic properties of a Boolean algebra (B, *, +, ', 0, 1) for any elements a,
b, c belongs to B. The greatest and least elements of B are denoted by 1 and 0 respectively.

1. a ≤b iff a+b=b 2. a ≤b iff a * b = a

3. Idempotent Laws
4. Commutative Property
 (i)a+b=a (i)a+b=b+a
(ii) a * a = a (ii)a*b=b*a
5. Associative Property 6. Absorption Laws
(i)a+(b+c)=(a+b)+c (i)a+(a*b)=a
(ii)a*(b*c)=(a*b)*c (ii)a*(a+b)=a
7. Identity Laws 8. Null Laws
(i) a+0=a (i)a*0=0
(ii) a*1=a (ii)a+1=1
9. Distributive Laws 10. Complement Laws
(i)a*(b+c)=(a*b)+(a*c) (i)0'=1
(ii) a+(b*c) = (a+b)*(a+c) (ii)1'=0
(iii)a+a'=1
(iv)a*a'=0
11. Involution Law 12.De Morgan's Laws
(a')'=a (i)(a *b)'=(a' +b')
(ii) (a+b)'=(a' *b')

Note:
1. 0 ≤ a ≤ 1 for every a ∈ B.
2. Every element b has a unique complement b'.

Boolean Functions:
Consider the Boolean algebra (B, ∨,∧,',0,1). A function from A''to A is called a Boolean
Function if a Boolean Expression of n variables can specify it.

For the two-valued Boolean algebra, any function from [0, 1]n to [0, 1] is a Boolean function.

Example1: The table shows a function f from {0, 1}^3 to {0, 1}

(x, y, z) f
(0, 0, 0) 0
(0, 0, 1) 0
(0, 1, 0) 1
(0, 1, 1) 0
(1, 0, 0) 1
(1, 0, 1) 1
(1, 1, 0) 0
(1, 1, 1) 1
Example2: The table shows a function f from {0, 1, 2, 3}^2 to {0,1,2,3}.

(x, y) f
(0, 0) 1
(0, 1) 0
(0, 2) 0
(0, 3) 3
(1, 0) 1
(1, 1) 1
(1, 2) 0
(1, 3) 3
(2, 0) 2
(2, 1) 0
(2, 2) 1
(2, 3) 1
(3, 0) 3
(3, 1) 0
(3, 2) 0
(3, 3) 2
Note: A function can always be described in tabular form. An alternative way of expressing the
functions is specifying the function by an expression.
===============

Refer:
https://www.javatpoint.com/discrete-mathematics-boolean-algebra