Cartesian Product
● Cartesian Product: - of two sets A and B in the set of all ordered pairs, whose first
member belongs to the first set and second member belongs to the second set, denoted
by A * B.
● It is a kind of maximum relation possible, where every member of the first set belong to
every member of the second set. A*B = {(a, b) | a ∈ A and b ∈ B}
● For E.g. if A = {a, b}, B = {1, 2, 3}, A*B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
● In general, commutative law does not hold good A* B != B*A
● If |A| = m and |B| = n then |A*B| = m.n
Q Let A be a finite set of size n. The number of elements in the power set of A×A is: (GATE-
1993) (1 Marks)
a) 2^(2^n) b) 2^(n^2) c) 2^n
d) 2^n e) None of the above
Answer: (B)
Relation
● Relation: - Let A and B are sets then every subset of ‘A*B’ is called a relation from A to B.
● If |A| =m and |B| = n then total no of element(pair) will be m*n, every element will
have two choice weather to present or not present in the subset(relation), therefore the
total number of relation possible is 2m.n.
● Largest relation possible will be A*B
● Smallest possible relation will be ɸ
● Complement of a relation: - Let R be a relation from A to B, then the complement of
relation will be denoted by R’, RC or R. R = {(a,b)|(a,b) ϵ A*B, (a,b) ϵ! R}
o R’ = (A*B) – R
o R U R’ = A*B
o R ⋂ R’ = ɸ
● For E.g. if A*B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}, R= {(a, 1), (a, 3), (b, 2)}, R’
= {(a, 2), (b, 1), (b, 3)}
● Inverse of a relation: - Let R be a relation from A to B, then the inverse of relation will be
a relation from B to A, denoted by R-1. R-1 = {(b, a) | (a, b) ∈ R}
● A*B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
● R = {(a, 1), (a, 3), (b, 2)}
● R-1 = {(1, a), (3, a), (2, b)}
● |R|=| R-1 |
Diagonal relation: - A relation R on a set A is said to be diagonal relation if, R is a set of all
ordered pair (x,x), for every ∀x ∈ A, sometimes it is also denoted by ▲A
R = {(x, x) | ∀ x ∈ A}
Q The number of binary relations on a set with n elements is: (GATE-1999) (1 Marks)
(A) n² (B) 2^n (C) 2^n² (D) None of the above
Answer: (C)
Types of a Relation
• To further study types of relations, we consider a set A with n elements, then a cartesian
product A*A will have n2 elements(pairs). Therefore, total number of relation possible is
2n * n
• Reflexive relation: - A relation R on a set A with cartesian product A*A is said to be
reflexive,
o If ∀ x ∈ A
o (x, x) ∈ R
• Smallest reflexive relation is ▲A
• Largest reflexive relation is A*A
• Total number of reflexive relations will be 2n(n-1)
Q What is the possible number of reflexive relations on a set of 5 elements? (GATE-2010) (1
Marks)
(A) 210 (B) 215 (C) 220 (D) 225
Answer: (C)
• Irreflexive relation: - A relation R on a set A with cartesian product A*A is said to be
Irreflexive,
o If ∀ x ∈ A
o (x, x) ∉ R
• Smallest irreflexive relation is ɸ
• Largest irreflexive relation is (A*A) - ▲A
• Total number of irreflexive relation will be 2n(n-1)
Q consider a set A = {1,2,3}, find which of the following relations are reflexive and
Irreflexive?
Relation Reflexive Irreflexive
A*A Yes No
ɸ No Yes
{(1,1), (2,2), (3,3)} Yes No
{(1,2), (2,3), (1,3)} No Yes
{(1,1), (1,2), (2,1), (2,2)} No No
{(1,1), (2,2), (3,3), (1,3), (2,1)} yes No
{(1,3), (2,1), (2,3), (3,2)} no yes
If a relation R on a set A is reflexive, then RC is Irreflexive
• If two relations R1 and R2 are reflexive then their union and intersection will also be
reflexive.
• If two relations R1 and R2 are Irreflexive then their union and intersection will also be
Irreflexive.
Q Suppose that R1 and R2 are reflexive relations on a set A. Which of the following
statements is correct? (NET-July-2016)
a) R1 ∩ R2 is reflexive and R1 ∪ R2 is irreflexive.
b) R1 ∩ R2 is irreflexive and R1 ∪ R2 is reflexive.
c) Both R1 ∩ R2 and R1 ∪ R2 are reflexive.
d) Both R1 ∩ R2 and R1 ∪ R2 are irreflexive
Ans: c
Symmetric relation: - A relation R on a set A with cartesian product A*A is said to be
Symmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
……………………………
then (b, a) ∈ R
……………………………
• If a relation on a set A is symmetric then R = R-1
• If two relations R1 and R2 are symmetric then their union and intersection will also
be symmetric.
• Smallest symmetric relation is ɸ
• Largest symmetric relation is A*A
• Total number of symmetric relation will be 2[n(n+1)]/2
Anti-Symmetric relation: - A relation R on a set A with cartesian product A*A is said to be
Anti-Symmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
(b, a) ∈ R
……………………………
a=b
……………………………
Conclusion: Symmetry is not allowed but diagonal pairs are allowed
• A relation R on a set A is Anti-Symmetric if (R ⋂ R-1) ⊑ ▲A
• Sub set of a Anti-Symmetric will also be Anti-Symmetric
• If two relations R1 and R2 are Anti - symmetric then their union need not to be Anti-
symmetric but intersection will also be Anti-symmetric.
• Smallest Anti-symmetric relation is ɸ
• Largest Anti-symmetric relation will contain n(n+1)/2 elements
• Total number of Anti-symmetric relation will be 2n *3[n(n-1)]/2
Asymmetric relation: - A relation R on a set A with cartesian product A*A is said to be
Asymmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
……………………………
(b, a) ∉ R
……………………………
Conclusion: Symmetry is not allowed; even diagonal pairs are not allowed
Every asymmetric relation is also anti-symmetric
• Smallest Asymmetric relation is ɸ
• Largest Asymmetric relation will contain n(n-1)/2 elements
• Total number of Asymmetric relation will be 3[n(n-1)]/2
Relation Symmetric Anti-Symmetric Asymmetric
A*A Y N N
ɸ Y Y Y
{(1,1), (2,2), (3,3)} Y Y N
{(1,2), (2,3), (1,3)} N Y Y
{(1,1), (1,2), (2,1), (2,2)} Y N N
{(1,1), (2,2), (3,3), (1,3), (2,1)} N Y N
{(1,3), (2,1), (2,3), (3,2)} n n N
Q Consider a set A = {a, b, c} and R1, R2, R3 and R4 are relations on A which of the following
is not true?
Symmetric Anti-Symmetric Asymmetric
R1 = {(a, a), (c, c)} y Y T
R2 = {(a, b), (b, a), (a, c)} n N T
R2 = {(a, b), (b, c), (a, c)} n Y T
R2 = {(a, b), (b, a), (c, c)} y n T
Q Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of
the following is TRUE? (GATE-2009) (1 Marks)
(A) R is symmetric but NOT antisymmetric
(B) R is NOT symmetric but antisymmetric
(C) R is both symmetric and antisymmetric
(D) R is neither symmetric nor antisymmetric
Answer: (D)
Q Let R be a relation on the set of ordered pairs of positive integers such that ((p, q), (r, s))
∈ R if and only if p–s = q–r. Which one of the following is true about R? (GATE-2015) (2
Marks)
(A) Both reflexive and symmetric
(B) Reflexive but not symmetric
(C) Not reflexive but symmetric
(D) Neither reflexive nor symmetric
Answer: (C)
Q How many relations are there on a set with n elements that are symmetric and a set with
n elements that are reflexive and symmetric? (NET-Dec-2012)
a) 2n(n+1)/2 and 2n.3n(n–1)/2 b) 3n(n–1)/2 and 2n(n–1)
C) 2n(n+1)/2 and 3n(n–1)/2 D) 2n(n+1)/2 and 2n(n–1)/2
Answer: (d)
Transitive relation: - A relation R on a set A with cartesian product A*A is said to be
Transitive,
If ∀ a, b ∈ A
(a, b) ∈ R
(b, c) ∈ R
……………………………
(a, c) ∈ R
……………………………
• Smallest Asymmetric relation is ɸ
• Largest Asymmetric relation will contain A*A elements
• If two relations R1 and R2 are Transitive then their union need not to be transitive
but intersection will also be transitive.
Relation Transitive
A*A Y
ɸ N
{(1,1), (2,2), (3,3)} Y
{(1,2), (2,3), (1,3)} y
{(1,1), (1,2), (2,1), (2,2)} y
{(1,1), (2,2), (3,3), (1,3), (2,1)} n
{(1,3), (2,1), (2,3), (3,2)} N
{(1,2)} y
{(1,3), (2,3)} Y
{(1,2), (1,3)} Y
{(2,3), (1,2)} n
|A| = n No of transitive relation
0 1
1 2
2 13
3 171
4 3994
Warshall’s Algorithm
Q Consider a set A = {a, b, c, d} and a relation R = {(a, d), (b, a), (b, c), (c, a), (c, d), (d, c)}?
Q consider a set A = {1,2,3,4} and a relation R = {(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2),
(3, 3), (3, 4)}?
Q Consider a set A = {1,2,3} and a relation R = {(1,1), (1,3), (2,2), (3,1), (3,2)}?
1 2 3
1 1 0 1
2 0 1 0
3 1 1
1 2 3
Column (1,3) (2,3) (1,3)
Row (1,3) (2) (1,2,3)
(1,1), (1,3), (3,1), (2,2), (3,2) (1,1), (1,2), (1,3),
(3,3) (3,1), (3,2), (3,3)
Q Let R be the relation on the set of positive integers such that a R b if and only if a and b
are distinct and have a common divisor other than 1. Which one of the following
statements about R is True? (GATE-2015) (1 Marks)
(A) R is symmetric and reflexive but not transitive
(B) R is reflexive but not symmetric and not transitive
(C) R is transitive but not reflexive and not symmetric
(D) R is symmetric but not reflexive and not transitive
Answer: (D)
Q A binary relation R on N x N is defined as follows:
(a, b) R (c, d) if a <= c or b <= d
Consider the following propositions:
P: R is reflexive
Q: R is transitive
Which one of the following statements is TRUE? (GATE- 2016) (2 Marks)
(A) Both P and Q are true. (B) P is true and Q is false.
(C) P is false and Q is true. (D) Both P and Q are false.
Answer: (B)
Q The binary relation R= {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4)} on the set A =
{1,2,3,4} is (GATE-1998) (2 Marks)
(a) reflexive, symmetric and transitive
(b) neither reflexive, nor irreflexive but transitive
(c) irreflexive, symmetric and transitive
(d) irreflexive and antisymmetric
Ans: b
Q The binary relation S = φ (empty set) on set A = {1,2,3} is (GATE-2002) (2 Marks)
(a) Neither reflexive nor symmetric (b) Symmetric and reflexive
(c) Transitive and reflexive (d) Transitive and symmetric
Ans d
Q The relation “divides” on a set of positive integers is ________. (NET-June-2013)
a) Symmetric and transitive b) Anti symmetric and transitive
c) Symmetric only d) Transitive only
Answer: (b)
Q A relation R in {1, 2,3,4,5,6} is given by {(1,2), (2,3), (3,4), (4,4), (4,5)}. This relation is:
(NET-Dec-2008)
a) Reflexive b) Symmetric
c) Transitive d) not reflexive, not symmetric and not transitive
Answer: (a)
0 1 0
Q the transitive closure of a relation R on a set A whose relation matrix 0 0 1 is: (NET-
1 0 0
June-2005)
0 1 0 1 1 0 1 1 1 0 1 1
a) 0 0 1 b) 1 1 0 c) 1 1 1 d) 0 1 1
1 0 0 1 1 0 1 1 1 0 1 1
Ans: c
Q The transitive closure of the relation {(1,2), (2,3), (3,4), (5,4)} on the set {1,2,3,4,5} is
___________. (GATE-1989) (2 Marks)
Equivalence Relation: - A relation R on a set A with cartesian product A*A is said to be
Equivalence, if it is
• Reflexive
• Symmetric
• Transitive
If two relations R1 and R2 are Equivalence then their union need not to be equivalence but
intersection will also be Equivalence.
Q Let R and S be any two equivalence relations on a non-empty set A. Which one of the
following statements is TRUE? (GATE-2005) (2 Marks)
(A) R ∪ S, R ∩ S are both equivalence relations
(B) R ∪ S is an equivalence relation
(C) R ∩ S is an equivalence relation
(D) Neither R ∪ S nor R ∩ S is an equivalence relation
Answer: (C)
Q Let R1 and R2 be two equivalence relations on a set. Consider the following assertions
(GATE-1998) (1 Marks)
(i) R1 U R2 is an equivalence relation
(ii) R1 ∩ R2 is an equivalence relation
Which of the following is correct?
a) Both assertions are true
b) Assertions (i) is true but assertions (ii) is not true
c) Assertions (ii) is true but assertions (i) is not true
d) Neither (i) nor (ii) is true
Answer: C
Q Consider the following relations:
R1 : (a, b) iff (a + b) is even over the set of integers
R2 : (a, b) iff (a + b) is odd over the set of integers
R3 : (a, b) iff a. b > 0 over the set of non-zero rational numbers
R4 : (a, b) iff |a – b| ≤ 2 over the set of natural numbers
Which of the following statements is correct? (GATE-2001) (1 Marks)
(a) R1 and R2 are equivalence relations, R3 and R4 are not
(b) R1 and R3 are equivalence relations, R2 and R4 are not
(c) R1 and R4 are equivalence relations, R2 and R3 are not
(d) R1, R2, R3 and R4 are all equivalence relations
Ans: b
Q Which of the relations on {0, 1, 2, 3} is an equivalence relation? (NET-July-2018)
a) {(0, 0) (0, 2) (2, 0) (2, 2) (2, 3) (3, 2) (3, 3)}
b) {(0, 0) (1, 1) (2, 2) (3, 3)}
c) {(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0)}
d) {(0, 0) (0, 2) (2, 3) (1, 1) (2, 2)}
Ans: b
Equivalence Class: - of an element is denoted by [x].
[x] = {y | y ∈ A and (x, y) ∈ R} for all x ∈ A
We can have [x] = [y], even if x != y
Q Consider A = {1, 2, 3, 4, 5} an equivalence relation R on A, R =
{(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,5),(5,2)} find the partition of a set A, defined by R.
[1] = {1, 4}
[2] = {2, 5}
[3] = {3}
[4] = {1,4}
[5] = {2, 5}
Partitions of a Set: - let A be a set, with n elements. Based on our understanding of
equivalent classes, a subdivision of A into non-empty and non-overlapping subset is called a
partition of A
A1 U A2 U A3 U ………….. U An = A
A1 ⋂ A2 ⋂ A3 ⋂ ………….. ⋂ An = ɸ
so we have partitions = {1, 4}, {2, 5}, {3}
Q Let A = {1,2,3,4,5} is a set having partitions as {1, 4}, {2, 3, 5} , find the equivalence
relation from which these partitions are created?
R = {(1, 4)* (1, 4), (2, 3, 5)* (2, 3, 5)}
R = {(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,3),(3,2),(2,5),(5,2)(3,5)(5,3)}
Q A relation R is defined on the set of integers as x Ry iff (x + y) is even. Which of the
following statements is true? (GATE-2000) (2 Marks)
(a) R is not an equivalence relation
(b) R is an equivalence relation having 1 equivalence class
(c) R is an equivalence relation having 2 equivalence classes
(d) R is an equivalence relation having 3 equivalence classes
Answer: C
Q Let S be a set of n elements. The number of ordered pairs in the largest and the smallest
equivalence relations on S are (GATE-2007) (1 Marks)
(A) n and n (B) n2 and n (C) n2 and 0 (D) n and 1
Answer: (B)
Q Suppose A is a finite set with n elements. The number of elements in the largest
equivalence relation of A is? (GATE-1998) (1 Marks)
(a) n (b) n2 (c) 1 (d) n + 1
Ans: c
Q Let R be a non-empty relation on a collection of sets defined by A R B if and only if A ∩ B
= φ. Then, (pick the true statement) (GATE-1996) (2 Marks)
(a) R is reflexive and transitive (b) R is symmetric and not transitive
(c) R is an equivalence relation (d) R is not reflexive and not symmetric
Ans: b
Q How many different equivalence relations with exactly three different equivalence
classes are there on a set with five elements? (NET-July-2016)
(A) 10 (B) 15 (C) 25 (D) 30
Answer: (C)
Q The number of equivalence relations of the set {1,2,3,4} is (GATE-1997) (1 Marks)
a) 15 b) 16 c) 24 d) 4
Answer: (A)
Q “x^1 is a clone of x” means x^1 is identical to x in terms of the physical attributes namely,
height, weight and complexion. Given, height, weight and complexion only form a complete
set of attributes for an entity, cloning is an equivalence relation. What is your impression
about this statement? (NET-June-2010)
a) The statement is true b) The statement is false
c) The truth value of the statement cannot be computed d) None of these
Answer: (a)
Partial Order Relation: - A relation R on a set A with cartesian product A*A is said to be
partial order, if it is
• Reflexive
• Anti - Symmetric
• Transitive
Partial ordering set (Poset): - a set A with partial ordering relation R defined on A is called a
POSET and is denoted by [A; R]
For e.g. [A, /], [A, <=], [P(S), ⊑]
Total order relation: - A Poset [A; R] is called a total order set, if every pair of elements are
comparable i.e. either (a, b) or (b, a) x ∈ R, for ∀ a, b ∈ A
For e.g. A = {1, 2, 3, 6}, then Poset [A,/] is not a total order relation but A = {1248} will be
Q A relation R is defined on ordered pairs of integers as follows: (x, y) R (u, v) if x < u and y >
v. Then R is (GATR-2006) (1 Marks)
(A) Neither a Partial Order nor an Equivalence Relation
(B) A Partial Order but not a Total Order
(C) A Total Order
(D) An Equivalence Relation
Answer: A
Q let R1 be a relation from A = {1,3,5,7} to B = {2,4,6,8} and R2 be another relation from B to
C = {1,2,3,4} as defined below (GATE-2004) (1 Marks)
(i) an element x in A is related to an element y in B if x + y is divisible by 3
(ii) an element x in B is related to an element y in C if x + y is even but not divisible by 3.
Which is the composite relation R1R2 from A to C?
a) {(1,2), (1,4), (3,3), (5,4), (7,3)} b) {(1,2), (1,3), (3,2), (5,2), (7,3)}
c) {(1,2), (3,2), (3,4), (5,4), (7,2)} d) {(3,2), (3,4), (5,1), (5,3), (7,1)}
Answer: C
Q Which of the following statements is true? (NET-July-2018)
a) (Z, ≤) is not totally ordered
b) The set inclusion relation ⊆ is a partial ordering on the power set of a set S
c) (Z, ≠) is a Poset
d) The directed graph is not a partial order
Ans: b
Q Let R be a symmetric and transitive relation on a set A. Then (GATE-1995) (1 Marks)
a) R is reflexive and hence an equivalence relation
b) R is reflexive and hence a partial order
c) R is reflexive and hence not an equivalence relation
d) None of the above
Answer: (D)
Q A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
(GATE-2007) (2 Marks)
(1) (0,0) ∈ P (2) (a, b) ∈ P if and only if a % 10 <= b % 10 and (a/10, b/10) ∈ P.
Consider the following ordered pairs:
(i) (101,22) (ii) (22,101) (iii) (145,265) (iv) (0,153)
a) I & iii b) ii & iv c) I & iv d) iii & iv
Ans : d
Conversion of poset into a Hasse Diagram
If we want to study Partial order relation further then it will be better to convert it into
more convinent notation so that it can be studied easily. This graphical representation is
called Hasse Diagram
Stepts to convert partial order relation into hasse diagram
1- Draw a vertex for each element in the Set
2- If (a,b) ϵ R then draw an edge from a to b
3- Remove all Reflexive and Transitive edges
4- Remove the direction of edges and arrange them in the increasing order of heights.
Q Consider a Partial order relation and convert it into hasse diagram?
R = {(1,1), (1,2), (1,4), (1,8), (2,2), (2,4), (2,8), (4,4), (4,8), (8,8)}
Q Consider a Partial order relation and convert it into hasse diagram?
R = {(1,1), (1,2), (1,3), (1,6), (2,2), (2,6), (3,3), (3,6), (6,6)}
Q Study the follwing hasse diagram and find which of the follwing are valid?
Conclusion
• We can not have a horizontal edge in a hasse diagram
• We can not have a reflexive and transativie edge in Hasse Diagram
Q Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y. Number of
edges as in the Hasse diagram of (X, ≤) is. (GATE-1996) (1 Marks)
(a) 3 (b) 4 (c) 9 (d) None of the above
Ans b
Elements of a Poset
Maximal Element: - An element is said to be maximal if it is not related to any other
element in the Partial order relation.
Minimal Element: - An element is said to be minimal if no other element is related to it in
the Partial order relation.
• Every hasse diagram will have at least one Maximal and Minimal element(one or
more).
Maximum/Greatest Element: - An element is said to be Maximum/Greatest if it is not
related to any other element but every element is related to it in Partial order relation. Or if
a hasse diagram has only one Maximal element then it will also be Maximum/Greatest
element.
Minimum/Least Element: - An element is said to be Minimum/Least if no other element is
related to it but it is related to every element Partial order relation. Or if a hasse diagram
has only one Minimal element then it will also be Minimum/Least element.
• Every hasse diagram will have at most one Greatest and Least element(zero or one).
• Every Greatest element is also Maximal
• Every Least element is also Minimal
Upper Bound: - Upper bound of a subset B with respect to set A, will contain all
those element to which all the elements of B is related.
Lower Bound: - lower bound of a subset B with respect to A, will contain all
those elements which are related to every element of B.
Least Upper Bound/LUB/Join/Supremeum/∨: - Least value in the upper bpund
Greatest Lower Bound/GLB/Meet/Infimum/∧: - Greatest value in the lower bound
Q Consider the Poset ({3,5,9,15,24,45}, /). Which of the following is correct for the given
Poset? (NET-JUNE-2019)
a) There exist a greatest element and a least element
b) There exist a greatest element but not a least element
c) There exist a least element but not a greatest element
d) There does not exist a greatest element and a least element
Ans: d
Lattice
Join Semi Lattice :- A hasse diagram/Partial order relation is called Join Semi Lattice if for
every elements their exists a Join.
Meet Semi Lattice :- A hasse diagram/Partial order relation is called Meet Semi Lattice if for
every elements their exists a Meet.
Lattice :- A hasse diagram/Partial order relation is called Lattice if their exist a Join and
Meet for every pair of element. Or A hasse diagram/Partial order relation is called Latice if
it is both Join Semi Lattice and Meet Semi Lattice.
Q Which of the following elements are lattice ?
Q A partially ordered set is said to be a lattice if every two elements in the set have (NET-
Dec-2010)
a) a unique least upper bound b) a unique greatest lower bound
c) both (A) and (B) d) none of the above
Answer: (C)
Q the inclusion of which of the following set into S = {{1,2},{1,2,3},{1,3,5},{1,2,4},{1,2,3,4,5}}
is necessary and sufficient to make S a complete lattice under the partial order defined by
set containment? (GATE-2004) (2 Marks)
a) {1} b) {1}, {2,3} c) {1}, {1,3} d) {1}, {1,3}, {1,2,3,4}, {1,2,3,5}
Ans: a
Q Consider the following Hasse diagrams
Which all of the above represent a lattice? (GATE-2008) (2 Marks)
(A) (i) and (iv) only (B) (ii) and (iii) only
(C) (iii) only (D) (i), (ii) and (iv) only
Answer: (A)
Q Consider the set X={a, b, c, d, e} under partial
ordering R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}. The Hasse
diagram of the partial order (X, R) is shown below.
The Hasse diagram of the partial order (X, R) is shown below.
The minimum number of ordered pairs that need to be added to RR to make (X, R) a lattice
is ______ (GATE-2017) (1 Marks)
Answer: 0
Boolean algebra
Unbounded Lattice :- If a lattice has infinite of elements then it is called
Unbounded Lattice.
Bounded Lattice :- If a lattice has finite number of elements then it is called
Bounded lattice, there will be upper and lower bound in lattice.
Complement of an element in a Lattice :- If two elements a and ac, are complement
of each other, then the following equations must always holds good.
a ∨ ac = Upper bound of lattice
a ∧ ac = Lower bound of lattice
Distributive Lattice :- A lattice is said to be distributted lattice. if for every element
their exist at most one element(zero or one).
Complement Lattice :- A Lattice is said to be Complement lattice. if for every
element their exist at least one element(one or more).
Boolean Algebra :- A Lattice is said to be Boolean Algebra, if for every element
their exist exactly one complement. Or if a lattice is both complemented and
distributed then it is called Boolean Algebra.
Q The complement(s) of the element 'a' in the lattice shown in below figure is (are) ____
(GATE-1988) (2 Marks)
Q the relation <= and < om a Boolean algebra is defined as :
x<=y if and only if x ∨ y =y
x<y means x<=y but x!=y
x>=y means y<=x and
x>y means y<x
considering the above definitions, which of the following in not true in the Boolean
algebra?
1) if x<=y and y<=z, then x<=z 2) if x<=y and y<=x, then x=y
3) if x<y and y<z, then x<=y 4) if x<y and y<z, then x<y
a)2 and 3 b)3 c)1 and 2 d) 4
(NET-Dec-2018)
Q The following is the Hasse diagram of the Poset [{a, b, c, d, e}, ≤]
The Poset is (GATE-2005) (1 Marks)
(A) not a lattice (B) a lattice but not a distributive lattice
(C) a distributive lattice but not a Boolean algebra (D) a Boolean algebra
Answer: (B)
Q Find which of the following is a lattice and Boolean Algebra?
1) [D12, /]
2) [{1,2,3,4,6,9}, /]
3) [{2,3,4,6,12}, /]
4) [{1,2,3,5,30}, /]
5) [{1,2,3,6,9,18}, /]
6) [D110, /]
7) [D45, /]
8) [{2,3,4,9,12,18}, /]
9) [R, <=]
10) [D81, /]
11) [D30, /]
12) [D64, /]
13) [D10, /]
14) [D91, /]
15) [D10, /]
16) [P(A), ⊑], A = {1,2,3}
Q Consider the following hasse diagram, find which of the following is true?
a) it is a lattice b) subset {a,b,c,d} is a lattice
c) subset {b,c,d,e} is a lattice d) subset {a,b,c,e} is a lattice
Q Consider the following hasse diagram, find which of the following is true?
a) subset {a,b,c,g} is a lattice b) subset {a,b,f,g} is a lattice
c) subset {a,d,e,g} is a lattice d) subset {a,c,e,g} is a lattice
Q Suppose L = {p, q, r, s, t} is a lattice represented by the following Hasse diagram:
For any x, y ∈ L, not necessarily distinct, x ∨ y and x ∧ y are join and meet of x, y
respectively. Let L3 = {(x, y, z): x, y, z ∈ L} be the set of all ordered triplets of the elements of
L. Let Pr be the probability that an element (x, y, z) ∈ L3chosen equiprobably satisfies x ∨ (y
∧ z) = (x ∨ y) ∧ (x ∨ z). Then (GATE-2015) (2 Marks)
(A) Pr = 0 (B) Pr = 1 (C) 0 < Pr ≤ 1/5 (D) 1/5 < Pr < 1
Answer: (D)
Q Consider the set S = {a, b, c, d}.
Consider the following 4 partitions π1, π2, π3, π4 on
S: π1={abcd}, π2={ab, cd}, π3={abc, d}, π4={a, b, c, d}
Let ≺ be the partial order on the set of partitions S′={π1,π2,π3,π4} defined as
follows: πi≺πj if and only if πi refines πj. The Poset diagram for (S′, ≺) is: (GATE-2007) (2
Marks)
a) b) c) d)
Ans: c