Discrete math 1

definitions take the form of

an object x is called the term being defined provided it satisfies specific conditions

divisible

an integer a is divisible by integer b, denoted b|a provided there exists an integer c such that a = bc

even

an integer a is called even provided that it is divisible by 2. this means there exists some integer k such that a = 2k. (7|21)

odd

an integer a is called odd provided that there exist an integer k such that a = 2k + 1

prime

a positive integer p is called prime provided p is greater than 1 and that the only positive divisors of p are 1 & p

composite

a positive integer a is called composite provided there is an integer b such that 1 < b < a

N

the set of natural numbers: {0,1,2,3,...}

Q

The set of rational number : {a / b | a, b ∈ Z & b ≠ 0}

Z

the set of integers : {..,-2,-1, 0, 1, 2}

R

real numbers

mathematical writing

1. use complete sentences

2. be precise

3. rewrite

4. first perso plura;

theorem

a declarative statement for which there is proof, it is absolute and alwaus true

predicate

truth values depends on the variable assignment, neither true or false (once assigned it becomes a statement)

proposition

a statement is either true or false

if-then statement

if A then B

- implication

- if A happens, B happens

if and only if statement

A if and only b

- biconditional statement

- denotes equivalence

converse statements

written by exchanging the hypothesis and conclusion (if A then B -> If B, then A)

contrapositive statements

If not B then not A

- exchanges the hypothesis and conclusion and negates both parts

Vacous Truths

If A then B, when A is impossible

truth tables

- 2^n columns; n = number of propositions/variables

- used to evaluate truth values of compound statements

tautology

always trues

contradiction

always false

AND

- both are true

- multiplication

OR

- one is true

- addition

NOT

- neither is true

counterexample

case where a general statement is false. It disproves a claim by showing an instance where the hypothesis holds, but the conclusion does not

order of operation

parenthese, NOT, AND, OR

logical equivalence

A ≡ B if A ↔ B; meaning they have the same truth value for all possible values of their variables

- prove by properties and truth tables

identity laws

p ∧ T ≡ p

p ∨ F ≡ p

domination laws

p ∨ T ≡ T

p ∧ F ≡ F

idempotent laws

p ∨ p ≡ p

p ∧ p ≡ p

double negation laws

¬(¬p) ≡ p

absorption laws

p ∨ (p ∧ q) ≡ p

p ∧ (p ∨ q) ≡ p

negation laws

p ∨ ¬p ≡ T

p ∧ ¬p ≡ F

commutative laws (order)

p ∨ q ≡ q ∨ p

p ∧ q ≡ q ∧ p

associative laws (grouping)

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

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

distributive laws

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

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

- notice sign change

de Morgans' Laws

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

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

prop 7. 3

x → y ≡ (¬ x) ∨ y

contingency

not a tautology or contradiction

is if true, then false valid?

no, this is always a false statement (the reverse is valid, because if no valid claim is made on the hypothesis, no claim can be made about the conclusion, it can exist independently;)

writing mathematical proofs

Restate the problem, define terms, choose proof method (direct, contradiction, induction, contrapositive), break it down step-by-step, justify each step, and conclude by proving the statement

direct proofs

- starts with known facts or assumptions and logically deduces the statement you're trying to prove; used for conditional statements

If p then q

Assume p

Therefore q

proof by contradiction

proof by contradiction assumes that the statement you're trying to prove is false, then shows this leads to a contradiction.

proof by induction

contrapositive proof

Assume not Q, then show not P , and since

~Q -> ~P is logically equivalent to P -> Q, we have proven both.

Assume not Q

.

.

.

Thus not P

Thus not Q implies not P

Thus P implies Q

lists

- ordered sequence of objects

- order matters

- repetition allowed

- (1,2, 3, 3, 1)

sets

- unordered sequences

- no repetition

- {1, 2, 3, 4}

- cardinality or size denoted by |A|(finite if cardinality is an integer, other wise it is infinite)∈

multiplication rule

If one event can happen in A ways and a second event can happen in B ways, the total number of ways both events can happen is A×B

permutation (order matters)/falling factorial

- P(n, k)/(n)k = n!/(n-k)! if repetition forbidden (n(n-1)(n-2)..(n - k+1))

- n^k if repetition allowed

- k ≤ n

binomial coefficient (order does not matter)

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

- number of ways to choose k items from a set of n distinct items

- n choose k

- repetition not allowed

inclusion-exclusion principle

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

- used when counting overlapping evenets

partitions

a way of dividing the set into non-empty subsets such that every element is in exactly one subset.

factorials (when n = k)

the numbers of lists of lengths where the elements are chosen from a pool of possibilities and no two elements are the same

- choosing order of all items rather than a subset

- (n)n

- 0! = 1

- n! = ∏ k = 1, n k

set builder notation

{dummy element ∈ set : conditions}

- {x :x ∈ X, x ≥ 0}

subsets

When every element of A is also an element of B; A ⊆ B

- ∅ is always a subset of any set

- number of possible subsets = 2 ^ |A|

# of possible subsets

2 ^ |A|

- to create a subset of a, each ai is either in the subset or not, yielding 2^n options

- equal to power ser

power sets

The set of all subsets of a set A, denoted P(A), is called the power set of A.

ex:

If A = {a,b} then

P(A) = {ø, {a},{b},{a,b}}

proof by double inclusion

1. Prove A ⊆ B. Show that every element of set A is also an element of set B.

2. Prove B⊆A. Show that every element of set B is also an element of set A.

If both inclusions are true, then A=B7

UNION

DENOTED BY U & = OR

- A U B is the elements in A or B or both

- no repeitiion

- A U B = { x: x ∈ A ∨ x ∈ B}

INTERSECTION

- DENOTED BY & = AND

- A ∩ B elements both in A & B

- A ∩ B = {x: x ∈ A ∧ x ∈ B}

addition principle

If two sets A and B are disjoint (no elements in common), then the number of elements in their union is:

∣A∪B∣=∣A∣+∣B∣

set difference

- set of all elements of A that are not in B

- {x: x ∈ A ∧ x ∉ B}

symmetric difference

- set of all elements in A but not in B or in B not A

- A Δ B

- {x: x ∈ A - B ∨ x ∈ B- a}

Cartesian Product of Sets

- denoted A x B is the set of all ordered pairs formed by taking an element from A with an element from B

- Ax B = { (a, b) : a ∈ A, b ∈ B}

- A x B ≠ B x A

pairwise disjoint

if every pair of distinct sets in the sequence is disjoint

disjoint

Mutually Exclusive

Existential Quantifier

∃ "there exists, for some"

- at least one, could be more

- ∃ x ∈ A, assertions about x

- negation: ¬ (∃ x ∈ A, assertions about x)

Universal Quantifier

∀ "for all, each, every"

- all elements verify conditions with exception

- ∀ x ∈ A, assertion about x

- negation: ¬ (∀ x ∈ A, assertion about x)

combinatorial proof

1. pose a counting question

2: LHS

3: RHS

4. Conclusion

relation

a set of ordered pairs

- R is a relation on A and B provided that R ⊆ A x B

- aRb = (a ,b) ∈ R ⊆ A x B

relation on between sets

- R is a relation ON A provided R ⊆ A x A

- R is a relation FROM A TO B provided R ⊆ A x B

inverse relation

- the inverse of r, R ^ -1,is the relation formed by reversing the order of all ordered pairs in r

- R ^ -1 = { (x, y) : (y, x) ∈ R}

prop 14.6

suppoe (x, y) ∈ R, then (y , x) ∈ R^ -1. thus (x ,y) ∈ (R^-1)^-1. now suppose (x, y) ∈ (R^-1)&-1 and so (x, y) ∈ R

reflexive

for all x ∈ A, we have x R x

- every element relates to itself

irreflexive

for all x ∈ A, x /R x

- no element relates to itself

symmetric

for all x, y ∈ A, x R y → y R x

- if x is related to y then y is related to x

antisymmetric

for all x, y ∈ A, ( x R y ∧ y R x) → x = y

- if x is related to y and y is related to x, then they are equal

transitive

for all x , y , z ∈ A ( x R y ∧ y R z) → x R z

- if x is related to y, and y is related to z, then x is related to z

congruence modulo n

x ≡ y (mod n ) provided n | (x -y)

- x ≡ y (mod n ) if and only if x and y differ by a multiple of n

15.5

the is congruent mod n relation on the set of integers

equivalence relations

Relations that are reflexive, symmetric, and transitive

equivalence classes

set of elements related under an equivalence relation

-[a] = {x ∈ a : x R a}

- non empty pairiwise disjoint

an partition of a set...

gives rise to an equivalence relation

pascal's identity

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

strong induction

1. Prove some base case

2. Show correctness for all input values up to some value k

3. Show correctness for an input k + 1