Use truth tables to evaluate logical expressions - Discrete Math

1. Using a truth table to analyze $(P \land Q) \leftrightarrow (\neg P \lor \neg Q)$, what type of logical expression is this?
   Answer: This expression is a contradiction (always false) When analyzing compound logical expressions, constructing a truth table helps you determine whether the expression is always true (tautology), always false (contradiction), or sometimes true and sometimes false (satisfiable but not a tautology). Let's build the truth table for $(P \land Q) \leftrightarrow (\neg P \lor \neg Q)$:

   P	Q	P ∧ Q	¬P	¬Q	¬P ∨ ¬Q	(P ∧ Q) ↔ (¬P ∨ ¬Q)
   T	T	T	F	F	F	F
   T	F	F	F	T	T	F
   F	T	F	T	F	T	F
   F	F	F	T	T	T	F

   The final column shows all false values, making this a contradiction. The biconditional $\leftrightarrow$ is true only when both sides have the same truth value, but $(P \land Q)$ and $(\neg P \lor \neg Q)$ always have opposite truth values. Answer A is wrong because the expression is never true. Answer B is incorrect because $P \oplus Q$ (exclusive or) has the pattern F, T, T, F, not all false values. Answer C is wrong because a satisfiable expression must be true in at least one case, but this expression is false in every row. Study tip: Remember that De Morgan's Law tells us $\neg(P \land Q) \equiv (\neg P \lor \neg Q)$. So this expression is really asking whether $(P \land Q)$ equals its own negation, which is impossible—hence always false.
2. A student claims that $\neg(p \land q) \rightarrow (\neg p \lor \neg q)$ is a tautology. Using truth table analysis, what can be concluded?
   Answer: The student is correct; this is a tautology by De Morgan's law By De Morgan's law, $\neg(p \land q) \equiv (\neg p \lor \neg q)$. So the expression becomes $(\neg p \lor \neg q) \rightarrow (\neg p \lor \neg q)$, which is of the form $A \rightarrow A$. This is always true regardless of the truth value of $A$, making it a tautology. We can verify: when $p=T, q=T$: $F \rightarrow F = T$. When $p=T, q=F$: $T \rightarrow T = T$. When $p=F, q=T$: $T \rightarrow T = T$. When $p=F, q=F$: $T \rightarrow T = T$. Choice B suggests limited truth conditions. Choice C claims it's always false. Choice D claims it's sometimes false.
3. Using truth table evaluation, determine when the expression $(p \leftrightarrow q) \land (q \leftrightarrow r) \land (r \leftrightarrow p)$ is true. How many of the 8 possible truth value assignments satisfy this condition?
   Answer: Exactly 2 assignments: when all three variables are true or all are false When you encounter compound logical expressions with biconditionals ($\leftrightarrow$), remember that a biconditional $p \leftrightarrow q$ is true only when both variables have the same truth value—either both true or both false. To solve this systematically, construct a truth table with all 8 possible combinations of truth values for $p$, $q$, and $r$. For each row, evaluate each biconditional separately, then determine when all three are simultaneously true. Let's examine the key cases: - When $p = T, q = T, r = T$: All biconditionals are true ($T \leftrightarrow T = T$), so the entire expression is true. - When $p = F, q = F, r = F$: All biconditionals are true ($F \leftrightarrow F = T$), so the entire expression is true. - When variables have mixed values (like $p = T, q = T, r = F$): At least one biconditional becomes false ($T \leftrightarrow F = F$), making the entire conjunction false. The pattern emerges: the expression is true only when all three variables have identical truth values. Answer A is incorrect because having any two variables the same doesn't guarantee the third matches. Answer C is wrong because "at least two the same" includes cases where the third differs. Answer D fails because "exactly two the same" means one variable differs, breaking at least one biconditional. Study tip: With multiple biconditionals connected by AND, look for cases where all variables are uniform. Biconditionals demand consistency—mixed truth values will always break the chain.
4. A logic circuit implements the expression $\neg((P \land Q) \lor (\neg P \land \neg Q))$. For which input combinations does this circuit output true?
   Answer: When $P$ and $Q$ have different truth values The expression $(P \land Q) \lor (\neg P \land \neg Q)$ is true when either both $P,Q$ are true OR both are false (i.e., when they have the same truth value). The negation of this expression is therefore true when $P$ and $Q$ have different truth values. For $P=T, Q=F$: $\neg((T \land F) \lor (F \land T)) = \neg(F \lor F) = \neg F = T$. For $P=F, Q=T$: $\neg((F \land T) \lor (T \land F)) = \neg(F \lor F) = T$. Choice A describes when the non-negated expression is true. Choice C is too broad and includes cases where the output is false. Choice D is too specific and misses one of the true cases.
5. Consider the compound statement: $((P \land Q) \rightarrow R) \land (\neg R \land P)$. For which truth value assignment is this statement true?
   Answer: $P = \text{True}, Q = \text{False}, R = \text{False}$ For the compound statement to be true, both conjuncts must be true: $((P \land Q) \rightarrow R)$ and $(\neg R \land P)$. From the second conjunct, we need $\neg R$ true and $P$ true, so $R = \text{False}$ and $P = \text{True}$. For the first conjunct with $R = \text{False}$, we need $(P \land Q) \rightarrow \text{False}$ to be true, which requires $(P \land Q) = \text{False}$. Since $P = \text{True}$, we need $Q = \text{False}$. Choice A fails because $P \land Q = \text{True}$ makes the implication false. Choice C fails because $P = \text{False}$ makes $\neg R \land P$ false. Choice D fails because $R = \text{True}$ makes $\neg R \land P$ false.
6. A truth table is constructed for the expression $((P \oplus Q) \land R) \lor (\neg P \land \neg Q \land \neg R)$. In how many rows does this expression evaluate to true?
   Answer: Exactly three rows evaluate to true When you encounter a complex logical expression, the systematic approach is to construct a complete truth table with all possible combinations of the variables and evaluate the expression step by step. For $((P \oplus Q) \land R) \lor (\neg P \land \neg Q \land \neg R)$, you need all eight possible combinations of P, Q, and R. Let's break this down systematically: The expression is true when either the first part $((P \oplus Q) \land R)$ is true OR the second part $(\neg P \land \neg Q \land \neg R)$ is true. Remember that $P \oplus Q$ (exclusive or) is true when exactly one of P or Q is true, but not both. Working through each row: - The first part $((P \oplus Q) \land R)$ is true when P and Q have different truth values AND R is true. This occurs in exactly two cases: (T,F,T) and (F,T,T). - The second part $(\neg P \land \neg Q \land \neg R)$ is true only when all three variables are false: (F,F,F). Since these conditions don't overlap, the expression evaluates to true in exactly three rows total. Answer A (five rows) likely comes from incorrectly counting cases where $P \oplus Q$ is true regardless of R's value. Answer B (four rows) might result from misunderstanding the exclusive or operation. Answer D (six rows) could arise from treating $\oplus$ as inclusive or rather than exclusive or. Strategy tip: For complex logical expressions, always work methodically through the truth table and double-check your understanding of each logical operator, especially $\oplus$ which students often confuse with inclusive or.
7. Using the truth table for the expression $(P \rightarrow Q) \land (Q \rightarrow R) \land (\neg R)$, determine which of the following must be true when the entire expression evaluates to true.
   Answer: Both $P$ and $Q$ must be false, and $R$ must be false For the conjunction to be true, all three parts must be true: $(P \rightarrow Q)$, $(Q \rightarrow R)$, and $\neg R$. From $\neg R$, we know $R = \text{False}$. From $(Q \rightarrow R)$ with $R = \text{False}$, for this to be true we need $Q = \text{False}$ (since $\text{True} \rightarrow \text{False} = \text{False}$). From $(P \rightarrow Q)$ with $Q = \text{False}$, for this to be true we need $P = \text{False}$. Choice B incorrectly suggests $Q$ can be true. Choice C incorrectly suggests $P$ can be true. Choice D incorrectly states $P$ must be true, which would make $P \rightarrow Q$ false when $Q$ is false.
8. The expression $(p \rightarrow q) \land (q \rightarrow r) \land (r \rightarrow p)$ forms a logical cycle. In how many rows of its truth table does this expression evaluate to true?
   Answer: 2 rows: when all variables have the same truth value This expression is true when all three implications are true simultaneously. Since we have $p \rightarrow q \rightarrow r \rightarrow p$, this creates a cycle where all variables must have the same truth value. When $p=q=r=T$: $(T \rightarrow T) \land (T \rightarrow T) \land (T \rightarrow T) = T \land T \land T = T$. When $p=q=r=F$: $(F \rightarrow F) \land (F \rightarrow F) \land (F \rightarrow F) = T \land T \land T = T$. Any other combination breaks at least one implication. For example, if $p=T, q=F, r=T$, then $p \rightarrow q = F$. Choice B incorrectly suggests 4 solutions. Choice C overcounts. Choice D undercounts and has wrong reasoning.
9. Consider the nested conditional $p \rightarrow (q \rightarrow (r \rightarrow s))$. This expression is logically equivalent to which of the following when expanded using truth table analysis?
   Answer: All of the above expressions are logically equivalent to the original nested conditional Let's verify each equivalence. The original $p \rightarrow (q \rightarrow (r \rightarrow s))$ can be rewritten as: $\neg p \lor (\neg q \lor (\neg r \lor s)) = \neg p \lor \neg q \lor \neg r \lor s$ (Choice A). This is also equivalent to $(p \land q \land r) \rightarrow s$ because $\neg p \lor \neg q \lor \neg r \lor s = \neg(p \land q \land r) \lor s$ (Choice B). By De Morgan's law, this equals $\neg(p \land q \land r \land \neg s)$ (Choice C). All three forms represent the same logical relationship: the nested conditional is false only when $p$, $q$, and $r$ are all true but $s$ is false. Each choice represents a valid equivalent form.
10. Given that the biconditional $p \leftrightarrow (q \land r)$ is true, and $q \rightarrow s$ is false, what can be concluded about the truth value of $p \lor s$?
    Answer: $p \lor s$ could be either true or false depending on other values From $q \rightarrow s$ being false, we know $q$ is true and $s$ is false. From $p \leftrightarrow (q \land r)$ being true, $p$ and $(q \land r)$ have the same truth value. Since $q$ is true, $(q \land r)$ depends on $r$. Case 1: If $r$ is true, then $p$ is true, so $p \lor s = T \lor F = T$. Case 2: If $r$ is false, then $p$ is false, so $p \lor s = F \lor F = F$. Therefore, $p \lor s$ can be either true or false. Choice A incorrectly assumes $p \lor s$ is always true. Choice B incorrectly assumes it's always false. Choice D correctly identifies the dependency on $r$ but states it backwards.
11. In constructing a truth table for $(p \rightarrow q) \oplus (q \rightarrow p)$, which pattern emerges?
    Answer: The expression is true exactly when $p$ and $q$ have different truth values When you encounter logical expressions with exclusive or ($\oplus$) combined with conditionals, construct a systematic truth table to identify the pattern. Let's build the truth table for $(p \rightarrow q) \oplus (q \rightarrow p)$: For $p = T, q = T$: Both $p \rightarrow q$ and $q \rightarrow p$ are true, so $T \oplus T = F$ For $p = T, q = F$: $p \rightarrow q$ is false, $q \rightarrow p$ is true, so $F \oplus T = T$ For $p = F, q = T$: $p \rightarrow q$ is true, $q \rightarrow p$ is false, so $T \oplus F = T$ For $p = F, q = F$: Both conditionals are true, so $T \oplus T = F$ The expression evaluates to true only when $p$ and $q$ have different truth values, confirming answer D. Answer A is wrong because the expression is false in two cases (when both variables match), so it's not a tautology. Answer B incorrectly states the opposite pattern—the expression is actually false when $p$ and $q$ have the same truth values. Answer C is wrong because the expression evaluates to true in two cases, so it's not a contradiction. Remember that exclusive or ($\oplus$) is true when its operands differ. When you see $\oplus$ in logical expressions, look for patterns where the components have opposite truth values. This often reveals whether variables need to match or differ for the overall expression to be true.
12. The logical expression $\neg((p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p))$ represents the negation of which fundamental logical principle?
    Answer: The law of contraposition (creating a contradiction since contraposition is always valid) When you encounter logical expressions involving implications and their negations, you're typically dealing with fundamental principles of logical equivalence. The key here is recognizing what happens when you negate a well-established logical law. The expression $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$ represents the law of contraposition, which states that any conditional statement is logically equivalent to its contrapositive. This is always true in classical logic—contraposition is a fundamental principle that never fails. When you negate this expression with $\neg((p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p))$, you're creating a logical contradiction because you're asserting that contraposition doesn't hold, which is impossible. Let's examine why the other options don't fit: Option A mentions De Morgan's laws, but those specifically deal with negating conjunctions and disjunctions ($\neg(p \land q) \equiv \neg p \lor \neg q$), not the relationship between conditionals and their contrapositives. Option B refers to the law of excluded middle ($p \lor \neg p$), which involves disjunction and has a completely different logical structure. Option D discusses distributive properties between conjunction and disjunction, which again involves different operators and relationships than what we see in this implication-based expression. The correct answer is C because negating the law of contraposition creates an inherent logical contradiction. Study tip: When you see nested implications in logic problems, first identify if the inner structure represents a known logical principle. Contraposition problems often appear as implications between a conditional and its contrapositive form.
13. Consider the truth table for the expression $(P \land Q) \rightarrow (P \lor R)$. This expression is false in exactly how many rows of the complete truth table?
    Answer: The expression is false in exactly zero rows An implication $A \rightarrow B$ is false only when $A$ is true and $B$ is false. Here, $A = (P \land Q)$ and $B = (P \lor R)$. For the expression to be false, we need $(P \land Q) = \text{True}$ and $(P \lor R) = \text{False}$. If $(P \land Q) = \text{True}$, then both $P$ and $Q$ are true. But if $P = \text{True}$, then $(P \lor R) = \text{True}$ regardless of $R$'s value. Therefore, it's impossible to have $(P \land Q) = \text{True}$ and $(P \lor R) = \text{False}$ simultaneously. The expression is a tautology. Choices B, C, and D incorrectly assume there exist rows where the implication fails.
14. When evaluating $(p \land \neg q) \lor (\neg p \land q) \lor (\neg p \land \neg q)$ using a systematic truth table approach, the result is equivalent to which single logical operator applied to $p$ and $q$?
    Answer: $\neg(p \land q)$, which is the NAND operation between $p$ and $q$ When you encounter complex logical expressions with multiple operators, the key is to systematically evaluate all possible truth value combinations and look for patterns that match simpler, equivalent expressions. Let's build a truth table for $(p \land \neg q) \lor (\neg p \land q) \lor (\neg p \land \neg q)$:

    p	q	$\neg p$	$\neg q$	$p \land \neg q$	$\neg p \land q$	$\neg p \land \neg q$	Final Result
    T	T	F	F	F	F	F	F
    T	F	F	T	T	F	F	T
    F	T	T	F	F	T	F	T
    F	F	T	T	F	F	T	T

    The expression is true in three cases: when p is true and q is false, when p is false and q is true, and when both are false. It's only false when both p and q are true. Now compare this to $\neg(p \land q)$: this is false only when both p and q are true, and true in all other cases. This matches our result exactly, confirming answer B is correct. Option A ($\neg(p \lor q)$) is true only when both variables are false. Option C ($p \oplus q$) is false when both variables have the same truth value. Option D ($p \leftrightarrow q$) is true when both variables have the same truth value. Study tip: When simplifying complex logical expressions, always construct the complete truth table first, then compare the final column against standard logical operators. This systematic approach prevents errors and reveals equivalent forms.
15. Consider the compound statement: $(p \land q) \rightarrow (\neg r \lor s)$. If this statement is false, which of the following must be true?
    Answer: $p$ is true, $q$ is true, $r$ is true, and $s$ is false For an implication $A \rightarrow B$ to be false, we need $A$ true and $B$ false. So $(p \land q)$ must be true and $(\neg r \lor s)$ must be false. For $(p \land q)$ to be true, both $p$ and $q$ must be true. For $(\neg r \lor s)$ to be false, both $\neg r$ and $s$ must be false, meaning $r$ is true and $s$ is false. Choice B makes the antecedent false (since $p$ and $q$ are both false), which would make the implication true. Choice C makes the antecedent false (since $q$ is false). Choice D also makes the antecedent false (since $p$ is false).
16. A complex logical circuit evaluates $((P \rightarrow Q) \land (Q \rightarrow R)) \rightarrow (P \rightarrow R)$. After constructing the complete truth table with variables $P$, $Q$, and $R$, how many rows show this expression as false?
    Answer: No rows show the expression as false This question tests your understanding of logical equivalences and the concept of tautologies. When you encounter a complex logical expression like this, you're essentially looking at a potential logical law that might always be true regardless of the truth values of its variables. The expression $((P \rightarrow Q) \land (Q \rightarrow R)) \rightarrow (P \rightarrow R)$ represents the transitive property of implication. To verify this, construct a truth table with all eight possible combinations of P, Q, and R values. For each row, evaluate the antecedent $(P \rightarrow Q) \land (Q \rightarrow R)$ and the consequent $(P \rightarrow R)$, then determine the truth value of the entire implication. When you work through each row systematically, you'll discover that this expression evaluates to true in every single case. This makes it a tautology—a logical statement that's always true regardless of the truth values of its components. The transitive property holds because whenever both "if P then Q" and "if Q then R" are true, "if P then R" must also be true. Answer choice A suggests exactly two false rows, which would indicate a partially valid logical relationship. Answer choice B proposes exactly one false row, suggesting the expression fails in just one scenario. Answer choice D claims exactly three false rows, indicating multiple logical failures. All of these are incorrect because the expression never evaluates to false. When studying logical equivalences, focus on recognizing fundamental logical laws like transitivity, which appear frequently in discrete mathematics. Tautologies are particularly important—they represent universally valid logical principles.
17. Given the compound statement $((p \lor q) \rightarrow r) \land (r \rightarrow (s \land t))$, if $p$ is true and the entire compound statement is true, what must be true about $s$ and $t$?
    Answer: Both $s$ and $t$ must be true, regardless of other variable values When analyzing compound logical statements, you need to trace through the implications systematically, especially when given specific conditions that make the entire statement true. Given that $p$ is true and the entire compound statement $((p \lor q) \rightarrow r) \land (r \rightarrow (s \land t))$ is true, let's work through what must follow. Since $p$ is true, $(p \lor q)$ is automatically true regardless of $q$'s value. For the first part $((p \lor q) \rightarrow r)$ to be true when $(p \lor q)$ is true, $r$ must also be true (since a true antecedent in a true implication forces a true consequent). Now that we know $r$ is true, look at the second part: $(r \rightarrow (s \land t))$. Since $r$ is true and this implication must be true for the entire compound statement to be true, $(s \land t)$ must be true. For a conjunction to be true, both components must be true, so both $s$ and $t$ must be true. Choice A is wrong because $r$ is forced to be true, eliminating variability. Choice B misunderstands conjunctions—$(s \land t)$ requires both variables to be true, not just one. Choice D incorrectly suggests $q$'s value matters, but since $p$ alone makes $(p \lor q)$ true, $q$ is irrelevant to the chain of reasoning. The answer is C: both $s$ and $t$ must be true regardless of other variables. Study tip: In logical chains, trace through each implication step-by-step. When the entire compound statement must be true, work forwards from your known values to find what else must be true.
18. Consider the statement: "If $p$ or $q$ is true, then both $r$ and $s$ are false." Using truth table analysis, under which conditions is this statement false?
    Answer: When at least one of $p$ or $q$ is true, and at least one of $r$ or $s$ is true The statement translates to $(p \lor q) \rightarrow (\neg r \land \neg s)$. An implication is false only when the antecedent is true and the consequent is false. The antecedent $(p \lor q)$ is true when at least one of $p$ or $q$ is true. The consequent $(\neg r \land \neg s)$ is false when at least one of $r$ or $s$ is true (since then not both $r$ and $s$ are false). Choice A describes when the antecedent is false, making the implication vacuously true. Choice C describes when both antecedent and consequent are true. Choice D is too restrictive about the "exactly one" conditions.
19. The expression $\neg(P \rightarrow Q) \land (P \lor Q)$ is evaluated using a truth table. Which truth value assignment makes this expression true?
    Answer: $P = \text{True}, Q = \text{False}$ When you encounter compound logical expressions like this one, you need to systematically evaluate each component using the given truth values. This expression combines negation, implication, and conjunction, so understanding operator precedence and truth conditions is crucial. Let's work through option D: $P = \text{True}, Q = \text{False}$. First, evaluate $P \rightarrow Q$. An implication is false only when the antecedent is true and the consequent is false, which is exactly our case: $\text{True} \rightarrow \text{False} = \text{False}$. Therefore, $\neg(P \rightarrow Q) = \neg\text{False} = \text{True}$. Next, evaluate $P \lor Q$: $\text{True} \lor \text{False} = \text{True}$. Finally, the conjunction: $\text{True} \land \text{True} = \text{True}$. The entire expression is true. Option A fails because when both $P$ and $Q$ are true, $P \rightarrow Q$ becomes $\text{True} \rightarrow \text{True} = \text{True}$, making $\neg(P \rightarrow Q) = \text{False}$, and $\text{False} \land \text{True} = \text{False}$. Option B fails because $P \rightarrow Q$ becomes $\text{False} \rightarrow \text{False} = \text{True}$, so $\neg(P \rightarrow Q) = \text{False}$, and $\text{False} \land \text{False} = \text{False}$. Option C fails because $P \rightarrow Q$ becomes $\text{False} \rightarrow \text{True} = \text{True}$, making $\neg(P \rightarrow Q) = \text{False}$, and $\text{False} \land \text{True} = \text{False}$. Remember: implications are only false when you have "true implies false." This makes option D the only case where negating the implication yields true, allowing the entire conjunction to be true.

Start this quiz