1. **Show that $P : p \to (q \to r)$ and $Q : (p \wedge q) \to r$ are logically equivalent.** (a) Using a truth table: | $p$ | $q$ | $r$ | $q \to r$ | $p \to (q \to r)$ | $p \wedge q$ | $(p \wedge q) \to r$ | |-----|-----|-----|------------|---------------------|--------------|-----------------------| | T | T | T | T | T | T | T | | T | T | F | F | F | T | F | | T | F | T | T | T | F | T | | T | F | F | T | T | F | T | | F | T | T | T | T | F | T | | F | T | F | F | T | F | T | | F | F | T | T | T | F | T | | F | F | F | T | T | F | T | The columns for $p \to (q \to r)$ and $(p \wedge q) \to r$ are identical, so $P$ and $Q$ are logically equivalent. (b) Using laws of logical equivalence: 1. $p \to (q \to r) \equiv p \to (\neg q \lor r)$ by definition of implication. 2. $p \to (\neg q \lor r) \equiv \neg p \lor (\neg q \lor r)$ by implication equivalence. 3. $\neg p \lor \neg q \lor r$ is associative and commutative. 4. $(p \wedge q) \to r \equiv \neg (p \wedge q) \lor r \equiv \neg p \lor \neg q \lor r$. Since both simplify to $\neg p \lor \neg q \lor r$, $P$ and $Q$ are logically equivalent. 2. **Show that $\forall x (P(x) \to Q(x))$ and $\forall x P(x) \to \forall x Q(x)$ are not equivalent.** Choose domain $D = \{a,b\}$. Let $P(a) = \text{true}$, $P(b) = \text{false}$. Let $Q(a) = \text{false}$, $Q(b) = \text{true}$. Evaluate $\forall x (P(x) \to Q(x))$: - For $a$: $P(a) \to Q(a) = \text{true} \to \text{false} = \text{false}$. - For $b$: $P(b) \to Q(b) = \text{false} \to \text{true} = \text{true}$. So $\forall x (P(x) \to Q(x)) = \text{false}$. Evaluate $\forall x P(x) \to \forall x Q(x)$: - $\forall x P(x) = P(a) \wedge P(b) = \text{true} \wedge \text{false} = \text{false}$. - $\forall x Q(x) = Q(a) \wedge Q(b) = \text{false} \wedge \text{true} = \text{false}$. - So $\forall x P(x) \to \forall x Q(x) = \text{false} \to \text{false} = \text{true}$. Since $\forall x (P(x) \to Q(x))$ is false but $\forall x P(x) \to \forall x Q(x)$ is true, they are not equivalent. 3. **Using rules of inference, show that from premises $P1: r \to p$, $P2: p \to c$, $P3: r \lor (q \wedge s)$, $P4: \neg s$, conclude $c$.** 1. From $P4: \neg s$, and $P3: r \lor (q \wedge s)$, since $s$ is false, $q \wedge s$ is false. 2. Therefore, $r \lor (q \wedge s)$ reduces to $r \lor \text{false} = r$. 3. So $r$ must be true. 4. From $P1: r \to p$ and $r$ true, by Modus Ponens, $p$ is true. 5. From $P2: p \to c$ and $p$ true, by Modus Ponens, $c$ is true. 6. Hence, conclusion $c$ follows validly. 4. **True/False statements with justifications:** (a) $\neg (p \leftrightarrow q)$ and $\neg p \leftrightarrow \neg q$ are logically equivalent? - False. $\neg (p \leftrightarrow q)$ is the negation of equivalence (exclusive or), but $\neg p \leftrightarrow \neg q$ is equivalent to $p \leftrightarrow q$. (b) $\neg (p \wedge q) \wedge (q \lor r) \to (p \to r)$ is a tautology? - True. By logical simplification, this always holds. (c) $\exists x (P(x) \to Q(x))$ is logically equivalent to $\forall x P(x) \to \exists x Q(x)$? - False. Counterexample: if $P(x)$ is true for all $x$ but $Q(x)$ is false for all $x$, then $\exists x (P(x) \to Q(x))$ is true (because $P(x) \to Q(x)$ is false only if $P(x)$ true and $Q(x)$ false), but $\forall x P(x) \to \exists x Q(x)$ is false. (d) If $\exists! x \neg P(x)$, then $\neg \forall x P(x)$? - True. $\exists! x \neg P(x)$ means exactly one $x$ does not satisfy $P$, so not all satisfy $P$. (e) If $\forall x \exists y P(x,y)$ is true, then $\exists y \forall x P(x,y)$ must be false? - False. It is possible both are true depending on $P$. (f) The argument: "If you secured your database, then your system is safe. You did not secure your database. Therefore, your system is unsafe." is valid? - False. This is denying the antecedent, which is invalid. 5. **Determine whether the following logical equivalences are True or False:** (a) $(p \to q) \wedge (p \to r) \equiv p \to (q \wedge r)$ - True. By distributive property of implication. (b) $(p \to q) \vee (p \to r) \equiv p \to (q \vee r)$ - False. Counterexample: $p$ true, $q$ false, $r$ false. (c) $(p \to r) \wedge (q \to r) \equiv (p \wedge q) \to r$ - False. Counterexample: $p$ true, $q$ false, $r$ false. (d) $(p \to r) \vee (q \to r) \equiv (p \wedge q) \to r$ - True. Both sides are true except when $p$ and $q$ are true and $r$ is false.