Identify logical equivalences (De Morgan’s, implication forms) - Discrete Math

1. The statement "If John studies hard, then he will pass the exam" can be written as S → P. Which of the following represents the direct logical equivalence of this implication?
   Answer: ¬S ∨ P (Either John doesn't study hard or he passes) When you encounter questions about logical equivalence of implications, you need to understand how conditional statements can be rewritten in different but logically identical forms. The implication $S \rightarrow P$ ("If John studies hard, then he will pass") is logically equivalent to $\neg S \vee P$ ("Either John doesn't study hard or he passes"). This equivalence comes from the definition of implication: $S \rightarrow P$ is false only when the antecedent (S) is true and the consequent (P) is false. In all other cases, it's true. The disjunction $\neg S \vee P$ captures this same truth condition perfectly. Choice D correctly represents this logical equivalence using the disjunction form. Choice A ($S \wedge P$) is wrong because it states both conditions must be true simultaneously, which is much stronger than the original implication. The implication doesn't require John to actually study hard—it only tells us what happens if he does. Choice B ($P \rightarrow S$) represents the converse of the original statement, which is not logically equivalent. Just because John passes doesn't mean he necessarily studied hard—he might have gotten lucky or been naturally gifted. Choice C ($\neg P \rightarrow \neg S$) is the contrapositive, which is indeed logically equivalent to the original statement, but the question asks for the "direct logical equivalence," referring to the standard disjunctive form. Remember this key equivalence: any implication $A \rightarrow B$ can always be rewritten as $\neg A \vee B$. This transformation is fundamental in discrete mathematics and formal logic.
2. In a logic circuit, the output expression is $\overline{A \cdot B + C \cdot D}$ where the overline represents negation, $\cdot$ represents AND, and $+$ represents OR. Using De Morgan's laws, this expression simplifies to:
   Answer: $(\overline{A} + \overline{B}) \cdot (\overline{C} + \overline{D})$ Starting with $\overline{A \cdot B + C \cdot D}$, we apply De Morgan's law to get $\overline{A \cdot B} \cdot \overline{C \cdot D}$. Then applying De Morgan's law again to each term: $\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{C \cdot D} = \overline{C} + \overline{D}$. So the final result is $(\overline{A} + \overline{B}) \cdot (\overline{C} + \overline{D})$. Choice A stops after the first application. Choice B incorrectly distributes the negation. Choice D applies De Morgan's incorrectly by using AND instead of OR within each group.
3. Consider the statement: "If it is not the case that both $P$ and $Q$ are true, then either $R$ is false or $S$ is true." Which of the following is logically equivalent to this statement?
   Answer: $\neg(P \land Q) \rightarrow (\neg R \lor S)$ The statement translates to $\neg(P \land Q) \rightarrow (\neg R \lor S)$. Choice B incorrectly uses conjunction instead of disjunction in the consequent. Choice C represents the contrapositive incorrectly by negating the antecedent improperly. Choice D misinterprets "not both P and Q" as "neither P nor Q" and changes the consequent structure.
4. A database query uses the condition: $\neg((\text{Age} < 25) \land (\text{Salary} > 50000))$. Using logical equivalences, this condition will select records where:
   Answer: Age is 25 or older, or salary is $50,000 or less Using De Morgan's law on $\neg((\text{Age} < 25) \land (\text{Salary} > 50000))$, we get $\neg(\text{Age} < 25) \lor \neg(\text{Salary} > 50000)$. This simplifies to $(\text{Age} \geq 25) \lor (\text{Salary} \leq 50000)$, which means "Age is 25 or older, OR salary is $50,000 or less." Choice A incorrectly uses AND instead of OR. Choice C incorrectly negates the age condition. Choice D represents the original condition before applying De Morgan's law.
5. Which of the following statements is equivalent to saying "It is not true that: if $P$ is false, then both $Q$ and $R$ are true"?
   Answer: $P$ is false, and either $Q$ is false or $R$ is false The statement is $\neg(\neg P \rightarrow (Q \land R)) \equiv \neg P \land \neg(Q \land R) \equiv \neg P \land (\neg Q \lor \neg R)$. This means "P is false, and either Q is false or R is false." Choice B incorrectly states P is true. Choice C uses conjunction instead of disjunction for the Q and R parts. Choice D converts back to an implication form incorrectly.
6. The expression $\neg(P \land Q) \rightarrow \neg(R \lor S)$ is logically equivalent to which of the following when fully simplified using De Morgan's laws and implication equivalences?
   Answer: $(P \land Q) \lor (\neg R \land \neg S)$ When you encounter logical equivalence problems involving implications and De Morgan's laws, your goal is to systematically transform the expression using established equivalences until you reach the simplest form. Let's work through $\neg(P \land Q) \rightarrow \neg(R \lor S)$ step by step. First, recall that any implication $A \rightarrow B$ is equivalent to $\neg A \lor B$. Applying this rule: $\neg(P \land Q) \rightarrow \neg(R \lor S) \equiv \neg[\neg(P \land Q)] \lor \neg(R \lor S)$ Next, simplify $\neg[\neg(P \land Q)]$ using the double negation law: this becomes simply $(P \land Q)$. Now apply De Morgan's law to $\neg(R \lor S)$: this transforms to $(\neg R \land \neg S)$. Our expression is now: $(P \land Q) \lor (\neg R \land \neg S)$, which matches answer choice D. Let's examine why the other options are incorrect: A uses conjunction ($\land$) between the two parts, but our derivation shows they should be connected by disjunction ($\lor$). B keeps the implication structure instead of converting it to disjunction, so it's not fully simplified as the question requires. C incorrectly shows $(P \lor Q)$ in the first part. This would result from incorrectly applying De Morgan's law to $\neg(P \land Q)$, but we actually need to apply double negation first. Study tip: Always work methodically through logical equivalences: handle implications first (convert to disjunctions), then apply De Morgan's laws to negated compound statements, and finally use double negation to simplify.
7. The expression $\neg((P \rightarrow Q) \land (R \rightarrow S))$ can be simplified using De Morgan's law and implication equivalences. Which form represents the complete simplification?
   Answer: $(P \land \neg Q) \lor (R \land \neg S)$ Applying De Morgan's law: $\neg(P \rightarrow Q) \lor \neg(R \rightarrow S)$. Then converting each negated implication: $(P \land \neg Q) \lor (R \land \neg S)$. Choice A stops after applying De Morgan's law. Choice C converts implications to disjunctive form but doesn't simplify the negations. Choice D doesn't apply the initial negation correctly.
8. Which of the following is equivalent to the statement $(P \rightarrow Q) \land (R \rightarrow S)$ when both implications are converted to their disjunctive forms?
   Answer: $(\neg P \lor Q) \land (\neg R \lor S)$ Using the equivalence $P \rightarrow Q \equiv \neg P \lor Q$, we get $(\neg P \lor Q) \land (\neg R \lor S)$. Choice B incorrectly uses conjunction within each implication and disjunction between them. Choice C attempts to distribute incorrectly. Choice D negates the wrong components in each disjunction.
9. The statement "It is not true that if the weather is sunny, then both the park is crowded and the lake is warm" can be expressed symbolically as $\neg(S \rightarrow (C \land W))$. Which of the following represents the same logical meaning?
   Answer: The weather is sunny, and either the park is not crowded or the lake is not warm $\neg(S \rightarrow (C \land W)) \equiv S \land \neg(C \land W) \equiv S \land (\neg C \lor \neg W)$. This translates to "The weather is sunny, and either the park is not crowded or the lake is not warm." Choice B negates the wrong component. Choice C converts to an implication incorrectly. Choice D uses conjunction instead of disjunction in the second part.
10. Consider the expression $\neg((P \land Q) \lor (R \land S))$. After applying De Morgan's laws completely, which form represents the equivalent expression?
    Answer: $(\neg P \lor \neg Q) \land (\neg R \lor \neg S)$ Applying De Morgan's law: $\neg((P \land Q) \lor (R \land S)) \equiv \neg(P \land Q) \land \neg(R \land S)$, then applying De Morgan's again to each part: $(\neg P \lor \neg Q) \land (\neg R \lor \neg S)$. Choice B uses disjunction instead of conjunction between the main parts. Choice C stops after the first application. Choice D incorrectly applies De Morgan's to get conjunctions instead of disjunctions within parentheses.
11. Consider the compound statement: "$\neg((P \land Q) \lor (R \land S))$". Using De Morgan's laws repeatedly, this statement is equivalent to:
    Answer: $(\neg P \lor \neg Q) \land (\neg R \lor \neg S)$ Applying De Morgan's law to $\neg((P \land Q) \lor (R \land S))$: First step gives us $\neg(P \land Q) \land \neg(R \land S)$. Applying De Morgan's again to each part: $\neg(P \land Q) \equiv (\neg P \lor \neg Q)$ and $\neg(R \land S) \equiv (\neg R \lor \neg S)$. So the final result is $(\neg P \lor \neg Q) \land (\neg R \lor \neg S)$. Choice B incorrectly uses OR between the groups. Choice C incorrectly uses AND throughout. Choice D incorrectly uses OR throughout.
12. The compound statement $\neg(A \rightarrow B) \lor (C \rightarrow D)$ can be rewritten using only conjunction, disjunction, and negation operators. Which form is correct?
    Answer: $(A \land \neg B) \lor (\neg C \lor D)$ $\neg(A \rightarrow B) \equiv A \land \neg B$ and $C \rightarrow D \equiv \neg C \lor D$. Therefore: $(A \land \neg B) \lor (\neg C \lor D)$. Choice B incorrectly converts $\neg(A \rightarrow B)$. Choice C uses conjunction instead of disjunction between the main parts. Choice D incorrectly handles both the negated implication and the regular implication.
13. Consider the statement: "If it is not the case that (P and Q), then either not P or not Q." Which of the following best describes this statement?
    Answer: This is a tautology that demonstrates De Morgan's law The statement $\neg(P \land Q) \rightarrow (\neg P \lor \neg Q)$ is actually a tautology because the antecedent $\neg(P \land Q)$ is logically equivalent to the consequent $(\neg P \lor \neg Q)$ by De Morgan's law. Since the antecedent and consequent are equivalent, the conditional is always true. Choice B is wrong because tautologies are never false. Choice C describes a different (and obvious) tautology. Choice D is incorrect because this statement actually demonstrates De Morgan's law.
14. The statement "$\neg(\forall x \in S, P(x)) \equiv \exists x \in S, \neg P(x)$" is an application of De Morgan's law to quantified statements. Which of the following is the correct application of this principle to the statement "It is not true that all students passed the exam"?
    Answer: At least one student did not pass the exam The negation of "all students passed" is equivalent to "there exists at least one student who did not pass," which is choice A. This directly applies De Morgan's law for quantifiers. Choice B ("No students passed") is too strong - it's the negation of "some students passed." Choice C ("All students did not pass") is also too strong and represents $\forall x, \neg P(x)$ rather than $\exists x, \neg P(x)$. Choice D adds unnecessary information not implied by the original negation.
15. Which of the following is logically equivalent to the statement "$\neg(A \rightarrow B)$"?
    Answer: $A \land \neg B$ To find $\neg(A \rightarrow B)$, we first note that $A \rightarrow B \equiv \neg A \lor B$. Therefore, $\neg(A \rightarrow B) \equiv \neg(\neg A \lor B)$. Applying De Morgan's law: $\neg(\neg A \lor B) \equiv \neg(\neg A) \land \neg B \equiv A \land \neg B$. Choice B is the contrapositive of the original (not its negation). Choice C incorrectly negates A instead of B. Choice D applies De Morgan's incorrectly and gives $\neg A \land \neg B$ instead of the correct answer.
16. Which expression represents the logical equivalent of "Either it is not the case that both $A$ and $B$ are true, or it is not the case that if $C$ is true then $D$ is true"?
    Answer: $\neg(A \land B) \lor (C \land \neg D)$ When translating complex English statements into logical notation, you need to carefully parse each component and identify the logical structure. This question tests your ability to convert natural language into symbolic logic while recognizing how negations interact with compound statements. Let's break down the statement piece by piece. "Either...or" indicates a disjunction ($\lor$). The first part says "it is not the case that both A and B are true," which translates to $\neg(A \land B)$. The second part says "it is not the case that if C is true then D is true," which means $\neg(C \rightarrow D)$. However, we need to simplify $\neg(C \rightarrow D)$. Since $C \rightarrow D$ is logically equivalent to $\neg C \lor D$, the negation $\neg(C \rightarrow D)$ becomes $\neg(\neg C \lor D)$. Using De Morgan's law, this simplifies to $C \land \neg D$. Therefore, the complete expression is $\neg(A \land B) \lor (C \land \neg D)$, which is answer D. Answer A incorrectly applies De Morgan's law to the first part, changing $\neg(A \land B)$ to $(\neg A \land \neg B)$ instead of $(\neg A \lor \neg B)$, and mishandles the conditional negation. Answer B correctly applies De Morgan's to the first part but fails to properly negate the conditional, leaving it as $(\neg C \lor D)$ instead of $(C \land \neg D)$. Answer C stops halfway through the simplification, leaving $\neg(C \rightarrow D)$ in its complex form rather than simplifying it. Always fully simplify logical expressions by applying equivalences like De Morgan's laws and the definition of conditionals to reach the clearest form.
17. The statement "If either $A$ or $B$ is true, then it is not the case that both $C$ and $D$ are false" is logically equivalent to which of the following?
    Answer: $\neg(A \lor B) \lor \neg(\neg C \land \neg D)$ The statement is $(A \lor B) \rightarrow \neg(\neg C \land \neg D)$. Converting to disjunctive form: $\neg(A \lor B) \lor \neg(\neg C \land \neg D)$. Choice A incorrectly simplifies the consequent. Choice B keeps the implication form rather than converting to disjunctive form. Choice D incorrectly applies De Morgan's law to the consequent.
18. Which of the following pairs of statements are logically equivalent due to De Morgan's laws?
    Answer: "It's not sunny and not warm" and "It's not the case that it's sunny or warm" Choice D represents $\neg S \land \neg W$ and $\neg(S \lor W)$, which are equivalent by De Morgan's law: $\neg(A \lor B) \equiv \neg A \land \neg B$. Choice A is correct but represents quantifier negation, not basic De Morgan's laws. Choice B represents equivalent statements but not through De Morgan's laws (they're equivalent by definition). Choice C actually represents the same statement said two different ways, not a De Morgan's equivalence.
19. Consider the statement: "It is not the case that if the weather is nice, then we will go hiking or swimming." Which of the following is the simplified logical form of this statement?
    Answer: W ∧ ¬(H ∨ S) where W = weather is nice, H = go hiking, S = go swimming When you encounter statements with "It is not the case that..." followed by a conditional, you're dealing with negation of implications, which requires careful logical parsing. Let's break down the original statement step by step. First, identify the core conditional: "if the weather is nice, then we will go hiking or swimming." In logical form, this is $W \to (H \vee S)$. The entire statement negates this conditional: "It is not the case that [$W \to (H \vee S)$]," giving us $\neg(W \to (H \vee S))$. To simplify $\neg(W \to (H \vee S))$, recall that $P \to Q$ is equivalent to $\neg P \vee Q$. So $W \to (H \vee S)$ becomes $\neg W \vee (H \vee S)$. When we negate this using De Morgan's law, $\neg(\neg W \vee (H \vee S))$ becomes $W \wedge \neg(H \vee S)$. This matches option C. Option A ($\neg W \wedge (H \vee S)$) incorrectly negates only the weather condition while keeping the activities positive. Option B ($\neg W \to \neg(H \vee S)$) fails to properly negate the original implication and instead creates a new conditional. Option D ($W \to \neg(H \vee S)$) also creates a new conditional rather than negating the original statement. The key insight is that negating "if P then Q" means P is true AND Q is false—the antecedent happens but the consequent doesn't. Remember: $\neg(P \to Q) \equiv P \wedge \neg Q$.
20. Consider the nested implication: $P \rightarrow (Q \rightarrow R)$. Which expression is equivalent when all implications are converted to their disjunctive forms?
    Answer: $\neg P \lor (\neg Q \lor R)$ When you encounter nested implications like this, you need to systematically convert each implication to its disjunctive form using the equivalence $P \rightarrow Q \equiv \neg P \lor Q$. Starting with $P \rightarrow (Q \rightarrow R)$, work from the inside out. First, convert the inner implication: $Q \rightarrow R$ becomes $\neg Q \lor R$. Now you have $P \rightarrow (\neg Q \lor R)$. Apply the conversion rule again: this becomes $\neg P \lor (\neg Q \lor R)$. The correct answer is D because it preserves the exact logical structure after both conversions. The parentheses maintain the proper grouping from the original nested structure. Option A represents $(P \land Q) \rightarrow R$, which would convert to $\neg(P \land Q) \lor R$, or equivalently $(\neg P \lor \neg Q) \lor R$. This changes the logical meaning entirely. Option B is exactly that incorrect conversion of A, treating the original as if it were $(P \land Q) \rightarrow R$ rather than the nested form given. Option C, $\neg P \lor (Q \land R)$, incorrectly uses conjunction instead of disjunction in the second part, which would represent $P \rightarrow (Q \land R)$—a completely different statement. Remember this key strategy: when converting nested implications, always work from the innermost parentheses outward, and double-check by converting your answer back to implication form. If it doesn't match the original structure, you've made an error in the conversion process.

Start this quiz