Discrete-math 2

1

\begin{matrix} Which of the following is equivalent to the negation of the statement: \\ ”For every chef, there exists a dish they make that is tasty." \\ C = {chef} \\ D = {dish} \\ M (c, d) = c makes d \\ D_{c} = {d ∣ d \in D \land M (c, d)} \\ T (d) = d is tasty \\ Statement is: \forall c \in C \exists d \in D_{c} : T (d) \\ Negated statement is: \\ \neg (\forall c \in C \exists d \in D_{c} : T (d)) \equiv (h) \equiv \\ \equiv \exists c \in C \neg (\exists d \in D_{c} : T (d)) \equiv (b) \equiv \\ \equiv \exists c \in C \forall d i n D_{c} \neg T (d) \equiv (f) \\ Answer: Statements (h), (b), (f) \end{matrix}

2

\begin{matrix} Which of the following is equivalent to the negation of the proposition: \\ \forall x \exists y \forall z (P (x, y, z) \land P (z, x, y)) \\ \neg (\forall x \exists y \forall z (P (x, y, z) \land P (z, x, y))) \equiv \\ \equiv \exists x \neg (\exists y \forall z (P (x, y, z) \land P (z, x, y))) \equiv \\ \equiv \exists x \forall y \neg (\forall z (P (x, y, z) \land P (z, x, y))) \equiv (d) \equiv \\ \equiv \exists x \forall y \exists z \neg (P (x, y, z) \land P (z, x, y)) \equiv \\ \equiv \exists x \forall y \exists z (\neg P (x, y, z) \lor \neg P (z, x, y)) \equiv (a) \\ Answer: Statements (d), (a) \end{matrix}

3

\begin{matrix} Q over R \\ Find a predicate Q for which the statement \\ (\forall x \exists y Q (x, y) \land \forall y \exists x Q (x, y)) \to \forall x \exists y (Q (x, y) \land Q (y, x)) \\ is false \\ Q (x, y) = x > y \\ \forall x \exists y Q (x, y) \equiv T \\ \forall x \exists y = x - 1 : x > y \equiv T \\ \forall y \exists x Q (x, y) \equiv T \\ \forall y \exists x = y + 1 : x > y \equiv T \\ \forall x \exists y (Q (x, y) \land Q (y, x)) \equiv F \\ Q (x, y) \land Q (y, x) \equiv x > y \land y > x \equiv F \\ (T \land T) \to F \equiv T \to F \equiv F \\ Answer: Q (x, y) = x > y \end{matrix}

4a

\begin{matrix} P (x, y) over Z \\ Disproof: \\ S (x, y) \equiv \exists x \forall y P (x, y) \to \forall x \exists y P (x, y) \\ P (x, y) = (x > 0) \land (y > y - 1) \\ \exists x \forall y P (x, y) \equiv T \\ \forall x \exists y P (x, y) \equiv F \\ ⟹ S (x, y) \equiv T \to F \equiv F \end{matrix}

4b

\begin{matrix} P (x, y) over Z \\ Disproof: \\ S (x, y) \equiv \forall x \exists y P (x, y) \to \exists x \forall y P (x, y) \\ P (x, y) = (y > 0) \land (x > x - 1) \\ \forall x \exists y P (x, y) \equiv T \\ \exists x \forall y P (x, y) \equiv F \\ ⟹ S (x, y) \equiv T \to F \equiv F \end{matrix}

4c

\begin{matrix} P (x), Q (x) over Z \\ Proof: \\ S (x) \equiv \forall x (P (x) \land Q (x)) \to (\forall x P (x) \land \forall x Q (x)) \\ Let (\forall x P (x) \land \forall x Q (x)) \equiv F \\ Then \forall x P (x) \equiv F or \forall x Q (x) \equiv F \\ Then \forall x (P (x) \land Q (x)) \equiv F \\ Then the case where \forall x (P (x) \land Q (x)) \equiv T and (\forall x P (x) \land \forall x Q (x)) \equiv F is impossible \\ ⟹ S (x) \equiv \forall (P (x) \land Q (x)) \to \forall x P (x) \land \forall x Q (x) \equiv T \end{matrix}

4d

\begin{matrix} P (x), Q (x) over Z \\ S (x) \equiv (\forall x P (x) \land \forall x Q (x)) \to \forall x (P (x) \land Q (x)) \\ Proof: \\ Let \forall x (P (x) \land Q (x)) \equiv F \\ Then \forall x P (x) \equiv F or \forall x Q (x) \equiv F \\ Which is equivalent to (\forall x P (x) \land \forall x Q (x)) \equiv F \\ Then the case where (\forall x P (x) \land \forall x Q (x)) \equiv T and \forall x (P (x) \land Q (x)) \equiv F is impossible \\ ⟹ S (x) \equiv (\forall x P (x) \land \forall x Q (x)) \to \forall x (P (x) \land Q (x)) \equiv T \end{matrix}

5

\begin{matrix} P (x) over Z \\ Prove or disprove: S (P, a) \equiv \forall P (a) \exists a \in Z : P (a) \to P (a + 1) \\ Proof: \\ Let S \equiv F : \\ \exists P (a) : \forall a : (P (a) \to P (a + 1)) \equiv F ⟺ (P (a) \equiv T) \land (P (a + 1) \equiv F) \\ Let a = x \\ (P (a) \equiv P (x) \equiv T) \land (P (a + 1) \equiv P (x + 1) \equiv F) \\ Now let a = x + 1 \\ (P (a) \equiv P (x + 1) \equiv T) \land (P (x + 1) \equiv F) \\ ⟹ P (x + 1) \equiv T \equiv F - Contradiction! \\ ⟹ S (P, a) ≢ F ⟹ S (P, a) \equiv T \end{matrix}

6

\begin{matrix} Write an equivalent statement to the following without using negation: \\ \neg (\exists x \in Q . \forall y \in Q . ((y^{2} < 2 \to x > y) \land (\forall ε > 0. \exists z \in Q . (z^{2} < 2 \land z > x - ε)))) \\ \equiv \forall x \in Q . \neg (\forall y \in Q . ((y^{2} < 2 \to x > y) \land (\forall ε > 0. \exists z \in Q . (z^{2} < 2 \land z > x - ε)))) \\ \equiv \forall x \in Q . \exists y \in Q . \neg ((y^{2} < 2 \to x > y) \land (\forall ε > 0. \exists z \in Q . (z^{2} < 2 \land z > x - ε))) \\ \equiv \forall x \in Q . \exists y \in Q . (\neg (y^{2} < 2 \to x > y) \lor \neg (\forall ε > 0. \exists z \in Q . (z^{2} < 2 \land z > x - ε))) \\ \equiv \forall x \in Q . \exists y \in Q . ((y^{2} < 2 \land x \leq y) \lor (\exists ε > 0. \neg (\exists z \in Q . (z^{2} < 2 \land z > x - ε)))) \\ \equiv \forall x \in Q . \exists y \in Q . ((y^{2} < 2 \land x \leq y) \lor (\exists ε > 0. \forall z \in Q . \neg (z^{2} < 2 \land z > x - ε))) \\ \equiv \forall x \in Q . \exists y \in Q . ((y^{2} < 2 \land x \leq y) \lor (\exists ε > 0. \forall z \in Q . (2 \leq z^{2} \lor z \leq x - ε))) \end{matrix}

In each of the following, find sets A, B, and C that satisfy the conditions of the clause:

7a

\begin{matrix} A \subseteq B, B \in C, A \notin C \\ A = {1}, B = {1, 2}, C = {{1, 2}} \end{matrix}

7b

\begin{matrix} A \subseteq B, A \in C, B \notin C \\ A = {1}, B = {1, 2}, C = {{1}} \end{matrix}

7c

\begin{matrix} A \in B, B \in C, A \notin C \\ A = {1}, B = {{1}}, C = {{{1}}} \end{matrix}

7d

\begin{matrix} A \in B, B \in C, A \in C \\ A = {1}, B = {{1}}, C = {{1}, {{1}}} \end{matrix}

7e

\begin{matrix} A \in B, A \subseteq B \\ A = {1}, B = {1, {1}} \end{matrix}

8a

\begin{matrix} Prove or disprove: {2 n - 1 ∣ n \in N} \subseteq {2 n + 1 ∣ n \in N} \\ Disproof: \\ x = 1 \in {2 n - 1 ∣ n \in N} \\ x = 1 \notin {2 n + 1 ∣ n \in N} \\ ⟹ {2 n - 1 ∣ n \in N} ⊈ {2 n + 1 ∣ n \in N} \end{matrix}

8b

\begin{matrix} Prove or disprove: {2 n - 1 ∣ n \in N} \supseteq {2 n + 1 ∣ n \in N} \\ Proof: \\ Let x \in {2 n + 1 ∣ n \in N} \\ Then \exists m \in N : x = 2 m + 1 \\ Let n = m + 1 \\ n is a sum of two natural numbers, therefore n \in N \\ x = 2 m + 1 = 2 (n - 1) + 1 = 2 n - 1 \\ \exists n \in N : x = 2 n - 1 ⟹ x \in {2 n - 1 ∣ n \in N} \\ ⟹ {2 n + 1 ∣ n \in N} \subseteq {2 n - 1 ∣ n \in N} \\ ⟺ {2 n - 1 ∣ n \in N} \supseteq {2 n + 1 ∣ n \in N} \end{matrix}