578 lines
17 KiB
Typst
578 lines
17 KiB
Typst
#import "@local/dtu-template:0.5.1":*
|
|
#import "@preview/cetz:0.4.2"
|
|
#import "@preview/cetz-venn:0.1.4": venn2, venn3
|
|
#import "@preview/auto-div:0.1.0": poly-div, poly-div-working
|
|
|
|
#let mark-circle = box(width: 0.8em, height: 0.8em, stroke: 0.5pt + black, radius: 50%)
|
|
#let ans(body) = grid(columns: (auto, 1fr), column-gutter: 0.5em, align: (center, left), mark-circle, body)
|
|
|
|
#let corr-circle = box(width: 0.8em, height: 0.8em, stroke: 0.5pt + black, fill: black, radius: 50%)
|
|
#let corr(body) = grid(columns: (auto, 1fr), column-gutter: 0.5em, align: (center, left), corr-circle, body)
|
|
|
|
#show heading: it => { pagebreak(weak: true); it }
|
|
== Question 1
|
|
|
|
If $p,q$ are prime numbers such that $100 < p < q$, then the number of positive integers less than $p q$ which are relative prime to $p q$ is:
|
|
|
|
#corr[$p q - p - q + 1$ (Rasmus's, Sebastian's answer)]
|
|
#ans[$p q - q + 1$]
|
|
#ans[$p q-p-q-1$]
|
|
#ans[$p q-p-q$ (Mikkel's answer)]
|
|
#ans[$p q-1$]
|
|
#ans[None of these]
|
|
|
|
== Question 2
|
|
|
|
The number $(4^100 mod 6 )^100 mod 10$ equals
|
|
|
|
#ans[3]
|
|
#corr[6 (All's answer)]
|
|
#ans[2]
|
|
#ans[None of these]
|
|
#ans[5]
|
|
#ans[1]
|
|
#ans[4]
|
|
|
|
== Question 3
|
|
|
|
Consider the set of all 99 positive integers not exceeding 99.
|
|
|
|
#table(
|
|
columns: (18%, auto, auto, auto, auto, auto, auto, auto, auto),
|
|
align: (left, center, center, center, center, center, center, center, center),
|
|
stroke: none,
|
|
[],
|
|
[$binom(99, 50)$],
|
|
[$2^98$],
|
|
[$2^97$],
|
|
[$2^49$],
|
|
[None of these],
|
|
[$2^50$],
|
|
[$binom(99,50) binom(99,49)$],
|
|
[$binom(99,49) binom(99, 49)$],
|
|
[How many subsets have an odd number of odd numbers, and an even number of even numbers?],
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
[*Sebastian's answer*],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[How many subsets have an odd number of even numbers and an even number of odd numbers?],
|
|
mark-circle,
|
|
mark-circle,
|
|
corr-circle,
|
|
[Rasmus's answer],
|
|
[Sebastian's answer],
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[How many subsets have 49 elements?],
|
|
[*Rasmus's answer*],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's, Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[How many subsets have an odd number of odd numbers?],
|
|
mark-circle,
|
|
[*Rasmus's, Sebastian's answer*],
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
)
|
|
|
|
== Question 4
|
|
|
|
Consider the following system of congruences:
|
|
|
|
$
|
|
x &equiv 1 mod 2 \
|
|
x &equiv 1 mod 5 \
|
|
x &equiv 7 mod 9
|
|
$
|
|
|
|
Indicate the set of all solutions to the above system of congruences.
|
|
|
|
#ans[None of these]
|
|
#ans[${90 + 7k | k in ZZ}$]
|
|
#ans[${1 + 2k | k in ZZ} union {1 + 5k | k in ZZ} union {7 + 9k | k in ZZ}$]
|
|
#ans[${9 + 90k | k in ZZ}$]
|
|
#corr[${61 + 90k | k in ZZ}$ (All's answer)]
|
|
#ans[${7 + 90k | k in ZZ}$]
|
|
|
|
|
|
== Question 5
|
|
|
|
Find a greatest common divisor of the polynomials $x^3 - 1$ and $x^3 + 2x^2 + 2x + 1$
|
|
|
|
#ans[$x+1$]
|
|
#ans[$1$(Mikkel's answer)]
|
|
#ans[$x-1$]
|
|
#corr[$x^2 + x + 1$ (Rasmus's, Sebastian's answer)]
|
|
#ans[$x^2 + x - 1$]
|
|
#ans[None of these]
|
|
#ans[$x^2 - x + 1$]
|
|
#ans[$x^2-x-1$]
|
|
|
|
|
|
== Question 6
|
|
|
|
Recall that $NN$ is the set of natural numbers, in other words the set of nonnegative integers. For all $n in NN$ define $f(n) = sum^n_(k=0) k dot k! = 0 dot 0! + 1 dot !+ dots + n dot n!$. It is possible to prove by induction that $f(n) = (n+1)! -1$ holds for all nonnegative integers $n$.
|
|
|
|
By choosing 4 of the following 8 text fragments and putting them in the correct order, a proof by induction for the above statement can be created.
|
|
|
|
A. To prove the induction step, we assume that $f(n+1) = ((n+1)+1)!-1$ holds for some $n in NN$. We will now prove that under this assumption, $f(n) = (n+1)!-1$
|
|
|
|
B. To prove the induction step we assume that $f(n) = (n+1)!-1$ holds for all $n in NN$. We will now prove that under this assumption, $f(n+1) = ((n+1)+1)!-1$ holds for all $n in NN$.
|
|
|
|
C. To prove the induction step we assume that $f(n) = (n+1)!-1$ holds for some $n in NN$. We will now prove that under this assumption, $f(n+1) = ((n+1)+1)!-1$.
|
|
|
|
D. The statement now follows from the principle of mathematical induction.
|
|
|
|
E. We prove the statement by induction. The base case is $n = 1$. For $n=1$, we see that $f(1) = sum^1_(k=0)k dot k! = 0 dot 0! + 1 dot 1! = 0 dot 1 + 1 dot 1 = 1$ and also that $(n+1)! -1 = (1+1)!-1 = 2!-1 = 2-1 =1$. This proves the base case.
|
|
|
|
F. We prove the statement by induction. The base case is $n=0$. For $n=0$, we see that $f(0) = sum^0_(k=0) k dot k! = 0 dot 0! = 0 dot 1 = 0$ and also that $(n+1)! -1 = (0+1)!-1 = 1!-1 = 1-1 =0$. This proves the base case.
|
|
|
|
|
|
G. We have that $
|
|
f(n) &= sum^n_(k=0) k dot k! \
|
|
&= (sum^(n+1)_(k=0) k dot k! ) - (n+1)(n+1)! \
|
|
&= f(n+1) - (n+1)(n+1)! \
|
|
&= ((n+1)+1)! - 1 - (n+1)(n+1)! "By the induction hypothesis" \
|
|
&= (n+2)! -(n+1)(n+1)!-1 \
|
|
&= (n+2)(n+1)!-(n+1)(n+1)!-1 \
|
|
&= (n+2 - (n+1))(n+1)!-1 \
|
|
&= (n+1)! -1
|
|
$ which is what we wanted to prove. This concludes the induction step.
|
|
|
|
H. We have that $
|
|
f(n+1) &= sum^(n+1)_(k=0) k dot k! \
|
|
&= (sum^n_(k=0) k dot k!) + (n+1)(n+1)! \
|
|
&= f(n)+(n+1)(n+1)! \
|
|
&= (n+1)!-1+(n+1)(n+1)! "By the induction hypothesis" \
|
|
&= (n+1)(n+1)!+(n+1)!-1 \
|
|
&= [(n+1)+1](n+1)!-1 \
|
|
&= (n+2)! - 1 = ((n+1)+1)!-1
|
|
$ which is what we wanted to prove. This concludes the induction step.
|
|
|
|
#table(
|
|
columns: (20%, auto, auto, auto, auto, auto, auto, auto, auto),
|
|
align: (left, center, center, center, center, center, center, center, center),
|
|
stroke: none,
|
|
[],
|
|
[A],
|
|
[B],
|
|
[C],
|
|
[D],
|
|
[E],
|
|
[F],
|
|
[G],
|
|
[H],
|
|
[The first fragment is:],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
[*Rasmus's, Sebastian's answer*],
|
|
mark-circle,
|
|
mark-circle,
|
|
[The second fragment is:],
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[The third fragment is:],
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
[The fourth fragment is:],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
[Mikkel's answer],
|
|
)
|
|
|
|
== Question 7
|
|
|
|
For all $n in NN$ define $a_n$ recursively as follows $a_0 = 2, a_1 = 3, a_n = cases(a_(n-1) + n "if" n "is even", a_(n-1) + 2a_(n-2) "if" n "is odd")$
|
|
|
|
1. 37 (All's answer)
|
|
2. 38
|
|
3. 35
|
|
4. 40
|
|
5. None of these
|
|
6. 36
|
|
7. 39
|
|
|
|
== Question 8
|
|
|
|
We wish to construct a bipartite graph with bipartition $(V_1, V_2)$ such that $abs(V_1) = 4, abs(V_2) = 5$ (Note that a bipartite graph has no loops, but it may contain multiple edges.)
|
|
#table(
|
|
columns: (40%, 1fr, 1fr, 1fr, 1fr, 1fr),
|
|
align: (left, center, center, center, center, center),
|
|
[],
|
|
[The graph exists without multiple edges.],
|
|
[The graph exists but only if we allow multiple edges.],
|
|
[The graph does not exist, but it will exist if we are allowed to increase one of the degrees in $V_1$.],
|
|
[The graph does not exist, but it will exist if we are allowed to increase one of the degrees in $V_2$.],
|
|
[None of these are correct],
|
|
[If the degrees in $V_1$ are $5,5,5,5$ and the degrees in $V_2$ are $4,4,4,4,4$ then],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's, Sebastian's answer],
|
|
mark-circle,
|
|
[If the degrees in $V_1$ are $1,2,2,2$ and the degrees in $V_2$ are $1,2,2,2,2$ then],
|
|
[Sebastian's answer],
|
|
[Mikkel's answer],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[If the degrees in $V_1$ are $4,4,4,4$, and the degrees in $V_2$ are $5,5,5,5,5$ then],
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
[Mikkel's, Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
)
|
|
|
|
|
|
== Question 9
|
|
|
|
The formula $binom(m+n, r) = sum^r_(k=a) binom(m, r-k) binom(n,k)$ is true for all integers $m,n,r$ satisfying $0 < m < r < n$ if we let the summation start with:
|
|
|
|
1. $a = n$ (Sebastian's answer)
|
|
2. $a = r$
|
|
3. None of these (Rasmus's answer)
|
|
4. $a = n -r$ (Mikkel's answer)
|
|
5. $a = m$
|
|
6. $a = r - m$
|
|
|
|
|
|
== Question 10
|
|
|
|
Let $A = {0,1,2,4}, B = {0,1,3,5}, "and" C = {0,2,3,6}$. IF the universal set $U = {0,1,2,3,4,5,6,7}$, then which of hte following is equal to $((A inter B) backslash C) union ((B inter C) backslash C) union ((C inter A) backslash B)$
|
|
|
|
1. ${0,1,2,3}$
|
|
2. All of these sets
|
|
3. $emptyset$ (Mikkel's answer)
|
|
4, ${4,5,6}$
|
|
5. None of these
|
|
6. ${0,4,5,6}$
|
|
7. ${1,2,3}$ (Rasmus's, Sebastian's answer)
|
|
|
|
== Question 11
|
|
|
|
Consider the statement "for every positive rational number $x$ there are positive integers $a$ and $b$ such that $x = a/b$ and $gcd(a,b) = 1$." Which of the following statement in predicate logic is equivalent to this if we let $G(a,b)$ denote the statement " $a "and" b$ are relatively prime"?
|
|
|
|
1. It is not possible to translate the statement into predicate logic. (Sebastian's answer)
|
|
2. $forall x in QQ^+ exists a in ZZ^+ exists b in ZZ^+ (x = a/b and G(a,b)) $ (Mikkel's, Rasmus's answer)
|
|
3. $forall x in QQ^+ exists a in ZZ^+ exists b in ZZ^+ (G(a,b) -> x = a/b)$
|
|
4. $forall x in QQ^+ forall a in ZZ^+ forall b in ZZ^+ (x = a/b and G(a,b))$
|
|
5. $forall x in QQ^+ exists a in ZZ^+ exists b in ZZ^+ (x = a/b -> G(a,b))$
|
|
|
|
== Question 12
|
|
|
|
Given a univerisal set $U$, which of the following is equal to the set $A inter overline(B backslash C)$?
|
|
|
|
1. None of these
|
|
2. $A inter B inter overline(C)$
|
|
3. $(A union B) inter (A union overline(C))$
|
|
4. $(A inter overline(B)) union (A inter C)$ (Rasmus's answer)
|
|
5. $A inter overline(B) inter C$
|
|
6. $A inter (C backslash B)$ (Mikkel's, Sebastian's answer)
|
|
|
|
|
|
== Question 13
|
|
|
|
The empty set is an element of which of the following sets?
|
|
|
|
1. ${{emptyset}}$
|
|
2. None of these
|
|
3. $emptyset$ (Mikkel's answer)
|
|
4. ${x in RR : x < x}$
|
|
5. ${emptyset}$ (Rasmus's, Sebastian's answer)
|
|
6. All of these sets
|
|
|
|
== Question 14
|
|
|
|
Which of the following are tautologies?
|
|
|
|
1. $(p -> q) or (not q -> not p)$ (Sebastian's answer)
|
|
2. None of these
|
|
3. $p <-> q$
|
|
4. All of these
|
|
5. $(not p or not q) -> (not (p and q))$ (Mikkel's, Rasmus's answer)
|
|
6. $(p or q or r) and (p or not q or not r)$
|
|
|
|
== Question 15
|
|
|
|
Consider all possible seatings of $3n$ people around two tables, one with $n$ seats and one with $2n$ seats. Find the number of seatings when
|
|
#table(
|
|
columns: (20%, auto, auto, auto, auto, auto, auto, auto, auto, auto),
|
|
align: (left, center, center, center, center, center, center, center, center, center),
|
|
stroke: none,
|
|
[],
|
|
[$((3n)!)/(2(n!))$],
|
|
[$((3n)!)/(4(n!))$],
|
|
[$((3n)!)/(4n)$],
|
|
[$2 binom(3n,n)$],
|
|
[$((3n)!)/(2n^2)$],
|
|
[$((3n)!)/(4n^2)$],
|
|
[$((3n)!)/(8n^2)$],
|
|
[$4 binom(3n,n)$],
|
|
[None of these],
|
|
[Two seatings are considered the same when each person has the same left and right neighbor.],
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
[Two seatings are considered the same when each person has the same neighbors (and we do not care about right or left)],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
)
|
|
|
|
== Question 16
|
|
|
|
For each of the following, determine whether it is surjective/injective, or not a well defined function. Recall that $NN$ is the set of natural numbers, in other words the set of nonnegative integers.
|
|
|
|
#table(
|
|
columns: (35%, 1fr, 1fr, 1fr, 1fr, 1fr),
|
|
align: (left, center, center, center, center, center),
|
|
[],
|
|
[Not a well defined function],
|
|
[Well defined but neither injective nor surjective],
|
|
[Surjective],
|
|
[Injective],
|
|
[Both injective and surjective],
|
|
[$ f: RR -> ZZ $ given by $f(x) = 2 floor(x/2)$],
|
|
[Mikkel's, Sebastian's answer],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[$f : RR -> {x in RR : x >= 0}$ given by $f(x) = sqrt(x^2)$],
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
[$f: NN -> NN$ given by $f(x) = 2x +7$],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[All's answer],
|
|
mark-circle,
|
|
[$f: NN -> NN$ given by $f(x) = x-x^2$],
|
|
[Rasmus's, Sebastian's answer],
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[$f: RR -> RR$ given by $f(x) = cases(x "if" x in QQ, -x "if" x in.not QQ)$],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's, Sebastian's answer],
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
)
|
|
|
|
== Question 17
|
|
|
|
Consider all permutations of ABCDE
|
|
#table(
|
|
columns: (20%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
|
|
align: (left, center, center, center, center, center, center, center),
|
|
[],
|
|
[12],
|
|
[24],
|
|
[36],
|
|
[48],
|
|
[50],
|
|
[64],
|
|
[None of these],
|
|
[How many contain none of AB, BC, CD],
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
[How many contain ACE],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
[Mikkel's, Rasmus's answer],
|
|
[How many contain precisely one of AB, CD],
|
|
mark-circle,
|
|
[Mikkels's, Sebastian's answer],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle
|
|
)
|
|
|
|
== Question 18
|
|
|
|
For each relation on the set of four distinct elements $a,b,c,d$ below, decide which property it has.
|
|
|
|
#table(
|
|
columns: (30%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
|
|
align: (left, center, center, center, center, center, center, center),
|
|
stroke: none,
|
|
[],
|
|
[The edges of a hasse diagram],
|
|
[Partial order],
|
|
[Total order but not well ordered],
|
|
[Well-order],
|
|
[None of these],
|
|
[Total order but not partial order],
|
|
[Equivalence relation],
|
|
[$(a,a),(a,b),(a,c)(a,d)$],
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's answer],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[$(a,b),(b,c),(c,d)$],
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Mikkel's, Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[$(a,a),(b,b),(c,c),\ (d,d),(a,d),(d,a)$],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
[Mikkel's, Rasmus's answer],
|
|
[$(a,a),(b,b),(c,c),\ (d,d),(d,c)$],
|
|
mark-circle,
|
|
[Mikkel's, Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
[$(a,a),(b,b),(c,c),(d,d),\ (a,b),(a,c),(a,d),(b,c),\ (b,d),(c,d)$],
|
|
[Mikkel's answer],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer]
|
|
)
|
|
|
|
|
|
== Question 19
|
|
|
|
Which of the following is a recursively defined function for the number of ways to tile an $n times 2$ board using $2 times 1$ tiles.
|
|
|
|
1. $f(0) = 1, f(1) = 1, f(n) = f(n - 1) + f(n - 2) "for" n >= 2$
|
|
2. $f(0) = 0, f(1) = 1, f(n) = 2f(n - 2) "for" n >= 2$
|
|
3. $f(0) = 1, f(1) = 1, f(n) = 2f(n - 2) "for" n >= 2$
|
|
4. $f(0) = 1, f(1) = 1, f(n) = f(n - 1)f(n - 2) "for" n >= 2$
|
|
5. All of these (Mikkel's answer)
|
|
6. $f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2) "for" n >= 2$ (Rasmus's, Sebastian's answer)
|
|
7. None of these
|
|
|
|
|
|
== Question 20
|
|
|
|
Find the coefficient of $x^15 y^20$ in the polynomials below.
|
|
|
|
#table(
|
|
columns: (20%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
|
|
align: (left, center, center, center, center, center, center, center),
|
|
[],
|
|
[$- binom(10,5)2^5$],
|
|
[$binom(10,5) 2^15$],
|
|
[$- binom(10,5)2^15$],
|
|
[0],
|
|
[None of these],
|
|
[$-binom(10,5)2^10$],
|
|
[$- binom(10,3)2^5$],
|
|
[$(2x^3-y^4)^10$],
|
|
[Mikkel's, Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
[$(1-2x^3y^4)^10$],
|
|
[Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
[Mikkel's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[$(x^3-2y^4)^10$],
|
|
[Mikkel's, Rasmus's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
[Sebastian's answer],
|
|
mark-circle,
|
|
mark-circle,
|
|
mark-circle,
|
|
)
|
|
|
|
|
|
== Question 21
|
|
|
|
Which of the following is equivalent to the statement " $a$ and $b$ are relatively prime"? The domain for each statement is
|
|
the set of all positive integers
|
|
|
|
1. None of these three are equivalent to the statement.
|
|
2. $not (exists c (c divides a and c divides b and c > 1) )$ is equivalent to the statement, and the other two are not.
|
|
3. $forall c (not (c divides a) or not (c divides b) or (c <= 1))$ is equivalent to the statement, and the other two are not.
|
|
4. All of these three are equivalent to the statement.
|
|
5. $forall c ( (c divides a and c divides b) -> (c <= 1))$ is equivalent to the statement, and other two are not. (All's answer)
|
|
|