The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3.2k views

Which of the following predicate calculus statements is/are valid?

  1. $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$
  2. $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$
  3. $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$
  4. $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$
asked in Mathematical Logic by Veteran (355k points)
retagged by | 3.2k views

2 Answers

+36 votes
Best answer
  1. The corresponding English meaning: If $P(x)$ is true for all $x$, or if $Q(x)$ is true for all $x$, then for all $x$, either $P(x)$ is true or $Q(x)$ is true. This is always true and hence valid. To understand deeply, consider $X = \{3,6,9,12\}$. For LHS of implication to be true, either $P(x)$ must be true for all elements in $X$ or $Q(x)$ must be true for all elements in $X$. In either case, if we take each element $x$ in $X$, either one of $P(x)$ or $Q(x)$ will be true. Hence, this implication is always valid.
    If still in doubt, let $P(x)$ mean $x$ is a multiple of $3$ and $Q(x)$ means $x$ is a multiple of $2$)
  2. The corresponding English meaning: If $P(x)$ is true for at least one $x$, and if $Q(x)$ is true for at least one $x$, then there is at least one $x$ for which both $P(x)$ and $Q(x)$ are true. This is not always true as $P(x)$ can be true for one $x$ and $Q(x)$ can be true for some other $x$ . To understand deeply, consider $X = \{3,6,9,12\}$. Let $P(x)$ be $x$ is a multiple of $9$ and $Q(x)$ be $x$ is a multiple of $6$. Now, LHS of implication is true, since $P(x)$ is true for $x = 9$, and $Q(x)$ is true for $x = 6$. But RHS of implication is not true as there is no $x$ for which both $P(x)$ and $Q(x)$ holds.  Hence, this implication is not valid.
  3. If for each $x$, either $P(x)$ is true or $Q(x)$ is true then $P(x)$ is true for all $x$ or $Q(x)$ is true for all $x$. Just one read is enough to see this is an invalid implication. Consider set {2,4,5}. Here every element is either a multiple or 2 or 5. But all elements are neither multiple of 2 nor 5.
  4. If there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $P(x)$ is true for all $x$ or $Q(x)$ is true for at least one $x$. This is clearly invalid as  LHS of implication becomes true if $P(x)$ is true for some $x$ and $Q(x)$ is not true for any $x$, but RHS will be false (if $P(x)$ is true for all $x$).
    A little modification to the statement is enough to make it valid:
    $$\exists (x) (P(x) \vee Q(x)) \implies \sim (\forall (x) \sim  P(x)) \vee \exists (x) Q(x)$$
    which means if there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then
    either it is not the case that $\sim P(x)$ is true for all $x$ (which means P(x)  is true for some $x$) or $Q(x)$ is true for some $x$.

Note
De Morgan's law is applicable in first order logic and is quite useful:

$$\forall(x)(P(x)) \equiv \neg \exists (x)(\neg P(x))$$

This is a logical reasoning statement which means if $P(x)$ is true for all $x$, then there can never exist an $x$ for which $P(x)$ is not true. This formula is quite useful in proving validity of many statements as is its converse given below:

$$\exists(x)(P(x)) \equiv \neg \forall (x)(\neg P(x))$$

answered by Boss (18.1k points)
edited by
0
for 2 nd option there exist some x i.e 64 which is divisible by both why we are saying there exist no x.considering the above example
0
We are always telling with respect to the considered set.
0
I dnt understand ..no 3 should be valid ..why invalid ?
0
There was some mistake in words- I have changed.

Basically for each x, either P or Q is true. So, overall for all x, we can't say P is true or Q is true. {2,4,5}. Here every element is either a multiple or 2 or 5. But all elements are neither multiple of 2 nor 5.
+1
ok .I got it now
0
Sir. I Think for option 4 explanation should be as-

Either px or qx is true for some x then either not for all x px is true or for some x qx is true.

Case 1 px is true for some x and qx is not true for any x. this makes lhs true and rhs also true.because px is true for some x (for all x it cn be false too)  and negation makes /forall p(x) true and rhs true too.

Case 2 But if px is true for all x and qx is not true for any x thn lhs would be true And rhs would b false. So Invalid
0
because px is true for some x (for all x it cn be false too) 

"can", "may" etc cannot be used to say a statement true or false. Here, when LHS is true RHS can either be true or false which makes the implication false. 

I guess you meant p(x) is true fir some x and p(x) is false for some x. Then the argument is correct. 

+1
Yes.if px is true for some x thn px is not true for some x. I used can bcz (if for all x px is true it will be true for some x too. And if px is true for some x then it may not be true for some x)

To show option 4 is invalid we need to take the case where px true for all x and qx not true for any x.
0
yes, because in order to show that $A \implies B$ is invalid, we have to take the case where $B$ is false (and A true).
+2
superb fantastic explanation.... cheers
0
Please suggest any study material to solve these type of questions generally.
0

You can see weblinks here but trick is to think and just think.

http://gatecse.in/mathematical-logic/

+3
Why scope of the ~ is not limited to x only?

∼(∀(x)) P(x)

In the given answer we ae taking complement to the P(x) also.So how do we know that where the scope of ~ ends?

By putting the brackets around the x,the scope of the ~ should be limited to the brackets only and it should not propagate to P(x) as brackets has higher proprity.

∼(∀(x)) P(x)

 = ∃ P(x)

@Arju sir.Please clarify?If we are taking complement of P(x) then why are we not moving to the Q(x)?
0
coooollllll
–1
Nice solution.All doubts are clear.Thanks gatecse .
+2

Although the correct answer is (A),
But still why at the bottom of page it is B?

Admins please resolve

0
@rahul I think that predicate and variables are bounded by the quantifiers.. If negation on any quantifier.. It has to be forwarded inside... Please reply and have u reached any conclusion for this?
+15 votes

$A \implies B$ in this implication we can say this is false, if we can show a situation where A is true but at the same time B is false.

In the 4th case : $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

To check validity we do the following : 

1st approach:

  • Assume LHS as true or (1) based on some condition.
  • Then try to make RHS false (0) on the same set of conditions as above.

Or,

2nd approach:

  • Assume RHS as false (0) and try to make LHS as true (1) on some common conditions.

if we can show anyone one of the above situation exists. Then implication 4 is false.

Using second approach:

in RHS assume all $Q(x)$ are false (0) and all $P(x)$ are true (1) such that RHS becomes false (0).

Based on these above condition if we look on the left hand side, we find that LHS side is true (1) since all $P(x)$ are true.

answered by Veteran (56.9k points)
edited by
0
Why scope of the ~ is not limited to x only?

∼(∀(x)) P(x)

In the given answer we ae taking complement to the P(x) also.So how do we know that where the scope of ~ ends?

By putting the brackets around the x,the scope of the ~ should be limited to the brackets only and it should not propagate to P(x) as brackets has higher proprity.

∼(∀(x)) P(x)

 = ∃ P(x)
0

Not of all $P(x)$ true is there exist some $P(x)$ that is not true.

What that means, universal quantifier is at least bound to it nearest predicate. No bracket does not mean we can put a NOT and change $\forall$ to $\exists$.

0
∼(∀(x))P(x)∨(∃(x))Q(x) is it similar to ∼(∀(x)P(x))∨(∃(x))Q(x)? coz it makes no sense in negating only quantifier and not he predicate associated with it


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,018 questions
45,509 answers
131,697 comments
48,741 users