LECTURE NOTES

PROGRAMME – BCA

SEMESTER- II
DISCRETE MATHEMATICS (BCA- 401 )

UNIT III

DISCRETE MATHEMATICS
 Unit-III (10)

Partial order sets: Definition, Partial order sets,

Combination of partial order sets, Hasse diagram.

Lattices: Definition, Properties of lattices – Bounded,

Complemented, Modular and Complete lattice. Boolean

Algebra: Introduction, Axioms and Theorems of Boolean

algebra ,Algebraic manipulation of Boolean expressions.

Simplification of Boolean Functions, Karnaugh maps,

DISCRETE MATHEMATICS
 Logic gates, Digital circuits and Boolean algebra.

DISCRETE MATHEMATICS
 Partial orders, Lattices,
etc.

DISCRETE MATHEMATICS
 In our context…
• We aim at computing properties on programs
• How can we represent these properties? Which kind of algebraic
features have to be satisfied on these representations?
• Which conditions guarantee that this computation terminates?

DISCRETE MATHEMATICS BCA IV SEM

 Motivating Example (1)
• Consider the renovation of the building of a firm.
In this process several tasks are undertaken
– Remove asbestos
– Replace windows
– Paint walls
– Refinish floors
– Assign offices
– Move in office furniture
– …

DISCRETE MATHEMATICS BCA IV SEM

 Motivating Example (2)
• Clearly, some things had to be done before others could begin
– Asbestos had to be removed before anything (except assigning
offices)
– Painting walls had to be done before refinishing floors to avoid
ruining them, etc.
• On the other hand, several things could be done concurrently:
– Painting could be done while replacing the windows
– Assigning offices could be done at anytime before moving in
office furniture
• This scenario can be nicely modeled using partial orderings

DISCRETE MATHEMATICS BCA IV SEM

 Partial Orderings: Definitions
• Definitions:
– A relation R on a set S is called a partial order if it is
• Reflexive
• Antisymmetric
• Transitive
– A set S together with a partial ordering R is called a partially
ordered set (poset, for short) and is denote (S,R)
• Partial orderings are used to give an order to sets that may not have
a natural one
• In our renovation example, we could define an ordering such that
(a,b)R if ‘a must be done before b can be done’

DISCRETE MATHEMATICS BCA IV SEM

 Partial Orderings: Notation
• We use the notation:
– a p b, when (a,b)R
– a p b, when (a,b)R and ab
• The notation p is not to be mistaken for “less than” (p versus ≤)
• The notation p is used to denote any partial ordering

DISCRETE MATHEMATICS BCA IV SEM

 Comparability: Definition

• Definition:
– The elements a and b of a poset (S, p) are called comparable if
either apb or bpa.
– When for a,bS, we have neither apb nor bpa, we say that a,b
are incomparable
• Consider again our renovation example
– Remove Asbestos p ai for all activities ai except assign offices
– Paint walls p Refinish floors
– Some tasks are incomparable: Replacing windows can be done
before, after, or during the assignment of offices

DISCRETE MATHEMATICS BCA IV SEM

 Total orders: Definition
• Definition:
– If (S,p) is a poset and every two elements of S are comparable,
S is called a totally ordered set.
– The relation p is said to be a total order
• Example
– The relation “less than or equal to” over the set of integers (Z, )
since for every a,bZ, it must be the case that ab or ba
– What happens if we replace  with <?

The relation < is not reflexive, and (Z,<) is not a poset

DISCRETE MATHEMATICS BCA IV SEM

 Hasse Diagrams

• Like relations and functions, partial orders have a convenient graphical

representation: Hasse Diagrams
– Consider the digraph representation of a partial order
– Because we are dealing with a partial order, we know that the
relation must be reflexive and transitive
– Thus, we can simplify the graph as follows
• Remove all self loops
• Remove all transitive edges
• Remove directions on edges assuming that they are oriented
upwards
– The resulting diagram is far simpler

DISCRETE MATHEMATICS BCA IV SEM

 Hasse Diagram: Example

a4 a5 a4 a5

a2 a2
a3 a3

a1 a1

DISCRETE MATHEMATICS BCA IV SEM

 Hasse Diagrams: Example (1)
• Of course, you need not always start with the complete relation in
the partial order and then trim everything.
• Rather, you can build a Hasse Diagram directly from the partial
order
• Example: Draw the Hasse Diagram
– for the following partial ordering: {(a,b) | a|b }
– on the set {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}
– (these are the divisors of 60 which form the basis of the ancient
Babylonian base-60 numeral system)

DISCRETE MATHEMATICS BCA IV SEM

 Hasse Diagram: Example (2)

60

12 20 30

4 6 10 15

2 3 5

DISCRETE MATHEMATICS BCA IV SEM

 Example

c d e f

a b

L= {a,b,c,d,e,f,g}
p ={(a,c), (a,e), (b,d), (b,f), (c,g), (d,g), (e,g), (f,g)}RT

(L, p) is a partial order

DISCRETE MATHEMATICS BCA IV SEM

 Example

6 L= N (natural numbers)
5 p ={(0,1), (1,2), (2,3), (3,4), (4,5),…}RT
4
3 (L, p) is a totally ordered set (infinite)
2
1
0

DISCRETE MATHEMATICS BCA IV SEM

 Example

9
8
7
L= N (natural numbers)
6
p ={(n,m):  k such that m=n*k}
5
4 (L, p) is a partially ordered set (infinite)
3
2

DISCRETE MATHEMATICS BCA IV SEM

 Example
• On the same set E={1,2,3,4,6,12} we can define different partial
orders:

12 12
12
6 6
6
4 4 4
3
3 2 2
2 1 3
1 1

DISCRETE MATHEMATICS BCA IV SEM

 Example

• All possible partial orders on a set of three elements

(modulo renaming)

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Summary
We will define the following terms:
• A maximal/minimal element in a poset (S, p)
• The maximum (greatest)/minimum (least) element of a poset (S, p)
• An upper/lower bound element of a subset A of a poset (S, p)
• The greatest lower/least upper bound element of a subset A of a
poset (S, p)

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Maximal
• Definition: An element a in a poset (S, p) is called maximal if it is
not less than any other element in S. That is: (bS (apb))
• If there is one unique maximal element a, we call it the maximum
element (or the greatest element)

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Minimal
• Definition: An element a in a poset (S, p) is called minimal if it is not
greater than any other element in S. That is: (bS (bpa))
• If there is one unique minimal element a, we call it the minimum
element (or the least element)

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Upper Bound
• Definition: Let (S,p) be a poset and let AS. If u is an element of S
such that a p u for all aA then u is an upper bound of A
• An element x that is an upper bound on a subset A and is less than
all other upper bounds on A is called the least upper bound on A.
We abbreviate it as lub.

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Lower Bound
• Definition: Let (S,p) be a poset and let AS. If l is an element of S
such that l p a for all aA then l is an lower bound of A
• An element x that is a lower bound on a subset A and is greater than
all other lower bounds on A is called the greatest lower bound on A.
We abbreviate it glb.

DISCRETE MATHEMATICS BCA IV SEM

 Example

NxN

(x1,y1) N x N (x2,y2)  x1N x2  y1N y2

DISCRETE MATHEMATICS BCA IV SEM

 Example

N´N
upper bounds of Y

Y lub(Y)

glb(Y)

lower bounds of Y

(x1,y1) N x N (x2,y2)  x1N x2  y1N y2

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Example 1
c d

a b

What are the minimal, maximal, minimum, maximum elements?

• Minimal: {a,b}
• Maximal: {c,d}
• There are no unique minimal or maximal elements, thus no
minimum or maximum

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Example 2
Give lower/upper bounds & {d,e,f}
glb/lub of the sets:
• Lower bounds: , thus no glb
{d,e,f}, {a,c} and {b,d} • Upper bounds: , thus no lub

{a,c}
g h i • Lower bounds: , thus no glb
• Upper bounds: {h}, lub: h

d e f
{b,d}
• Lower bounds: {b}, glb: b
a b c • Upper bounds: {d,g}, lub: d
because dpg

DISCRETE MATHEMATICS BCA IV SEM

 Extremal Elements: Example 3

• Minimal/Maximal elements?
i j
• Minimal & Minimum element: a
• Maximal elements: b,d,i,j
f g h
• Bounds, glb, lub of {c,e}?

• Lower bounds: {a,c}, thus glb is c

e
• Upper bounds: {e,f,g,h,i,j}, thus lub is e

b c d • Bounds, glb, lub of {b,i}?

• Lower bounds: {a}, thus glb is c
• Upper bounds: , thus lub DNE
a

DISCRETE MATHEMATICS BCA IV SEM

 Lattices
• A special structure arises when every pair of elements in a poset
has an lub and a glb
• Definition: A lattice is a partially ordered set in which every pair of
elements has both
– a least upper bound and
– a greatest lower bound

DISCRETE MATHEMATICS BCA IV SEM

 Lattices: Example 1

• Is the example from before a i j

lattice?

f g h

• No, because the pair {b,c} e

does not have a least upper
bound

b c d

DISCRETE MATHEMATICS BCA IV SEM

 Lattices: Example 2

• What if we modified it as shown j

here?
i

f g h

• Yes, because for any pair, e

there is an lub & a glb

b c d

DISCRETE MATHEMATICS BCA IV SEM

 A Lattice Or Not a Lattice?
• To show that a partial order is not a lattice, it suffices to find a pair
that does not have an lub or a glb (i.e., a counter-example)
• For a pair not to have an lub/glb, the elements of the pair must first
be incomparable (Why?)
• You can then view the upper/lower bounds on a pair as a sub-Hasse
diagram: If there is no maximum/minimum element in this sub-
diagram, then it is not a lattice

DISCRETE MATHEMATICS BCA IV SEM

 Complete lattices
• Definition:
A lattice A is called a complete lattice if every subset S of A admits a
glb and a lub in A.

• Exercise:
Show that for any (possibly infinite) set E, (P(E),) is a complete
lattice
(P(E) denotes the powerset of E, i.e. the set of all subsets of E).

DISCRETE MATHEMATICS BCA IV SEM

 Example

Y
c d e f

a b
L= {a,b,c,d,e,f,g}
 ={(a,c), (a,e), (b,d), (b,f), (c,g), (d,g), (e,g), (f,g)}T

(L,) is not a lattice:

a and b are lower bounds of Y, but a and b are not comparable

DISCRETE MATHEMATICS BCA IV SEM

 Exercise

• Prove that “Every finite lattice is a complete lattice”.

DISCRETE MATHEMATICS BCA IV SEM

 Example

{1,2,3}

lub(Y)

{1,2} {1,3} {2,3}

Y

{1} {2} {3}

L= ({1,2,3})
p= 
lub(Y) = Y glb(Y)
glb(Y) = Y

DISCRETE MATHEMATICS BCA IV SEM

 Example

-4 -3 -2 -1 0 1 2 3 4


L= Z  {T,} 
nZ : p n pT

DISCRETE MATHEMATICS BCA IV SEM

 Example

L= Z+
6
p total order on Z+
5
lub = max
4
glb = min
3
2
It is a lattice, but not complete: 1
For instance, the set of even numbers has no lub 0

37
DISCRETE MATHEMATICS BCA IV SEM
 Example

L= Z+  {T}
6
p total order on Z+  {T}
5
lub = max
4
glb = min
3
2
This is a complete lattice 1
0

DISCRETE MATHEMATICS BCA IV SEM

 Examples

L=R (real numbers) with p =  (total order)

(R,  ) is not a complete lattice:
for instance {x  R | x > 2} has no lub
On the other hand,
for each x<y in R, ([x,y],  ) is a complete lattice

L=Q (rational numbers) with p =  (total order)

(Q,  ) is not a complete lattice
The set {x  Q | x2 < 2} has upper bounds but there is no
least upper bound in Q.

DISCRETE MATHEMATICS BCA IV SEM

 • Theorem:
Let (L, p) be a partial order. The following conditions are
equivalent:
1. L is a complete lattice
2. Each subset of L has a least upper bound
3. Each subset of L has a greatest lower bound

• Proof:
– 1  2 e 1  3 by definition
– In order to prove that 2  1, let us define for each Y  L
glb(Y) = lub({l L |  l’  Y : l  l’})

DISCRETE MATHEMATICS BCA IV SEM

 upper bounds of Z

{1,2,3}
glb(Y)= lub({l L |  l’  Y : l  l’})

Y
{1,2} {1,3} {2,3}

lub(Z) {1} {2} {3}

Z= {l L |  l’  Y : l  l’} 


DISCRETE MATHEMATICS BCA IV SEM

 Functions on partial orders
• Let (P,P) and (Q,Q) two partial orders. A function  from P to Q is
said:

• monotone (order preserving) if

p1 P p2  p1 Q p2


• embedding if
p1 P p2  p1 Q p2


• Isomorphism if it is a surjective embedding

DISCRETE MATHEMATICS BCA IV SEM

 Examples

b d 1a  1 is not monotone

1d
a c 1b1c

e
d 2d2e  2 is monotone, but it is not
 b c
b c 2 2 an embedding:2bQ2c
2a but it is not true that bPc
a

DISCRETE MATHEMATICS BCA IV SEM

 Examples
e
d 3e   3 is monotone but it is not
3c3d an embedding:3bQ3c
b c but it is not true that bPc
3a3b
a 
4d 
 
d  4 is an embedding, but not
  an isomorphism.
b c 4c
4b
a 4a

DISCRETE MATHEMATICS BCA IV SEM

 Isomorphism

j j’

i g h g’
i’ h’

f
d’
d e’ f’
e

b b’
a
a’

c
c’

DISCRETE MATHEMATICS BCA IV SEM

Monotone? Embedding? Isomorphism?

  from (Z, ) to (Z, ), defined by: (x)=x+1

1
  from((S), ) to 0 , defined by:
(U)=1 if U is nonempty, ()=0.

  from ((Z), ) to ((Z), ) , defined by:

(U)={1} if 1  U
(U)={2} if 2  U and 1 does not belong to U
(U)=  otherwise

DISCRETE MATHEMATICS BCA IV SEM

 Ascending chains

• A sequence (ln)nN of elements in a partial order L is an

ascending chain if
n  m  ln lm

• A sequence (ln)nN converges if and only if

 n0N :  nN : n0  n  ln 0  ln

• A partial order (L,) satisfes the ascending chain condition

(ACC) iff each ascending chain converges.

DISCRETE MATHEMATICS BCA IV SEM

 Example

• The set of even natural

12 numbers satisfies the
10 descending chain condition,
8
but not the ascending chain
condition
6
4
2
0

DISCRETE MATHEMATICS BCA IV SEM

 Example

• Infinite set
• Satisfies both ACC and
... DCC

DISCRETE MATHEMATICS BCA IV SEM

 Lattices and ACC
• If P is a lattice, it has a bottom element and satisfies ACC, tyen it is
a complete lattice

• If P is a lattice without infinite chains, then it is complete

DISCRETE MATHEMATICS BCA IV SEM

 Continuity
• In Calculus, a function is continuous if it preserves the limits.
• Given two partial orders (P,P) and (Q,Q), a functoin  from P to Q
is continuous id for every chain S in P

lubS  lub{ (x) | xS }

(P,P)  (Q,Q)

S
(S)

DISCRETE MATHEMATICS BCA IV SEM

 Fixpoints

• Consider a monotone function f: (P,P)  (P,P) on a partial

order P.

• An element x of P is a fixpoint of f if f(x)=x.

• The set of fixpoints of f is a subset of P called Fix(f):

Fix(f) ={ l  P | f(l)=l}

DISCRETE MATHEMATICS BCA IV SEM

 Fixpoint on Complete Lattices

• Consider a monotone function f:LL on a complete lattice L.

• Fix(f) is also a complete lattice:

lfp(f) = glb(Fix(f))  Fix(f)

gfp(f) = lub(Fix(f))  Fix(f)

• Tarski Theorem:
Let L be a complete lattice. If f:LL is monotone then
lfp(f) = glb{ l  L | f(l)  l }
gfp(f) = lub{ l  L | l  f(l) }

DISCRETE MATHEMATICS BCA IV SEM

 Fixpoints on Complete Lattices

{ l  L | f(l) P l}

gfp(f) = lub{ l  L | l  f(l) }

Fix(f) ={ l  L | f(l)=l}
lfp(f) = glb{ l  L | f(l)  l }

{ l  L | l P f(l)}

DISCRETE MATHEMATICS BCA IV SEM

 Kleene Theorem
• Let f be a monotone function: (P,P)  (P,P) on a complete lattice P.
Let = n0 f n()

– If Fix(f) then = lfp(f)

– Kleene Theorem
If f is continuous then the least fixpoint of f esists , and it is equal
to 

DISCRETE MATHEMATICS BCA IV SEM