Discrete Math Quiz: Logical Equivalences

20 questions · exam conditions

0:00

Logical EquivalencesQuestion 1 of 20

Consider the nested implication: $P \rightarrow (Q \rightarrow R)$ . Which expression is equivalent when all implications are converted to their disjunctive forms?

(P \land Q) \rightarrow R

(\neg P \lor \neg Q) \lor R

\neg P \lor (Q \land R)

\neg P \lor (\neg Q \lor R)

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Logical Equivalences

Practice Logical Equivalences in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Logical Equivalences, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

Consider the nested implication: $P \rightarrow (Q \rightarrow R)$ . Which expression is equivalent when all implications are converted to their disjunctive forms?

$(P \land Q) \rightarrow R$
$(\neg P \lor \neg Q) \lor R$
$\neg P \lor (Q \land R)$
$\neg P \lor (\neg Q \lor R)$ (correct answer)

Explanation: 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.

Question 2

Given the equivalences for implications, which expression is NOT equivalent to $\neg(P \rightarrow Q)$ ?

$P \land \neg Q$
$\neg(\neg P \lor Q)$
$\neg Q \rightarrow \neg P$ (correct answer)
$P \land (Q \rightarrow \perp)$

Explanation:

\neg(P \rightarrow Q) \equiv P \land \neg Q

. Choice A is the standard form. Choice B uses the disjunctive form of implication. Choice D represents

P

and

Q

being false (contradiction). Choice C represents the contrapositive of the original implication, which is equivalent to

P \rightarrow Q

, not its negation.

Question 3

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:

$\overline{A \cdot B} \cdot \overline{C \cdot D}$
$\overline{A} + \overline{B} + \overline{C} + \overline{D}$
$(\overline{A} + \overline{B}) \cdot (\overline{C} + \overline{D})$ (correct answer)
$\overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D}$

Explanation: 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.

Question 4

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"?

$P$ is false, and either $Q$ is false or $R$ is false (correct answer)
$P$ is true, and either $Q$ is false or $R$ is false
$P$ is false, and both $Q$ and $R$ are false
If $P$ is true, then either $Q$ is false or $R$ is false

Explanation: 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.

Question 5

The statement $(P \lor Q) \rightarrow \neg(R \land S)$ is equivalent to its contrapositive. Which of the following correctly represents this contrapositive?

$(R \land S) \rightarrow \neg(P \lor Q)$
$(R \land S) \rightarrow (\neg P \land \neg Q)$ (correct answer)
$\neg(R \land S) \rightarrow (P \lor Q)$
$(\neg R \lor \neg S) \rightarrow (P \lor Q)$

Explanation: The contrapositive of

A \rightarrow B

\neg B \rightarrow \neg A

. Here:

\neg\neg(R \land S) \rightarrow \neg(P \lor Q) \equiv (R \land S) \rightarrow (\neg P \land \neg Q)

after applying De Morgan's law. Choice A doesn't apply De Morgan's to the consequent. Choice C reverses the roles incorrectly. Choice D applies De Morgan's to the wrong part.

Question 6

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?

$(A \land \neg B) \lor (\neg C \lor D)$ (correct answer)
$(\neg A \lor B) \lor (\neg C \lor D)$
$(A \land \neg B) \land (\neg C \lor D)$
$(A \lor \neg B) \lor (C \lor \neg D)$

Explanation:

\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.

Question 7

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?

The weather is sunny, and either the park is not crowded or the lake is not warm (correct answer)
The weather is not sunny, and both the park is crowded and the lake is warm
If the weather is not sunny, then the park is not crowded or the lake is not warm
The weather is sunny, and both the park is not crowded and the lake is not warm

Explanation:

\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.

Question 8

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"?

At least one student did not pass the exam (correct answer)
No students passed the exam
All students did not pass the exam
Some students passed and some students did not pass

Explanation: 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.

Question 9

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?

$\neg(P \rightarrow Q) \lor \neg(R \rightarrow S)$
$(P \land \neg Q) \lor (R \land \neg S)$ (correct answer)
$\neg(\neg P \lor Q) \lor \neg(\neg R \lor S)$
$(\neg P \lor Q) \land (\neg R \lor S)$

Explanation: 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.

Question 10

In formal logic, the biconditional $P \leftrightarrow Q$ is equivalent to $(P \rightarrow Q) \land (Q \rightarrow P)$ . What is the negation of $P \leftrightarrow Q$ when fully simplified using logical equivalences?

$\neg P \leftrightarrow \neg Q$
$(P \land \neg Q) \lor (\neg P \land Q)$ (correct answer)
$(\neg P \rightarrow \neg Q) \land (\neg Q \rightarrow \neg P)$
$\neg(P \rightarrow Q) \land \neg(Q \rightarrow P)$

Explanation: When you encounter questions about negating biconditionals, remember that a biconditional

P \leftrightarrow Q

means "P if and only if Q" — both statements must have the same truth value. The biconditional is true when P and Q are both true or both false, and false when they have different truth values. To find the negation, start with the given equivalence:

P \leftrightarrow Q \equiv (P \rightarrow Q) \land (Q \rightarrow P)

. Using De Morgan's law, the negation becomes:

\neg(P \leftrightarrow Q) \equiv \neg(P \rightarrow Q) \lor \neg(Q \rightarrow P)

Now apply the equivalence

\neg(A \rightarrow B) \equiv A \land \neg B

$\neg(P \rightarrow Q) \equiv P \land \neg Q$
$\neg(Q \rightarrow P) \equiv Q \land \neg P$

Therefore:

\neg(P \leftrightarrow Q) \equiv (P \land \neg Q) \lor (Q \land \neg P)

, which matches answer B when reordered. Option A (

\neg P \leftrightarrow \neg Q

) is incorrect because negating both components doesn't negate the biconditional — it's actually equivalent to the original

P \leftrightarrow Q

. Option C (

(\neg P \rightarrow \neg Q) \land (\neg Q \rightarrow \neg P)

) represents the contrapositive form of the original biconditional, which is logically equivalent to

P \leftrightarrow Q

, not its negation. Option D (

\neg(P \rightarrow Q) \land \neg(Q \rightarrow P)

) incorrectly uses conjunction instead of disjunction when applying De Morgan's law. Study tip: Remember that negating a biconditional gives you "exactly one is true" — the exclusive or situation where P and Q have opposite truth values.

Question 11

Consider the compound statement: " $\neg((P \land Q) \lor (R \land S))$ ". Using De Morgan's laws repeatedly, this statement is equivalent to:

$(\neg P \lor \neg Q) \land (\neg R \lor \neg S)$ (correct answer)
$(\neg P \land \neg Q) \lor (\neg R \land \neg S)$
$\neg P \land \neg Q \land \neg R \land \neg S$
$\neg P \lor \neg Q \lor \neg R \lor \neg S$

Explanation: 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.

Question 12

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?

$(\neg P \lor Q) \land (\neg R \lor S)$ (correct answer)
$(\neg P \land Q) \lor (\neg R \land S)$
$\neg(P \land R) \lor (Q \land S)$
$(P \lor \neg Q) \land (R \lor \neg S)$

Explanation: 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.

Question 13

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?

$(P \land Q) \land (\neg R \land \neg S)$
$(\neg P \lor \neg Q) \rightarrow (\neg R \land \neg S)$
$(P \lor Q) \lor (\neg R \land \neg S)$
$(P \land Q) \lor (\neg R \land \neg S)$ (correct answer)

Explanation: 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.

Question 14

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"?

$(\neg A \land \neg B) \lor (C \rightarrow \neg D)$
$(\neg A \lor \neg B) \lor (\neg C \lor D)$
$\neg(A \land B) \lor \neg(C \rightarrow D)$
$\neg(A \land B) \lor (C \land \neg D)$ (correct answer)

Explanation: 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)

(\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.

Question 15

Consider the expression $\neg((P \land Q) \lor (R \land S))$ . After applying De Morgan's laws completely, which form represents the equivalent expression?

$(\neg P \lor \neg Q) \land (\neg R \lor \neg S)$ (correct answer)
$(\neg P \land \neg Q) \lor (\neg R \land \neg S)$
$\neg(P \land Q) \land \neg(R \land S)$
$(\neg P \land \neg Q) \land (\neg R \land \neg S)$

Explanation: 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.

Question 16

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?

$\neg(A \lor B) \lor (C \lor D)$
$(A \lor B) \rightarrow \neg(\neg C \land \neg D)$
$\neg(A \lor B) \lor \neg(\neg C \land \neg D)$ (correct answer)
$(A \lor B) \rightarrow (\neg C \lor \neg D)$

Explanation: 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.

Question 17

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?

$\neg(P \land Q) \rightarrow (\neg R \lor S)$ (correct answer)
$(\neg P \lor \neg Q) \rightarrow (\neg R \land S)$
$(P \land Q) \rightarrow (R \land \neg S)$
$\neg(P \lor Q) \rightarrow (R \rightarrow S)$

Explanation: 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.

Question 18

Given that $\neg(P \rightarrow Q) \equiv (P \land \neg Q)$ , which expression is equivalent to $\neg((R \lor S) \rightarrow (T \land U))$ ?

$(R \lor S) \land \neg(T \land U)$
$(R \lor S) \land (\neg T \lor \neg U)$ (correct answer)
$\neg(R \lor S) \land (T \land U)$
$(R \land S) \land (\neg T \land \neg U)$

Explanation: Using the given equivalence with

A = (R \lor S)

and

B = (T \land U)

, we get

(R \lor S) \land \neg(T \land U)

. Applying De Morgan's law to

\neg(T \land U)

gives

(R \lor S) \land (\neg T \lor \neg U)

. Choice A stops before applying De Morgan's. Choice C incorrectly negates the antecedent. Choice D misapplies De Morgan's to both parts.

Question 19

Which of the following pairs of statements are logically equivalent due to De Morgan's laws?

"Not all birds can fly" and "Some birds cannot fly"
"No students failed" and "All students passed"
"Some cats are not friendly" and "Not all cats are friendly"
"It's not sunny and not warm" and "It's not the case that it's sunny or warm" (correct answer)

Explanation: 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.

Question 20

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?

This is a tautology that demonstrates De Morgan's law (correct answer)
This is a conditional statement that is sometimes false
This is equivalent to saying "If P and Q, then P or Q"
This contradicts De Morgan's law and is therefore invalid

Explanation: 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.