w1

w1.pdf

1. Let \(p\) stand for the proposition "The weather is cloudy" and \(q\) for "It's raining". Express the following as natural English sentences:
   (a) \(\neg p\)

   The weather isn't cloudy

   ‍

   (b) \(p \lor q\)

   The weather is cloudy or it's raining

   ‍

   (c) \(p \land q\)

   The weather is cloudy and it's raining

   ‍

   (d) \(p \implies q\)

   If the weather is cloudy, it's raining

   ‍

   (e) \(\neg p \implies \neg q\)

   If the weather isn't cloudy, it isn't raining

   (f) \(\neg p \lor (p \land q)\)

   The weather isn't cloudy, or the weather is cloudy and it's raining

   ‍

2. Determine whether the following two statements are logically equivalent or not. Justify your answer:
   (a) \(\neg (p \implies q)\) and \(p \land \neg q\)

   \(p\)​	\(q\)​	\(p\implies q\)​	\(\neg\left(p\implies q\right)\)​	\(\neg q\)​	\(p\wedge \neg q\)​
   T	T	T	F	F	F
   T	F	F	T	T	T
   F	T	T	F	F	F
   F	F	T	F	T	F

   Obviously, they are equivalent.

   ‍

   (b) \(p \implies (q \lor r)\) and \((p \implies q) \lor (p \implies r)\)

   \(p\)​	\(q\)​	\(r\)​	\(q\vee r\)​	\(p \implies (q \lor r)\)​	\(p \implies q\)​	\(p \implies r\)​	\((p \implies q) \lor (p \implies r)\)​
   T	T	T	T	T	T	T	T
   T	T	F	T	T	T	F	T
   T	F	T	T	T	F	T	T
   T	F	F	F	F	F	F	F
   F	T	T	T	T	T	T	T
   F	T	F	T	T	T	T	T
   F	F	T	T	T	T	T	T
   F	F	F	F	T	T	T	T

   Obviously, they are equivalent.

   ‍

3. Prove that:
   ​\((\exists x)(p(x) \land q(x)) \implies (\exists x)(p(x)) \land (\exists x)(q(x))\)
   and refute the other implication.

   Proof

   \((\exists x)(p(x)\land q(x))\) means: There exists \(x_0\) such that \(p(x_0)\) and \(q(x_0)\) are both true.

   Then there exists \(x_0\) such that \(p(x_0)\) is true and exists \(x_0\) such that \(q(x_0)\) is true.

   Which is \((\exists x)(p(x))\land(\exists x)(q(x))\).

   Refutation

   \((\exists x)(p(x))\land(\exists x)(q(x))\) means: There exists \(x_0\) such that \(p(x_0)\) is true and exists \(x_1\) such that \(q(x_1)\) is true.

   But it cannot imply there exists \(x\) such that \(p(x)\) and \(q(x)\) are both true, since \(x_0\) and \(x_1\) are not same.

   ‍

4. Prove that the existentially quantified statement:
   ​\((\exists x)\left(\frac{1}{x^2 + 1} > 1\right)\) is false where the domain of the propositional function \(p(x) \equiv \frac{1}{x^2 + 1}\) is \(\mathbb{R}\).

   Proof

   Since \(x\) is \(\R\), \(x^2\geq 0\). Then \(x^2+1\geq 1\), and \(0<\frac{1}{x^2+1}\leq1\)​

   Which means \((\exists x)\left(\frac{1}{x^2 + 1} > 1\right)\) is false.

   ‍

5. Which of the following are denials of \((\exists! x) p(x)\)? (There exists more than one solution)
   (a) \((\forall x) p(x) \lor (\forall x) \neg p(x)\)

   Proof

   The proposition means either \(p(x)\) is true or false for all \(x\)

   But it doesn't account for cases where multiple \(x\) (but not every \(x\)) satisfy \(p(x)\).

   Hence (a) is not the denials of \((\exists! x) p(x)\)

   ‍

   (b) \((\forall x) \neg p(x) \lor (\exists y)(\exists z) [(y \neq z) \land p(y) \land p(z)]\)

   Proof

   \((\forall x) \neg p(x)\) means \(p(x)\) is false for all \(x\)

   \((\exists y)(\exists z) [(y \neq z) \land p(y) \land p(z)]\) means: There exists two different elements \(y\), \(z\) such that \(p(y)\) and \(p(z)\) are both true.

   Thus the proposition means: no solution or two solution

   Hence (b) is not the denials of \((\exists! x) p(x)\)

   ‍

   (c) \((\forall x) [p(x) \implies (\exists y) (p(y) \land (y \neq x))]\)

   Proof

   The proposition means: For all \(x\), if \(p(x)\) is true, there exists another different element \(y\) such that \(p(y)\) is true.

   Thus there exists two elements that hold for \(p(x)\) at least.

   Hence (c) is the denials of \((\exists! x) p(x)\)

   ‍

   (d) \(\neg (\forall x)(\forall y)[(p(x) \land p(y)) \implies (y = x)]\)

   Proof

   The proposition means: For all \(x\) and \(y\), if \(p(x)\) and \(q(x)\) are both true, then \(y=x\). Which is false.

   Hence there is only one element that holds for \(p(x)\) that is false.

   This implies that there is more than one solution or no solution.

   Hence (d) is not the denials of \((\exists! x) p(x)\)

6. Prove that \((\exists! x) p(x)\) is equivalent to \((\exists x)[p(x) \land (\forall y)(p(y) \implies (y = x))]\). (Hint: Recall last problem)

   Proof

   \(\Rightarrow\)) \((\exists! x) p(x)\) means that there exists only one \(x\) holds for \(p(x)\).

   Thus let's consider \(x\) and \(y\).

   If there exists only one \(x\) holds for \(p(x)\)​, then we can conclude: If exists \(x\) such that \(p(x)\) and \(p(y)\) are both true, then \(x\) and \(y\) must be same.

   Hence \(y=x\).

   \(\Leftarrow\)) If exists \(x\) such that \(p(x)\) and \(p(y)\) are both true, then \(x=y\).

   This means that only one element holds for \(p(x)\).

   Hence \((\exists! x) p(x)\)

   ‍