Proving the Validity of an Argument in Predicate Logic

Printable View

March 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!
March 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.

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

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

3. Eliminate implications using $\neg, \vee..$ .
4. Using resolutions (if needed), reduce Premise1 $\wedge$ Premise 2.
5. Restore a universal quantifer and implication if possible. Then check it with a conclusion whether or not it is valid.
March 11th 2009, 06:01 AM
ft_fan

Thanks a lot for your hints, I'm on track now!

Cheers!
March 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. $\forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y))))$ - Premise

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

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

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

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

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

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

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

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

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

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

I just can't see how to proceed - any advice, much appreciated!
March 12th 2009, 02:04 PM
Plato

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

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

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

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

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

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

7. $R(a)$ _simp from 3

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

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

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

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

Now can you preceed?