Translate quantified statements (∀, ∃) into predicate logic - Discrete Math

1. 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?
   Answer: $\forall x(C(x) \rightarrow \exists y(M(y) \wedge O(y,x) \wedge \forall z(S(z,x) \rightarrow O(y,z))))$ 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.
2. 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?
   Answer: $\neg\exists x(P(x) \wedge D(x) \wedge \forall y(I(y) \rightarrow A(x,y)))$ 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.
3. 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?
   Answer: $\forall x(S(x) \rightarrow \exists y(A(y) \wedge U(x,y) \wedge \forall z(T(z) \rightarrow F(z,y))))$ 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.
4. 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?
   Answer: $\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)))$ "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.
5. A database administrator claims: "Every user who has both read and write permissions can access all confidential files." However, the actual system behavior is: "Every user can access some confidential file, provided they have both read and write permissions." Let $U(x)$ = "$x$ is a user", $R(x)$ = "$x$ has read permissions", $W(x)$ = "$x$ has write permissions", $F(y)$ = "$y$ is a confidential file", and $A(x,y)$ = "user $x$ can access file $y$". Which pair correctly represents the claimed vs. actual behavior?
   Answer: Claimed: $\forall x ((U(x) \land R(x) \land W(x)) \rightarrow \forall y (F(y) \rightarrow A(x,y)))$; Actual: $\forall x ((U(x) \land R(x) \land W(x)) \rightarrow \exists y (F(y) \land A(x,y)))$ The claimed behavior says every qualified user can access ALL confidential files: $\forall x$ (for every user with read+write permissions) $\rightarrow \forall y (F(y) \rightarrow A(x,y))$ (they can access every confidential file). The actual behavior says every qualified user can access SOME confidential file: the same antecedent but $\rightarrow \exists y (F(y) \land A(x,y))$. Choice B has incorrect quantifier placement. Choice C unnecessarily restricts to users first. Choice D uses existential quantification for users, changing the meaning entirely.
6. A computer science professor states: "There exists a programming language such that for every algorithm, that algorithm can be efficiently implemented in that language." Let $L(x)$ = "$x$ is a programming language", $A(y)$ = "$y$ is an algorithm", and $E(y,x)$ = "algorithm $y$ can be efficiently implemented in language $x$". Which translation is correct?
   Answer: $\exists x (L(x) \land \forall y (A(y) \rightarrow E(y,x)))$ The statement claims there exists ONE specific programming language that can efficiently implement ALL algorithms. This means: $\exists x$ (there exists a language $x$) such that $L(x)$ ($x$ is a programming language) and $\forall y (A(y) \rightarrow E(y,x))$ (for every algorithm $y$, $y$ can be efficiently implemented in $x$). Choice B says for each algorithm there exists some language (not necessarily the same one). Choice C has incorrect operator precedence. Choice D uses implication incorrectly with the existential quantifier.
7. 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?
   Answer: $\forall x (P(x) \rightarrow ((C(x) \land S(x) \land \neg M(x)) \rightarrow A(x)))$ 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.
8. A university registration system implements the rule: "Students can enroll in advanced courses only if they have completed all prerequisites, and there exists at least one instructor qualified to teach each advanced course." Let $S(x)$ = "$x$ is a student", $A(y)$ = "$y$ is an advanced course", $E(x,y)$ = "student $x$ can enroll in course $y$", $C(x,y)$ = "student $x$ has completed all prerequisites for course $y$", $I(z)$ = "$z$ is an instructor", and $Q(z,y)$ = "instructor $z$ is qualified to teach course $y$". Which translation correctly represents this rule?
   Answer: $\forall x \forall y ((S(x) \land A(y)) \rightarrow (E(x,y) \rightarrow C(x,y))) \land \forall y (A(y) \rightarrow \exists z (I(z) \land Q(z,y)))$ When translating conditional statements from English to predicate logic, you need to carefully identify the direction of implication and distinguish between necessary and sufficient conditions. The rule states students can enroll "only if" they meet prerequisites, which means having prerequisites is necessary for enrollment. In logic, "A only if B" translates to "A → B." So enrollment implies prerequisites are completed: $E(x,y) \rightarrow C(x,y)$. The second part requires that for each advanced course, at least one qualified instructor exists. Choice D correctly captures both parts. The first component $\forall x \forall y ((S(x) \land A(y)) \rightarrow (E(x,y) \rightarrow C(x,y)))$ says: for any student and advanced course, if the student can enroll, then they must have completed prerequisites. The second part $\forall y (A(y) \rightarrow \exists z (I(z) \land Q(z,y)))$ ensures every advanced course has at least one qualified instructor. Choice A incorrectly makes enrollment imply prerequisites, but then adds a confusing condition about instructors that doesn't match the original rule. Choice B reverses the implication, making prerequisites sufficient for enrollment rather than necessary - this is too strong since the rule doesn't guarantee enrollment just from having prerequisites. Choice C uses a biconditional ($\leftrightarrow$), claiming prerequisites are both necessary and sufficient for enrollment, which again overstates the rule. Remember: "only if" creates a necessary condition, translating to an implication in the forward direction (A only if B means A → B). Don't confuse this with sufficient conditions.
9. 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?
   Answer: $\forall x ((P(x) \land G(x)) \rightarrow \neg E(x))$ "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.
10. A social media platform's privacy policy states: "All users' personal data is protected unless they explicitly consent to sharing, but there exists some user data that is always kept private regardless of consent." Let $U(x)$ = "$x$ is a user", $D(y)$ = "$y$ is personal data", $B(y,x)$ = "data $y$ belongs to user $x$", $P(y)$ = "data $y$ is protected", $C(x,y)$ = "user $x$ consents to sharing data $y$", and $A(y)$ = "data $y$ is always kept private". Which translation correctly represents this policy?
    Answer: $\forall x \forall y ((U(x) \land D(y) \land B(y,x)) \rightarrow (\neg C(x,y) \rightarrow P(y))) \land \exists y (D(y) \land A(y))$ The policy states that personal data is protected UNLESS users consent to sharing. "Unless" means "if not", so: if a user does NOT consent to sharing their data, then it is protected. This gives us: $\forall x \forall y ((U(x) \land D(y) \land B(y,x)) \rightarrow (\neg C(x,y) \rightarrow P(y)))$. The second part states some user data is always private: $\exists y (D(y) \land A(y))$. Choice A incorrectly uses disjunction. Choice B is equivalent to C but less clear about the conditional structure. Choice D adds unnecessary constraints about consent for always-private data.
11. 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?
    Answer: $\neg\exists x(C(x) \wedge \forall y((C(y) \wedge x \neq y) \rightarrow R(x,y)))$ 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.
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?
    Answer: $\forall x(D(x,f) \rightarrow \forall ε(P(ε) \rightarrow \exists δ(P(δ) \wedge C(x,f,ε,δ))))$ 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.
13. 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?
    Answer: $\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)))))$ 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.
14. 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?
    Answer: $\forall x (I(x) \rightarrow ((E(x) \lor O(x)) \land \neg(E(x) \land O(x))))$ 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.
15. 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?
    Answer: $\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)))$ 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.
16. 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?
    Answer: $\forall x (S(x) \rightarrow ((D(x) \land A(x)) \rightarrow P(x)))$ 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.
17. 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?
    Answer: $\forall x((R(x) \wedge P(x)) \rightarrow \exists y(R(y) \wedge P(y) \wedge L(y,x)))$ 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.
18. 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?
    Answer: $\forall x(R(x) \rightarrow \forall ε(T(ε) \rightarrow \exists y(Q(y) \wedge W(x,y,ε))))$ 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.
19. 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?
    Answer: $\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)))$ 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.
20. 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?
    Answer: $\forall x(N(x) \rightarrow \exists y(P(y) \wedge B(x,y,2x)))$ 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.

Start this quiz