Discrete Math Study

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

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

p∧T

identity, p

p∨F

identity, p

p∨T

domination, T

p∧F

domination, F

p∧p

idempotent, p

p∨p

idempotent, p

¬(¬p)

double negation, p

p∨q

commutative, q∨p

p∧q

commutative, q∧p

(p∨q)∨r

associative, p∨(q∨r)

p∧(q∧r)

associative, (p∧q)∧r

p∨(q∧r)

distributive, (p∨q)∧(p∨r)

p∧(q∨r)

distributive, (p∧q)∨(p∧r)

¬(p∧q)

de morgan’s, ¬p∨¬q

¬(p∨q)

de morgan’s, ¬p∧¬q

p∨(p∧q)

absorption, p

p∧(p∨q)

absorption, p

p∨¬p

negation, T

p∧¬p

negation, F

p, p→q

modus ponens, q

¬q, p→q

modus tollens, ¬p

p→q, q→r

hypothetical syllogism, p→r

p∨q, ¬p

disjunctive syllogism, q

p

addition, p∨q

p∧q

simplification, p

p,q

conjunction, p∧q

p∨q, ¬p∨r

resolution, q∨r

resolution

p∨q, ¬p∨r leads to q∨r

conjunction

p,q leads to p∧q

simplification

p∧q leads to p

addition

p leads to p∨q

disjunctive syllogism

p∨q, ¬p leads to q

hypothetical syllogism

p→q, q→r leads to p→r

modus tollens

¬q, p→q leads to ¬p

modus ponens

p, p→q leads to q

logical equivalency

p→q leads to ¬p∨q and p→q leads to ¬q→¬p

biconditional logical equivalency

p⇆q leads to (p→q)∧(q→p)

reflexive

for all a in A, (a,a) is in R

symmetric

∀a,b ∈ A, aRb→bRa

antisymmetric

∀a,b ∈ A, (aRb ∧ bRa) → a=b

transitive

∀a,b,c ∈ A, (aRb ∧ bRc) → aRc

equivalence relation

reflexive, symmetric and transitive

division algorithm

Let a∈Z and d∈Z+, then ∃!q,r ∈Z 0<=r<d s.t. a=qd+r

q

q = a div d

r

r = a mod d

congruent modulo

let a,b∈Z and m∈Z+, a is congruent to bmodm iff m|(a-b) aka a and b have the same remainder when divided by m

relatively prime

a and b are relatively prime iff gcd(a,b)=1

gcd(a,d)

gcd(a,d)=gcd(d,r)=gcd(d, a mod d)

euclid’s lemma

let a,b,c ∈ Z+, if a|(bc) and gcd(a,b)=1, then a|c

lcm identity

ab=lcm(a,b)gcd(a,b)

pigeonhole principle

if there are k boxes and k+1 items, then AT LEAST one box will contain more than one item

generalized pigeonhole principle

for n items in k boxes, AT LEAST one box will contain [n/k] items (CEILING FUNCTION)

contraposition

p→q equals ¬q→¬p

contradiction

negate p→q so that ¬(p→q) equals p∧¬q