discrete structures exam 2

cs 3000 ohio univ. '25

what does A ∩ B mean?

the intersection of sets A and B, which includes all elements that are shared by both A and B

what does A ∪ B mean?

the union of sets A and B, which includes all elements that are in either A, B, or in both.

what does A - B mean?

the set difference between A and B which contains all elements in A that are not in B. This can be rewritten as the complement of the intersection of A and B.

what does A ⊆ B mean?

A is a subset of B, meaning all elements of A are also in B.

given set A = {d,e,f} what is 𝒫(A) (the power set)?

{{ø},{d},{d,e},{d,f},{e},{e,f},{f},{d,e,f}}

if sets A₁ , A₂ , … A_n represent a partition of set A, what can be said about their union and intersection?

The union of sets A1, A2, …, An equals set A, while the intersection of any two distinct sets Ai and Aj is empty, meaning they have no elements in common.

if the universal set is integers, and A = (-2,2] and B = [0,3), what is A ∪ B and A ∩ B?

A ∪ B = (-2, 3), A ∩ B = [0, 2)

the process of showing that set A = set B usually involves proving …

that every element of set A is also an element of set B, and vice versa. (A is a subset of B and B is a subset of A)

what are demorgan’s laws for sets?

De Morgan's Laws state that the complement of the union of two sets is equal to the intersection of their complements, and the complement of the intersection of two sets is equal to the union of their complements. Formally, these can be expressed as: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'.

what are the distributive laws for sets?

The distributive laws for sets state that for any sets A, B, and C: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

how do you set up an inductive proof?

An inductive proof is set up by first establishing a base case to demonstrate that the statement holds for the initial value, usually n=1. Then, assuming the statement is true for some arbitrary case n=k, you must prove it for the next case n=k+1 to complete the induction.

what is the formula for the sum of integers 1 through n?

The formula for the sum of integers from 1 to n is given by S = n(n + 1)/2. This formula allows for the efficient calculation of the total sum without needing to add each integer individually.

describe summation notation

summation notation is used to represent the sum of a sequence of numbers. It is denoted by Σ and includes an index of summation (#, which goes on top), limits of summation ( i, which goes on bottom), and the expression.

describe product notation

Product notation is used to represent the product of a sequence of numbers. It is denoted by Π and includes an index of multiplication (#, which goes on top), limits of multiplication (i, which goes on bottom), and the expression.

reflexive

R is reflexive only if for every x in A, x R x holds true in the relation R. This means that each element in the set A is related to itself.

symmetric

A relation R is symmetric if for every x and y in the set A, whenever x R y holds true, then y R x also holds true. This means that the relationship is mutual between elements.

transitive

if element A is related to element B and B is related to element C, then A is also related to C

how would you prove that a function is one-to-one?

you must prove that for each input value (x) there is no more than one output value (y)

how do you convert f(x) to f^-1 (y)

swap x for y and y for x and then solve for y. ex: if f(x) = 2x then f^-1(x) = y/2

what does the cardinality of a set mean?

it describes the number of items in a set.

what does it mean if two sets (A and B) have the same cardinality?

there exists a function where set A is one-to-one and onto set B