Discrete Math Quiz: Translating Quantified Statements

20 questions · exam conditions

0:00

Translating Quantified StatementsQuestion 1 of 20

Consider the statement: "No prime number greater than 2 is even." Let $P(x)$ = " $x$ is prime", $G(x)$ = " $x > 2$ , and $E(x)$ = " $x$ is even". Which predicate logic translation correctly represents this statement?

\forall x ((P(x) \land G(x)) \rightarrow \neg E(x))

\neg \exists x (P(x) \land G(x) \land E(x))

\forall x (P(x) \rightarrow (G(x) \rightarrow \neg E(x)))

\forall x ((P(x) \land \neg E(x)) \rightarrow G(x))

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Translating Quantified Statements

Practice Translating Quantified Statements 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 Translating Quantified Statements, 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

$\forall x ((P(x) \land G(x)) \rightarrow \neg E(x))$ (correct answer)
$\neg \exists x (P(x) \land G(x) \land E(x))$
$\forall x (P(x) \rightarrow (G(x) \rightarrow \neg E(x)))$
$\forall x ((P(x) \land \neg E(x)) \rightarrow G(x))$

Explanation: "No prime number greater than 2 is even" means that for all numbers, if they are prime and greater than 2, then they are not even. This is captured by

\forall x ((P(x) \land G(x)) \rightarrow \neg E(x))

. Choice B (

\neg \exists x (P(x) \land G(x) \land E(x))

) is logically equivalent by De Morgan's laws but choice A more directly follows the conditional structure of the statement. Choice C has unnecessary nested implications. Choice D reverses the logical relationship entirely.

Question 2

A theorem states: "For every positive integer n, there exists a prime number p such that n < p < 2n." Let $N(x)$ denote " $x$ is a positive integer," $P(y)$ denote " $y$ is a prime number," and $B(x,y,z)$ denote " $x < y < z$ ." Which translation correctly formalizes this theorem?

$\forall x(N(x) \rightarrow \exists y(P(y) \wedge B(x,y,2x)))$ (correct answer)
$\forall x\exists y(N(x) \wedge P(y) \wedge B(x,y,2x))$
$\exists x(N(x) \rightarrow \exists y(P(y) \wedge B(x,y,2x)))$
$\forall x(N(x) \rightarrow \forall y(P(y) \rightarrow B(x,y,2x)))$

Explanation: The theorem has the form "for every positive integer n" (∀x with condition N(x)) followed by "there exists a prime p" (∃y with condition P(y)) such that the relationship n < p < 2n holds (B(x,y,2x)). This requires the implication structure ∀x(N(x) → ...) since the claim only applies to positive integers. Choice B removes the implication structure, making the claim about all x regardless of whether x is a positive integer. Choice C weakens the claim to only some positive integer rather than every positive integer. Choice D incorrectly uses ∀y, requiring every prime to satisfy the inequality for each n, rather than just requiring the existence of one such prime.

Question 3

Consider the statement: "Every student in the class has read at least one book that every professor in the department has recommended." Let $S(x)$ denote " $x$ is a student in the class," $P(y)$ denote " $y$ is a professor in the department," $R(x,z)$ denote " $x$ has read book $z$ ," and $Q(y,z)$ denote " $y$ has recommended book $z$ ." Which predicate logic expression correctly translates this statement?

$\forall x(S(x) \rightarrow \exists z(R(x,z) \wedge \forall y(P(y) \rightarrow Q(y,z))))$ (correct answer)
$\forall x(S(x) \rightarrow \forall z(R(x,z) \rightarrow \forall y(P(y) \rightarrow Q(y,z))))$
$\exists x(S(x) \wedge \exists z(R(x,z) \wedge \forall y(P(y) \rightarrow Q(y,z))))$
$\forall x(S(x) \rightarrow \forall y(P(y) \rightarrow \exists z(R(x,z) \wedge Q(y,z))))$

Explanation: The statement means for every student, there exists at least one book such that the student has read it AND every professor has recommended it. This requires: ∀x(S(x) → ...) for "every student," ∃z for "at least one book," R(x,z) for the student reading that book, and ∀y(P(y) → Q(y,z)) for every professor recommending that same book. Choice B incorrectly uses ∀z (every book) instead of ∃z (at least one book). Choice C uses ∃x (some student) instead of ∀x (every student). Choice D incorrectly quantifies over professors first, changing the meaning to each student-professor pair having some book in common.

Question 4

Consider the statement: "Every student has submitted at least one assignment that received feedback from all teaching assistants." Let $S(x)$ denote " $x$ is a student," $A(y)$ denote " $y$ is an assignment," $T(z)$ denote " $z$ is a teaching assistant," $U(x,y)$ denote "student $x$ submitted assignment $y$ ," and $F(z,y)$ denote "teaching assistant $z$ gave feedback on assignment $y$ ." Which predicate logic expression correctly translates this statement?

$\exists x(S(x) \wedge \exists y(A(y) \wedge U(x,y) \wedge \forall z(T(z) \rightarrow F(z,y))))$
$\forall x(S(x) \rightarrow \forall y(A(y) \rightarrow (U(x,y) \rightarrow \forall z(T(z) \rightarrow F(z,y)))))$
$\forall x(S(x) \rightarrow \exists y(A(y) \wedge U(x,y) \wedge \forall z(T(z) \rightarrow F(z,y))))$ (correct answer)
$\forall x(S(x) \rightarrow \exists y(A(y) \wedge U(x,y) \wedge \exists z(T(z) \wedge F(z,y))))$

Explanation: When translating natural language statements into predicate logic, you need to carefully identify the scope and structure of quantifiers. The key is recognizing what "every," "at least one," and "all" refer to in the original statement. The statement "Every student has submitted at least one assignment that received feedback from all teaching assistants" breaks down as follows: For every student (∀x), there exists at least one assignment (∃y) that the student submitted, and this assignment received feedback from all teaching assistants (∀z). This translates to:

\forall x(S(x) \rightarrow \exists y(A(y) \wedge U(x,y) \wedge \forall z(T(z) \rightarrow F(z,y))))

Option C correctly captures this structure. The universal quantifier ∀x ensures we're talking about every student, the existential quantifier ∃y captures "at least one assignment," and the universal quantifier ∀z ensures all teaching assistants gave feedback. Option A incorrectly uses ∃x, which would mean "there exists some student" rather than "every student." Option B uses ∀y instead of ∃y, meaning every assignment the student submitted received feedback from all TAs, which is much stronger than the original statement requiring only one such assignment. Option D uses ∃z instead of ∀z, meaning the assignment received feedback from at least one TA rather than all TAs. Remember: "Every" typically translates to ∀, "at least one" to ∃, and pay close attention to the scope of each quantifier. Practice breaking down complex statements into their logical components before writing the formal expression.

Question 5

Consider the statement: "For every positive real number, there exists a rational number that approximates it within any given tolerance." Let $R(x)$ denote " $x$ is a positive real number," $Q(y)$ denote " $y$ is a rational number," $T(ε)$ denote " $ε$ is a positive tolerance," and $W(x,y,ε)$ denote "rational number $y$ approximates real number $x$ within tolerance $ε$ ." Which translation correctly captures this mathematical principle?

$\forall x(R(x) \rightarrow \exists y(Q(y) \wedge \forall ε(T(ε) \rightarrow W(x,y,ε))))$
$\forall x(R(x) \rightarrow \forall ε(T(ε) \rightarrow \exists y(Q(y) \wedge W(x,y,ε))))$ (correct answer)
$\exists x(R(x) \wedge \forall ε(T(ε) \rightarrow \exists y(Q(y) \wedge W(x,y,ε))))$
$\forall x\forall ε(R(x) \wedge T(ε) \rightarrow \exists y(Q(y) \wedge W(x,y,ε)))$

Explanation: When translating complex mathematical statements into logical formulas, you need to carefully identify the scope and order of quantifiers. This statement expresses the density of rational numbers in real numbers - a fundamental property meaning rationals can get arbitrarily close to any real number. The key insight is understanding what "within any given tolerance" means logically. The statement says that for every positive real number, no matter what tolerance you choose, there exists a rational number that approximates it within that tolerance. This creates a dependency: the choice of rational number depends on both the real number AND the specific tolerance. Answer B correctly captures this with the quantifier order

\forall x(R(x) \rightarrow \forall ε(T(ε) \rightarrow \exists y(Q(y) \wedge W(x,y,ε))))

. It says: for every positive real

x

, and for every tolerance

ε

, there exists a rational

y

that works. Answer A incorrectly places

\exists y

before

\forall ε

, suggesting one rational number works for ALL tolerances simultaneously - which is impossible since we can always choose smaller tolerances. Answer C uses

\exists x

instead of

\forall x

, claiming the property holds for only some positive real numbers rather than all of them. Answer D restructures the quantifiers as

\forall x\forall ε

, which changes the logical dependency structure and doesn't properly nest the tolerance condition within the real number condition. Study tip: In quantifier problems, pay close attention to dependencies - when one variable's choice depends on another's value, the dependent variable's quantifier must come after (have smaller scope than) the independent variable's quantifier.

Question 6

Consider the statement: "No student failed every exam, but every exam was failed by at least one student." Let $S(x)$ denote " $x$ is a student," $E(y)$ denote " $y$ is an exam," and $F(x,y)$ denote "student $x$ failed exam $y$ ." Which predicate logic expression correctly translates this compound statement?

$\neg\exists x(S(x) \wedge \forall y(E(y) \rightarrow F(x,y))) \wedge \forall y(E(y) \rightarrow \exists x(S(x) \wedge F(x,y)))$ (correct answer)
$\forall x(S(x) \rightarrow \neg\forall y(E(y) \rightarrow F(x,y))) \wedge \forall y(E(y) \rightarrow \exists x(S(x) \wedge F(x,y)))$
$\neg\forall x(S(x) \rightarrow \forall y(E(y) \rightarrow F(x,y))) \wedge \exists y(E(y) \wedge \forall x(S(x) \rightarrow F(x,y)))$
$\forall x\forall y((S(x) \wedge E(y)) \rightarrow \neg F(x,y)) \wedge \forall y(E(y) \rightarrow \exists x(S(x) \wedge F(x,y)))$

Explanation: "No student failed every exam" means there does not exist a student who failed all exams: ¬∃x(S(x) ∧ ∀y(E(y) → F(x,y))). "Every exam was failed by at least one student" means ∀y(E(y) → ∃x(S(x) ∧ F(x,y))). These are connected by "but" (logical AND). Choice B uses ∀x...¬∀y instead of ¬∃x...∀y, which is logically equivalent but doesn't match the direct translation. Choice C incorrectly translates the second part as ∃y...∀x (some exam failed by all students) instead of ∀y...∃x. Choice D contradicts itself by saying no student-exam pairs involve failure, then saying every exam has failures.

Question 7

A network security policy states: "Every user who can access sensitive data must be authenticated by all security protocols." Let $U(x)$ denote " $x$ is a user," $A(x,y)$ denote " $x$ can access data $y$ ," $S(y)$ denote "data $y$ is sensitive," $T(x,z)$ denote " $x$ is authenticated by protocol $z$ ," and $P(z)$ denote " $z$ is a security protocol." Which translation correctly formalizes this policy?

$\exists x(U(x) \wedge \exists y(A(x,y) \wedge S(y)) \wedge \forall z(P(z) \rightarrow T(x,z)))$
$\forall x(U(x) \rightarrow \forall y((A(x,y) \wedge S(y)) \rightarrow \forall z(P(z) \rightarrow T(x,z))))$
$\forall x\forall y\forall z((U(x) \wedge A(x,y) \wedge S(y) \wedge P(z)) \rightarrow T(x,z))$
$\forall x(U(x) \rightarrow (\exists y(A(x,y) \wedge S(y)) \rightarrow \forall z(P(z) \rightarrow T(x,z))))$ (correct answer)

Explanation: When translating English statements into predicate logic, you need to carefully identify the scope and structure of quantifiers. This policy creates a conditional relationship: IF a user can access sensitive data, THEN they must be authenticated by all security protocols. The correct translation is D because it properly captures the logical structure. It states: "For every user

x

, if

x

is a user, then (if there exists some sensitive data

y

that

x

can access, then

x

must be authenticated by every security protocol

z

)." This creates the right conditional chain: user → (can access sensitive data → authenticated by all protocols). Option A is wrong because it uses

\exists x

instead of

\forall x

. The policy applies to ALL users who meet the condition, not just asserting that SOME user exists with these properties. Option B incorrectly uses

\forall y

in the middle quantifier. This would mean "for ALL data

y

, if the user can access

y

and

y

is sensitive..." But the policy should trigger when a user can access ANY sensitive data, not require them to access ALL sensitive data. Option C uses all universal quantifiers and creates an unnecessarily complex structure. While logically equivalent in some interpretations, it doesn't capture the natural conditional flow of the English statement and makes the relationship between accessing sensitive data and authentication less clear. Remember: when translating conditional policies, identify what triggers the requirement (accessing sensitive data) and what the consequence must be (authentication by all protocols). Use

\exists

for the trigger condition and

\forall

for universal requirements.

Question 8

Consider the statement: "Each team has at least one player who has scored in every game the team has played." Let $T(x)$ denote " $x$ is a team," $L(y)$ denote " $y$ is a player," $G(z)$ denote " $z$ is a game," $M(y,x)$ denote "player $y$ is on team $x$ ," $P(x,z)$ denote "team $x$ played game $z$ ," and $S(y,z)$ denote "player $y$ scored in game $z$ ." Which predicate logic expression correctly formalizes this statement?

$\forall x(T(x) \rightarrow \forall y(L(y) \rightarrow (M(y,x) \rightarrow \forall z(G(z) \rightarrow (P(x,z) \rightarrow S(y,z))))))$
$\forall x(T(x) \rightarrow \exists y(L(y) \wedge M(y,x) \wedge \forall z(G(z) \rightarrow (P(x,z) \rightarrow S(y,z)))))$ (correct answer)
$\exists x(T(x) \wedge \exists y(L(y) \wedge M(y,x) \wedge \forall z(G(z) \rightarrow (P(x,z) \rightarrow S(y,z)))))$
$\forall x(T(x) \rightarrow \exists y(L(y) \wedge M(y,x) \wedge \exists z(G(z) \wedge P(x,z) \wedge S(y,z))))$

Explanation: When translating English statements into predicate logic, you need to carefully identify the quantifier structure and logical relationships. The key phrase here is "each team has at least one player" - this signals a universal quantifier for teams followed by an existential quantifier for players. Let's break down the statement systematically. "Each team" requires

\forall x(T(x) \rightarrow ...)

. The phrase "has at least one player" means there exists a player on that team, so we need

\exists y(L(y) \wedge M(y,x) \wedge ...)

. The crucial part is "who has scored in every game the team has played" - this specific player must score in all games that their team played, requiring

\forall z(G(z) \rightarrow (P(x,z) \rightarrow S(y,z)))

. Option B correctly captures this structure:

\forall x(T(x) \rightarrow \exists y(L(y) \wedge M(y,x) \wedge \forall z(G(z) \rightarrow (P(x,z) \rightarrow S(y,z)))))

. Option A uses

\forall y

instead of

\exists y

, incorrectly claiming that every player on every team scores in every game. Option C starts with

\exists x

, limiting the statement to just one team rather than all teams. Option D uses

\exists z

in the innermost part, requiring only that the player scored in at least one game rather than every game the team played. Remember: "each" typically translates to universal quantification, while "at least one" signals existential quantification. Pay close attention to scope - nested quantifiers must maintain the correct logical relationships throughout the formula.

Question 9

Consider the mathematical statement: "For any real number, if it is positive, then there exists a smaller positive real number." Let $R(x)$ denote " $x$ is a real number," $P(x)$ denote " $x$ is positive," and $L(x,y)$ denote " $x < y$ ." Which predicate logic expression correctly formalizes this statement?

$\forall x((R(x) \wedge P(x)) \rightarrow \exists y(R(y) \wedge P(y) \wedge L(y,x)))$ (correct answer)
$\forall x(R(x) \rightarrow (P(x) \rightarrow \exists y(R(y) \wedge P(y) \wedge L(x,y))))$
$\exists x((R(x) \wedge P(x)) \rightarrow \exists y(R(y) \wedge P(y) \wedge L(y,x)))$
$\forall x(R(x) \rightarrow \exists y((P(x) \wedge R(y) \wedge P(y)) \rightarrow L(y,x)))$

Explanation: The statement has the form "for any real number x, if x is positive, then there exists a smaller positive real number y." This requires ∀x for "any real number," the condition (R(x) ∧ P(x)) for "if it is positive," and the conclusion ∃y(R(y) ∧ P(y) ∧ L(y,x)) for "there exists a smaller positive real number." Choice B incorrectly uses L(x,y) instead of L(y,x), meaning x < y rather than y < x. Choice C uses ∃x instead of ∀x, weakening the claim to only some positive real numbers. Choice D has malformed logic with the implication inside the existential quantifier, changing the meaning entirely.

Question 10

Consider the statement: "Every committee has at least one member who serves on all subcommittees of that committee." Let $C(x)$ denote " $x$ is a committee," $M(y)$ denote " $y$ is a member," $S(z,x)$ denote " $z$ is a subcommittee of $x$ ," $O(y,x)$ denote " $y$ serves on committee $x$ ," and $O(y,z)$ denote " $y$ serves on subcommittee $z$ ." Which predicate logic expression correctly captures this statement?

$\forall x(C(x) \rightarrow \exists y(M(y) \wedge \forall z(S(z,x) \rightarrow (O(y,x) \wedge O(y,z)))))$
$\forall x(C(x) \rightarrow \forall y(M(y) \rightarrow (O(y,x) \rightarrow \forall z(S(z,x) \rightarrow O(y,z)))))$
$\exists x(C(x) \wedge \exists y(M(y) \wedge O(y,x) \wedge \forall z(S(z,x) \rightarrow O(y,z))))$
$\forall x(C(x) \rightarrow \exists y(M(y) \wedge O(y,x) \wedge \forall z(S(z,x) \rightarrow O(y,z))))$ (correct answer)

Explanation: When translating natural language statements into predicate logic, you need to carefully identify the scope and order of quantifiers while preserving the logical structure of the original statement. The given statement says "Every committee has at least one member who serves on all subcommittees of that committee." Let's break this down systematically. The statement begins with "every committee," indicating we need

\forall x(C(x) \rightarrow ...)

. Next, "has at least one member" requires an existential quantifier

\exists y(M(y) \wedge ...)

. This member must serve on the committee itself, so we need

O(y,x)

. Finally, this member serves on "all subcommittees," requiring

\forall z(S(z,x) \rightarrow O(y,z))

. Option D correctly captures this structure:

\forall x(C(x) \rightarrow \exists y(M(y) \wedge O(y,x) \wedge \forall z(S(z,x) \rightarrow O(y,z))))

. It states that for every committee, there exists a member who serves on that committee and serves on all of its subcommittees. Option A is missing the crucial requirement

O(y,x)

that the special member must serve on the original committee. Option B incorrectly uses universal quantification for the member (

\forall y

), claiming every member has this property, rather than asserting at least one such member exists. Option C uses existential quantification for the committee (

\exists x

), which would only claim some committee has this property, not that every committee does. Remember: When translating "every...has at least one," start with universal quantification, then use existential quantification for the "at least one" part. Pay attention to the logical dependencies between quantifiers.

Question 11

A database query needs to express: "There exists a customer who has placed orders for all products in category X." Let $C(x)$ denote " $x$ is a customer," $O(x,y)$ denote "customer $x$ has placed an order for product $y$ ," and $X(y)$ denote "product $y$ is in category X." Which translation captures the intended meaning most precisely?

$\exists x(C(x) \wedge \forall y(X(y) \rightarrow O(x,y)))$ (correct answer)
$\exists x(C(x) \wedge \exists y(X(y) \wedge O(x,y)))$
$\forall x(C(x) \rightarrow \forall y(X(y) \rightarrow O(x,y)))$
$\exists x\exists y(C(x) \wedge X(y) \wedge O(x,y))$

Explanation: The statement requires there to exist at least one customer who has ordered ALL products in category X. This needs ∃x for "there exists a customer" and ∀y(X(y) → O(x,y)) meaning "for all products in category X, this customer has ordered them." Choice B only requires the customer to have ordered at least one product in category X (∃y instead of ∀y). Choice C requires ALL customers to have ordered all products in category X (∀x instead of ∃x). Choice D only requires some customer to have ordered some product in category X, which is much weaker than the original statement.

Question 12

A mathematical definition states: "A function f is continuous if for every point in its domain, and for every ε > 0, there exists a δ > 0 such that the function value changes by less than ε whenever the input changes by less than δ." Let $D(x,f)$ denote " $x$ is in the domain of $f$ ," $P(ε)$ denote " $ε > 0$ ," and $C(x,f,ε,δ)$ denote "for input changes less than $δ$ at $x$ , function $f$ changes by less than $ε$ ." Which translation captures the logical structure of continuity?

$\exists x(D(x,f) \wedge \forall ε(P(ε) \rightarrow \exists δ(P(δ) \wedge C(x,f,ε,δ))))$
$\forall x\forall ε(D(x,f) \wedge P(ε) \rightarrow \exists δ(P(δ) \wedge C(x,f,ε,δ)))$
$\forall x(D(x,f) \rightarrow \forall ε(P(ε) \rightarrow \exists δ(P(δ) \wedge C(x,f,ε,δ))))$ (correct answer)
$\forall x(D(x,f) \rightarrow \exists ε(P(ε) \wedge \forall δ(P(δ) \rightarrow C(x,f,ε,δ))))$

Explanation: When translating mathematical definitions into logical notation, you need to carefully identify the quantifier structure and how conditions relate to each other. Mathematical continuity has a specific logical pattern: it's a universal property that must hold for ALL points in the domain, and for EACH of those points, it must work for EVERY possible epsilon value. The definition states continuity requires three nested conditions: for every domain point x, and for every ε > 0, there must exist some δ > 0 with the desired property. This creates a

\forall x \rightarrow \forall ε \rightarrow \exists δ

structure. The correct translation is C:

\forall x(D(x,f) \rightarrow \forall ε(P(ε) \rightarrow \exists δ(P(δ) \wedge C(x,f,ε,δ))))

. This properly captures that for every x in the domain, and for every positive ε, there exists a suitable δ. Option A incorrectly uses

\exists x

at the start, meaning continuity would only require the property to hold at some point rather than all points. Option B restructures the quantifiers as

\forall x \forall ε

, which changes the logical dependency—it doesn't properly nest the ε condition within each x case. Option D swaps the roles of ε and δ, claiming there exists some ε such that for all δ the property holds, which completely reverses the mathematical meaning. Remember: when translating nested mathematical conditions, pay close attention to the quantifier order (∀ vs ∃) and how implications should be structured. Universal properties like continuity typically start with "for all" quantifiers before introducing existential claims.

Question 13

A software specification states: "Every user can access some file, and every file can be accessed by some user." Let $U(x)$ denote " $x$ is a user," $F(y)$ denote " $y$ is a file," and $A(x,y)$ denote "user $x$ can access file $y$ ." Which logical expression correctly captures both parts of this specification?

$\forall x(U(x) \rightarrow \exists y(F(y) \wedge A(x,y))) \wedge \forall y(F(y) \rightarrow \exists x(U(x) \wedge A(x,y)))$ (correct answer)
$\forall x\forall y((U(x) \wedge F(y)) \rightarrow A(x,y))$
$\exists x\exists y(U(x) \wedge F(y) \wedge A(x,y))$
$\forall x(U(x) \rightarrow \exists y(F(y) \wedge A(x,y))) \vee \forall y(F(y) \rightarrow \exists x(U(x) \wedge A(x,y)))$

Explanation: The specification contains two separate requirements connected by "and": (1) every user can access some file, and (2) every file can be accessed by some user. The first part translates to ∀x(U(x) → ∃y(F(y) ∧ A(x,y))) and the second to ∀y(F(y) → ∃x(U(x) ∧ A(x,y))). These must be joined with ∧ since both conditions must hold. Choice B requires every user to access every file, which is much stronger. Choice C only requires the existence of one user-file pair with access. Choice D uses ∨ instead of ∧, meaning only one of the two conditions needs to be satisfied rather than both.

Question 14

Consider the statement: "There is no course that is a prerequisite for all other courses." Let $C(x)$ denote " $x$ is a course" and $R(x,y)$ denote "course $x$ is a prerequisite for course $y$ ." Which predicate logic expression correctly translates this negation?

$\forall x\forall y((C(x) \wedge C(y) \wedge x \neq y) \rightarrow \neg R(x,y))$
$\forall x(C(x) \rightarrow \neg\forall y((C(y) \wedge x \neq y) \rightarrow R(x,y)))$
$\neg\forall x(C(x) \rightarrow \forall y((C(y) \wedge x \neq y) \rightarrow R(x,y)))$
$\neg\exists x(C(x) \wedge \forall y((C(y) \wedge x \neq y) \rightarrow R(x,y)))$ (correct answer)

Explanation: When translating natural language statements into predicate logic, you need to carefully identify the logical structure, especially with negations. The original statement "There is no course that is a prerequisite for all other courses" is already a negation of "There exists a course that is a prerequisite for all other courses." Let's first translate the positive statement: "There exists a course that is a prerequisite for all other courses." This means:

\exists x(C(x) \wedge \forall y((C(y) \wedge x \neq y) \rightarrow R(x,y)))

. Breaking this down: there exists some course

x

, and for all other courses

y

, if

y

is a course different from

x

, then

x

is a prerequisite for

y

. Since our original statement negates this, we simply add

\neg

to the front:

\neg\exists x(C(x) \wedge \forall y((C(y) \wedge x \neq y) \rightarrow R(x,y)))

, which is answer D. Looking at the wrong answers: A incorrectly states that no course is ever a prerequisite for any other course, which is much stronger than the original statement. B uses

\forall x

with an internal negation, creating a confusing double structure that doesn't match the original meaning. C starts with the right approach but uses

\forall x

instead of

\exists x

in the expression being negated, changing the fundamental meaning. Remember: when translating negations, first write out the positive statement clearly in predicate logic, then apply the negation operator. This systematic approach prevents errors in complex logical structures.

Question 15

A social network analysis requires formalizing: "Every person is connected to someone who knows everyone that person knows." Let $P(x)$ denote " $x$ is a person," $C(x,y)$ denote "person $x$ is connected to person $y$ ," and $K(x,y)$ denote "person $x$ knows person $y$ ." Which predicate logic expression correctly translates this relationship?

$\forall x(P(x) \rightarrow \exists y(P(y) \wedge C(x,y) \wedge \forall z(P(z) \rightarrow (K(y,z) \rightarrow K(x,z)))))$
$\forall x(P(x) \rightarrow \exists y(P(y) \wedge C(x,y) \wedge \forall z(P(z) \rightarrow (K(x,z) \rightarrow K(y,z)))))$ (correct answer)
$\exists x(P(x) \wedge \exists y(P(y) \wedge C(x,y) \wedge \forall z(P(z) \rightarrow (K(x,z) \rightarrow K(y,z)))))$
$\forall x(P(x) \rightarrow \forall y(P(y) \rightarrow (C(x,y) \rightarrow \forall z(P(z) \rightarrow (K(x,z) \rightarrow K(y,z))))))$

Explanation: When translating English statements into predicate logic, you need to carefully parse the logical structure and quantifier scope. The statement "Every person is connected to someone who knows everyone that person knows" has a specific hierarchical structure: for each person, there exists a connected person with a particular knowledge property. The correct translation is option B:

\forall x(P(x) \rightarrow \exists y(P(y) \wedge C(x,y) \wedge \forall z(P(z) \rightarrow (K(x,z) \rightarrow K(y,z)))))

. This reads: "For every person x, there exists a person y such that x is connected to y, and for all persons z, if x knows z, then y also knows z." The critical part is the final implication

K(x,z) \rightarrow K(y,z)

, which captures "y knows everyone that x knows." Option A reverses the knowledge relationship to

K(y,z) \rightarrow K(x,z)

, making x know everyone that y knows—the opposite of what we want. Option C uses existential quantification (

\exists x

) instead of universal (

\forall x

), claiming only some person has this property rather than every person. Option D uses

\forall y

instead of

\exists y

, requiring that every person y connected to x must have this knowledge property, which is much stronger than the original statement requiring only that some such person exists. Pay special attention to the direction of implications in knowledge relationships and whether quantifiers are universal or existential—these details completely change the meaning of social network properties.

Question 16

A quality control specification states: "No defective part passes all inspection stages." Let $P(x)$ denote " $x$ is a part," $D(x)$ denote " $x$ is defective," $I(y)$ denote " $y$ is an inspection stage," and $A(x,y)$ denote "part $x$ passes inspection stage $y$ ." Which predicate logic expression correctly formalizes this specification?

$\forall x\forall y((P(x) \wedge D(x) \wedge I(y)) \rightarrow \neg A(x,y))$
$\forall x((P(x) \wedge D(x)) \rightarrow \neg\forall y(I(y) \rightarrow A(x,y)))$
$\neg\exists x(P(x) \wedge D(x) \wedge \forall y(I(y) \rightarrow A(x,y)))$ (correct answer)
$\neg\forall x((P(x) \wedge D(x)) \rightarrow \forall y(I(y) \rightarrow A(x,y)))$

Explanation: When translating natural language statements into predicate logic, you need to carefully analyze what the statement is actually claiming and what would make it false. The statement "No defective part passes all inspection stages" means that there does not exist any part that is both defective AND passes every single inspection stage. To formalize this, you need to express "passes all inspection stages" as

\forall y(I(y) \rightarrow A(x,y))

- meaning for every inspection stage y, the part x passes it. Option C correctly captures this:

\neg\exists x(P(x) \wedge D(x) \wedge \forall y(I(y) \rightarrow A(x,y)))

. This says "there does not exist a part x such that x is a part AND x is defective AND x passes all inspection stages" - which perfectly matches our specification. Option A is wrong because it says defective parts cannot pass ANY inspection stage, which is much stronger than the original statement. The specification allows defective parts to pass some stages, just not all of them. Option B incorrectly uses

\neg\forall y

which is equivalent to

\exists y \neg

, meaning there exists some stage the defective part doesn't pass. This actually contradicts our specification. Option D creates a logical contradiction by negating a universal statement about what should happen to defective parts, making it unnecessarily complex and incorrect. Remember: when you see "no" statements in logic problems, they typically translate to negated existential quantifiers (

\neg\exists

). Also, "all" in natural language usually becomes universal quantification (

\forall

) in the formalization.

Question 17

Consider the statement: "Among all the books in the library, there are some that every student has read, and every student has read some book." Let $B(x)$ = " $x$ is a book in the library", $S(y)$ = " $y$ is a student", and $R(y,x)$ = "student $y$ has read book $x$ ". Which translation correctly captures both parts of this statement?

$\exists x (B(x) \land \forall y (S(y) \land R(y,x))) \land \forall y (S(y) \land \exists x (B(x) \land R(y,x)))$
$\forall y (S(y) \rightarrow \exists x (B(x) \land R(y,x))) \land \exists x (B(x) \land \forall y (S(y) \rightarrow R(y,x)))$
$\exists x \forall y ((B(x) \land S(y)) \rightarrow R(y,x)) \land \forall y \exists x ((S(y) \land B(x)) \rightarrow R(y,x))$
$\exists x (B(x) \land \forall y (S(y) \rightarrow R(y,x))) \land \forall y (S(y) \rightarrow \exists x (B(x) \land R(y,x)))$ (correct answer)

Explanation: When translating complex English statements into predicate logic, you need to carefully parse each component and identify the logical structure. This statement has two distinct parts connected by "and": (1) there exist books that every student has read, and (2) every student has read at least some book. For the first part, "there are some [books] that every student has read," you need an existential quantifier for books followed by a universal quantifier for students:

\exists x (B(x) \land \forall y (S(y) \rightarrow R(y,x)))

. This says "there exists a book such that for all students, if someone is a student, then they've read that book." For the second part, "every student has read some book," you need a universal quantifier for students followed by an existential quantifier for books:

\forall y (S(y) \rightarrow \exists x (B(x) \land R(y,x)))

. This says "for every student, there exists some book they've read." Answer D correctly combines both parts with proper implication structure (

\rightarrow

) rather than conjunction (

\land

) within the quantified statements. Answer A incorrectly uses conjunction instead of implication, making the logic too restrictive. Answer B reverses the order of the two parts and has structural issues. Answer C uses improper conditional structures that don't capture the intended meaning—the conditions should apply to the domain restrictions, not the entire relationships. Remember: when translating between quantifiers and domain predicates, use implications (

\rightarrow

) for universal statements and conjunctions (

\land

) for existential statements to properly restrict your domains.

Question 18

Consider the statement: "Anyone who completes all assignments and scores above 85 on every exam will receive an A, unless they miss more than two classes." Let $P(x)$ = " $x$ is a person", $C(x)$ = " $x$ completes all assignments", $S(x)$ = " $x$ scores above 85 on every exam", $M(x)$ = " $x$ misses more than two classes", and $A(x)$ = " $x$ receives an A". Which translation is correct?

$\forall x (P(x) \rightarrow ((C(x) \land S(x) \land \neg M(x)) \rightarrow A(x)))$ (correct answer)
$\forall x ((P(x) \land C(x) \land S(x)) \rightarrow (A(x) \lor M(x)))$
$\forall x (P(x) \rightarrow ((C(x) \land S(x)) \rightarrow (A(x) \lor M(x))))$
$\forall x ((P(x) \land C(x) \land S(x) \land \neg M(x)) \rightarrow A(x))$

Explanation: The statement says that completing assignments AND scoring above 85 on every exam will result in an A, UNLESS the person misses more than two classes. The "unless" clause means the person must NOT miss more than two classes for the guarantee to hold. So: for any person, if they complete all assignments AND score above 85 AND don't miss more than two classes, then they get an A. This is

\forall x (P(x) \rightarrow ((C(x) \land S(x) \land \neg M(x)) \rightarrow A(x)))

. Choice B incorrectly uses disjunction. Choice C misplaces the negation. Choice D doesn't properly restrict to persons first.

Question 19

Consider the statement: "Every student who studies discrete mathematics and attends all lectures will pass the final exam." Let $S(x)$ = " $x$ is a student", $D(x)$ = " $x$ studies discrete mathematics", $A(x)$ = " $x$ attends all lectures", and $P(x)$ = " $x$ passes the final exam". Which predicate logic translation correctly captures the original statement?

$\forall x ((S(x) \land D(x) \land A(x)) \rightarrow P(x))$
$\forall x (S(x) \rightarrow ((D(x) \land A(x)) \rightarrow P(x)))$ (correct answer)
$\forall x ((D(x) \land A(x)) \rightarrow (S(x) \rightarrow P(x)))$
$\forall x (S(x) \rightarrow (D(x) \land A(x) \land P(x)))$

Explanation: The original statement is about students specifically, so we need to restrict the domain to students first:

\forall x (S(x) \rightarrow ...)

. Then, for those who are students, if they study discrete math AND attend all lectures, they will pass. This gives us

\forall x (S(x) \rightarrow ((D(x) \land A(x)) \rightarrow P(x)))

. Choice A treats non-students the same as students by not properly restricting the domain. Choice C incorrectly places the student condition inside the consequent. Choice D incorrectly states that all students must study discrete math, attend lectures, and pass.

Question 20

Consider the statement: "Every integer is either even or odd, but not both." Let $I(x)$ = " $x$ is an integer", $E(x)$ = " $x$ is even", and $O(x)$ = " $x$ is odd". Which predicate logic translation most explicitly shows both the inclusive disjunction and the mutual exclusion?

$\forall x ((I(x) \land E(x)) \lor (I(x) \land O(x)))$
$\forall x (I(x) \rightarrow (E(x) \oplus O(x)))$
$\forall x (I(x) \rightarrow ((E(x) \lor O(x)) \land \neg(E(x) \land O(x))))$ (correct answer)
$\forall x (I(x) \rightarrow ((E(x) \land \neg O(x)) \lor (O(x) \land \neg E(x))))$

Explanation: When translating complex logical statements into predicate logic, you need to identify all the logical components and represent them explicitly. The statement "Every integer is either even or odd, but not both" contains three key parts: a universal quantifier over integers, an inclusive disjunction (either/or), and mutual exclusion (but not both). The correct translation in option C captures all three components perfectly:

\forall x (I(x) \rightarrow ((E(x) \lor O(x)) \land \neg(E(x) \land O(x))))

. The structure

I(x) \rightarrow

establishes that this applies to all integers. The term

(E(x) \lor O(x))

explicitly shows the inclusive disjunction - every integer is even OR odd. The term

\neg(E(x) \land O(x))

explicitly shows mutual exclusion - no integer is both even AND odd simultaneously. Option A fails because it uses conjunction instead of implication, creating a statement that requires every x to be an integer AND either even or odd, rather than saying that IF x is an integer, THEN it has these properties. Option B uses exclusive or (

\oplus

), which technically captures the meaning but doesn't explicitly show both components as requested - the inclusive disjunction and mutual exclusion are combined into one operator rather than being separately visible. Option D is unnecessarily complex and redundant. While logically equivalent, it doesn't clearly separate the "either/or" from the "not both" aspects. Study tip: When translating "either...or, but not both" statements, look for answers that explicitly show

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

rather than just using exclusive or.