Self-Assessment Quiz: Propositional Logic

Twenty questions to check your grasp of propositions, connectives, truth tables, equivalence, and satisfiability. Answer each before opening the key. Aim for 16+.

Question 1

Which of the following is a proposition?

A) "Deploy the new build." B) "$x \le 10$." (with $x$ a free variable) C) "$100$ is a perfect square." D) "Is the cache stale?"

Question 2

The connective whose defining feature is "true exactly when its two inputs differ" is:

A) conjunction ($\land$) B) disjunction ($\lor$) C) exclusive or ($\oplus$) D) biconditional ($\leftrightarrow$)

Question 3

$p \rightarrow q$ is false in exactly which case?

A) $p$ false, $q$ false B) $p$ true, $q$ false C) $p$ false, $q$ true D) $p$ true, $q$ true

Question 4

How many rows does the truth table of a compound proposition with six distinct variables have?

A) $12$ B) $36$ C) $64$ D) $128$

Question 5

Given the precedence rules of the chapter, $\neg p \lor q \land r$ is grouped as:

A) $\neg(p \lor (q \land r))$ B) $(\neg p) \lor (q \land r)$ C) $((\neg p) \lor q) \land r$ D) $\neg((p \lor q) \land r)$

Question 6

"$p \rightarrow q$ with $p$ false" is true regardless of $q$. The chapter's name for this is:

A) the converse B) vacuously true C) the contrapositive D) a contradiction

Question 7

Which pair is logically equivalent?

A) $p \rightarrow q$ and $q \rightarrow p$ B) $p \rightarrow q$ and $\neg q \rightarrow \neg p$ C) $\neg(p \land q)$ and $\neg p \land \neg q$ D) $p \oplus q$ and $p \leftrightarrow q$

Question 8

De Morgan's first law states that $\neg(p \land q)$ is equivalent to:

A) $\neg p \land \neg q$ B) $\neg p \lor \neg q$ C) $p \lor q$ D) $\neg p \rightarrow \neg q$

Question 9

A proposition that is true on every assignment is a:

A) contradiction B) contingency C) tautology D) satisfiable formula only

Question 10

By the absorption law, $a \lor (a \land b)$ simplifies to:

A) $a \land b$ B) $a \lor b$ C) $a$ D) $b$

Question 11

A proposition is satisfiable when:

A) it is true on every assignment B) there exists at least one assignment making it true C) it is false on every assignment D) it has no free variables

Question 12

An unsatisfiable proposition is the same thing as a:

A) tautology B) contingency C) contradiction D) biconditional

Question 13

The reason Python implements implication as (not p) or q is the equivalence:

A) $p \rightarrow q \equiv \neg p \lor q$ B) $p \rightarrow q \equiv \neg q \rightarrow \neg p$ C) $p \rightarrow q \equiv q \rightarrow p$ D) $p \rightarrow q \equiv p \land \neg q$

Question 14

$\neg(p \rightarrow q)$ is logically equivalent to:

A) $\neg p \rightarrow \neg q$ B) $\neg p \lor q$ C) $p \land \neg q$ D) $q \rightarrow p$

Question 15 (True/False, justify)

True or false: For the purposes of logical equivalence, $p \land q$ and $q \land p$ are interchangeable. Justify in one sentence, and add one sentence on whether p and q and q and p are always interchangeable in code.

Question 16 (True/False, justify)

True or false: The converse of an implication is logically equivalent to the implication. Justify with a single assignment of truth values.

Question 17 (True/False, justify)

True or false: If a compound proposition is a tautology, then its negation is unsatisfiable. Justify in one sentence.

Question 18 (Short answer)

State both of De Morgan's laws in symbols.

Question 19 (Short answer)

A streaming service writes if is_subscriber or is_free and age > 13: intending the rule "(subscriber or free) and over thirteen." In one sentence, explain why the code is wrong, and give the corrected condition.

Question 20 (Short answer)

A truth table has $2^n$ rows. In one or two sentences, explain how this innocent doubling becomes the "exponential wall" behind the satisfiability problem (§1.6).

Answer Key

Topics to review by question