Discrete Math Exam 2

Studying exam two materials like definitions and rules

N

Natural numbers like 1,2,3

N and 0

Some definitions do not include zero

Z

All integers like -1,0,2

Q

Rational numbers that can be written in p/q form

R

real numbers, includes N,Z,Q and irrational numbers

C

Complex numbers, includes R and imaginary numbers

{x ∈ D | P(x)}

the set of all x in the domain D such that P(x) is true

A=B=∀x{x∈A ⇆ x∈B} (read as “if x, then y”)

Set equality: A and B are equal if and only if they contain the exact same elements

A⊆B=∀x{x∈A →x∈B} (read as “if x, then y”)

A is a subset of B if and only if every element of A is in B

A=B≣ {(A⊆B) ∧ (B⊆A)}

Set equality: A and B are equal if they are both subsets of one another

|A| = x

Cardinality: The number of elements in set A is x

|A|∈ℕ

cardinality is finite

|A|∉ℕ

Cardinality is infinite

note to self: add cartesian product and power sets from 2.1 if needed

note to self: add cartesian product and power sets from 2.1 if needed

A→B: A is the

Domain, the set of all possible input values

A→B: B is

Codomain, the set of all possible output values

f(a)=b, b is the ___ of a

image

f(a)=b, a is the ___ of b

preimage

Let f: A→B. define injectivity

For all a1, a2 in A, A is injective if and only if a1≠a2 then f(a1)≠f(a2)

Let f: A→B. define surjectivity

For all b in B, there exists an a in A such that f(a)=b.

surjectivity simply put

every output has an input. you can’t have A to B and A only has 4 things while B has 5 things. f(a5) doesn’t exist

∀a1,a2∈A {a1≠a2 → f(a1)≠f(a2)}

injectivity

∀b∈B, ∃a∈A s.t. f(a)=b

surjectivity, codomain equals range

best method for proving injectivity

contraposition- if f(a1)=f(a2) then a1=a2

review floor and ceiling stuff

note to self

injectivity simply put

only one x per y, so 2 x-values can NOT point to the same y-value because then x1≠x2 but f(x1)=f(x2)

From A →B, range simply put

the stuff in B that correlates to A. Values that include the function A to B but NOT the other values of B.

bijectivity For f:A→B

injective and surjective. Each a in A maps to exactly one unique b in B, so the domain and codomain are equal

you can only take the ____ if a function is ____

inverse, bijective. if something is inverse, it implies bijectivity

Given f:x→y, then f inverse is ____

y to x

identity laws

A∩U=A, A∪∅=A

Domination laws

A∪U=U, A∩∅=∅

Idempotent laws

A∪A=A, A∩A=A

Complementation law

¬(¬A)=A *shown with a bar above not the ¬ sign

Commutative laws

A∪B=B∪A, A∩B=B∩A

Associative laws

A∪(B∪C)=(A∪B)∪C, A∩(B∩C)=(A∩B)∩C

Distributive laws

A∪(B∩C)=(A∪B)∩(A∪C), A∩(B∪C)=(A∩B)∪(A∩C)

De Morgan’s laws

¬(A∩B)= ¬A∪¬B, ¬(A∪B)= ¬A∩¬B

Absorption laws

A∪(A∩B)=A, A∩(A∪B)=A

Complement laws

A∪¬A=U, A∩¬A=∅

A∪¬A=U

complement, U

A∩¬A=∅

complement, empty

A∪U

domination, U

A∩∅

domination, empty

A∩U

identity, A

A∪∅

identity, A