The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
2.6k views

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]$
asked in Mathematical Logic by Boss (16k points)
retagged by | 2.6k views
+2
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.
0
Can the answer to this be "∀x ∃y (teacher (x) ∧ student (y) ∧ likes (y,x))" ?
0
Use ^ for there exist(∃) and use -> for all(∀).

2 Answers

+39 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. 

answered by Active (2.6k points)
edited by
+17
Yes. Option C is wrong because it says that all teachers are liked by the SAME student.
+1
please provide the statement equivalent to option D
+1
Added...
+1
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...?
+17
When we want to say something "EXIST" we must not use implication but AND, because implication is true even if nothing exist.
+1
* note - gateforum booklet have provided answer c which is wrong.
+1
awesome explanation.. superb.
–1
what if X is not a teacher .. then it is also like by student . Then
0
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)???
0
@rahul jain25 ya right
0
∀(x)[teacher(x)→∃(y)[student(y)∧likes(y,x)]]=∀(x)∃(y)[teacher(x)→[student(y)∧likes(y,x)]]

and option c->the given statement  and option b <-> the given statement ..
+1
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 ?
0

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

+3
@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.

answered by Active (1.2k points)
Answer:

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
49,535 questions
54,122 answers
187,321 comments
71,039 users