Quiz 0 Review

Question 1

variables

Question 2

boolean operations

Answer 2

5

Question 3

truth tables

Answer 3

evaluating expressions

Question 4

tautology

Answer 4

always true (law of excluded middle)

Question 5

DeMorgan Laws

Answer 5

not (p or q) = not p and not q
not (p and q) = not p or not q

Question 6

distributive laws

Answer 6

r or (p and q) = (r or p) and (r or q)
r and (p or q) = (r and p) or (r and q)

Question 7

predicates

Answer 7

statements with variables
P(x) - x is even

Question 8

quantifiers

Answer 8

for all and there exists

Question 9

quantifiers DeMorgan Laws

Answer 9

not for all P(X) = there exists not P(x)
not there exists P(x) = for all not P(x)

Question 10

notation for sets

Answer 10

enumeration: A = {a,b,c}
predicate: A= {x | x is even}

Question 11

set operations (5)

Answer 11

union - combine
intersection - common
difference - in one but not the other
complement - everything not in it
cartesian product - pairs of elements

Question 12

empty set

Answer 12

A union empty = A
A intersection empty = empty

Question 13

infinite sets
countable vs uncountable

Answer 13

countable - listed in sequence
uncountable - real numbers between 0 and 1

Question 14

sequence

Answer 14

ordered list, elements can repeat
notation: (a1,a2…) or {an} or (an)

Question 15

set

Answer 15

unordered, elements do not repeat
notation: A = {a1,a2…}

Question 16

sequence vs set

Answer 16

sequence is order with repeat
set is not ordered and do not repeat

Question 17

relation

Answer 17

on A is a subset AxA
how elements relate to each other

Question 18

reflexive

Answer 18

for all A, x,x is in A
every element is related to itself

Question 19

symmetric

Answer 19

for all x and y, x,y is in A and y,x is in A

Question 20

transmitive

Answer 20

for all x,y,z in A, x,y is in A, y,z, is in A so x,z is in A

Question 21

anti symmetric

Answer 21

if x,y in A and y,x in R then x=y

Question 22

partial orders

Answer 22

relation that is reflexive, anti symmetric, and transmitive

Question 23

posets

Answer 23

partially ordered set, set with partial order

Question 24

hasse diagrams

Answer 24

representing a partial order by removing reflexive edges and using directed edges to show ordering
1. draw all elements
2. make arrow relations
3. remove self loops
4. remove transitive edges (ab and bc…remove a to c)
5. bottom to top edges and remove all arrows

Question 25

topological sorting

Answer 25

a linear ordering of elements in a directed acyclic graph (DAG) based on a partial order topological - sort is not unique, no closed cycle, linear ordering u to v, u comes before v in ordering at least one topological sort 1. find in-degree of each 2. start with the vertex that in degree=0 3. delete its out edges - new graph 4. do again

Question 26

equivalence relations

Answer 26

relation that is reflexive, symmetric, transitive

Question 27

equivalence classes

Answer 27

set of all elements related to a given statement under an equivalence relation

Question 28

addition rule

Answer 28

union of disjoint sets A and B are disjoint then |AuB| = |A|+|B|

Question 29

multiplication rule

Answer 29

for independent choices one task in m ways and another in n ways, total ways = m x n

Question 30

subsets

Answer 30

number of subsets of a set of n elements is 2^n

Question 31

permutations

Answer 31

order matters - arrange n elements = n!

Question 32

functions

Answer 32

set A to set B (each in A to exactly one in B) - total = B^A

Question 33

k-permutations

Answer 33

selecting k from n, # of ways with order = n!/(n-k)!

Question 34

k-elements subsets(combinations)

Answer 34

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

Question 35

basic probability

Answer 35

of want / # of total

Question 36

polynomials

Answer 36

degree 2 - quadratic formula, diamond degree 3 - candidates are factors of d, test, then factor out x-# degree 4 - let y=x^2 and solve

Question 37

exponential

Answer 37

b^x

Question 38

logarithmic

Answer 38

log b x what power do i raise b to ger x

Question 39

euler number

Answer 39

e = 2.71828 base of natural log

Question 40

pi

Answer 40

3.14159

Question 41

circumference/diameter for a circle

Answer 41

C= 2pir

Question 42

phi

Answer 42

golden ration = 1.61803 when a line is divided into 2 parts such that ratio of entire length to longer part = ratio of longer to shorter

Question 43

finite arithmetic sequence

Answer 43

difference between consecutive terms is constant an = a1+(n-1)c sn = n(a1+a2)/2...n(n+1)/2

Question 44

finite geometric sequence

Answer 44

each term after the 1st is found by multiplying prev by const r an = a1 x r^n-1 sn = a1 x (1-r^n)/1-r

Question 45

infinite geometric sequences

Answer 45

geometric sequence by 3 of terms are infinite (converge if |r|<1) sn = a1/1-r if |r|<1

Question 46

zeno's paradox

Answer 46

keep halving distances between you and a point, you will never reach it geo with a1=1/2 and r=1/2

Question 47

harmonic numbers

Answer 47

sum of reciprocals, grow without bound

Question 48

fibonacci numbers

Answer 48

F0 = F1, Fn=Fn-1 + Fn-2 each term is sum of 2 prev, grows exponentially

Question 49

prime numbers

Answer 49

natural numbers > 1 has no divisors by 1 and itself

Question 50

composite numbers

Answer 50

natural numbers > 1 can be divided by at least one other number besides 1 and itself

Question 51

prime factors and factorization

Answer 51

expressing composite number as a product of prime numbers

Question 52

gcd

Answer 52

largest number that divides both exactly factorize, common prime factors, gcd=product of prime factors - use smallest power

Question 53

lcm

Answer 53

smallest # that is divisible by both factorize, find all prime factors, lcm=product of all prime factors - use highest power

Question 54

solving quadratics

Answer 54

diamond complete square: ax^2 + bx = -c and add (b/2a)^2 to both sides quadratic formula

Question 55

solving polynomial with integer roots

Answer 55

1. possible roots (factors of d divided by factors of a 2. test 3. facto4r x-test 4. solve

Question 56

factoring polynomials

Answer 56

factoring quadratic grouping difference if square

Question 57

solving sys of linear equations

Answer 57

matrices

Question 58

vectors and matrices and oeprations

Answer 58

vector = add and scalar multiplication matrix = add (same size), multiplication (c=r), det

Question 59

proof

Answer 59

rigorous argument justifying validity of a mathematical statement, showing that this statement logically follows from the assumptions care - provides absolute uncertainty

Question 60

induction

Answer 60

base case inductive step: assume claim holds for n=k that is.. then for n=k+t - use inductive step stuff to make into k+1 want thus claim hold for n=k+1. from the base case and inductive step, claim holds for all n

Question 61

induction sum of arithmetic sequence sum of finite geometric sequence estimate for fibonacci numbers sum of infinite geometric sequence estimating harmonic numbers

Question 62

other proofs if R is an equivalence relation on a set x, then the equivalence classes of R form a partition of x into disjoint sets each finite poset has a topological sort (linear extension) relations involving binomial coefficients, (n choose k) = (n-1 choose k)+(n-1 choose k-1)

Question 63

total number of subsets

Answer 63

2^items

Question 64

ordered without repitition

Answer 64

n!/(n-x)!

Question 65

ordered with repitition

Answer 65

n^x

Question 66

not ordered without repitition

Answer 66

n!/n!(n-x)!

Question 67

ways to order

Answer 67

n!

Question 68

X has n elements, Y has m elements, XxY has...

Answer 68

n x m

Question 69

permutations

Answer 69

n!

Question 70

length k-sequences with repetitions allowed

Answer 70

n^k

Question 71

k-elements subsets

Answer 71

(n choose k)

Question 72

power set

Question 73

finite a^i sum

Answer 73

to n (a^n+1 -1)/a-1