Discrete Math Final

Proposition

A declarative statement that is either true or false

¬

not/negation

∧

and/conjunction

∨

or/disjunction

→

if…then/implication

⟺

if and only if/bidirectional

knights

always tell the truth

knaves

always lie

tautology

A compound proposition that is always true

contradiction

A compound proposition that is always false

≡

logically equivalent

converse

If q, then p

inverse

If not p, then not q

Contrapositive

If not q, then not p

DeMorgan's Law

~(p ^ q) = ~p v ~q

~(p v q) = ~p ^ ~q

DeMorgan’s Law

∀

for all

∃

there exists

∃!

there exists exactly one

Direct Proof

assume if statement is true, then show facts that force then statement to be true

Proof by Contraposition

a proof that p → q is true that proceeds by showing that p must be false when q is false

proof by contradiction

Assuming the opposite to prove a statement.

Proof by Cases

a proof broken into separate cases, where these cases cover all possibilities

without loss of generality

an assumption in a proof that makes it possible to prove a theorem by reducing the number of cases to consider in the proof

Proof by exhaustion

If there are a finite number of possibilities then proving by exhaustion involves testing the assertion in every case.

even

2k for some kEZ

odd

2k+1 for some kEZ

rational

p/q and q=/0

irrational

Cannot be written as a fraction

set

a collection of objects

∈

element of

{,}

braces to contain set elements

N

set of natural numbers

Equal Sets

A=B if and only if for all x(xEA

⊆

subset

⊂

proper subset

empty set

a set with no elements

P(A)

power set

|A|

cardinality

AxB

Cartesian Products

U

union {x | xEA V xEB}

∩

intersection {x | xEA and xEB}

¯A

compliment {xEU | xE/A}

A-B

difference {x | xEA and xE/B}

|AUB|=|A|+|B|-|A∩B|

inclusion/exclusion

f:A->B

function

f(S)={t|EsES(t=f(s))

image of S

f(a)=f(b) -> a=b

one-to-one

AbEB EaEA such that f(a)=b

onto

ceiling

round up

floor

round down

|A| < |P(A)|

Cantor's theorem

divisibility

a | b

Division Algorithm

a=dq+r

Where d is divisor

Q is quotient

R is remainder

quotient

q=a div d (floor a/d)

remainder

r=a mod d (a-d[floor a/d])

a≡b mod m

there exists kEZ such that a=b+km, m | a+b, a mod m=b mod m

GCD

largest integer d | a and d | b

LCM

smallest integer a | d and b | d

Euclidean Algorithm

Used to find the greatest common divisor of a and b. It is the last nonzero number.

Bezout's Theorem

gcd(a,b)=sa+tb

Mathematical Induction

A two-part proof that shows a statement is true for all positive integers by first showing the statement is true for the number one (1), then assuming the statement is true for some positive integer, k, and showing it must then be true for k + 1

Strong Induction

the statement ∀nP (n) is true if P (1) is true and ∀k[(P (1) ∧ · · · ∧ P (k)) → P (k + 1)] is true

at least one

total number - none of one item

permutations

an arragement or listing in which an order or placement is important

P(n,r)

n!/(n-r)!

combination

a grouping of items in which order does not matter

C(n,r)

n!/r!(n-r)!

binomial coefficient formula

(n k) = n!/(k!(n-k)!)

Pascal's Identity

(n+1 choose k) = (n choose k-1) + (n choose k)

Repetition in Combinations

C(n+r-1, n-1)

Multinomial Coefficient

n!/nsub1!nsub2!nsub3!

Pigeonhole Principle

if n items are put into m containers, with n > m, then at least one container must contain more than one item

experiment

procedure that yields one of a given set of possible outcomes

sample space

the set of all possible outcomes

event

A subset of a sample space.

|E|/|S|

probability

N(P'1P'2P'3)

N-N(P1)-N(P2)-N(P3)+N(P1P2)+N(P1P3)+N(P2P3)-N(P1P2P3)

derangement

Dsubn = n![1-1/1!+1/2!-1/3!+…+(-1)^n*1/n!]

relation

a subset of the Cartesian product of two sets.

Reflexive

aRa for every element aEA

symmetric

if aRb, then bRa

antisymmetric

if aRb and bRa then a=b

transitive

If aRb and bRc, then aRc.

Equivalence Relation

a relation that is reflexive, symmetric, and transitive

Equivalence Class

The set of all elements in A that are related to an element of A.

Partial Ordering

a relation that is reflexive, antisymmetric, and transitive

Poset

Partially-Ordered Set

Hasse Diagram

Graphical representation of a partially ordered set.

vertices

dots on a graph

edges

lines on a graph

multiple edges

two or more edges connecting the same two vertices

Simple graph

undirected, no multiple edges, no loops

Multigraph

undirected, multiple edges, no loops

pseudograph

undirected, multiple edges, loops

simple directed graph

directed, no multiple edges, no loops