GATE IT 2007 | Question: 21

Question

Which one of these first-order logic formulae is valid?

• A. $\forall x\left(P\left(x\right) \implies Q\left(x\right)\right) \implies \left(∀xP\left(x\right)\implies \forall xQ\left(x\right)\right)$
• B. $\exists x\left(P\left(x\right) \vee Q\left(x\right)\right)\implies \left(\exists xP\left(x\right)\implies \exists xQ\left(x\right)\right)$
• C. $\exists x\left(P\left(x\right) \wedge Q\left(x\right)\right) \iff \left(\exists xP\left(x\right) \wedge \exists xQ\left(x\right)\right)$
• D. $\forall x \exists y P\left(x, y\right)\implies \exists y \forall x P\left(x, y\right)$

Comments

Thanks @Manis :) 

---

How do you come up with these examples for solving them. Don't say practice even after lots of practice I start from ground 0 whenever solving a new question of this type.

Is there some trick or some example which works for most cases?

Please help.

---

Same happening with me.  Is there a formal way to go about questions?

Please help.

Answer 1

(A) is the answer

• A. LHS: For every x, if P holds then Q holds
  RHS: If P(x) holds for all x, then Q(x) holds for all x.
  LHS implies RHS but RHS does not imply LHS.
   
• B. LHS: An x exist for which either P(x) is true or Q(x) is true.
  RHS: If an x exist for which P(x) is true then another x exist for which Q(x) is true.
  LHS does not imply RHS, but on RHS if we change ∃xP(x) to ~∃xP(x), implication becomes TRUE.
   
• C. LHS: There exist an x for which both P(x) and Q(x) are true.
  RHS: There exist an x for which P(x) is true and there exist an x for which Q(x) is true.
  LHS implies RHS but RHS does not imply LHS as the 'x' for P and Q can be different on the RHS
   
• D. LHS: For every x, there exist a y such that P(x, y) holds.
  RHS: There exist a y such that for all x P(x, y) holds.
  Here RHS implies LHS but LHS does not imply RHS as the y on LHS can be different for each x.

Comments

in option c), LHS implies RHS, RHS needs not to imply LHS.

The argument is valid if

1. All premises are true then the conclusion must be true.
2. If at least one of the premises is false then the conclusion must be false.

The argument is invalid if

1. All premises are true but the conclusion is false.

 

 

---

If in Option B , We convert ƎP(x) on RHS to ~ƎP(x) (Means negate), then I think in Option B BiImplication will be satisfied between LHS and RHS. , Please do this exercise.

---

@Blackcode00 

yes correct 

Answer 2

(A) LHS= if anyone is robbed then he is searched

RHS= if anyone are robbed then anyone is searched'

Both are not true.

(B) LHS=there is some wrestler or batminton player

RHS= if there is some wrestler then there also have some batminton player

Both are not similar

(C)LHS=there is some player who is wrestler and batminton player

RHS=there is a player who is wrestler and there also has a batminton player

it is true in unidirection but not both direction. like

∃x(P(x) ∧ Q(x)) => (∃xP(x) ∧ ∃xQ(x))

(D)LHS= For all wrestler there is a trainer

RHS= There is same trainer for all wrestler

not true always

Comments

Lets give an example of a class of boy (for ease of writing) students.

$P(x) : x \text{ performs well}$

$Q(x): x \text{ gets medal}$

$\forall x, P(x) \implies Q(x)$

means,

• For everyone belonging to class, if he performs well then he gets medal
• Equivalently, if anyone in the class performs well, then he gets a medal

$(\forall x P(x)) \implies \forall x Q(x)$

means,

• If everyone in the class performs well then each of them gets a prize.
• This is different from the previous as now the medal requires a good performance from everyone in the class and not individual performance. 
• Still the first statement do imply the second one because in first case we say that anyone performing well is given a medal. So, even if everyone performs well, every one will get medal.

---

@Arjun sir....∀x, P(x)⟹Q(x) and ∀x( P(x) ⟹ Q(x) ) are same ?? I think yes.

---

option d can be termed as x+y=0. Domain is the real number

LHS: for all x there exist some y which makes x+y=0  is true(1) always as

( x=2,y=-2,x+y=0

x=3,y=-3,x+y=0 and so on.)

RHS: for some y there exist all x which makes x+y=0  is not true(0).

as for (y=2, there is only one value of x=-2 which makes X+Y=0 but other than x=2 , everything else will not make X+Y=0.)

So (LHS=1)->(RHS=0) makes it invalid

Answer 3

For the options, I treat x for boy, y for girl.
P(x) means, he flirts. Q(x) means he loves.
P(x,y) means the boy & girls both are in relationship.     (Prefer this trick or build your own example)

Option A:   For all boys ( a boy flirts -> he loves too)      ->     (all boys flirts -> all boys love)      It is valid.
Option B:   For Some boys ( either flirts or loves)    ->   ( if a guy flirts he loves too)      No way, its not valid.
Option C:   For Some boys ( both flirts and loves)   < ->   ( a guy is there who flirts & a guy is there who loves)    I think it should be ->  not  <->            Hence not valid.
Option D:  For all boys there are some girlfriends -> there are some girls for which all the boys are boy friends.   (Not valid.)

Comments

How can Implication and logical implication be interchanged? They are different operators right?

I mean, => is "logically implies" and <=> is equivalence. Where am I wrong?

---

if implication (->) is true  for all cases then it converted to logical implication (=>) likewise Bi-implication (<->) converted to equivalence(<=>)

Answer 4

option A

Let P(x)=All are multiple of 4

     Q(X)= All are even numbers

if a ∈ P(X) then a must  ∈ Q(X)