GATE CSE 1992 | Question: 92,xv

Question

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

• A. $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$
• B. $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$
• C. $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$
• D. $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

Comments

(∃(x)) (P(x) v Q(x)) => ~ (∀(x))P(x) v (∃(x))Q(x)

Given equation will be converted to this form (∃(x)) (P(x) v Q(x)) => (∃(x)) ~P(x) v (∃(x))Q(x) 

According to my intution:

If we make RHS as false:

For making RHS fase P(x) should be true  and Q(x) is false for one of the element of the domain.

So ~P(x) gives us false. For example Domain D: (a,b,c) here P(x) is true for all a,b,c and Q(x) is false for a so

(∃(x)) ~P(x) v (∃(x))Q(x) this will give us false.

Now on LHS if we try to make it true we can have Q(x) as true for b and it becomes true.

Whole equation becomes T=>F which is False so this equation is invalid

Please correct me if i am wrong. @Deepak Poonia can you please help me with the 4th statement intution:

---

YES ITS CORRECT

---

https://youtu.be/wzVFO4hyVfo?list=PLIPZ2_p3RNHidhFvyKH4U_VE1rFAyvG8U&t=7005

Answer 1

• A. 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$.
• B. 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.
• C. 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.$
• D. 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$

Comments

@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

 

​

---

i am also getting the answer A but i have used an arbitrary domain for it like{a,b,c,d,…….}

do you think taking a interpretation like you have for first option will always work because i understand that for proving something false you need a counter example but for proving something to be true you cannot say its true because it worked on 1 interpretaion whenever universal quantifier is used. i am talking about option A where you have used a certain interpretation with domain {3,6,9,12}.

please reply as i want to clear this doubt..

---

nice explaination

Answer 2

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

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)

---

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

---

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

---

@dd So does that mean we shouldn't apply negation to quantifiers without applying it on predicate. But here it was given with paranthesis that negation is applied only to Universal quantifier and when negation applied to quantifers then it's bit complicate to convert that FOL stmt into a sentence.

Answer 3

For brevity, I will write $P(x)$ as $P_x$

Let the domain of $x = \{1, 2\}$

Option A:

$(\forall x P(x) \lor \forall x Q(x)) \rightarrow \forall x (P(x) \lor Q(x))$

$=(P_1P_2 + Q_1Q_2) \rightarrow (P_1 + Q_1)(P_2 + Q_2)$

$=(P_1P_2 + Q_1Q_2) \rightarrow (P_1P_2 + Q_1Q_2 + P_1Q_2 + P_2Q_1)$

$=(P_1P_2 + Q_1Q_2)’ + (P_1P_2 + Q_1Q_2) + (P_1Q_2 + P_2Q_1)$

$=true$

$\therefore$ valid

Option B:

$(\exists x P(x) \land \exists x Q(x)) \rightarrow \exists x (P(x) \land Q(x))$

$=\{(P_1 + P_2)(Q_1 + Q_2)\} \rightarrow (P_1Q_1 + P_2Q_2)$

$=\{(P_1 + P_2)(Q_1 + Q_2)\}’ + (P_1Q_1 + P_2Q_2)$

$=P_1’P_2’ + Q_1’Q_2’ + P_1Q_1 + P_2Q_2$

$\therefore$ NOT valid

Option C:

$\forall x (P(x) \lor Q(x)) \rightarrow (\forall x P(x) \lor \forall x Q(x))$

$=  \{(P_1 + Q_1)(P_2 + Q_2)\} \rightarrow (P_1P_2 + Q_1Q_2)$

$= \{(P_1 + Q_1)(P_2 + Q_2)\}’ + (P_1P_2 + Q_1Q_2)$

$= P_1’Q_1’ + P_2’Q_2’ + P_1P_2 + Q_1Q_2$

$\therefore$ NOT valid

Option D:

$\exists x (P(x) \lor Q(x)) \rightarrow \neg (\forall x P(x) \lor \exists x Q(x))$

$=\exists x (P(x) \lor Q(x)) \rightarrow (\exists x \neg P(x) \land \forall x \neg Q(x))$

$= \{(P_1 + Q_1)(P_2 + Q_2)\} \rightarrow (P_1’ + P_2’)(Q_1’Q_2’)$

$= P_1’Q_1’ + P_2’Q_2’ + (P_1’ + P_2’)(Q_1’Q_2’)$

$=P_1’Q_1’ + P_2’Q_2’$

$\therefore$ NOT valid

 

Comments

Required Information:

FOL conversion to Propositional Form

$\forall xP(x) \equiv \{P(x_1) \land P(x_2) \land … \}, x_i \in \text{domain(}x)$

i.e., the conjunction of all propositions

 

$\exists xP(x) \equiv \{P(x_1) \lor P(x_2) \lor … \}, x_i \in \text{domain(}x)$

i.e., the disjunction of all propositions

---

Please tell how you are determining whether the statement is valid or not valid based on result....like for Op-A how is it valid and other options how it invalid . Rest process I have understood.

---

This is the most straight forward way to answer these type of questins without getting into formal proofs

Answer 4

 

learn this trick and according to this option A is correct 

u can answer this question within 5 sec 

 

Answer 5

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 6

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 

Comments

Can you please elaborate a bit more on why c is not valid.