Quiz · Medium
Twenty questions on logical equivalences, quantifier negation, valid and invalid arguments, and choosing a proof technique, for first-year discrete math.
To prove 'if is odd then n is odd' the neatest approach is
direct proof starting from n^2 = 2k + 1
proof by induction on n
proof by exhaustion over small n
proof by contrapositive: assume n is even
Assuming n even makes n = 2k and n^2 = 4k^2 even, finishing in one line. The direct route requires taking a square root of an odd number, which is awkward.
Which statement is logically equivalent to ?
is false only when p is true and q is false, exactly like . is the converse and is the inverse; both can differ from . is the negation of .
What is the negation of 'All birds can fly'?
Some bird cannot fly
No bird can fly
All birds cannot fly
Some bird can fly
The negation of a universal statement is an existential one: there exists a bird that cannot fly. 'No bird can fly' is far stronger, and 'All birds cannot fly' says the same as it.
The shaded Venn diagram shows the sets where p (in A) and q (in B) are combined by which connective?

AND
OR
XOR
NAND
The overlap is left unshaded and the two crescents are shaded: true when exactly one of p, q holds. That is XOR. OR would shade the overlap too.
Which translation is correct for 'Some student likes pizza' with S(x): x is a student, P(x): x likes pizza?
Existential statements pair with conjunction. is true if any non-student exists, which says nothing about students.
Argument: 'If it rains, the match is cancelled. The match is cancelled. Therefore it rained.' This is
valid (modus ponens)
valid (modus tollens)
invalid (denying the antecedent)
invalid (affirming the consequent)
From p -> q and q you cannot infer p: the match might be cancelled for another reason. This is the fallacy of affirming the consequent. Denying the antecedent would start from 'not p'.
How many rows does the truth table of have?
4
6
8
9
Three variables p, q, r give 2^3 = 8 rows. The number of operators does not matter, only the number of distinct variables.
Over the real numbers, which statement is TRUE?
For each x take y = -x. In the first statement one y would have to cancel every x at once, which is impossible.
The contrapositive of 'If a number is divisible by 6, then it is divisible by 3' is
If a number is divisible by 3, it is divisible by 6
If a number is not divisible by 3, it is not divisible by 6
If a number is not divisible by 6, it is not divisible by 3
A number is divisible by 6 and not divisible by 3
Contrapositive: swap and negate both parts. Choice A is the converse (false: 9), choice B the inverse (false: 3), choice D the negation.
Which of these is a tautology?
This is modus ponens as a statement: if p and p -> q are true then q is true. The others fail: choice A when p is true and q false, C when q true and p false, D when q true and p false.
In a proof of by contradiction, which assumption is made at the start?
in lowest terms with integers a, b
is an integer
and are both even
We assume the opposite of the claim (rational) and write it in lowest terms; the contradiction comes from showing both a and b are even.
The negation of is
Flip the quantifier and negate the implication: not(P -> Q) = P and not Q. Choice D is the original statement rewritten, not its negation.
Which expression is equivalent to (exclusive or)?
XOR is true exactly when p and q differ, so it is the negation of the biconditional.
An induction proof that holds for all should use base case
n = 0
n = 5
n = 1
n = 4
The claim starts at n = 5: 32 > 25. It fails at n = 2, 3, 4 (4 = 4, 8 < 9, 16 = 16), so n = 4 would be a false base case, and the step from small n cannot work either.
True or false: if is true and q is true, then p must be true.
True
False
False: when q is true, p -> q is true whatever p is. Concluding p is the fallacy of affirming the consequent.
Strong induction is most natural to prove which claim?
1 + 2 + ... + n = n(n+1)/2
n^3 - n is divisible by 3
2^n > n
Every integer greater than 1 is a product of primes
The factors of n can be anywhere below n, so you need P(j) for all smaller j. The other three only use P(k) in the step for k + 1.
In an empty domain, the statement is
true (vacuously)
false
undefined
equal to
A universal claim can only be refuted by an element that fails; with no elements it can't fail. The existential statement is false for an empty domain.
The argument 'All mammals are warm-blooded. Whales are mammals. So whales are warm-blooded.' uses
universal instantiation then modus ponens
existential generalization only
disjunctive syllogism
resolution
Instantiate 'all mammals are warm-blooded' to whales (mammal(whale) -> warm(whale)), then modus ponens with mammal(whale).
A statement is a contingency if it is
true under every assignment
false under every assignment
not a proposition
true under some assignments and false under others
Tautologies are always true, contradictions always false. Contingencies depend on the assignment, like p AND q.
Which connective is functionally complete on its own?
NAND ()
NAND alone can build NOT, AND, OR. AND, OR and implication cannot express negation by themselves.
Which is an example of a vacuous truth?
Every even prime is greater than 2
Every prime is odd
Every element of the empty set is a prime
Some element of the empty set is prime
With no elements, nothing can violate the universal claim. 'Every prime is odd' is false (2); 'every even prime is greater than 2' is false (2 is the even prime); the last is an existential claim, false for the empty set.
Treat each circle as the set where p or q is true. Which diagram shades ?



AND is the overlap only (the intersection). The first diagram shades both circles entirely (OR); the third shades both circles except the overlap (XOR).