Logic Questions and Answers

Answer: D

Correct answer: Both (b) and (c)

A set is functionally complete if every truth function can be expressed with it. NOR alone will do, since \( \lnot p \) is \( p \downarrow p \) and the rest follows, so the second set is complete; and NAND alone is complete for the same reason, which is why a whole processor can be built from NAND gates. The set with only conjunction and disjunction cannot express negation and so is not complete.

Answer: B

Correct answer: The conjuction F1 ^ F2 is not satisfiable

If both implications are tautologies then whenever \( F_1 \land F_2 \) is true, F3 and its negation are both true - which is impossible. So \( F_1 \land F_2 \) can never be true, and it is unsatisfiable. Nothing follows about F1 or F2 individually; each may be satisfiable on its own.

Answer: C

Correct answer: p v (p→q)

Rewrite the implication: \( p \lor (p \to q) \equiv p \lor \lnot p \lor q \), and \( p \lor \lnot p \) is already true, so the whole is true whatever the values. The other candidate reduces to \( p \lor \lnot q \), which fails when p is false and q true, and the first option fails when p is true and q false.

Answer: C

Correct answer: R

Both P and Q lead to R, and \( P \lor Q \) guarantees that one of them holds, so R follows in either case. This is the constructive dilemma with the same conclusion on both branches, which collapses it to a proof of R. Neither P nor Q individually can be concluded, since the premises do not say which of them is true.

Answer: C

Correct answer: Peter’s team

Take the comparisons in turn. Peter beats David; Smith beats Peter; Smith beats Taiwa; and Taiwa scores less than David. That gives Smith above Peter above David above Taiwa, a complete ordering. Second in descending order is therefore Peter’s team.

Answer: A

Correct answer: niece

Your father’s mother is your grandmother, and her grandsons are you and your brothers and male cousins. Her grandson’s daughter is therefore your own daughter or your brother’s daughter, and since the question asks how Samantha is related to you rather than the reverse, the intended answer is your brother’s daughter - your niece.

Answer: C

Correct answer: S v R

This is the constructive dilemma. \( P \lor Q \) guarantees that at least one of P and Q holds; if P holds then \( P \to R \) gives R, and if Q holds then \( Q \to S \) gives S. Either way at least one of R and S is true, which is exactly \( S \lor R \). Nothing stronger follows, since neither R nor S is guaranteed on its own.

Answer: C

Correct answer: between Peter and Kenel

Chumley and Senthil take the two ends. Chumley must sit next to Peter, so Peter is in the second seat. Donald may not sit next to Senthil, so he cannot take the fourth seat and must take the third. Kenel must sit next to Donald, and the only seat left is the fourth. The order is Chumley, Peter, Donald, Kenel, Senthil.

Answer: D

Correct answer: ((x v y) ↔( ~x v ~y))

This fails whenever x and y have the same truth value: with both true, the left side is true and the right false, so the biconditional is false. The other three are valid - modus ponens, an implication with a self-contradictory antecedent, and the addition law - and a valid formula cannot be the false one.

Answer: A

Correct answer: True

The first equivalence makes a equivalent to \( b \lor \lnot b \), which is a tautology, so a is always true. Now suppose the antecedent \( a \land b \) holds; then b is true, and since \( b \leftrightarrow c \), c is true too, so \( a \land c \) is true and the consequent holds. The implication is therefore true in every case.