1 $If set has 10 elements, set has 15 elements, and the intersection has 5 elements, what is the cardinality of according to the Principle of Inclusion-Exclusion?$

A.

15

B.

20

C.

25

D.

30

2 $Which formula represents the Principle of Inclusion-Exclusion for three sets ?$

A.

B.

C.

D.

3 $In a group of 50 students, 30 take Math, 25 take Physics, and 15 take both. How many students take neither Math nor Physics?$

A.

5

B.

10

C.

15

D.

20

4 $How many positive integers not exceeding 100 are divisible by 2 or 3?$

A.

67

B.

66

C.

50

D.

83

5 $The Principle of Inclusion-Exclusion can be generalized to find the size of the union of sets. What is the sign of the term involving the intersection of sets?$

A.

Always positive

B.

Always negative

C.

D.

6 $What is the minimum number of people required to guarantee that at least two of them share the same birthday month?$

A.

12

B.

13

C.

24

D.

365

7 $State the Generalized Pigeonhole Principle: If objects are placed into boxes, then there is at least one box containing at least _____ objects.$

A.

B.

C.

D.

8 $If there are 4 different colors of socks in a drawer, what is the minimum number of socks one must pull out (blindly) to guarantee a matching pair?$

A.

4

B.

5

C.

8

D.

9

9 $A professor grades 25 students. The grades can be A, B, C, D, or F. What is the minimum number of students guaranteed to get the same grade?$

A.

4

B.

5

C.

6

D.

25

10 $How many cards must be selected from a standard deck of 52 cards to guarantee that at least 3 cards of the same suit are chosen?$

A.

9

B.

8

C.

13

D.

5

11 $Let be a relation on set . is reflexive if and only if:$

A.

B.

For all

C.

For all

D.

12 $Let . Which of the following relations is symmetric ?$

A.

B.

C.

D.

13 $A relation is anti-symmetric if:$

A.

B.

C.

D.

It is not symmetric

14 $Which relation on the set of integers is transitive ?$

A.

if divides

B.

if

C.

if

D.

if

15 $How many binary relations are there on a set with elements?$

A.

B.

C.

D.

16 $How many reflexive relations are there on a set with elements?$

A.

B.

C.

D.

17 $If is a relation on set, the inverse relation is defined as:$

A.

B.

C.

D.

18 $Let and be relations on . What is the composition ?$

A.

B.

C.

D.

19 $If relation is represented by matrix and relation by, the matrix representing is:$

A.

B.

(Element-wise logical AND)

C.

(Element-wise logical OR)

D.

20 $If is the zero-one matrix of a relation, how do we check if is symmetric?$

A.

All diagonal elements are 1

B.

(Transpose)

C.

has no zeros

D.

is the Identity matrix

21 $In the directed graph representation of a relation, a loop at vertex implies:$

A.

B.

for some

C.

The relation is transitive

D.

The relation is anti-symmetric

22 $What is the matrix multiplication equivalent used to find the composition of relations ?$

A.

Standard arithmetic matrix multiplication

B.

Boolean product (Logical AND then Logical OR)

C.

Cross product

D.

Element-wise multiplication

23 $A relation is an Equivalence Relation if it is:$

A.

Reflexive, Symmetric, and Transitive

B.

Reflexive, Anti-symmetric, and Transitive

C.

Irreflexive, Symmetric, and Transitive

D.

Reflexive and Symmetric only

24 $The set of all elements related to an element in an equivalence relation is called the:$

A.

Range of

B.

Domain of

C.

Equivalence Class

D.

Partition of

25 $Which of the following is an Equivalence Relation on the set of integers?$

A.

iff

B.

iff is even

C.

iff

D.

iff

26 $The equivalence classes of an equivalence relation on set form a:$

A.

Subset of

B.

Power set of

C.

Partition of

D.

Cartesian product

27 $Let be the relation modulo 3 on integers: . How many distinct equivalence classes are there?$

A.

1

B.

2

C.

3

D.

Infinite

28 $A relation is a Partial Ordering (POSET) if it is:$

A.

Reflexive, Symmetric, Transitive

B.

Reflexive, Anti-symmetric, Transitive

C.

Irreflexive, Anti-symmetric, Transitive

D.

Symmetric and Transitive only

29 $In a POSET, two elements and are called comparable if:$

A.

or

B.

and

C.

D.

They belong to the same lattice

30 $A POSET where every pair of elements is comparable is called a:$

A.

Lattice

B.

Equivalence Relation

C.

Total Ordering (or Chain)

D.

Well-ordered set

31 $In a Hasse diagram, the edges implied by _____ are removed to simplify the graph.$

A.

Symmetry

B.

Anti-symmetry

C.

Transitivity and Reflexivity

D.

Connectivity

32 $Consider the POSET where denotes divisibility. Which element is the maximal element?$

A.

1

B.

2

C.

4

D.

8

33 $An element in a POSET is minimal if:$

A.

There is no such that and

B.

There is no such that

C.

for all

D.

for all

34 $What is the difference between a maximal element and a greatest element?$

A.

They are the same.

B.

Greatest is unique and succeeds all others; Maximal has no successors but might not be unique.

C.

Maximal succeeds all others; Greatest has no successors.

D.

Maximal only exists in total orderings.

35 $A Lattice is a POSET in which every pair of elements has:$

A.

A least upper bound (LUB) and a greatest lower bound (GLB)

B.

A maximal and minimal element

C.

An inverse

D.

Equal rank

36 $In the lattice (Power set under inclusion), what is the LUB of two sets and ?$

A.

B.

C.

D.

37 $In the lattice (positive integers under divisibility), what is the GLB of two numbers and ?$

A.

B.

C.

D.

38 $A sublattice of a lattice must:$

A.

Be a subset of

B.

Be closed under the LUB () and GLB () operations of

C.

Have the same greatest element as

D.

Be a finite subset

39 $A lattice is bounded if it has:$

A.

Finite number of elements

B.

A greatest element (1) and a least element (0)

C.

No infinite chains

D.

At least one comparable pair

40 $A lattice is called distributive if:$

A.

for all

B.

C.

It contains a complement for every element

D.

It is a total ordering

41 $In a Hasse diagram, if vertex is drawn higher than vertex and there is a line connecting them (possibly through other vertices), it implies:$

A.

B.

C.

and are incomparable

D.

42 $Let on . Is a partial ordering?$

A.

Yes

B.

No, it is not reflexive

C.

No, it is not anti-symmetric

D.

No, it is not transitive

43 $Which of the following describes the closure of a relation with respect to property ?$

A.

The smallest relation containing that has property

B.

The largest relation contained in that has property

C.

The intersection of all relations having property

D.

The relation itself

44 $The transitive closure of a relation is often denoted as:$

A.

B.

C.

D.

45 $If is a relation on represented by matrix, the matrix for the reflexive closure of is calculated by:$

A.

(where is Identity matrix)

B.

C.

D.

46 $A set is Well-Ordered if:$

A.

It is a total ordering and every non-empty subset has a least element

B.

It is a partial ordering with a maximal element

C.

It is infinite

D.

It has no minimal element

47 $In the context of the Pigeonhole Principle, if 101 integers are selected from the set, at least one selected integer must:$

A.

Divide another selected integer

B.

Be equal to 100

C.

Be prime

D.

Be odd

48 $For a relation to be irreflexive, it must satisfy:$

A.

B.

C.

D.

It is not symmetric

49 $Which of the following Hasse diagrams represents a totally ordered set (chain)?$

A.

A vertical line of nodes

B.

Two parallel vertical lines

C.

A diamond shape

D.

A single node with a loop

50 $Let . Let . What are the equivalence classes?$

A.

B.

C.

D.

is not an equivalence relation

Unit 3 - Practice Quiz