discrete math exam 1

ℝ

all real numbers; positive, negative, fractions, etc.

ℤ

integers; whole numbers, positive and negative

ℕ

natural numbers; positive integers

ℚ

rational numbers

∅ or {}

empty set; no elements

injective (one-to-one)

every output has only one input
f(s) = f(t) implies s = t

surjective (onto)

every element in the codomain (output) is an output for some element in the domain (input)

every element b ∈ B = f(a) for some a ∈ A

identity laws

p ∧ T ≡ p
p ∨ F ≡ p

domination laws

p ∨ T ≡ T
p ∧ F ≡ F

idempotent laws

p ∧ p ≡ p
p ∨ p ≡ p

commutative laws

p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p

associative laws

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ≡ p ∧ (q ∧ r)

distributive laws

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

De Morgan’s laws

¬ (p ∧ q) ≡ (¬p ∨ ¬q)
¬ (p ∨ q) ≡ (¬p ∧ ¬q)

law of excluded middle class

p ∨ ¬p ≡ T

law of contradiction

p ∧ ¬p ≡ T

disjunctive form

p → q ≡ ¬p ∨ q

implication ≡ contrapositive

p → q ≡ ¬q → ¬p

inverse ≡ converse

¬p → q ≡ q → p

predicate

statement that can’t be assigned a truth value unless more info on a variable is supplied

instantiation

process of setting a variable equal to a specific object in its domain of discourse

existential quantification

“There is an x such that”
∃x S(x)

universal quantification

“For all x”
∀x P(x)

modus ponens

p and p → q ∴ q

modus tollens

¬q and p → q ∴ ¬p

hypothetical syllogism

p → q and q → r ∴ p → r

addition (inference)

p ∴ p ∨ q

simplification (inference)

p ∧ q ∴ p

conjunction (inference)

p and q ∴ p ∧ q

disjunctive syllogism

p ∨ q and ¬p ∴ q

universal instantiation

∀x P(x) ∴ P(c) if c is in the domain of x

existential instantiation

∃x P(x) ∴ P(c) for some c in the domain of x

universal generalization

P(c) for arbitrary c in the domain of x ∴ ∀x P(x)

existential generalization

P(c) for some c in the domain of x ∴ ∃x P(x)

equal sets

two sets comprised of exactly the same elements

set-builder notation

A = {x | p(x)}

subset

A ⊆ B if every element of A is also an element of B

power set

set of all subsets of a set

intersection

objects that are in both sets
A ∩ B, {x | x ∈ A ∧ x ∈ B}

union

elements that appear in at least A and B
A ∪ B, {x | x ∈ A ∨ x ∈ B}

symmetric difference

elements which appear in exactly one of A and Bcom

complement of B relative to A

A - B, {x | x ∈ A ∧ x ∈ B}

identity laws (set theory)

A ∩ U = A
A ∪ Ø = A

domination laws (set theory)

A ∪ U = U
A ∩ Ø = Ø

idempotent laws (set theory)

A ∪ A = A
A ∩ A = A

commutative laws (set theory)

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

associative laws (set theory)

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

distributive laws (set theory)

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

De Morgan’s law (set theory)

(A̅ ̅∩̅ ̅B̅)= (A̅ ∪ B̅)
(A̅ ̅∪̅ ̅B̅) = (A̅ ∩ B̅)

law of excluded middle (set theory)

A ∪ A̅ = U

law of contradiction (set theory)

A ∩ A̅ = Ø

cartesian product

A x B; all ordered pairs that can be formed from A and B

ways to justify a step in a proof

1. hypothesis

2. application of a definition

3. known fact proved previously

4. consequence of applying a rule of inference or logical equivalence to earlier steps

direct proof

hypothesis appears as steps, last step is the conclusion

indirect proof

replace implication with the contrapositive and prove that

proof by contradiction

replace theorem r with ¬r → F

existence proof

proof of a statement of form ∃x P(x)

prove by counterexample

how a specific element for which P(x) is falso

bipartite graph

column of dots labeled with names of elements connected by edges

digraph

vertices with edges that have a direction

composition (S by R)

when S is a relation from A to B, and R is a relation from B to C, RºS

Boolean product

product of two matrices

reflexive relation

every element of its domain is related to itself
(∀a ∈ A) [aRa]
main diagonal on matrix is all 1

irreflexive relation

no element of A is related to itself
a(not R)a

main diagonal on matrix is all 0

symmetric relation

if a is related to b, then b is related to a

(a,b) ∈ R → (b,a) ∈ R

antisymmetric relation

if two elements are related in both directions, then they must be the same element

transitive relation

if (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R

equivalence relation

any reflexive, symmetric, transitive relation on set A

equivalence class

the set of all the things in A that are equivalent to x

partition

a set of non-empty, pairwise disjoint subsets whose union is A

floor function

assigns the largest integer less than or equal to x to each real number x, part before decimal

⌊x⌋

ceiling function

fractional part of a number

x - ⌊x⌋ if x≥0

x - ⌈x⌉ if x<0

integral part of a number

⌊x⌋ if x≥0

⌈x⌉ if x<0

power function

f(x) = x^a

law of exponents

a^b+c = a^b + a^c

a^bc = (a^b)^c

a^cb^c = (ab)^c

law of logs

log_abc = log_ab + log_ac

log_a(b^c) = c log_ab

a^log_abc = bc

log_a(x) = lnx/lna