discrete structures final exam

OU cs 3000

conjunction (and, ^)

P = its raining

Q = its cold

both statements must be true

P ^ Q = its raining and its cold

disjunction (or, V)

P = it is sunny

Q = it is windy

at least one statement must be true

P V Q = it is sunny or it is windy

exclusive or (xor)

p = light is on

q = fan is on

one statement must be true, but not both

p xor q = one is on but not both

conditional (if-then)

p = its raining

q = the ground is wet

if the first part is true, then the second part must also be true

if it rains, then the ground is wet

converse

q → p

p = its raining

q = ground is wet

flip the if and then

if the ground is wet then it is raining

inverse

~p → ~q

p = its raining

q = ground is wet

negate both hypothesis and conclusion

if it is not raining then the ground is not wet

contrapositive

~q → ~p

p = its a dog

q = its a mammal

negate and flip hypothesis and conclusion

if it is not a mammal then it is not a dog

negation

~p

p = its sunny

opposite (ex: not p)

it is not sunny

biconditional (if and only if)

p ↔ q

both sides must be both true or both false

ex: you can only drive if you have a license

modus ponens

if p → q and p is true, then q must be true

modus tollens

if p → q and q is false then p must be false

direct proof

prove is n is even then n² is even

prove a statement directly

let n = 2k

n² = 4k² = 2(2k²) which is even

indirect proof

assume the opposite to derive a contradiction

universal quantifier

upside down A, for all elements in a set

existential quantifier

backwards E, there exists at least one element in a set

negation of quantifiers

A becomes E and vice versa

math definition of even numbers

2k

math definition of odd numbers

2k + 1

rational numbers

numbers that can be written as a fraction of integers, p/q, where they are both real numbers and q ≠ 0

divisibility

int a divides b if there is an int c such that b = a * c

a | b if b = a * c

prime factorization

ex: 60

expressing a number as a product of primes

60 = 2² * 3 * 5

quotient-remainder theorem

any integer n can be written as

n = dq + r where 0 <= r < d

r = remainder, q = quotient, d = divisor

finding a formula

ex: 2, 4, 6, 8 …

a_n = 2n

look for patterns that get you from one number to the next

summation (∑)

∑ₖ₌₁ⁿ k = 1 + 2 + 3 + ... + n = n(n+1)/2

sum of terms in a sequence (with lower and upper limit)

product notation (∏)

∏ₖ₌₁ⁿ k = 1 2 3 ... n = n!

product of terms in a sequence

inductive proof

step 1: base case, prove true for smallest value

step 2: inductive hypothesis, set n = k and replace

step 3: prove true for n = k + 1

set membership

x ∈ A means x is in set A.

subset

A ⊆ B means every element of A is in B.

union

A ∪ B = { x | x ∈ A or x ∈ B }.

intersection

A ∩ B = { x | x ∈ A and x ∈ B }.

difference

A - B = elements in A but not in B

disjoint sets

A ∩ B = ∅

partition

A set split into disjoint, non-empty subsets

cartesian product

A × B = { (a, b) | a ∈ A, b ∈ B }

power set

All subsets of A, including the empty set

well defined function

every input has exactly one output

one-to-one functions

f(a) = f(b) implies a = b

each element in the domain maps to one element in the codomain

onto functions

Every y ∈ codomain has at least one x ∈ domain.

inverse function

f⁻¹(f(x)) = x.

reverses original function (swap y and x)

cardinality

number of elements in a set

reflexive

a is related to a (itself)

symmetric

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

transitive

if a is related to b and b is related to c then a is related to c

congruence modulo (mod) n

a ≡ b mod n ↔ n | (a - b).

two numbers are congruent mod n if their remainders when divided by n are the same

relatively prime

gcd(a, b) = 1

relatively prime if the greatest common denominator is 1

RSA encryption

1. choose primes p, q

2. compute n = pq

3. choose e such that gcd(e, n) = 1

4. find d as inverse of e mod n

5. encryption c = m^e mod n

6. decryption m = c^d mod n

probability- multiplication rule

for independent events: P(A ∩ B) = P(A) * P(B).

probability- addition rule (disjoint)

P(A ∪ B) = P(A) + P(B).

probability- difference rule

P(A \ B) = P(A) - P(A ∩ B).

probability- permutations

n! / (n - r)!

number of ways to arrage a set of items

probability- combinations

n C r = n!/ (r!(n-r)!)

number of ways to select a subset of items from a set

pascal’s triangle

triangle giving binomial coefficients

binomial theorem

(a+b)^n = ∑k=0, n ​(^k _n​)a^(n−k) b^k.

big-o

describes upper bound (worst-case) of an algorithms run-time

ex: f(n) = 3n² + 5n is O(n²)

big-omega

f(n) = Ω(n²) if it grows at least as fast as n²

lower bound (best case scenario)

big-theta

exact bound (both upper and lower).
Example: f(n) = Θ(n²).