Discrete Structures Practice Questions

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

If the relation R on the set of all integers is defined as x ≠ y, which of the following properties does R satisfy?

It is transitive.

It is reflexive.

It is symmetric. (correct)

It is antisymmetric.

If the relation R is defined as x ≡ y (mod 7) on the set of all integers, which of the following properties does R satisfy?

It is symmetric and transitive. (correct)

It is asymmetric.

It is reflexive.

It is not reflexive.

How many different relations are there from a set with m elements to a set with n elements?

m^n

m × n

2^(m × n) (correct)

m + n

Let R be the relation R = {(a, b) | a divides b} on the set of positive integers. What is R^(-1)?

The relation {(b, a) | b divides a}. Signup and view all the answers

Let f be a one-to-one correspondence from A to B. Let R be the relation that equals the graph of f. Which of the following is true about R?

R is a function. Signup and view all the answers

Give an example of a relation on a set that is both symmetric and antisymmetric.

The relation {(a, b) | a = b} on the set of all integers. Signup and view all the answers

What do you obtain when you apply the selection operator sC, where C is the condition (Project=2)∧(Quantity≥ 50), to the database in Table 10?

A subset of tuples from Table 10 with Project = 2 and Quantity ≥ 50 Signup and view all the answers

What is the result of applying the projection P2,3,5 to the 5-tuple (a, b, c, d, e)?

(b, c, e) Signup and view all the answers

Which projection mapping is used to delete the first, second, and fourth components of a 6-tuple?

P3,4,5 Signup and view all the answers

What are the operations that correspond to the query expressed using the SQL statement SELECT Supplier FROM Part_needs WHERE 1000 ≤ Part_number ≤ 5000?

Selection and projection Signup and view all the answers

Which of the following relations on {0, 1, 2, 3} are equivalence relations?

Only a Signup and view all the answers

What is the output of the query given the database in Table 9 as input?

A list of suppliers for parts with 1000 ≤ Part_number ≤ 5000 Signup and view all the answers

What is the inverse relation R−1 of R = {(a, f(a)) | a ∈ A}?

R−1 = {(f(a), a) | a ∈ A} Signup and view all the answers

What is the composition of R2 and R6, denoted by R2 ⊕ R6?

R2 ⊕ R6 = {(a, b) | a ≠ b and a ≥ b} Signup and view all the answers

How many relations are there on the set {a, b, c, d} that contain the pair (a, a)?

2^8 Signup and view all the answers

What is the error in the 'proof' of the 'theorem' that a symmetric and transitive relation R is reflexive?

The use of the transitive property to conclude that (a, a) ∈ R. Signup and view all the answers

What is the relation R3 ∪ R6 on the set {a, b, c, d}?

The 'less than or unequal to' relation. Signup and view all the answers

What is the representation of the relation R5 = {(a, b) ∈ R2 | a = b} as a matrix on {1, 2, 3}?

A matrix with 1's on the diagonal and 0's elsewhere. Signup and view all the answers

What is the characteristic of a relation R on a set A if the matrix representing R has no nonzero entries on the main diagonal?

It is irreflexive Signup and view all the answers

What is the matrix representing the relation $R^{-1}$, where R is a relation on a finite set A?

The transpose of the matrix representing R Signup and view all the answers

If a relation R on a set A is represented by a matrix with only one nonzero entry, what can be said about the relation?

It is a function Signup and view all the answers

What is the complement of a relation R on a set A, represented as a matrix?

The matrix obtained by replacing all 1s with 0s and 0s with 1s Signup and view all the answers

If a relation R on a set A is represented by a matrix with all nonzero entries on the main diagonal, what can be said about the relation?

It is reflexive Signup and view all the answers

What is the number of nonzero entries in the matrix representing the relation R on A = {1, 2, 3,..., 100} consisting of the first 100 positive integers, if R is {(a, b) | a > b}?

4950 Signup and view all the answers

Let R be the relation {(a, b) | a and b are the same age} on the set of humans. What is the symmetric closure of R?

R itself, since it is already symmetric Signup and view all the answers

Let R be the relation {(a, b) | a divides b} on the set of integers. What is the reflexive closure of R?

{(a, a) | a is an integer} Signup and view all the answers

Let R be the relation {(a, b) | a and b have met} on the set of humans. Is R an equivalence relation?

No, it is not symmetric Signup and view all the answers

What is the congruence class [2]5?

{…, -13, -8, -3, 2, 7, 12, …} Signup and view all the answers

Which of the following collections of subsets are partitions of {1, 2, 3, 4, 5, 6}?

{{1}, {2, 3, 6}, {4}, {5}} Signup and view all the answers

Let R be a relation on a finite set. How can the directed graph representing the reflexive closure of R be constructed from the directed graph of R?

By adding an edge from each vertex to itself Signup and view all the answers

Study Notes

Relations in Discrete Structures

A relation R from a set A to a set B is a subset of the Cartesian product A × B.

Properties of Relations

Reflexive: a relation R is reflexive if for every a in A, (a, a) ∈ R.
Irreflexive: a relation R is irreflexive if for no a in A, (a, a) ∈ R.
Symmetric: a relation R is symmetric if for every a, b in A, (a, b) ∈ R implies (b, a) ∈ R.
Antisymmetric: a relation R is antisymmetric if for every a, b in A, (a, b) ∈ R and (b, a) ∈ R implies a = b.
Asymmetric: a relation R is asymmetric if it is not symmetric.
Transitive: a relation R is transitive if for every a, b, c in A, (a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R.

Examples of Relations

a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}: not reflexive, not symmetric, transitive.
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}: reflexive, symmetric, transitive.
c) {(2, 4), (4, 2)}: not reflexive, symmetric, not transitive.
d) {(1, 2), (2, 3), (3, 4)}: not reflexive, not symmetric, transitive.
e) {(1, 1), (2, 2), (3, 3), (4, 4)}: reflexive, not symmetric, transitive.
f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}: not reflexive, symmetric, not transitive.

Equivalence Relations

An equivalence relation is a relation that is reflexive, symmetric, and transitive.
Examples of equivalence relations:
- {(0, 0), (1, 1), (2, 2), (3, 3)}.
- {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}.
- {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}.

Operations on Relations

Union: R ∪ S = {(a, b) | (a, b) ∈ R or (a, b) ∈ S}.
Intersection: R ∩ S = {(a, b) | (a, b) ∈ R and (a, b) ∈ S}.
Difference: R - S = {(a, b) | (a, b) ∈ R and (a, b) ∉ S}.
Complement: R' = {(a, b) | (a, b) ∉ R}.
Symmetric difference: R ⊕ S = (R ∪ S) - (R ∩ S).

Matrix Representation of Relations

A relation R on a set A can be represented as a matrix, where the entry at row i and column j is 1 if (i, j) ∈ R, and 0 otherwise.
The matrix representing the relation R can be used to determine whether R is reflexive, irreflexive, symmetric, antisymmetric, or transitive.

Inverse Relations

The inverse relation R^(-1) of a relation R is defined as R^(-1) = {(b, a) | (a, b) ∈ R}.
Example: R = {(a, b) | a > b}, then R^(-1) = {(a, b) | a < b}.

Equivalence Classes

The equivalence class [a] of an element a with respect to an equivalence relation R is the set of all elements b such that (a, b) ∈ R.
Example: R = {(a, b) | a ≡ b (mod 5)}, then [2] = {2, 7, 12, ...}.

Partitions

A partition of a set A is a collection of non-empty subsets of A such that every element of A is in exactly one subset.
Example: {{1, 2}, {3, 4}, {5, 6}} is a partition of {1, 2, 3, 4, 5, 6}.

Reflexive and Symmetric Closures

The reflexive closure of a relation R is the smallest reflexive relation that contains R.
The symmetric closure of a relation R is the smallest symmetric relation that contains R.
Example: R = {(a, b) | a ≠ b}, then the reflexive closure of R is R ∪ {(a, a) | a ∈ A}.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Practice questions on discrete structures, including relations and properties such as reflexivity, symmetry, and transitivity. Questions involve identifying ordered pairs in a relation and determining its properties.