retagged by
11,632 views
50 votes
50 votes

What is the first order predicate calculus statement equivalent to the following?

"Every teacher is liked by some student"

  1. $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$
  2. $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) ∧ \text{likes}\left(y,x\right)\right]\right]$
  3. $∃(y) ∀(x)\left[\text{teacher}\left(x\right) → \left[\text{student}\left(y\right) ∧ \text{likes}\left(y,x\right)\right]\right]$
  4. $∀(x)\left[\text{teacher}\left(x\right) ∧ ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$
retagged by

4 Answers

Best answer
68 votes
68 votes

Answer is (B). In simpler way we can say "If $X$ is a teacher then there exists some $Y$ who is a student and likes $X$".

(A) choice:  If $X$ is a teacher, then there exists a $Y$ such that if $Y$ is a student, then $Y$ likes $X$. 
(C) choice: There exist a student who likes all teachers.
(D) choice: Everyone is a teacher and there exists a $Y$ such that if $Y$ is student then $y$ likes $X$. Assuming one cannot be both student and teacher at same time, this just means, everyone is a teacher. 

edited by
6 votes
6 votes

We can easlily eliminate option A & D as $\exists$ with $\rightarrow$  and  $\forall$ with $\wedge$

now comes the most confusing part option B & C.

Let's take a counter example -

   Suppose we have 3 teachers ($x_{1}$, $x_{2}$ & $x_{3}$)  &  10 students ( $y_{1}$, $y_{2}$, $y_{3}$, $y_{4}$, $y_{5}$, $y_{6}$, $y_{7}$, $y_{8}$, $y_{9}$, $y_{10}$).

Now in option B outer for loop is x & inner for loop is y i.e for every value of x there will be multiple y. $\exists y$ is fixed in an particular iteration of x, not on all iteration of x.

for all x i.e $x_{1}$ $\rightarrow$ ($y_{2}, y_{3}, y_{4}$)   &   $x_{2}$ $\rightarrow$ ($y_{7}, y_{8}, y_{9}, y_{10}$)   &   $x_{3}$ $\rightarrow$ ($y_{1}, y_{2}, y_{5}, y_{6}$)

So, all of this implies Every Teacher is liked by Some students.( key point is this some is not same for all teacher)

 

Now in option B outer for loop is y & inner for loop is x, i.e - 

there exist some student at the beginning of the statement which says that this is talking about some fixed no. of students, Let's say ($y_{1}, y_{2}, y_{3}$)   &  ($x_{1}, x_{2}, x_{3}$)

now  $y_{1}$ $\rightarrow$ $(x_{1}, x_{2}, x_{3})$,   $y_{2}\rightarrow$ $(x_{1}, x_{2}, x_{3})$,    $y_{3}\rightarrow$ $(x_{1}, x_{2}, x_{3})$

So,this implies Some students like every teacher.

1 votes
1 votes

 

Always use ∧ with ∃  and  → with ∀ 

according to this

a-false

b-true

c-false

d- false

0 votes
0 votes

(D) states:  Everyone in the class must be a teacher and there should be at least one student who likes that teacher.

This is wrong.

(C) states:  There should be at least one student who likes all the teachers. This is wrong.

(A) might feel right because logically it states that if someone is a teacher there must be at least one student who likes him but due to implies , even if there is no teacher , the result would be true. Hence , this option is also wrong.

because in p-→ q

if p is wrong q’s value doesn't matter.

(B) is right.

Answer:

Related questions

34 votes
34 votes
4 answers
1
gatecse asked Sep 21, 2014
6,487 views
Let $P, Q,$ and $R$ be three atomic propositional assertions. Let $X$ denote $( P ∨ Q ) → R$ and $Y$ denote $(P → R) ∨ (Q → R).$ Which one of the following is a...
37 votes
37 votes
11 answers
2
52 votes
52 votes
8 answers
3
Arjun asked Sep 24, 2014
13,948 views
What is the logical translation of the following statement?"None of my friends are perfect."$∃x(F (x)∧ ¬P(x))$$∃ x(¬ F (x)∧ P(x))$$ ∃x(¬F (x)∧¬P(x))$$ ¬�...
43 votes
43 votes
8 answers
4
Kathleen asked Sep 21, 2014
8,806 views
Let $\text{ Graph}(x)$ be a predicate which denotes that $x$ is a graph. Let $\text{ Connected}(x)$ be a predicate which denotes that $x$ is connected. Which of the follo...