Final Flashcards
1
Q
Inverse of p->q
A
!p ->!q
2
Q
contrapositive of p->q
A
!q->!p
3
Q
converse of p->q
A
q->p
4
Q
!ExP(x) ->?
A
Ax!P(x)
5
Q
!AxP(x) ->?
A
Ex!P(x)
6
Q
!AxP(x) with negation inside
A
Ex!P(x)
7
Q
Proof by contraposition
A
p->q = !q->!p then prove this to be true
8
Q
perfect square x
A
for some int a; x=a^2
9
Q
Proof by contradiction
A
assume false then find a case that makes it true
10
Q
def: rational number
A
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
11
Q
def: irrational number
A
number can not be stated in terms of a/b where a and be are integeres
12
Q
prove if n=ab then (a <= sqr(n))
A
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
13
Q
if n^2 is odd prove n is odd
A
suppose n is even
n=2k ; n^2 = 4k^2
2*(2k^2) so is even
proof by contraposition
14
Q
prove sqr(2) is irrational by contradiction
A
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
15
Q
prove sum of rational and irrational is irrational
A
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
16
Q
prove product of 2 rational is rational
A
a/b * b/c = ab/bc which is rational
17
Q
prove product of 2 irrational is irrational
A
sqr(2) * sqr(2) = 2 contradiction
18
Q
if a < b prove average of a and b is > a
A
b = a + x
average = (a + a + x)/2
2a/2 + x/2 = a+x/2
x/2 > 0 so true
19
Q
prove if x is rational x/2 is ratinal
A
x=a/b
2a/b is rational
20
Q
prove if x is rational then 3x-1 is rational
A
x=a/b
3a/b -1
3a/b -b/b
3a-b/b is rational
21
Q
Identify the following sets N: Z: Z+: Q: R: R+: C:
A
N: 0,1,2,3 Z:integers Z+: positive integers Q:rational numbers R:real numbers R+:real positive number C:complex numbers
22
Q
def subset
A
every element of A is in B
23
Q
def strict subset
A
every element of A is in B but there exists an element in B which is not in A
24
Q
def: power set
A
all subsets of given set
{0,1} = {{o},{0},{1},{0,1}
25
def Cartesian Product
A x B = {(a,b) | a∈A ^ b∈B}
26
def: union of sets
a set that contains elements in A or B or both
| A u B = {x| x∈A v x∈b}
27
def intersection of sets
set contains elements in both A and B
| A n B = {x| x∈A ^ x∈B}
28
def: disjoint sets
intersection of sets is empty
29
def: complement set
ā = { x∈U | x !∈ a}
30
def: difference of A and B
A-B = {x | x∈A ^ x!∈B}
31
prove (A n B) is a subset (<=) A
A n B -> x∈A ^ x ∈ B -> x ∈ A
32
prove A-B subset of A
(A-B)-> x∈A ^ x !∈B -> x∈A
33
prove A n (B-A) = 0
```
A n (B-A) = A n (B ^ !A)
A n B n !A = A n !A = 0
```
34
prove A u (B-A) = A u B
Au(B-A) = A u (B ^ !A
| A u B u(A ^ !A) = A u B
35
does A=B if A u C=B u C
no if A={1,2} ;B = {3} ;C={1,2,3}
36
does A=B if A n C = B n C
no, what if A and C have different members both not in C
37
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
38
How many different three letter initials with none of the leters repeated can people have
26x25x24
39
How many bit strings of length n where n is a positive integer start and end with 1s
2^(n-2) + 1
40
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
41
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
42
How many positive integers between 1000 and 9999 are even
9999/2 - 999/2all even - even below 1000
43
How many positive integers between 1000 and 9999 have distinct digits
9x9x8x7(1-9)x(0-8)x8x7
44
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
45
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
46
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
47
How many positive integers between 1000 and 9999 are divisible by 5 and 7
(9999/35 - 999/35)
48
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
49
A palindrome is a string whos reversal is identical to the string, how many bit strings of length n are palindromes
(2^n/2)
50
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)
51
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
52
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
53
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
54
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
55
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
56
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
57
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
58
How many bit strings of length 12 contain exactly three 1s
C(12,3)
59
How many bit strings of length 12 contain at most three 1s
C(12,0) + C(12,1) + C(12,2) + C(12,3)
60
How many bit strings of length 12 contain at least 3 1s
2^12 - (C(12,1) + C(12,2) + C(12,0))
61
How many bit strings of length 12 contain an equal number of 0s and 1s
C(12,6)
62
Coin flipped eight times, how many possible outcomes in total
2^8
63
Coin flipped eight times, how many possible outcomes contain three heads
C(8,3)
64
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
65
Coin flipped eight times, how many possible outcomes contain the same number of heads and tails
C(8,4)
66
How many bit strings of length 10 have exactly three 0s
C(10,3)
67
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)
68
How many bit strings of length 10 have at least seven 1s
C(10,7) + C(10,8) + C(10,9) + C(10,10)
69
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)
70
How many permutations of the letters ABCDEFGH contain the string ED?
7!
71
How many permutations of the letters ABCDEFGH contain the string CDE?
6!
72
How many permutations of the letters ABCDEFGH contain the string BA and FGH?
5!
73
How many permutations of the letters ABCDEFGH contain the string AB, DE and GH?
5!
74
How many permutations of the letters ABCDEFGH contain the string CAB and BED?
4!
75
How many permutations of the letters ABCDEFGH contain the string BCA and ABF?
none since the b would never line up
76
How many ways to order 10 women and six men
10! x C(11,6) x 6!
77
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)
78
{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}reflexive, symmetric, antisymmetric, transitive?
transitive
79
{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}reflexive, symmetric, antisymmetric, transitive?
reflexive, transitive, symmetric
80
{(1,1),(2,2),(3,3),(4,4)reflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, antisymmetric, transitive
81
a is taller than breflexive, symmetric, antisymmetric, transitive?
transitive, antisymmetric
82
a and b were born on the same dayreflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
83
a has the same first name as breflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
84
a and b have a common grandparentreflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric
85
x + y = 0reflexive, symmetric, antisymmetric, transitive?
symmetric
86
x = +-yreflexive, symmetric, antisymmetric, transitive?
reflexive, symmetric, transitive
87
x=1reflexive, symmetric, antisymmetric, transitive?
antisymmetric, Transitive
88
xy >=0
reflexive, symmetric
89
Show that r=empty set on a nonempty set is symmetric and transitive, but not reflexive
answer?
90
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R1
R1
91
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R2
R1
92
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R3
?
93
R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R4
R^2
94
R1 = a divides bR2 = a is a multiple of bR1 u R2
a divides b or b divides a
95
R1 = a divides bR2 = a is a multiple of bR1 n R2
a = b or a=-b
96
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.
97
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.
98
Equivalence, if not what properties do they lack?a and b are the same age
yes
99
Equivalence, if not what properties do they lack?a and b have the same parents
yes
100
Equivalence, if not what properties do they lack?a and b share a common parent
no missing transitive
101
Equivalence, if not what properties do they lack?a and b have met
no missing transitive
102
Equivalence, if not what properties do they lack?a and b speak a common language
nomissing transitive
103
Equivalence, if not what properties do they lack?f(1)=g(1)
equivalence????
104
Equivalence, if not what properties do they lack?f(x)-g(x)=1
not reflexive, symmetric or transitive
105
Equivalence, if not what properties do they lack?f(x)-g(x) = C
equivalence????
106
Equivalence, if not what properties do they lack?f(0)=g(1) and f(1)=g(0)
not transitive or reflexive
107
f A->BDomain?
A
108
f A->Bcodomain
B
109
f A->Bimage
f(a)=bb is image
110
f A->Bpreimage
f(a)=ba is preimage
111
f maps A to B
f is a function that connects A to B
112
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
113
(f1+f2)(x)
f1(x) + f2(x)
114
(f1f2)(x)
f1(x)*f2(x)
115
one-to-one function
f(a)=f(b) ->a=b
116
onto
for all b E B there is an element a E A f(a)=b
117
surjective
a function that is onto
118
one-to-one correspondence or bijection
if f is one-to-one and onto
119
(f o g)(x)
f(g(x))
120
floor function
assigns to a real number the largest integer that is less to or equal to it
121
roof function
assigns to a real number the largest smallest integer that is greater than or equal to it
122
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
123
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
124
(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
125
variety of ways to choose a dozen donuts from 20 varieties if there are no two donuts of the same variety
C(20,12)
126
variety of ways to choose a dozen donuts from 20 varieties if all donuts are of the same variety
C(20,1)
127
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
128
r-combinations of a set with n elements when repetition is aloud
C(n+r-1,r)
129
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
130
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)
131
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)
132
C(x,y)
x!/((y!)(x-y)!)
133
Def Tree:
A connected, undirected graph with no simple circuits
134
an undirected graph is a tree iff
there is a unique simple path between any two of its vertices
135
Def Rooted Tree:
a tree in which one vertex has been designated as the root and every edge is directed away from the root
136
Def m-ary tree
if every internal vertex has no more than m children
137
def Full m-ary Tree
if every internal vertex has exactly m children
138
internal vertex
a vertex that has children
139
A tree with n vertices has how many edges
n-1
140
A full m-ary tree with i internal vertices contains how many vertices
mi+1 vertices
141
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
142
A full m-ary tree with i internal vertices has how many vertices
mi+1
143
How many ways are there to arrange the letters in THANKSGIVING
12!/((2!)(2!)(2!))divided by 2! for doubles of letters
144
How many ways are there to arrange the letters in THANKSGIVING that start with a T
11!/((2!)(2!)(2!))
145
How many ways are there to arrange the letters in THANKSGIVING contain the word HAT
10!/((2!)(2!)(2!))
146
How many ways are there to arrange the letters in THANKSGIVING where the two G's are not next to each other
???
147
How many ways are there to arrange the letters in THANKSGIVING where the vowels are in alphabetical order
???
148
How many different functions are there from a set of 5 elements to a set of 6
6^5
149
How many functions from a 5 element set too a 6 element set are 1-1
6x5x4x3x2
150
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
151
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
152
How many reflexive relations are there from a 5 element set to a 6 element set
5 at most
153
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
154
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)
155
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
156
Could the following degree sequences be a simple graph:
| 2,4,6,8,10,12
NO degrees higher than amoutn of verticies
157
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
158
Could the following degree sequences be a simple graph:
| 3,3,3,3,3,3
YES
159
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
160
def: self complementary
if G and !G are isomorphic
161
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)
???????
```
162
Def: Adjacency Matrix
```
[0110]
[1001]
[1001]
[0110]
graphs shoowing which vertices connect
vertices x vertices
```
163
Def: Adjacency List
list of vertices and the ones t hey connect to
| ex: vertex A --> b,c,d
164
Def: Incidence matrices
same as adjacency Matrix except Vertices x edges
165
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
166
Def: graph invarient
A property reserved by isomorphism of graphs
| ex: same number of degrees, or vertices
167
Def: Planar Graph
a graph that can be drawn on a plane without any edges overlapping
168
A graph is nonplanar if it contains either of these 2 subgraphs
k(5) and k(3,3)
169
Def: Eulers Formula
Regions = edges- vertices+2
170
G is connected planar graph with e edges and vertices where v>=3 then ?
e <= 3y-6
171
G is connected planar graph with e edges and vertices where v>=3 and no circuits then ?
e<=2v-4
172
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
```
173
```
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
174
Show that a simple graph with a circuit that has an odd number of vertices in it cannot be colored by 2 colors
????
175
Def: Uniform Distribution of probability
each possible outcome is 1/n
176
Complement of probability
p(!E) = 1-p(E)
177
p(E1 u E2)
p(21) + p(E2) - p(E1 n E1)
178
conditional probability
| p(E|F)
P(E n F) / p(F)
179
to dependents are independent iff?
p(EnF)= p(E)p(F)
180
Mutually independent
p(Ei1 n Ei2 n ... n Ein = p(Ei1)p(Ei2)*...*p(Ein)
181
Bernoulli Trial
An experiment with two possible outcomes
| ex flipping coin
182
Def Mutually independent
The probability of success on an given trial has no bearing on the next
183
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
184
Probability of K successes out of N trials
probability of T = p
probability of F = q
C(N,K) * p^k * q^n-k
185
What is the probability that a fair die comes up even if rolled six times
(1/2)^6
186
What is the probability that a positive integer not exceeding 100 selected at random is divisible by 3
100/3
33/100 = .33
33%
187
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
```
188
Probability that 4 people win 1st,2nd,3rd,4th respectively out of 50 people if you can only win 1 prize
1/50*1/49*1/48*1/47
189
Probability that 4 people win 1st,2nd,3rd,4th respectivly out of 50 people if you can win multiple prizes
(1/50)^4
190
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
191
Independent?
| first coin
???
