The Gateway to Computer Science Excellence
+28 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]$
in Mathematical Logic by Boss (17.5k points)
retagged by | 3.3k views
option C. ∃(y)∀(x)[teacher(x)→[student(y)∧likes(y,x)]]

                There is a student y for which every x, if x is a teacher then student y likes teacher x.

option D. ∀(x)[teacher(x)∧∃(y)[student(y)→likes(y,x)]]

                For every teacher x and some y, if y is a student then he likes teacher x.
Can the answer to this be "∀x ∃y (teacher (x) ∧ student (y) ∧ likes (y,x))" ?
Use ^ for there exist(∃) and use -> for all(∀).

2 Answers

+43 votes
Best answer

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. 

by Active (2.6k points)
edited by
Yes. Option C is wrong because it says that all teachers are liked by the SAME student.
please provide the statement equivalent to option D
sir , i did not understand one thing how to think that " when to use "implication" and when to use "AND" in above type of question...?
When we want to say something "EXIST" we must not use implication but AND, because implication is true even if nothing exist.
* note - gateforum booklet have provided answer c which is wrong.
awesome explanation.. superb.
what if X is not a teacher .. then it is also like by student . Then
Sir, I have an argument,

A) is not answer bcoz it says that if y is a student than all y "for which"

student(y) is true must like all teacher. Is this valid argument for rejecting A)???
@rahul jain25 ya right

and option c->the given statement  and option b <-> the given statement ..
Let's say there are 30 students in a class and roll no. 10 likes every teacher, now Roll no. 10 is "some" student of that class and he/she likes every teacher so by that thought process isn't Option C also correct @Arjun Sir ?

or does the question say like if there are 3 teachers then Teacher1 is liked by roll no. 5, Teacher2 is liked by Roll No. 10 and Teacher3 is liked by Roll No. 15

or Option C is also correct but Option B is stronger/better answer ?

"Every teacher is liked by some student" is equivalent to If (for all people ) person is the teacher then liked by some student.

Option B say exactly that. But Option D says (for all people ) person is the teacher and liked by some student.

@Rahul Jain25  option A is wrong because with option A, there can arise a chance that even if there is no student, statement can give true. We have at least one student which likes a teacher. in A, we can have a case of no student at all (false -> anything = true )
0 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.

by Active (3.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,311 answers
105,029 users