What is the first order predicate calculus statement equivalent to the following? "Every teacher is liked by some student" The following notations are used: G(x) : x is a gold ornament S(x) : x is a student T(x) : x is a teacher likes(x, y) : x likes y P(x) : x is precious A. forall(x) teacher(x) -> (exists(y) student(y) ^ likes(y, x)) B. forall(x) (T(x) -> (exists(y) (S(y) ^ likes(y, x)))) C. exists(y) (forall(x) (T(x) -> (student(y) ^ likes(y, x)))) D. forall(x) (forall(y) (T(x) -> (S(y) -> likes(y, x))))
GATE 2005 · Discrete Mathematics · First Order Logic · easy
Answer: The correct translation is B: forall(x) (T(x) -> (exists(y) (S(y) ^ likes(y, x)))).
- Translate 'Every teacher' using universal with implication: 'Every teacher' = forall x (T(x) -> ...). The implication is correct here: we constrain the statement to teachers only; using conjunction would incorrectly assert every domain object is a teacher.
- Translate 'is liked by some student': 'Is liked by some student' means there exists at least one student who likes x. This is exists y (S(y) ^ likes(y, x)). Note the argument order: y likes x is likes(y, x); 'x is liked' is passive so y is the liker.
- Combine to form the complete FOL statement: Full statement: forall x (T(x) -> (exists y (S(y) ^ likes(y, x)))). Matching the options: this is option B.