# Proving the Validity of an Argument in Predicate Logic

• Mar 10th 2009, 05:52 PM
ft_fan
Proving the Validity of an Argument in Predicate Logic - Another pointer please!
Hi all,

I am having an issue with the following question, I wonder if anyone could point me in the right direction:

Using only the standard rules of inference and logical equivalence, prove the validity of the following argument, where the propositional functions P, Q, R and S share the same domain.

http://img6.imageshack.us/img6/4817/mathsg.jpg

Any suggestions would be much appreciated!
• Mar 11th 2009, 02:32 AM
aliceinwonderland
Quote:

Originally Posted by ft_fan
Hi all,

I am having an issue with the following question, I wonder if anyone could point me in the right direction:

Using only the standard rules of inference and logical equivalence, prove the validity of the following argument, where the propositional functions P, Q, R and S share the same domain.

http://img6.imageshack.us/img6/4817/mathsg.jpg

Any suggestions would be much appreciated!

You might need to consider the following steps.

1. Change an existential quantifier in Premise 2 into a universal quantifier.

$\displaystyle \neg \forall x (\neg R(x)$.......

2. Drop all universal quantifers for premise 1 and 2.

3. Eliminate implications using $\displaystyle \neg, \vee..$.
4. Using resolutions (if needed), reduce Premise1 $\displaystyle \wedge$ Premise 2.
5. Restore a universal quantifer and implication if possible. Then check it with a conclusion whether or not it is valid.
• Mar 11th 2009, 06:01 AM
ft_fan
Thanks a lot for your hints, I'm on track now!

Cheers!
• Mar 12th 2009, 12:49 PM
ft_fan
Okay, so I'm getting there, but I'm stuck again, although I think I'm close! What I have so far is as follows:

1. $\displaystyle \forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y))))$ - Premise

2. $\displaystyle \exists x (R(x) \wedge \forall y (P(y) \rightarrow Q(x,y)))$ - Premise

3. $\displaystyle R(x) \wedge \forall y(P(y) \rightarrow Q(x,y))$ - $\displaystyle \exists$ _E from 2.

4. $\displaystyle R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q(x,y)))$ - $\displaystyle \forall$_E from 1.

5. $\displaystyle \neg R(x) \vee \forall y (S(y) \rightarrow (\neg Q(x,y)))$ - Implication, from 4.

6. $\displaystyle \neg R(x) \vee (S(y) \rightarrow (\neg Q(x,y))$ - $\displaystyle \forall$_E on 5.

7. $\displaystyle \neg R(x) \vee ((\neg S(y)) \vee (\neg Q(x,y))$ - Implication from 6.

8. $\displaystyle \forall y(P(y) \rightarrow Q(x,y)) \wedge R(x)$ - Commutative, from 3.

9. $\displaystyle \forall y (P(y) \rightarrow Q(x,y))$ - 8, simplification.

10. $\displaystyle P(y) \rightarrow Q(x,y)$ - $\displaystyle \forall$_E from 9.

11. $\displaystyle \neg P(y) \vee Q(x,y)$ - 10, implication.

I just can't see how to proceed - any advice, much appreciated!
• Mar 12th 2009, 02:04 PM
Plato
1. $\displaystyle \forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y))))$ - Premise

2. $\displaystyle \exists x (R(x) \wedge \forall y (P(y) \rightarrow Q(x,y)))$ - Premise

3. $\displaystyle R(a) \wedge \forall y(P(y) \rightarrow Q(a,y))$ - $\displaystyle \exists$ _E from 2. [changed to a]

4. $\displaystyle R(a) \rightarrow \forall y (S(y) \rightarrow (\neg Q(a,y)))$ - $\displaystyle \forall$_E from 1.

5. $\displaystyle \forall y(P(y) \rightarrow Q(a,y))$_Simp from 3

6. $\displaystyle (P(y) \rightarrow Q(a,y))$ - $\displaystyle \forall$_from 5

7. $\displaystyle R(a)$_simp from 3

8. $\displaystyle \forall y (S(y) \rightarrow (\neg Q(a,y)))$_M.P. From 4 & 7.

9. $\displaystyle S(y) \rightarrow \neg Q(a,y)$ - $\displaystyle \forall$_from 8

10. $\displaystyle Q(a,y) \rightarrow \neg S(y)$ –Trans from 9

11. $\displaystyle P(y) \rightarrow \neg S(y)$ –H.S. from 6 &10.

Now can you preceed?