in Mathematical Logic retagged by
11,692 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]$
in Mathematical Logic retagged by
by
11.7k views

7 Comments

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.
2
2
Can the answer to this be "∀x ∃y (teacher (x) ∧ student (y) ∧ likes (y,x))" ?
0
0
Use ^ for there exist(∃) and use -> for all(∀).
4
4
@rambo1987  No, this says, “every x is a teacher and….”
We need to say, “ if x is a teacher then...”
1
1

A general rule of thumb:

Universal Quantifier $(\forall x)$ goes  along with with implication $(\rightarrow)$

Example: $\forall x (P \rightarrow Q)$

Existential Quantifier $(\exists x)$ goes  along with with conjunction $(\land)$

Example: $\exists x (P \land Q)$

1
1
Very subtle difference between option b and c but it changes the whole meaning.

If this were to be MSQ I am sure I would have marked both b and c
1
1

 ∃(x)∀(y)P(x,y) --> There is someone who is for everyone.

(x)(y)P(x,y) -->for everyone there is someone.

∃(x)∃(y) P(x,y) -->there exist x and there exist y for which P(x,y) is true.

(x)(y)P(x,y) --> for every x and for every y P(x,y) is true.

0
0

4 Answers

68 votes
68 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. 

edited by

4 Comments

And in case of B if there is no student then due to AND operation it will give false. Please confirm if my interpretaion is correct? @junk_mayavi.
0
0
good question
0
0

@the.brahmin.guy 

You assumed Roll No. 10 likes every teacher but it won't be case that this is always true. We also have to account for the case that no student like every teacher. When this happens option B would still be true and option C would fail in this case 

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

3 Comments

best explanation
0
0
Thanks. This method is good to differentiate.
0
0
For option C you can use ∀(𝑥)∃(𝑦) in place of ∃(𝑦)∀(𝑥) because they are logically equivalent. Then your statement would be the same for both B and C.
0
0
1 vote
1 vote

 

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

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