1. **Problem statement:** We need to determine for each pair of expressions A and B whether the implication $A \to B$ is a tautology and whether $B \to A$ is a tautology. 2. **Recall:** - An implication $A \to B$ is a tautology if it is true under every interpretation. - For quantified statements, tautology means the implication holds for all possible domains and predicates. --- ### (a) Expressions: - $A: (\forall x, P(x)) \to (\exists x, Q(x))$ - $B: (\exists x, P(x)) \to Q(x)$ **Step 1:** Analyze $A \to B$. - $A$ says: If $P(x)$ is true for all $x$, then there exists some $x$ such that $Q(x)$ is true. - $B$ says: If there exists some $x$ such that $P(x)$ is true, then $Q(x)$ is true (note $Q(x)$ without quantifier means $Q$ holds for that particular $x$). **Step 2:** Check if $A \to B$ is always true. - Consider a domain with one element $a$. - Suppose $P(a)$ is true for all $x$ (only $a$), so $\forall x, P(x)$ is true. - Then $A$'s antecedent is true, so $A$ is true if $\exists x, Q(x)$ is true. - But $B$ requires that if $\exists x, P(x)$ then $Q(x)$ holds for that $x$. - Since $B$'s conclusion is $Q(x)$ for the same $x$ that satisfies $P(x)$, $B$ is not necessarily true if $Q(x)$ is false for that $x$. - So $A \to B$ is **not** a tautology. **Step 3:** Check if $B \to A$ is always true. - $B$ says: If there exists $x$ with $P(x)$, then $Q(x)$ holds for that $x$. - $A$ says: If $P(x)$ holds for all $x$, then there exists $x$ with $Q(x)$. - If $B$ is true, then for some $x$ with $P(x)$, $Q(x)$ holds. - If $P(x)$ holds for all $x$, then certainly $\exists x, P(x)$, so $Q(x)$ holds for that $x$. - Hence $\exists x, Q(x)$ is true. - So $B \to A$ is a tautology. --- ### (b) Expressions: - $A: \exists x \forall y, P(x,y)$ - $B: \forall y \exists x, P(x,y)$ **Step 1:** Analyze $A \to B$. - $A$ says: There exists an $x$ such that for all $y$, $P(x,y)$ holds. - $B$ says: For every $y$, there exists an $x$ such that $P(x,y)$ holds. - If $A$ is true, then for that particular $x$, $P(x,y)$ holds for all $y$. - So for each $y$, there exists an $x$ (the same $x$) such that $P(x,y)$ holds. - Therefore, $A \to B$ is a tautology. **Step 2:** Analyze $B \to A$. - $B$ says: For every $y$, there exists an $x$ such that $P(x,y)$ holds. - $A$ says: There exists an $x$ such that for all $y$, $P(x,y)$ holds. - $B$ does not guarantee the same $x$ works for all $y$. - So $B \to A$ is **not** a tautology. --- **Final answers:** - (a) $A \to B$ is not a tautology; $B \to A$ is a tautology. - (b) $A \to B$ is a tautology; $B \to A$ is not a tautology.