Logic Questions and Answers

Answer: C

Correct answer: If p is true and q is false and r is false, the P1 is true

Conjunction binds more tightly than disjunction, so the formula reads \( [(p \lor \lnot q) \land (q \to r)] \lor (r \lor p) \). With p true, q false and r false: \( p \lor \lnot q \) is true, \( q \to r \) is true because the antecedent is false, so the bracket is true and the whole is true. It is not a tautology, since p false, q true and r false makes every disjunct false.

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: 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: 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: A

Correct answer: P ^ ˝Q

An implication is false in exactly one case, when the antecedent is true and the consequent false, so its negation asserts precisely that case. Formally \( \lnot(P \to Q) \equiv \lnot(\lnot P \lor Q) \equiv P \land \lnot Q \) by De Morgan. Note that the result is a conjunction, not another implication.

Answer: B

Correct answer: ~p v q

This is the definition of material implication: \( p \to q \) is false only when p is true and q false, which is exactly when \( \lnot p \lor q \) is false. The equivalence is what allows implications to be eliminated from a formula so that De Morgan’s laws and distribution can be applied.

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: ((P → Q)^(Q → R))→ (P → R)

This is the hypothetical syllogism and it is valid: if P leads to Q and Q leads to R, then P leads to R. The second option is the fallacy of denying the antecedent, the third fails when P is false and Q false, and the fourth confuses the disjunction of two implications with the implication of a disjunction.

Answer: C

Correct answer: →→PQ→→QR→PR

In prefix notation the connective precedes its operands, so the string is read outward from the leading symbol. This one parses as an implication whose antecedent is \( P \to Q \) and whose consequent is \( (Q \to R) \to (P \to R) \) - a well-formed formula, and in fact a valid one. The others leave connectives without the operands they require.

Answer: A

Correct answer: True

Take p and q both true. Then \( p \leftrightarrow q \) is true, but \( p \to \lnot q \) is \( T \to F \), which is false. A single row in which the first is true and the second false is enough to show that the first does not imply the second, so the statement that it does not imply it is correct.