Determine truth of quantified statements over a domain - Discrete Math

1. Let $L(x, y)$ represent "$x \leq y$" over the finite domain $\{1, 2, 3\}$. Consider the statement $N$: "$\neg(\exists x \forall y L(x, y)) \land \neg(\forall x \exists y \neg L(x, y))$". Which of the following correctly describes what $N$ asserts?
   Answer: There is no element $\leq$ everything, and not every element fails to be $\leq$ something $N$ has two conjuncts: $\neg(\exists x \forall y L(x, y))$ means "there is no $x$ such that $x \leq y$ for all $y$", i.e., "no element is $\leq$ everything." The second part $\neg(\forall x \exists y \neg L(x, y))$ means "it's not the case that for every $x$, there exists $y$ such that $x \not\leq y$", which is equivalent to "not every element fails to be $\leq$ something." Option (D) correctly captures both parts of this logical structure.
2. Let $Z(a, b)$ be the predicate "$a^2 - b^2$ is divisible by 4" where the domain for both variables is $\{1, 2, 3, 4, 5\}$. Which statement correctly describes the truth value of $\exists a \forall b \, Z(a, b)$?
   Answer: False, because no value of a makes a² - b² divisible by 4 for all values of b We need to find if there exists an 'a' such that a² - b² is divisible by 4 for ALL values of b in {1,2,3,4,5}. Note that a² - b² ≡ 0 (mod 4) means a² ≡ b² (mod 4). First, let's find the possible values of squares mod 4: 1² ≡ 1, 2² ≡ 0, 3² ≡ 1, 4² ≡ 0, 5² ≡ 1 (mod 4). So squares can only be ≡ 0 or 1 (mod 4). For any fixed a, we need a² ≡ b² (mod 4) for all b. But since b² takes both values 0 and 1 (mod 4) as b varies, and a² can only be one specific value (either 0 or 1), there's no single a that works for all b. For example, if a = 2 (so a² ≡ 0 (mod 4)), then when b = 1, we get a² - b² ≡ 0 - 1 ≡ 3 (mod 4), which is not divisible by 4.
3. Consider the predicate $U(x, y): x^2 \equiv y \pmod{5}$ where both $x$ and $y$ are from the set $\{0, 1, 2, 3, 4\}$. Determine which quantified statement is FALSE.
   Answer: $\forall y \exists x \, U(x, y)$ First, let's find the possible values of x² (mod 5): 0² ≡ 0, 1² ≡ 1, 2² ≡ 4, 3² ≡ 4, 4² ≡ 1 (mod 5). So x² can only be congruent to 0, 1, or 4 modulo 5. For option A (∀y ∃x U(x,y)): This claims that for every y, there exists an x such that x² ≡ y (mod 5). But when y = 2 or y = 3, no x satisfies x² ≡ y (mod 5) since x² can only be 0, 1, or 4 (mod 5). Therefore, this statement is false. For option B: This claims some x and y satisfy the relation, which is true (e.g., x = 0, y = 0). For option C: This claims there exists a y such that x² ≡ y (mod 5) for all x. This is false since x² takes on different values (0, 1, 4) for different x values, so no single y works for all x. For option D: This claims that for every x, there exists some y such that x² ≡ y (mod 5), which is true since we can choose y = x² mod 5.
4. Let $P(x)$ be the statement "$x^2 + 3x - 4 > 0$" and let the domain be the set of integers from $-5$ to $5$ inclusive. Which of the following statements about the quantified expressions is true?
   Answer: $\exists x P(x)$ is true and $\forall x P(x)$ is false First, solve $x^2 + 3x - 4 > 0$. Factoring: $(x+4)(x-1) > 0$. This is true when both factors have the same sign, which occurs when $x < -4$ or $x > 1$. In the domain $\{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5\}$, $P(x)$ is true for $x = -5, 2, 3, 4, 5$. Since at least one value makes $P(x)$ true, $\exists x P(x)$ is true. Since not all values make $P(x)$ true (e.g., $P(-3)$ is false), $\forall x P(x)$ is false.
5. Let $F(x, y)$ be the statement "$x^2 - y^2 = 3$" over the domain $\{-2, -1, 0, 1, 2\}$. Consider the quantified statement $V$: "$\forall x \exists y F(x, y) \lor \exists x \forall y \neg F(x, y)$". What is the truth value of $V$?
   Answer: True, because the second disjunct is true When you encounter complex quantified statements with disjunctions, break them down systematically by evaluating each part separately over the given domain. Let's analyze statement $V$: "$\forall x \exists y F(x, y) \lor \exists x \forall y \neg F(x, y)$" where $F(x, y)$ means "$x^2 - y^2 = 3$" and our domain is $\{-2, -1, 0, 1, 2\}$. The first disjunct "$\forall x \exists y F(x, y)$" asks: "For every $x$, does there exist some $y$ such that $x^2 - y^2 = 3$?" Testing $x = 0$: we need $0 - y^2 = 3$, so $y^2 = -3$. Since no real number squared gives $-3$, no $y$ in our domain works for $x = 0$. The first disjunct is false. The second disjunct "$\exists x \forall y \neg F(x, y)$" asks: "Does there exist some $x$ such that for all $y$, $F(x, y)$ is false?" Again using $x = 0$: for every $y$ in the domain, $0^2 - y^2 = 3$ becomes $-y^2 = 3$, which is impossible. So $\neg F(0, y)$ is true for all $y$. The second disjunct is true. Since $V$ is a disjunction and the second part is true, $V$ is true. Answer A is wrong because the first disjunct is actually false. Answer B misses the logical structure entirely—individual solutions don't determine the truth of universal quantifiers. Answer C incorrectly claims both disjuncts are false when the second is true. Remember: in logic problems, always check quantified statements systematically by testing specific values, especially potential counterexamples like boundary cases.
6. Let $R(x, y)$ be the relation "$|x - y| \leq 2$" over the domain $\{1, 2, 3, 4, 5, 6\}$. Consider the statement $S$: "$\forall x \exists y (R(x, y) \land y > x + 1)$". Which of the following correctly describes the truth value of $S$ and provides the best reasoning?
   Answer: $S$ is false because when $x = 6$, no $y$ in the domain satisfies both $|6 - y| \leq 2$ and $y > 7$ For $S$ to be true, every $x$ must have some $y$ such that $|x - y| \leq 2$ and $y > x + 1$. When $x = 6$, we need $y > 7$ and $|6 - y| \leq 2$. The second condition means $4 \leq y \leq 8$, but our domain only goes up to 6. So we need $y \in \{4, 5, 6\}$ and $y > 7$, which is impossible. (A) is wrong because we can't always find such $y$. (B) is wrong because when $x = 5$, we could have $y = 6$ (since $|5-6| = 1 \leq 2$ but $6 \not> 6$), but we need $y > 6$. (D) is irrelevant to the specific statement.
7. Let $M(x, y)$ be "$\max(x, y) = x + 1$" over domain $\{0, 1, 2, 3\}$. Consider the statement $Z$: "$\exists x \forall y M(x, y) \lor \forall x \exists y M(x, y)$". Which reasoning correctly determines the truth value of $Z$?
   Answer: $Z$ is false because neither disjunct can be satisfied in the given domain First disjunct: $\exists x \forall y M(x, y)$ asks if there's an $x$ such that for ALL $y$, $\max(x, y) = x + 1$. For this to work, we'd need $\max(x, 0) = \max(x, 1) = \max(x, 2) = \max(x, 3) = x + 1$. This is impossible since $\max(x, y)$ varies with $y$. Second disjunct: $\forall x \exists y M(x, y)$ asks if for every $x$, there's some $y$ with $\max(x, y) = x + 1$. For $x = 3$: need $\max(3, y) = 4$, but $4 \notin \{0,1,2,3\}$, so $\max(3, y) \leq 3$ always. Thus no $y$ works for $x = 3$. Both disjuncts are false, so $Z$ is false.
8. Consider the predicate $S(x, y): |x - y| < 2$ where the domain for both variables is $\{0, 1, 2, 3, 4\}$. Evaluate the truth of the nested quantified statement $\forall x \exists y \, (y \neq x \wedge S(x, y))$.
   Answer: True, because for every x, there is always a different y within distance 2 We need to verify that for each x in {0,1,2,3,4}, there exists a y ≠ x such that |x - y| < 2. For x = 0: |0 - y| < 2 means -2 < -y < 2, so -2 < y < 2. In our domain, y ∈ {1} works (since y ≠ 0). For x = 1: |1 - y| < 2 means -2 < 1-y < 2, so -1 < y < 3. Values y ∈ {0, 2} work. For x = 2: |2 - y| < 2 means -2 < 2-y < 2, so 0 < y < 4. Values y ∈ {1, 3} work. For x = 3: |3 - y| < 2 means -2 < 3-y < 2, so 1 < y < 5. Values y ∈ {2, 4} work. For x = 4: |4 - y| < 2 means -2 < 4-y < 2, so 2 < y < 6. Only y = 3 works in our domain. Since every x has at least one valid y ≠ x, the statement is true.
9. Consider the domain $D = \{-2, -1, 0, 1, 2\}$ and predicates $P(x)$: "$x^2 \leq 1$" and $Q(x)$: "$x + 1 > 0$". Which of the following compound quantified statements has the same truth value as $\neg(\exists x (P(x) \land \neg Q(x)))$?
   Answer: $\forall x (P(x) \rightarrow Q(x))$ First, apply De Morgan's law: $\neg(\exists x (P(x) \land \neg Q(x))) \equiv \forall x \neg(P(x) \land \neg Q(x)) \equiv \forall x (\neg P(x) \lor \neg\neg Q(x)) \equiv \forall x (\neg P(x) \lor Q(x))$. Since $\neg P(x) \lor Q(x) \equiv P(x) \rightarrow Q(x)$, the answer is (A). Let's verify: $P(x)$ is true for $x \in \{-1, 0, 1\}$ and $Q(x)$ is true for $x \in \{0, 1, 2\}$. The original statement asks if there exists $x$ where $P(x)$ is true but $Q(x)$ is false. This happens when $x = -1$. So the original is true, meaning its negation is false. Statement (A) says whenever $P(x)$ is true, $Q(x)$ must be true, which fails for $x = -1$, so (A) is false. This matches.
10. Consider the three-variable predicate $M(x, y, z): x \cdot y = z$ where all variables range over the domain $\{0, 1, 2\}$. Evaluate the truth of the statement $\forall x \forall z \exists y \, M(x, y, z)$.
    Answer: False, because when x = 0 and z = 1, no y satisfies 0 · y = 1 We need to check if for every pair (x,z), there exists a y in {0,1,2} such that xy = z. Let's systematically check all cases: For x = 0: We need 0·y = z, so z must be 0. When z = 0, any y works. When z = 1 or z = 2, no y works since 0·y = 0 always. For x = 1: We need 1·y = z, so y = z. For any z ∈ {0,1,2}, we can choose y = z. For x = 2: We need 2·y = z. When z = 0, y = 0 works. When z = 1, we need y = 1/2, but 1/2 ∉ {0,1,2}. When z = 2, y = 1 works. Since the case x = 0, z = 1 has no solution (we need 0·y = 1, which is impossible), the statement is false.
11. Consider the predicate $W(x, y): x + y \text{ is prime}$ where $x, y \in \{1, 2, 3, 4, 5, 6\}$. Determine the truth value of $\forall x \exists y \, (x < y \wedge W(x, y))$.
    Answer: False, because when x = 4, no y > 4 in the domain makes x + y prime We need to check if for every x, there exists a y > x such that x + y is prime. Let's check each x: For x = 1: y ∈ {2,3,4,5,6}. Sums: 3,4,5,6,7. Primes: 3,5,7. So y = 2,4,6 work. For x = 2: y ∈ {3,4,5,6}. Sums: 5,6,7,8. Primes: 5,7. So y = 3,5 work. For x = 3: y ∈ {4,5,6}. Sums: 7,8,9. Primes: 7. So y = 4 works. For x = 4: y ∈ {5,6}. Sums: 9,10. 9 = 3² and 10 = 2×5, so neither is prime. No y works. For x = 5: y ∈ {6}. Sum: 11, which is prime. So y = 6 works. For x = 6: No y > 6 in domain. Since x = 4 has no suitable y, the statement is false.
12. Let $T(x, y)$ be the statement "$x^2 + y^2 = 5$" over the domain of integers from $-3$ to $3$. Consider the nested quantification $\exists x \forall y T(x, y)$. Which statement best explains why this quantification is false?
    Answer: No single value of $x$ makes $T(x, y)$ true for every possible $y$ in the domain The statement $\exists x \forall y T(x, y)$ asks whether there exists some $x$ such that for ALL values of $y$ in the domain, $x^2 + y^2 = 5$. This would require finding an $x$ where the equation holds for $y = -3, -2, -1, 0, 1, 2, 3$ simultaneously, which is impossible since $y^2$ takes different values. (B) is wrong because there are solutions like $(1, 2), (2, 1), (-1, 2)$, etc. (C) describes why $\forall x \forall y T(x, y)$ is false, not our statement. (D) is irrelevant to why the given statement is false.
13. Let $Q(x)$ be "$x$ is even" and $R(x)$ be "$x > 2$" over the domain $\{1, 2, 3, 4, 5, 6\}$. Consider the statement $T$: "$\exists x (Q(x) \land R(x)) \rightarrow \forall y (Q(y) \rightarrow R(y))$". What is the truth value of $T$?
    Answer: False, because the antecedent is true but the consequent is false First, evaluate the antecedent $\exists x (Q(x) \land R(x))$: this asks if there's an even number greater than 2. Yes: $x = 4$ and $x = 6$ are both even and greater than 2. So the antecedent is true. Next, evaluate the consequent $\forall y (Q(y) \rightarrow R(y))$: this asks if every even number is greater than 2. The even numbers in the domain are $\{2, 4, 6\}$. Since $2$ is even but not greater than 2, the statement $Q(2) \rightarrow R(2)$ is false (true $\rightarrow$ false). Therefore the consequent is false. Since we have true $\rightarrow$ false, the overall statement $T$ is false.
14. Let $T(a, b, c)$ be the statement "$a + b + c$ is divisible by 3" where $a, b, c \in \{0, 1, 2\}$. Which of the following is the correct truth value of $\exists a \forall b \exists c \, T(a, b, c)$?
    Answer: True, because a = 0 works: for any b, we can choose c ≡ -b (mod 3) We need to find if there exists an 'a' such that for every 'b', there exists a 'c' making a + b + c ≡ 0 (mod 3). Let's try a = 0: For any b ∈ {0,1,2}, we need 0 + b + c ≡ 0 (mod 3), so c ≡ -b ≡ 3-b (mod 3). When b = 0: c ≡ 0 (mod 3), so c = 0 works. When b = 1: c ≡ 2 (mod 3), so c = 2 works. When b = 2: c ≡ 1 (mod 3), so c = 1 works. Since for a = 0, we can always find an appropriate c for any b, the statement is true. We could also verify that a = 1 and a = 2 work similarly, but we only need one value of a to make the existential quantifier true.
15. Consider predicates $P(x)$: "$x < 3$" and $Q(x)$: "$x$ is odd" over domain $\{1, 2, 3, 4, 5\}$. Let $W$ be the statement "$\exists x (P(x) \land Q(x)) \leftrightarrow \forall x (P(x) \rightarrow Q(x))$". Which analysis of $W$ is correct?
    Answer: $W$ is false because the left side is true but the right side is false When evaluating biconditional statements involving quantifiers, you need to determine the truth value of each side independently, then check if they match. Let's analyze each side of $W$: "$\exists x (P(x) \land Q(x)) \leftrightarrow \forall x (P(x) \rightarrow Q(x))$" over domain $\{1, 2, 3, 4, 5\}$. Left side: $\exists x (P(x) \land Q(x))$ asks "Does there exist an $x$ where $x < 3$ AND $x$ is odd?" - For $x = 1$: $P(1)$ is true ($1 < 3$) and $Q(1)$ is true (1 is odd) - So $P(1) \land Q(1)$ is true, making the existential statement true. Right side: $\forall x (P(x) \rightarrow Q(x))$ asks "For all $x$, if $x < 3$, then $x$ is odd?" - For $x = 1$: $1 < 3$ and 1 is odd, so $P(1) \rightarrow Q(1)$ is true - For $x = 2$: $2 < 3$ but 2 is even, so $P(2) \rightarrow Q(2)$ is false - Since one case fails, the universal statement is false. The left side is true but the right side is false, so the biconditional $W$ is false. Answer D correctly identifies this situation. Answer A wrongly claims both sides have the same truth value. Answer B incorrectly suggests the biconditional is always true regardless of the predicates. Answer C reverses which side is true and which is false. Study tip: Always evaluate quantified statements systematically by checking each domain element, especially when mixing existential and universal quantifiers.
16. Consider the domain $D = \{0, 1, 2, 3\}$ and let $R(x, y, z)$ be the relation "$x + y = z$". Which of the following statements about the quantification $\forall x \exists y \exists z R(x, y, z)$ is correct?
    Answer: The statement is true because for any $x$, we can choose $y = 0$ and $z = x$ to satisfy the relation The statement asks whether for every $x \in D$, there exist $y, z \in D$ such that $x + y = z$. For $x = 0$: choose $y = 0, z = 0$ giving $0 + 0 = 0$ ✓. For $x = 1$: choose $y = 0, z = 1$ giving $1 + 0 = 1$ ✓. For $x = 2$: choose $y = 0, z = 2$ giving $2 + 0 = 2$ ✓. For $x = 3$: choose $y = 0, z = 3$ giving $3 + 0 = 3$ ✓. So (A) is correct. (B) is wrong because $y = 0, z = 3$ works for $x = 3$. (C) is irrelevant since reflexivity doesn't apply to a three-place relation in this context. (D) identifies a potential issue but misses that we can always choose $y = 0$.
17. Let $P(n)$ be the statement "$n$ is prime" over the domain $\{10, 11, 12, 13, 14, 15\}$. Consider the statement $S$: "$\neg(\forall n P(n)) \land \neg(\forall n \neg P(n))$". Which of the following best describes what $S$ asserts about the domain?
    Answer: Not all numbers in the domain are prime, and not all numbers are composite $S$ states $\neg(\forall n P(n)) \land \neg(\forall n \neg P(n))$. The first part $\neg(\forall n P(n))$ means "not all $n$ are prime," which is equivalent to "at least one $n$ is not prime." The second part $\neg(\forall n \neg P(n))$ means "not all $n$ are non-prime," which is equivalent to "at least one $n$ is prime." Together, this means the domain contains both prime and non-prime numbers. (A) contradicts the statement. (C) is close but uses "some" which could be interpreted as stronger than "at least one." (D) contradicts $S$ entirely. (B) correctly captures that it's not the case that all are prime, and not the case that all are composite.
18. Let $V(m, n)$ represent the statement "$\gcd(m, n) = 1$" where the domain is $\{2, 3, 4, 5, 6\}$. Which of the following statements about the truth values is correct?
    Answer: $\forall m \exists n \, (m \neq n \wedge V(m, n))$ is true for this domain Let's analyze each option systematically. For option A: We need one m that is coprime to ALL n in the domain. Let's check m = 3: gcd(3,2) = 1, gcd(3,3) = 3, gcd(3,4) = 1, gcd(3,5) = 1, gcd(3,6) = 3. Since gcd(3,3) ≠ 1 and gcd(3,6) ≠ 1, this is false. For option B: We need every m to have some n where gcd(m,n) = 1. For m = 4: gcd(4,3) = 1, gcd(4,5) = 1, so this works. Similarly, every m in the domain has at least one n where they're coprime, so this statement is actually true. For option C: For each m, we need some different n where gcd(m,n) = 1. m = 2: gcd(2,3) = 1, gcd(2,5) = 1. m = 3: gcd(3,2) = 1, gcd(3,4) = 1, gcd(3,5) = 1. m = 4: gcd(4,3) = 1, gcd(4,5) = 1. m = 5: gcd(5,2) = 1, gcd(5,3) = 1, gcd(5,4) = 1, gcd(5,6) = 1. m = 6: gcd(6,5) = 1. Every m has at least one different n that is coprime to it, so this is true.
19. Consider the domain $D = \{a, b, c\}$ where $a = 1, b = 2, c = 4$. Let $S(x, y)$ mean "$x$ divides $y$" and consider the statement $U$: "$\neg(\exists x \exists y (S(x, y) \land S(y, x) \land x \neq y))$". Which interpretation of $U$ is correct?
    Answer: No two distinct elements in the domain divide each other mutually The statement $U$ is $\neg(\exists x \exists y (S(x, y) \land S(y, x) \land x \neq y))$, which means "it is not the case that there exist distinct $x, y$ such that $x$ divides $y$ AND $y$ divides $x$". This is equivalent to saying "no two distinct elements divide each other mutually". Let's verify: In our domain, $1|2, 1|4, 2|4$, but $2 \nmid 1, 4 \nmid 1, 4 \nmid 2$. So indeed, no two distinct elements have mutual divisibility. (A) contradicts $U$. (C) is true but doesn't capture what $U$ says. (D) is about one element dividing others, not mutual divisibility.

Start this quiz