The truth column is true exactly when p and q agree, so it represents equivalence \(p\leftrightarrow q\). B simplifies as \(\neg(p\lor q)\lor(p\land q)=(\neg p\land\neg q)\lor(p\land q)\), exactly D. A simplifies to q and C is always true, so neither matches all four rows.
**Answer: B, D.**
A: **Incorrect:** At p=false,q=false the implication is false while the required column is true.
B: **Correct:** True when both inputs are true or both false, matching the table.
C: **Incorrect:** A conjunction always implies its disjunction, so this is a tautology rather than equivalence.
D: **Correct:** Explicitly lists the two cases in which the inputs agree.
Use axioms of inference to determine whether the conclusion inferred from the hypothesis is
logically valid or not.
The hypotheses are:
1. It is not raining or Yvette has her umbrella.
2. Yvette does not have her umbrella or she does not get wet.
3. It is raining or Yvette does not get wet.
Thus, the conclusion is: Yvette does not get wet.
6406537135219.
The conclusion is valid.
6406537135220.
The conclusion is invalid.
Published solution
Let R mean raining, U umbrella and W getting wet. The premises are \(\neg R\lor U\), \(\neg U\lor\neg W\), and \(R\lor\neg W\). Resolve the first two on U to get \(\neg R\lor\neg W\). Resolve this with the third on R to obtain \(\neg W\). Equivalently, if it rains the first two premises imply not wet, and if it does not rain the third premise implies not wet. Thus every case gives the conclusion.
**Answer: A.**
A: **Correct:** Resolution derives the conclusion from the premises.
B: **Incorrect:** No assignment satisfying all premises can make the conclusion false.
A composition of bijections is a bijection. For injectivity, if f(g(a1))=f(g(a2)), injectivity of f gives g(a1)=g(a2), and injectivity of g then gives a1=a2. For surjectivity, take any c in C; surjectivity of f gives a b in B with f(b)=c, and surjectivity of g gives an a in A with g(a)=b. Then f(g(a))=c. Hence f∘g maps A bijectively to C.
**Answer: A.**
A: **Correct:** Both injectivity and surjectivity are preserved in this composition.
B: **Incorrect:** The stated assumptions are sufficient; the composition cannot fail to be bijective.
Write the two odd integers as m=2x+1 and n=2y+1, where x,y are integers. Their sum is \(m+n=2x+1+2y+1=2(x+y+1)\). Since x+y+1 is an integer, this is twice an integer and hence even. A direct proof must establish the algebraic form for all choices, not only a special case.
**Answer: C.**
A: **Incorrect:** The two odd integers need not be equal.
B: **Incorrect:** Drops the two constant 1 terms.
C: **Correct:** Correctly factors the sum into twice an integer.
D: **Incorrect:** Only describes one possible sum, not the general case.
Consider the following proof to show that every positive integer can be written as a sum of a
subset of integers that are powers of
. For example, the integers
and
are powers
of
, and the integer
can be written as a sum of two integers that are
powers of
.
Proof. Let
be the statement that the positive integer
can be written as a sum of a subset of
distinct powers of
.
Base Case: When
, then
. Hence
is true.
Induction Hypothesis: ____________. We have to show that
is true.
Inductive Proof:
Case 1: If
is a power of
, then let
and hence,
is true.
Case 2: If
is not a power of
. Let
be the largest power of
less than
, i.e.,
. Let
. Then,
is the integer such that
. Hence, by the induction hypothesis,
is true, i.e.,
can be
written as a sum of a subset of distinct powers of
. Therefore,
, where both
terms are sums of distinct powers of
. Hence
is true.
Which of the following is the correct induction hypothesis for this proof?
6406537135225.
Assume
be true, where
6406537135226.
Assume
is true for every positive integer
, where
6406537135227.
Assume
be true, where
6406537135228.
Assume
is true for every positive integer
, where
Published solution
The proof uses strong induction: assume P(k) for every integer 1<=k<=n, with n>=1, to prove P(n+1). When n+1 is not a power of two, choose the largest power \(2^m<n+1\). The intended remainder is \(r=(n+1)-2^m\), so \(1\le r<2^m\) and r<=n. The hypothesis supplies a representation for this possibly much smaller r. Its powers are below 2^m, so adding 2^m preserves distinctness. A printed occurrence of n-1 in the remainder must be read as a typo; the corrected expression is n+1. Ordinary induction assuming only P(n) does not directly supply P(r).
**Answer: D.**
A: **Incorrect:** Assumes only P(n) and also uses a base range starting at zero, unlike the given positive-integer proof.
B: **Incorrect:** States the strong form but permits n=0 although the proof starts with P(1); D gives the correct stated range.
C: **Incorrect:** Assumes only P(n), insufficient for the smaller remainder used in this argument.
D: **Correct:** Supplies all earlier positive-integer cases with the correct n>=1 range.
Starting with a0=1, repeatedly apply an=n a(n-1): a1=1, a2=2, a3=6, and so on. The product is \(a_n=n(n-1)\cdots1\,a_0=n!\). Also 0!=1 satisfies the initial condition. A closed form must satisfy both the recurrence and the base value.
**Answer: B.**
A: **Incorrect:** The triangular-number expression has value 0 at n=0 and does not satisfy the factorial recurrence.
B: **Correct:** n! satisfies n(n-1)!=n! and 0!=1.
C: **Incorrect:** n fails both the n=0 initial value and later recurrence values.
D: **Incorrect:** B is a valid closed form.
The integers 101 through 200 inclusive form an arithmetic progression of 100 terms. Their average is (101+200)/2=150.5. Hence \(\sum_{k=101}^{200}k=100\cdot150.5=15050\). Alternatively subtract 1+...+100 from 1+...+200 using n(n+1)/2.
**Answer: 15050.**
(not necessarily consecutive) integers, at least how many integers must have
the same remainder when divided by
?
Published solution
Division by 15 has only 15 possible remainders, 0 through 14. Put 50 integers into these 15 remainder classes. By the generalised pigeonhole principle, some class contains at least \(\lceil50/15\rceil=4\) integers. If every class contained at most three, there would be at most 45 integers. The bound is sharp: distribute them with five classes of four and ten classes of three.
**Answer: 4.**
Given an=n(n+1), the next term is (n+1)(n+2). B works because \(a_{n+1}-a_n=(n+1)[(n+2)-n]=2n+2\). C gives \(a_n(a_n+n)/n^2=n(n+1)\cdot n(n+2)/n^2=(n+1)(n+2)\). D gives \((n+2)a_n/n=(n+1)(n+2)\). For a recursive definition these formulas also need the initial term a1=2; the question tests the displayed update relations for n>=1.
**Answer: B, C, D.**
A: **Incorrect:** For n=1 it produces 2(2+1)=6, but for n=2 it produces 6(6+1)=42 instead of 12.
B: **Correct:** The consecutive-term difference is exactly 2n+2.
C: **Correct:** Substituting an=n(n+1) simplifies to the correct next term.
D: **Correct:** The consecutive-term ratio is (n+2)/n.
E: **Incorrect:** For n=1 it gives 4 instead of a2=6.
To reach (4,3,5), every permitted path contains 4 x-steps, 3 y-steps and 5 z-steps: 12 steps total. Count arrangements of this multiset: \(12!/(4!3!5!)\). Equivalently choose 4 of the 12 positions for x, then 3 of the remaining 8 for y, and all 5 remaining for z: \(\binom{12}4\binom83\binom55\). Both give the same number of ordered paths.
**Answer: C, D.**
A: **Incorrect:** Multiplying the coordinate counts does not count arrangements of all steps.
B: **Incorrect:** Independently choosing each direction's positions from 12 allows overlaps and overcounts.
C: **Correct:** Sequential position choices use disjoint remaining slots correctly.
D: **Correct:** The multinomial coefficient counts all distinct step orderings.
Which of the following statements establishes a one-to-one correspondence between the set of
natural numbers
and
?
6406537135237.
For each
, assign the bit string containing
1s.
6406537135238.
For each
, assign the natural number whose binary representation is
.
6406537135239.
is countable but there is no correspondence between
and
.
6406537135240.
is uncountable and therefore, there is no correspondence between
and
.
Published solution
The set consists of finite strings containing only 1s. Assign natural number n to the string of n ones. Distinct lengths give distinct strings, and every all-ones string has exactly one such length, proving both injectivity and surjectivity. Match the convention for zero: if the empty string is included, use natural numbers beginning at 0; if only nonempty strings are included, begin at 1.
**Answer: A.**
A: **Correct:** The length map gives the required bijection under matching zero/empty-string conventions.
B: **Incorrect:** Maps to integers with all-ones binary expansions, only a subset of all natural numbers, so it is not onto the stated full natural-number set.
C: **Incorrect:** The explicit length correspondence exists.
D: **Incorrect:** The strings can be listed by length and are countable.
Use the geometric series \(1/(1-r)=\sum_{n=0}^{\infty}r^n\). Set r=-3x to get \(1/(1+3x)=\sum_{n=0}^{\infty}(-3)^nx^n\), then multiply by x cubed: \[\frac{x^3}{1+3x}=\sum_{n=0}^{\infty}(-3)^nx^{n+3}.\] Thus the first three coefficients are zero and later coefficients alternate 1,-3,9,-27,... . The identity holds as a formal generating series, and analytically for |x|<1/3.
**Answer: C.**
A: **Incorrect:** Uses positive 3 powers and corresponds to the wrong denominator sign.
B: **Incorrect:** Omits the x cubed shift.
C: **Correct:** Has both the alternating factor and the three-power shift.
D: **Incorrect:** An infinite product is not the required geometric-series expansion.
be the relation on the set of students consisting of pairs
, where
and
are enrolled in
the same course. Let
be the relation consisting of pairs
, where
and
belong to the same
department. Which of the following correctly describes
?
6406537135256.
The set of students who take the same course
6406537135257.
The set of students who belong to the same department
6406537135258.
The set of students
and
such that there exists a student
who shares a
course with
and a department with
.
6406537135259.
The set of students
and
such that there exists a student
who shares a
department with
and a course with
.
6406537135260.
Students who have identical course schedules
Published solution
Composition R∘S means apply S first, then R: \((a,c)\in R\circ S\) if there is b with (a,b) in S and (b,c) in R. Thus a shares a department with b, and b shares a course with c. The intermediate student links two different relations; a and c need not directly share a course or department.
**Answer: D.**
A: **Incorrect:** Omits the intermediate department step.
B: **Incorrect:** Omits the intermediate course step.
C: **Incorrect:** Describes applying R first and S second, the reversed composition.
D: **Correct:** Correctly applies the same-department relation before the same-course relation.
E: **Incorrect:** Identical entire schedules is much stronger and not required.
The requested relation is intersection, so an ordered pair is present only when its entry is 1 in both input matrices. Take the entrywise logical AND: row 1 is (0,1,0), row 2 is (0,1,1), and row 3 is (1,0,0). Therefore \(M_{R_1\cap R_2}=\begin{bmatrix}0&1&0\\0&1&1\\1&0&0\end{bmatrix}\). This is neither ordinary matrix multiplication nor Boolean relational composition.
**Answer: B.**
A: **Incorrect:** Keeps entries that occur in only one relation, resembling a union rather than intersection.
B: **Correct:** Matches the entrywise AND matrix.
C: **Incorrect:** Does not retain the entries common to both matrices.
D: **Incorrect:** B supplies the correct matrix.
Use inclusion-exclusion on the interval [100,999]. Multiples of 3 number floor(999/3)-floor(99/3)=333-33=300. Multiples of 4 number 249-24=225. Their overlap consists of multiples of lcm(3,4)=12, numbering 83-8=75. Total=300+225-75=450. Subtract the overlap once because it was counted twice.
**Answer: 450.**
Pascal's identity is \(\binom{n+1}k=\binom n{k-1}+\binom nk\). The two terms are supplied as 15 and 20, so the requested value is 15+20=35. It is unnecessary to solve separately for n and k, although n=6,k=3 provides a consistency check.
**Answer: 35.**
Divisibility is reflexive because a=a×1 for every integer a, including 0 under the usual definition a divides b iff b=ak for an integer k. It is transitive because b=ar and c=bs imply c=a(rs). Thus reflexive and transitive closure add no pairs. It is not symmetric: 2 divides 4 but 4 does not divide 2, so symmetric closure adds missing reversed pairs.
**Answer: A, C.**
A: **Correct:** Every diagonal pair is already present.
B: **Incorrect:** Some reversed pairs, such as (4,2), must be added.
C: **Correct:** Every two-step divisibility chain already implies its endpoint pair.
