Question 4. Some students from a large class like ours are lined up left to righ

Question

Question 4. Some students from a large class like ours are lined up left to right. You may assume at least two students are in the line. Translate each of the following assertions into predicate formulas with the set of students in the class as the universe of discourse. The only predicates you may use are: ? equality between students, written x = y, and ? F(x, y), defined to mean student x is somewhere to the left of student y in line. For example, in the line CDA, both F(C, A) and F(C, D) are true. On the contrary. F(D,C). F(B, A), and F(B, B)are all false. Once you define a formula for a predicate below, you can and should use that predicate in further formulas. We'll start you off with this definition of 1NLINE(x) : 3y.(F(x,y) V F(y. x)) (which you can now use). This predicate says x is in the line if and only if there is some person y who is either to the left or to the right of x in line. (a) LEFTMOST(x): Student x is leftmost in line. (b) SUCCESSOR( x, y): Student x is immediately to the right of student yin line. (c) SECOND(x): Students is second from the left in line. (d) MIDDLE(x): Student .r is in the middle (i.e., not at either end) of the line.

Explanation / Answer

(a). LEFTMOST(X): “Student x is the left most in line” is converted to Predicate as follows:

Means that , all elements should be right of the X OR there should not be any element which is the left of X.

                LEFTMOST(X): For all Y, F(X,Y)

                                                OR

                LEFTMOST(X): Not for some Y, F(Y,X)

(b). SUCCESSOR (X,Y): Student X is immediately to the right of student yin line.

Implies that there should not be any element which is the right of Y and left of X.

SUCCESSOR (X,Y): Not for some Z (F(Y,Z)^F(Z,X))

(c). SECOND(X): Students is second from the left in line.

There should be an element which the LEFTMOST i.e X is not LEFTMOST and LEFTMOST is only element which is LEFT of X i.e there is no element except LEFTMOST which is LEFT of X.

                SECOND(X): For some Z LEFTMOST(Z)^F(Z,X)^Not for some Y(Y,X)

(d). MIDDLE(X): Student X is in the middle (i.e., not at either end) of the line.

Means there should be at least one element that is the left of X and at least one element for which X is the left element.

                MIDDLE(x): ( For some Y, F(Y,X) ^ For some Z, F(X,Z))    

                                                                OR

                MIDDLE(X): For some Y , Z(F(Y,X)^ F(Z, X))

  

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.