edited by
17,071 views
72 votes
72 votes

Consider the first-order logic sentence $F:\forall x(\exists yR(x,y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$?

  1. $\exists y(\exists xR(x,y))$
  2. $\exists y(\forall xR(x,y))$
  3. $\forall y(\exists xR(x,y))$
  4. $¬\exists x(\forall y¬R(x,y))$
  1. IV only
  2. I and IV only
  3. II only
  4. II and III only
edited by

8 Answers

Best answer
146 votes
146 votes

Ans is B.

1st Method: $F:\forall x(\exists yR(x,y))$

Take option 4: $¬\exists x(\forall y¬R(x,y))$

$\quad \equiv \forall x(\exists yR(x,y))$  $($Since we know that $\neg \forall x \equiv \exists x $ And  $ \neg\exists x =\forall x )$


F:  For all girls there exist a boyfriend. (Given)
( $x$ for girl and $y$ for boys)

  1. There exists some boys who have girlfriends.  (True)
  2. There exists some boys for whom all the girls are girlfriend. (False)
  3. For all boys there exists a girlfriend. (False)
  4. For all girls, there exists a boyfriend (True) (Same as given statement $F$)
edited by
81 votes
81 votes

 

Solution.

  1. $\forall x\exists y$$R(x,y)$ $\rightarrow$$\exists y\exists x$$R(x,y)$     True
  2. $\forall x\exists y$$R(x,y)$ $\rightarrow$$\exists y\forall x$$R(x,y)$     False
  3. $\forall x\exists y$$R(x,y)$ $\rightarrow$$\exists x\exists y$$R(x,y)$     False
  4. $\forall x\exists y$$R(x,y)$ $\rightarrow \neg \exists x(\forall y\neg R(x,y))$

                                    $ \rightarrow \forall x\exists yR(x,y)$   True

So, I and IV are only true.

Answer is option B.

edited by
20 votes
20 votes

so B is the ans.

14 votes
14 votes

Here is a very simple method using which we can solve this type of problems easily.

Given F: $\forall$x($\exists$yR(x,y))

Let the Domain of x be (1,2) and y be (1,2)

Then above expression F can be rewritten as

F : ( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) for all x there must exist some y such that R(x,y) is true.

Now questions asks for which of the expressions are implied by this means given an expression E, is F$\rightarrow$E a tautology ?

Let's consider options one by one.

(I)$\exists$y ($\exists$xR(x,y))

 Considering above domains of x and y we can rewrite them as

( (R(1,1) v R(2,1) ) v ( R(1,2) v R(2,2) )

Now is this expression implied by F? means

is ( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) $\rightarrow$ ( (R(1,1) v R(2,1) ) v ( R(1,2) v R(2,2) ) a tautology?

Yes, it is absolutely a tautology because this implication will only be false when the antecedent is true and the consequent is false and you can check the above expression, it will never happen. So this is implied expression.

(II)$\exists$y($\forall$R(x,y))

   This can be rewritten as

( (R(1,1) ^ R(2,1) ) v ( R(1,2) ^ R(2,2) ) ) for some y there must exist all x such that R(x,y) is true.

is this implied by F?

( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) $\rightarrow$ ( (R(1,1) ^ R(2,1) ) v ( R(1,2) ^ R(2,2) ) ) a tautology?

This implication can be false when R(1,1) is true, R(2,2) is true and R(1,2) is false and R(2,1) is false.So, this is not implied expression.

(III)$\forall$y($\exists$xR(x,y)) can be rewritten as

( (R(1,1) v R(2,1) ) ^ ( R(1,2) v R(2,2) ) ) for all y there must exist some x such that R(x,y) is true.

is  ( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) $\rightarrow$ ( (R(1,1) v R(2,1) ) ^ ( R(1,2) v R(2,2) ) ) a tautology?

This implication can also become false when only R(1,1) and R(2,1) are true. So, this is also not implied expression.

(IV) $\sim\boldsymbol{ \exists x(\forall y \sim R(x,y))}$ The expression in bold is just the complement of the Given F. and so this option looks like $\sim$( $\sim$ F) which is equal to F. and so this is trivially implied by F.

So, answer is (I) and (IV).

Answer:

Related questions

29 votes
29 votes
8 answers
1
48 votes
48 votes
10 answers
2
37 votes
37 votes
6 answers
3
gatecse asked Sep 15, 2014
6,528 views
Consider the statement "Not all that glitters is gold”Predicate glitters$(x)$ is true if $x$ glitters and predicate gold$(x)$ is true if $x$ is gold. Which one of the ...