Exam 2 Discrete Mathematics

Let a and b be integers. The greatest common divisor of a and b is denoted by gcd(a, b) and is the natural number d that satisfies the following conditions:

d divides both a and b. If n is an integer that divides both a and b then n divides d

Two integers a and b are relatively prime if

gcd(a, b) = 1.

Let a and b be positive integers. A natural number n is the least common multiple of a and b if it satisfies the following properties:

a divides n and b divides n. If m is any other number so that a divides m and b divides m then n divides m.

To prove a statement using induction. We use the following procedure:

Show that the statement is true for the smallest value considered (usually n = 1). Then assume that the statement is true for n = k and use this to prove that the statement holds for n = k + 1.

To prove a statement using strong induction. We use the following procedure:

Show that the statement is true for the smallest value considered (usually n=1). Then assume that the statement is true for all n ≤ k and use this to prove that the statement holds for n = k + 1.

A set is

a specified collection of objects

if A is a set and x is an object that belongs to A

Then x is an element of A, denoted x ∈ A

If x is not an object that belongs to A

we say that x is not an element of A, denoted x /∈ A

If A and B are sets, B is a subset of A, denoted B ⊆ A if

every member of B is a member of A.

Sets A and B are equal, denoted A = B, if

A ⊆ B and B ⊆ A

The set with no members is called

The empty set and denoted ∅.

A subset A ⊆ B is a proper subset if

A ⊆ B and A /= B. This is denoted by A ⊂ B.

The power set of a set A is

the set of all (proper and not proper) subsets of A. This is denoted P(A).

If A and B are sets, then the union of A and B is

the set of all objects that belong to A or belong to B, denoted A ∪ B. In otherwords, A ∪ B = {x | x ∈ A or x ∈ B}

If A and B are sets, then the intersection of A and B is

the set of all objects that belong to both A and B, denoted A ∩ B. In other words, A ∩ B = {x | x ∈ A and x ∈ B}