in Mathematical Logic edited by
12,199 views
64 votes
64 votes

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)$
in Mathematical Logic edited by
by
12.2k views

4 Comments

@Deepak Poonia sir can we say like this?

0
0

@samarpita Yes, Correct.

0
0

@This_is_Nimishka make RHS false and try to make LHS true . if you are able to make LHS true then it is not valid else it is valid.

0
0

4 Answers

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

Correct Answer: $A$

edited by

4 Comments

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

@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

 

1
1
26 votes
26 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.

edited by
by

3 Comments

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

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

3
3
∼(∀(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
2
2
1 vote
1 vote

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 

1 comment

Can you please elaborate a bit more on why c is not valid.
0
0
0 votes
0 votes
A is correct as its the rule of distribution of quantifiers

B is incorrect as can be seen by translating the propositions

C is invalid and its correct rule is mentioned in option A

D is invalid and its correct version should have tautological equivalent instead of tautological implied.
Answer:

Related questions