You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
Validity of predicate logic arguments
- Thread starter A.H.S
- Start date
Again. Here is my attempt.
For part (a)
[MATH] \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \text{, }P(a) \vDash \exists z \forall y(\neg R(y,z))[/MATH]Valid
[MATH] \text {(1) } \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \hspace7ex \text{Premise}\\ \text {(2) } \forall y \forall z (P(z) \rightarrow \neg R(y,z)) \\ \text {(3) } \forall y (P(a) \rightarrow \neg R(y,a)) \hspace9ex \text{Universal Specification}\\ \text {(4) }P(a) \quad \quad \hspace20ex \text{Premise}\\ \text {(5) }\forall y (P(a) \rightarrow \neg R(y,a)) \land P(a) \hspace2ex \text{(3), (4)}\\ \text {(6) }\forall y ((P(a) \rightarrow \neg R(y,a)) \land P(a))\\ \text {(7) }\forall y ( \neg R(y,a)) \hspace17ex \text{MP (4), (6)}\\ \text {(8) }\exists z \forall y(\neg R(y,z)) \hspace15ex \text{Existential Generalisation}[/MATH][MATH]\text{_______________________________________}\\[10pt] \vDash \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \land P(a) \rightarrow \exists z \forall y(\neg R(y,z))\\ \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \text{, }P(a) \vDash \exists z \forall y(\neg R(y,z))[/MATH]
For part (b)
[MATH] \vDash \exists xP(x) \land Q(y) \rightarrow \exists z(P(z) \land Q(z))[/MATH]Not valid
Just because there exists a [MATH]x[/MATH]: P(x) true and that Q(y) true, doesn't mean there exists an [MATH]x[/MATH]: both P(x) true and Q(x) true.
[L.h.s [MATH]\rightarrow \exists x: P(x)[/MATH], so [MATH] P(a)[/MATH] true for some [MATH]a[/MATH].
L.h.s. [MATH]\rightarrow Q(y)[/MATH] true.
We know nothing about Q(a).
So we cannot say that [MATH]P(a) \land Q(a[/MATH]) true.
So we cannot conclude that [MATH]\exists z: P(z) \land Q(z)[/MATH] ].
Suppose that P(y) false, Q(y) true, and [MATH]\exists x≠y: P(x)[/MATH] true.
Consider a case where [MATH]\forall x P(x)= \neg Q(x)[/MATH] (this is not in conflict with the previous line),
then [MATH]\exists x P(x) \land Q(y)[/MATH], so L.h.s is true and
[MATH]\forall P(x)=\neg Q(x) \text{ so } \neg \exists x: P(x) \land Q(x)[/MATH], so R.h.s. is false.
[MATH]\text{_______________________________________}\\[10pt] \exists x P(x) \land Q(y) \not \vDash \exists z(P(z) \land Q(z))\\ \not \vDash \exists xP(x) \land Q(y) \rightarrow \exists z(P(z) \land Q(z))[/MATH]
For part (a)
[MATH] \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \text{, }P(a) \vDash \exists z \forall y(\neg R(y,z))[/MATH]Valid
[MATH] \text {(1) } \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \hspace7ex \text{Premise}\\ \text {(2) } \forall y \forall z (P(z) \rightarrow \neg R(y,z)) \\ \text {(3) } \forall y (P(a) \rightarrow \neg R(y,a)) \hspace9ex \text{Universal Specification}\\ \text {(4) }P(a) \quad \quad \hspace20ex \text{Premise}\\ \text {(5) }\forall y (P(a) \rightarrow \neg R(y,a)) \land P(a) \hspace2ex \text{(3), (4)}\\ \text {(6) }\forall y ((P(a) \rightarrow \neg R(y,a)) \land P(a))\\ \text {(7) }\forall y ( \neg R(y,a)) \hspace17ex \text{MP (4), (6)}\\ \text {(8) }\exists z \forall y(\neg R(y,z)) \hspace15ex \text{Existential Generalisation}[/MATH][MATH]\text{_______________________________________}\\[10pt] \vDash \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \land P(a) \rightarrow \exists z \forall y(\neg R(y,z))\\ \forall y \forall z (R(y,z) \rightarrow \neg P(z)) \text{, }P(a) \vDash \exists z \forall y(\neg R(y,z))[/MATH]
For part (b)
[MATH] \vDash \exists xP(x) \land Q(y) \rightarrow \exists z(P(z) \land Q(z))[/MATH]Not valid
Just because there exists a [MATH]x[/MATH]: P(x) true and that Q(y) true, doesn't mean there exists an [MATH]x[/MATH]: both P(x) true and Q(x) true.
[L.h.s [MATH]\rightarrow \exists x: P(x)[/MATH], so [MATH] P(a)[/MATH] true for some [MATH]a[/MATH].
L.h.s. [MATH]\rightarrow Q(y)[/MATH] true.
We know nothing about Q(a).
So we cannot say that [MATH]P(a) \land Q(a[/MATH]) true.
So we cannot conclude that [MATH]\exists z: P(z) \land Q(z)[/MATH] ].
Suppose that P(y) false, Q(y) true, and [MATH]\exists x≠y: P(x)[/MATH] true.
Consider a case where [MATH]\forall x P(x)= \neg Q(x)[/MATH] (this is not in conflict with the previous line),
then [MATH]\exists x P(x) \land Q(y)[/MATH], so L.h.s is true and
[MATH]\forall P(x)=\neg Q(x) \text{ so } \neg \exists x: P(x) \land Q(x)[/MATH], so R.h.s. is false.
[MATH]\text{_______________________________________}\\[10pt] \exists x P(x) \land Q(y) \not \vDash \exists z(P(z) \land Q(z))\\ \not \vDash \exists xP(x) \land Q(y) \rightarrow \exists z(P(z) \land Q(z))[/MATH]