Very frequent
0/14
Mathematical Logic & Reasoning
Truth tables, equivalences, quantifiers, and complexity reasoning - the fastest marks available in Round 1.
Truth tables, equivalences, quantifiers, and complexity reasoning - the fastest marks available in Round 1.
7 multiple choice at 2 marks and 5 fill-in-the-blank at 5, marked exactly as Round 1 marks them. Each answer is explained as soon as you check it. The clock is shown, not enforced.
Round 1 explicitly tests mathematical logic and algorithmic thinking. These questions follow repeatable steps and are usually quick once you have practised them.
The last of these is the contrapositive, and it is equivalent to the original. The converse () and the inverse () are not, and a question that offers all three as options is testing exactly that.
For two variables, four rows; three variables, eight. Fill them systematically rather than reasoning informally - under time pressure, informal reasoning about nested negation is where errors happen.
A useful shortcut: is false in exactly one case, when is true and is false. Checking that one row is often enough to eliminate options.
Order matters, and reversing it changes the claim: says each has some ; says one works for all . The second is strictly stronger.
"Algorithmic thinking" in Round 1 usually means recognising the running time of a snippet.
The master theorem covers the common recurrences: for , compare with .
def f(n):
total = 0
for i in range(n): # n
j = 1
while j < n: # log n
total += 1
j *= 2
return total # O(n log n)
Inclusion-exclusion, , appears regularly, as do permutations and combinations. Conditional probability questions almost always turn on remembering the base rate.
The contrapositive is equivalent; the converse and inverse are not. is false in exactly one row - check that row first.
Negating a quantifier flips it and pushes the negation inward. Recognise loop structure to complexity class on sight; this is drillable.
Which of these can differ in truth value from ?
The converse is independent of . The contrapositive is equivalent.
Select an answer
A propositional formula uses three atoms. How many rows does its truth table have?
.