Final Flashcards
Inverse of p->q
!p ->!q
contrapositive of p->q
!q->!p
converse of p->q
q->p
!ExP(x) ->?
Ax!P(x)
!AxP(x) ->?
Ex!P(x)
!AxP(x) with negation inside
Ex!P(x)
Proof by contraposition
p->q = !q->!p then prove this to be true
perfect square x
for some int a; x=a^2
Proof by contradiction
assume false then find a case that makes it true
def: rational number
number can be stated in terms of a/b where a and b are integers and a and b are written in the lowest common term
def: irrational number
number can not be stated in terms of a/b where a and be are integeres
prove if n=ab then (a <= sqr(n))
proof by contradiction a>sqr(n) and b>sqr(n) a>sqr(n) > 0 b > sqr(n) > 0 s > x > 0 t > y > 0 st>xy ab>n contradiction
if n^2 is odd prove n is odd
suppose n is even
n=2k ; n^2 = 4k^2
2*(2k^2) so is even
proof by contraposition
prove sqr(2) is irrational by contradiction
suppose sqr(2) is rational sqr(2) = a/b 2 = a^2/b^2 2b^2 = a^2 so a is even a=2c 2b^2 = 4c^2 b^2=2c^2 so b is even then a and b share common factor b CONTRADICTION
prove sum of rational and irrational is irrational
contradiction:
x=r;y=i;z=r
x+y=z; y=z-x; x = z +(-x)
a/b + c/d = ad+cb/bd which is rational
prove product of 2 rational is rational
a/b * b/c = ab/bc which is rational
prove product of 2 irrational is irrational
sqr(2) * sqr(2) = 2 contradiction
if a < b prove average of a and b is > a
b = a + x
average = (a + a + x)/2
2a/2 + x/2 = a+x/2
x/2 > 0 so true
prove if x is rational x/2 is ratinal
x=a/b
2a/b is rational
prove if x is rational then 3x-1 is rational
x=a/b
3a/b -1
3a/b -b/b
3a-b/b is rational
Identify the following sets N: Z: Z+: Q: R: R+: C:
N: 0,1,2,3 Z:integers Z+: positive integers Q:rational numbers R:real numbers R+:real positive number C:complex numbers
def subset
every element of A is in B
def strict subset
every element of A is in B but there exists an element in B which is not in A
def: power set
all subsets of given set
{0,1} = {{o},{0},{1},{0,1}
def Cartesian Product
A x B = {(a,b) | a∈A ^ b∈B}
def: union of sets
a set that contains elements in A or B or both
A u B = {x| x∈A v x∈b}
def intersection of sets
set contains elements in both A and B
A n B = {x| x∈A ^ x∈B}
def: disjoint sets
intersection of sets is empty
def: complement set
ā = { x∈U | x !∈ a}
def: difference of A and B
A-B = {x | x∈A ^ x!∈B}
prove (A n B) is a subset (<=) A
A n B -> x∈A ^ x ∈ B -> x ∈ A
prove A-B subset of A
(A-B)-> x∈A ^ x !∈B -> x∈A
prove A n (B-A) = 0
A n (B-A) = A n (B ^ !A) A n B n !A = A n !A = 0
prove A u (B-A) = A u B
Au(B-A) = A u (B ^ !A
A u B u(A ^ !A) = A u B
does A=B if A u C=B u C
no if A={1,2} ;B = {3} ;C={1,2,3}
does A=B if A n C = B n C
no, what if A and C have different members both not in C
does A=B if
1. Auc = Buc
and
2. AnC=BnC
yes
1. implies A and B don’t have members different outside of wahts in C
2. implies A and B dont have different numbers besides whats outside of C
Thus they must be the same
How many different three letter initials with none of the leters repeated can people have
26x25x24
How many bit strings of length n where n is a positive integer start and end with 1s
2^(n-2) + 1
How many strings are there of four lowercase letters that have the letter x in them
26^4 -25^4(all strings possible - all strings without the letter x
How many positive integers between 1000 and 9999 are divisible by 9
9999/9 - 999/9all divisible by 9 - lower than 1000 divisible by 9
How many positive integers between 1000 and 9999 are even
9999/2 - 999/2all even - even below 1000
How many positive integers between 1000 and 9999 have distinct digits
9x9x8x7(1-9)x(0-8)x8x7
How many positive integers between 1000 and 9999 are not divisible by 3
(9999-999) - (9999/3 - 999/3)all integers - integers divisible by 3
How many positive integers between 1000 and 9999 are divisible by 5 or 7
(9999/5-999/5) + (9999/7+999/7) -(9999/35 - 999/35)all divisible by 5 + all divisible by 7 - all divisible by both
How many positive integers between 1000 and 9999 are divisible by 5 but not by 7
(9999/5-999/5) -(9999/35 - 999/35)all divisible by 5 - all divisible by 5 and 7
How many positive integers between 1000 and 9999 are divisible by 5 and 7
(9999/35 - 999/35)
How many subsets of a set with 100 elements have more than one element
2^100 - 101all possible - 100 1 elements sets and 1 empty set
A palindrome is a string whos reversal is identical to the string, how many bit strings of length n are palindromes
(2^n/2)
In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if the bride must be in the picture
6(9x8x7x6x5)(1x9x8x7x6x5) + (9x1x8x7x6x5) + (9x8x1x7x6x5) + (9x8x7x1x6x5) + 9x8x7x6x1x5) + (9x8x7x6x5x1)
In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if the bride is not next to the groom
(5x6)(8x7x6x5)first place 4 that are not bride and groom, then place bride in 1 of 5 places then the groom in 1 of 6 places
In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if exactly one of the bride and the groom is in the picture
(8x7x6x5x4)x(2x6)Pick the other 5 people out of 8 then pick bride or groom then put it in one of the 6 possible places
How many bit strings of length 10 contain either 5 consecutive 0s or 5 consecutive 1s
6(2^6)6 possible locations for the string of 5, then possible choices for 5 other bits and if the string is 1 or 0
Show that among any group of five integers there are two with the same remainder when divided by 4
Since there are only 4 outcomes when divided by 4 {0,1,2,3} and there are 5 numbers, it must be the case via the pigeonhole principle that two have the same remainder
Show that any group of d+1 integers there are two with exactly the same remainder when they are divided by d
The possible remainders when divided by d are {0,1,2,…,d-1} which are d in total. since we check d+1 options it must be the case that two have the same remainder via the pigeonhole principle
Given a set of 5 distinct integer coordinates on the xy plane, show that the midpoint of the line joining at least one pair of these points has an integer coordinate
There are only 4 types of points that can occur {(even, odd),(even,even),(odd,odd),(odd,even)}. As we can see that the mid pint on any two of the same would be integers. Via the pigeonhole principle it must be the case that we have a midpoint that lies on integers
if there are 101 people of different heights standing in line it is possible to find 11 people that are in order of increasing or decreasing
theorem: every sequence of n^2+1 distinct real numbers contains a sub sequence of n+1 that is either strictly increasing or decreasing
How many bit strings of length 12 contain exactly three 1s
C(12,3)
How many bit strings of length 12 contain at most three 1s
C(12,0) + C(12,1) + C(12,2) + C(12,3)
How many bit strings of length 12 contain at least 3 1s
2^12 - (C(12,1) + C(12,2) + C(12,0))
How many bit strings of length 12 contain an equal number of 0s and 1s
C(12,6)
Coin flipped eight times, how many possible outcomes in total
2^8
Coin flipped eight times, how many possible outcomes contain three heads
C(8,3)
Coin flipped eight times, how many possible outcomes contain at least three heads
2^8 - (C(8,0) + C(8,1) + C(8,2))total - - 0 head -1 head - 2 head
Coin flipped eight times, how many possible outcomes contain the same number of heads and tails
C(8,4)
How many bit strings of length 10 have exactly three 0s
C(10,3)
How many bit strings of length 10 have more 0s than 1s
C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)
How many bit strings of length 10 have at least seven 1s
C(10,7) + C(10,8) + C(10,9) + C(10,10)
How many bit strings of length 10 have at least three 1s
C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)
How many permutations of the letters ABCDEFGH contain the string ED?
7!
How many permutations of the letters ABCDEFGH contain the string CDE?
6!
How many permutations of the letters ABCDEFGH contain the string BA and FGH?
5!
How many permutations of the letters ABCDEFGH contain the string AB, DE and GH?
5!
How many permutations of the letters ABCDEFGH contain the string CAB and BED?
4!
How many permutations of the letters ABCDEFGH contain the string BCA and ABF?
none since the b would never line up
How many ways to order 10 women and six men
10! x C(11,6) x 6!
Ways to form a committee of 6 with 15 women and 10 men with more women then men
C(15,6) + C(15,5)C(10,1) + C(15,4)C(10,2)
{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}reflexive, symmetric, antisymmetric, transitive?
transitive
{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}reflexive, symmetric, antisymmetric, transitive?
reflexive, transitive, symmetric
{(1,1),(2,2),(3,3),(4,4)reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, antisymmetric, transitive
a is taller than breflexive, symmetric, antisymmetric, transitive?
transitive, antisymmetric
a and b were born on the same dayreflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
a has the same first name as breflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
a and b have a common grandparentreflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric
x + y = 0reflexive, symmetric, antisymmetric, transitive?
symmetric
x = +-yreflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
x=1reflexive, symmetric, antisymmetric, transitive?
antisymmetric, Transitive
xy >=0
reflexive, symmetric
Show that r=empty set on a nonempty set is symmetric and transitive, but not reflexive
answer?
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R1
R1
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R2
R1
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R3
?
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R4
R^2
R1 = a divides bR2 = a is a multiple of bR1 u R2
a divides b or b divides a
R1 = a divides bR2 = a is a multiple of bR1 n R2
a = b or a=-b
if R and S are reflexive prove that R u S is reflexive
R and S are reflexive on Aso for all x in A, (x,x) is in R and S.
if R and S are reflexive prove that R n S is reflexive
R and S are reflexive on Aso for all x in A, (x,x) is in R and S.
Equivalence, if not what properties do they lack?a and b are the same age
yes
Equivalence, if not what properties do they lack?a and b have the same parents
yes
Equivalence, if not what properties do they lack?a and b share a common parent
no missing transitive
Equivalence, if not what properties do they lack?a and b have met
no missing transitive
Equivalence, if not what properties do they lack?a and b speak a common language
nomissing transitive
Equivalence, if not what properties do they lack?f(1)=g(1)
equivalence????
Equivalence, if not what properties do they lack?f(x)-g(x)=1
not reflexive, symmetric or transitive
Equivalence, if not what properties do they lack?f(x)-g(x) = C
equivalence????
Equivalence, if not what properties do they lack?f(0)=g(1) and f(1)=g(0)
not transitive or reflexive
f A->BDomain?
A
f A->Bcodomain
B
f A->Bimage
f(a)=bb is image
f A->Bpreimage
f(a)=ba is preimage
f maps A to B
f is a function that connects A to B
when are two functions equal
when they both have the same domain, codomain, and map each element in their domain to the same element in their codomain
(f1+f2)(x)
f1(x) + f2(x)
(f1f2)(x)
f1(x)*f2(x)
one-to-one function
f(a)=f(b) ->a=b
onto
for all b E B there is an element a E A f(a)=b
surjective
a function that is onto
one-to-one correspondence or bijection
if f is one-to-one and onto
(f o g)(x)
f(g(x))
floor function
assigns to a real number the largest integer that is less to or equal to it
roof function
assigns to a real number the largest smallest integer that is greater than or equal to it
Show that C(n,n/2) >= (2^n)/n
C(n,n/2) is the middlemost element in the binomial equation. 2^n is the sum of an entire level of the binomial equation, and when divided by n it is the average of all elements. Since the middlemost element is always larger than the average
Combinatorial proof:k(n choose k) = n((n-1) choose (k-1))
LHS: choose k elements then choose 1 out of the kRHS: choose 1 element then choose the k-1 others
(n choose r)(r choose k) = (n choose k)((n-k) choose (r-k))
LHS:choose set r then from r choose subset kRHS:Choose subset then choose the remaining for larger set
variety of ways to choose a dozen donuts from 20 varieties if there are no two donuts of the same variety
C(20,12)
variety of ways to choose a dozen donuts from 20 varieties if all donuts are of the same variety
C(20,1)
variety of ways to choose a dozen donuts from 20 varieties if there are no restrictions
c(12+20-1,12)choices plus varieties -1 choose choices
r-combinations of a set with n elements when repetition is aloud
C(n+r-1,r)
variety of ways to choose a dozen donuts from 20 varieties if there are at least two varieties among the dozen donuts chosen
C(12+20-1,r) -20all permutations minus 20 where they are all the same type
variety of ways to choose a dozen donuts from 20 varieties if theree must be at least six blueberry filled donuts
C(6+20-1,6)
variety of ways to choose a dozen donuts from 20 varieties if theree can be no more than six blueberry filled donuts
C(12+20-1,12) - C(5+20-1,5)
C(x,y)
x!/((y!)(x-y)!)
Def Tree:
A connected, undirected graph with no simple circuits
an undirected graph is a tree iff
there is a unique simple path between any two of its vertices
Def Rooted Tree:
a tree in which one vertex has been designated as the root and every edge is directed away from the root
Def m-ary tree
if every internal vertex has no more than m children
def Full m-ary Tree
if every internal vertex has exactly m children
internal vertex
a vertex that has children
A tree with n vertices has how many edges
n-1
A full m-ary tree with i internal vertices contains how many vertices
mi+1 vertices
A full m-ary tree with n vertices has how many internal vertices, how many leaves
(n -1)/m internal vertices and n-internal vertices leaves
A full m-ary tree with i internal vertices has how many vertices
mi+1
How many ways are there to arrange the letters in THANKSGIVING
12!/((2!)(2!)(2!))divided by 2! for doubles of letters
How many ways are there to arrange the letters in THANKSGIVING that start with a T
11!/((2!)(2!)(2!))
How many ways are there to arrange the letters in THANKSGIVING contain the word HAT
10!/((2!)(2!)(2!))
How many ways are there to arrange the letters in THANKSGIVING where the two G’s are not next to each other
???
How many ways are there to arrange the letters in THANKSGIVING where the vowels are in alphabetical order
???
How many different functions are there from a set of 5 elements to a set of 6
6^5
How many functions from a 5 element set too a 6 element set are 1-1
6x5x4x3x2
How many functions from a 5 element set to a 6 element set are onto
This is not possiible because a function only has 1 output so 5 functions could not output 6 answers
How many different relations are there from a 5 element set to a 6 element set
2^(5*6)
2 because its either in or not in the set
How many reflexive relations are there from a 5 element set to a 6 element set
5 at most
Prove or Disprove: if the relation R1 and R2 are symmetric, then so is R1 n R2
AaEA AbEB if (a,b) E R1 ->(a,b) E R1 and (a,b)E R2 -> (b,a)E R2 since
so it must be the case (a,b) E R1nR2->(b,a)E R1nR2
Prove or Disprove: if the relation R1 and R2 are transitive, then so is R1 n R2
AaAbAc{abc|(((a,b)E R1^(b,c)E R1)-> (a,c)E R1) ^ ((a,b)E R2^(b,c)E R2)-> (a,c)E R2) then it must be the case tha
((a,b)E R1nR2 ^(b,c)E R1nR2)-> (a,c)E R1nR2)
Could the following degree sequences be a simple graph:
2,3,3,3,4,6
NO degree of 6 is impossible since no loops and only 6 vertices
Could the following degree sequences be a simple graph:
2,4,6,8,10,12
NO degrees higher than amoutn of verticies
Could the following degree sequences be a simple graph:
0,1,2,2,4,5
No since degree of 5 implies that 1 vertice touches all others, but one of those verticies has degree 0 so this cannot be the case
Could the following degree sequences be a simple graph:
3,3,3,3,3,3
YES
if G and H are isomorphic graphs, show that !G and !H are isomorphic
since both graphs have matching edges, Possible^!G=G, so they have matching nonadjacencies so they must be isomorphic
def: self complementary
if G and !G are isomorphic
Show that if G is self complementary with v vertices then v % 4 = 0 or 1
Eg = c(v,2) - Eg 2Eg = v!/((v-2)!2! 4Eg=v!/(v-2)! 4Eg=v(v-1) ???????
Def: Adjacency Matrix
[0110] [1001] [1001] [0110] graphs shoowing which vertices connect vertices x vertices
Def: Adjacency List
list of vertices and the ones t hey connect to
ex: vertex A –> b,c,d
Def: Incidence matrices
same as adjacency Matrix except Vertices x edges
Def: Isomorphic
There exists a function that is 1-1 and onto that can trun one graph into the other
basically they are the same graph drawn differently
Def: graph invarient
A property reserved by isomorphism of graphs
ex: same number of degrees, or vertices
Def: Planar Graph
a graph that can be drawn on a plane without any edges overlapping
A graph is nonplanar if it contains either of these 2 subgraphs
k(5) and k(3,3)
Def: Eulers Formula
Regions = edges- vertices+2
G is connected planar graph with e edges and vertices where v>=3 then ?
e <= 3y-6
G is connected planar graph with e edges and vertices where v>=3 and no circuits then ?
e<=2v-4
Suppose that a connected bipartite planar simple graph has e edges and v vertices, show that e=3
since bipartite all faces have 4 edges or g each edge used for 2 faces 4r=e-v+2 // *2 e >= 2e -2v + 4 //-2e -e >= -2v + 4 //*-1 e <= 2v -4
By removing 1 vertices and all connecting edges can you make these graphs planar K5 K6 K3,3 K3,4
K5 yes
K6 no
K3,3 yes
K3,4 depends which you remove
Show that a simple graph with a circuit that has an odd number of vertices in it cannot be colored by 2 colors
????
Def: Uniform Distribution of probability
each possible outcome is 1/n
Complement of probability
p(!E) = 1-p(E)
p(E1 u E2)
p(21) + p(E2) - p(E1 n E1)
conditional probability
p(E|F)
P(E n F) / p(F)
to dependents are independent iff?
p(EnF)= p(E)p(F)
Mutually independent
p(Ei1 n Ei2 n … n Ein = p(Ei1)p(Ei2)…p(Ein)
Bernoulli Trial
An experiment with two possible outcomes
ex flipping coin
Def Mutually independent
The probability of success on an given trial has no bearing on the next
Coin is flipped 7 times where the probability of heads is 2/3, what is the probability that 4 heads come up
C(7,4) * (2/3)^4 * (1/3)^3
Probability of K successes out of N trials
probability of T = p
probability of F = q
C(N,K) * p^k * q^n-k
What is the probability that a fair die comes up even if rolled six times
(1/2)^6
What is the probability that a positive integer not exceeding 100 selected at random is divisible by 3
100/3
33/100 = .33
33%
What is the probability that a positive integer not exceeding 100 selected at random is divisible by 5 or 7
100/5 = 20; 100/7 = 14; 100/35 = 2 20 + 14 - 2 = 32 32/100 = .32
Probability that 4 people win 1st,2nd,3rd,4th respectively out of 50 people if you can only win 1 prize
1/501/491/48*1/47
Probability that 4 people win 1st,2nd,3rd,4th respectivly out of 50 people if you can win multiple prizes
(1/50)^4
Independent?
first coin comes up heads
second coin comes up tails
yes
P(E1nE2) = 1/16
P(E1)p(E2) = 1/4 * 1/4 = 1/16
Independent?
first coin
???
