edited by
10,352 views
42 votes
42 votes

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

  1. $\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)$
  2. $\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)$
  3. $\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)$
  4. $\forall x \exists y P\left(x, y\right)\implies \exists y \forall x P\left(x, y\right)$
edited by

5 Answers

Best answer
60 votes
60 votes

(A) is the answer

  1. 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.
     
  2. 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.
     
  3. 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
     
  4. 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.
edited by
12 votes
12 votes

(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

edited by
11 votes
11 votes

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

8 votes
8 votes

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) 

Answer:

Related questions

62 votes
62 votes
7 answers
1
3 votes
3 votes
3 answers
2
ParthPratim asked Nov 3, 2022
969 views
I have been trying to solve the question GATE CSE 2008 Question.Are the following two representations logically equivalent ?$\beta \rightarrow (\exists x, \alpha (x))$$\e...
50 votes
50 votes
9 answers
3
Ishrat Jahan asked Nov 3, 2014
14,635 views
Let $P(x)$ and $Q(x)$ be arbitrary predicates. Which of the following statements is always TRUE?$\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\r...