G H PATEL COLLEGE OF ENGINEERING & TECHNOLOGY, V V NAGAR
A.Y.2025-26: ODD SEMESTER
202230301: DISCRETE MATHEMATICS AND APPLICATIONS
Information and Communication Technology
Assignment 2: Relations, Partial Ordering & Lattice
1 {( ) } the “greater than” relation,
{( ) } the “greater than or equal to” relation,
{( ) } the “less than” relation,
{( ) } the “less than or equal to” relation,
{( ) } the “equal to” relation,
{( ) } the “not equal to” relation,
Find
2 Let be the relation on the set { } containing the ordered pairs
( ) ( ) ( ) ( ) ( ) ( )( ) ( ) Find
3 Which relations given below, are reflexive?; irreflexive?; symmetric?; anti-symmetric?;
transitive?
{( ) } the “greater than” relation,
{( ) } the “greater than or equal to” relation,
{( ) } the “less than” relation,
{( ) } the “less than or equal to” relation,
{( ) } the “equal to” relation,
{( ) } the “not equal to” relation,
4 Suppose that the relation on a set is represented by the matrix
[ ]
Is reflexive, symmetric, antisymmetric, Transitive?
5 Suppose that the relations and on a set are represented by the matrices
[ ] [ ]
What are the matrices representing and
6 Find the matrix representing the relations and where the matrices
representing and are
[ ] [ ]
7 Find the directed graph of the relation
{⟨ ⟩⟨ ⟩⟨ ⟩⟨ ⟩⟨ ⟩⟨ ⟩⟨ ⟩⟨ ⟩} on the set { }
8 What is the reflexive closure and symmetric closure of the relation
{( ) } on the set of integers?
9 If { } and {( ) ( ) ( ) ( ) ( )} find its
transitive closure.
10 Find the transitive closure of by Warshall’s algorithm where { }
and {( ) }
11 Let be a relation on the set { } defined by
( )( )( ) ( )( )( )
{ }
( )( )( )( )( )
Find transitive closure of using Warshall’s algorithm.
12 Let be the relation on the set of real numbers such that if and only if is an
integer. Is an equivalence relation?
13 Let be a positive integer with Show that the relation
*( ) ( )+
is an equivalence relation on the set of integers.
14 Show that for every set S of strings and every positive integer n, Rn is an equivalence
relation on S.
15 Let be the relation on the set of real numbers such that if and only if and are
real numbers that differ by less than that is Show that is not an
equivalence relation.
16 Which of these relations on the set of all functions from to are equivalence
relations? Determine the properties of an equivalence relation that the others lack.
( ) {( ) ( ) ( )}
( ) {( ) ( ) ( ) ( ) ( )}
( ) {( ) ( ) ( ) }
( ) {( ) ( ) ( ) }
( ) {( ) ( ) ( ) ( ) ( )}
17 Let be the relation on the set of ordered pairs of positive integers such that
(( )( )) if and only if Show that is an equivalence relation.
What is the equivalence class of ( ) with respect to this equivalence relation?
18 Which of these collections of subsets are partitions of the set of integers?
1. The set of even integers and the set of odd integers
2. The set of positive integers and the set of negative integers
3. The set of integers divisible by the set of integers leaving a remainder of
when divided by and the set of integers leaving a remainder of when divided
by
The set of integers less than the set of integers with absolute value not exceeding
and the set of integers greater than
19 Which of these relations on {0, 1, 2, 3} are partial orderings? Determine the properties of
a partial ordering that the others lack.
a) {(0, 0), (1, 1), (2, 2), (3, 3)} b) {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
c) {(0, 0), (1, 1), (1, 2), (2, 2), (3, 3)} d) {(0, 0), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}
20 Which of these are posets?
a) (Z, =) b) (Z, =) c) (Z, ≥) d) (Z,|)
21 Determine whether the relation with the directed graph shown is a partial order.
22 Which of these pairs of elements are comparable in the poset (Z+, |)? a) 5, 15 b) 6, 9 c)
8, 16 d) 7, 7
23 Draw the Hasse diagram for the “greater than or equal to” relation on {0, 1, 2, 3, 4, 5}.
24 List all ordered pairs in the partial ordering with the following Hasse diagram.
25 Answer these questions for the partial order represented by this Hasse diagram.
a) Find the maximal elements.
b) Find the minimal elements.
c) Is there a greatest element? Is there a least element?
e) Find all upper bounds of {a, b, c}.
f ) Find the least upper bound of {a, b, c}, if it exists.
g) Find all lower bounds of {f, g, h}. h) Find the greatest lower bound of {f, g, h}, if it
exists
26 Determine whether the posets with these Hasse diagrams are lattices
