6.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)$

retagged | 6.2k views
0

@Arjun sir please tell why option A is coming out to be correct ?

I am doubtful because I have read that the universal quantifier distributes over conjunction, but not disjunction, and the existential quantifier distributes over disjunction, but not conjunction.

Here in option A, universal quantifier distributes over disjunction.

+1
Option A is that or it's converse?
+1

@Niti Sethi The qs is asking for implication. What you're saying is  equivalence, which is proved by taking if and only if. In Rosen it's clearly given.

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))$$

Correct Answer: $A$

by
edited
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.
+1

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

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

+4
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
0
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?

+1
@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?
0
I'm unable to understand option C. Can anyone explain with different example? Thanks
0

@vijay_jr i will try to put a different perspective here:

let us assume there are 4 jobs:1,2,3,4 and 2 persons:p,q.

l.h.s of option c says, every job is completed by either p or q.

Here the aim is every job getting completed irrespective of who did it.

This becomes true even when a job can't be done by p but can be done by q.

r.h.s says, every job is completed by p or every job is completed by q.

This becomes true only when either p can do all jobs or q can do all jobs.

i will give a example : p can do jobs 1,2 and q can do jobs 3,4. Now l.h.s becomes true here.( because all jobs 1,2,3,4 are getting completed)and r.h.s becomes false( since neither p can do all jobs nor q can do all jobs).

since true-> false is false, option c is false.

or you can refer this answer

https://gateoverflow.in/39618/gate2016-2-27?show=39850#a39850

$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.

by
edited by
+1
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)
+3

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$.

+2
∼(∀(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

A. option is valid because $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$

LHS means that either for all values of x P(x) is true OR for all values of x Q(x) is true. On the RHS it may so happen that for some values of x P(x) is true and for the rest of the values Q(x) is true. Still then the whole of the RHS will be true as well as we can see that for the condition for which the LHS is true i.e., either for the whole of x P(x) is true or for whole of x Q(x) is true RHS is true . so we can say that $LHS \implies RHS$. so, A is valid

B. $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$

LHS means that if for even 1 value of x P(x) is true then $(\exists (x)) P(x)$ is true similar case can be considered for $(\exists (x))Q(x)$. But on RHS it says that there must exist at least one value of x such that both P(x) and Q(x) are true. so for all the true values of LHS RHS will not be true so not valid

C. $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$

On LHS it says that for all values of x (x is bounded by both P(x) and Q(x)) either P(x) is true or Q(x) is true. RHS says that for all the values of x either P(x) is true or Q(x) is true. Clearly you cannot replace LHS with RHS because it need not be the case in LHS that for all values of x P(x) is true or for all values of x Q(x) is true so not valid.

D.$(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

For this you can see that on the LHS P(x) is true when for all values of x P(x) is true but on RHS you will see that for the above condition RHS will give false value so it is not valid