General Question

Mariah's avatar

Predicate logic: is this notation correct?

Asked by Mariah (19103 points ) August 30th, 2012

Hey jellies,

I’ve got some homework on predicate logic and I’m wondering if I’m doing it right. Please don’t give me any answers, I’m just unsure about my syntax, basically.

I’m supposed to be translating English sentences into quantifiers. Here’s an example:

There is a student in the calculus class who is neither a math major nor a freshman.

I first defined my universe as being the calculus class, and a predicate P(s, c, m) as “student s is in class year c and majors in m.”

Then I translated the sentence like so:

∃s ¬(P(s, freshman, m) V P(s, c, math))

Which in my head reads “There exists a student s for whom is is not that case that student s is a freshman majoring in m or student s is in class year c majoring in math.”

But I’m thinking this isn’t right because you can’t just leave certain parameters in the predicate as variables to indicate that they can be anything (for example, in P(s, freshman, m) I was trying to indicate that the only parameter that matters/is known about the student is that he is a freshman).

Some pointers?

Observing members: 0 Composing members: 0

6 Answers

gasman's avatar

First, I’d say the phrase “neither X nor Y” should be translated as “not-X and not-Y” =
¬X ∧ ¬Y
rather than “not (X or Y)” =
¬(X V Y).
They are equivalent by DeMorgan’s theorem, but that’s an additional step.

As for your main question about using variables vs. constants, I don’t know predicate logic in this context. You could try formulating it as something like, “For all classes c there exists an s such that not P(s, c, math) etc. but that might be wrong. Can’t find it at Wikipedia or Wolfram mathworld. I’d work from examples given in your reading material.

SavoirFaire's avatar

First, I am going to disagree with @gasman about the translation of “neither x nor y.” Since you are just translating from English to predicate logic, there are no steps. It’s not like you have to write it one way and then transform it for your translation. Moreover, we cannot know which translation is easier to work with in the absence of a proof situation. Thus there is no place for talk of steps yet.

As ¬(x v y) is a more literal translation of the English, one could argue that it is more correct for your current purposes. This is, however, largely a matter of personal preferences. Unless your professor has expressed a distinct preference for one translation over the other, it is unlikely to matter. There is a symbol for “neither/nor,” by the way, but that’s often saved for higher level courses.

Second, are we to take it that you get to define your own predicates for this assignment? If so, you have been far too hard on yourself by inventing a three-place predicate. Define three one-place predicates instead and I bet you’ll find the exercise much simpler to complete. This will also some another problem, which is that you’ve only quantified one variable in your example. A three-place predicate calls for three quantifiers (which is why you’re running into your constants/variables problem).

Finally, I’m wondering what book/system you are using. It is typical for “a” through “v” to be reserved as constants, leaving “w” through “z” as variables. Some systems make “v” or even “u” variables to allow for greater complexity, but I’ve never seen a system go all the way back to “s” (and certainly not “c”). Were you told you could use whatever you wanted as a variable or constant so long as you were clear about what was what when defining your universe?

Mariah's avatar

Thanks guys. I ended up changing my answer to something that I know is right, even if it’s not as “elegant” a solution. That is,

Define the universe as the calculus class.
F(x) = x is a freshman
M(x) = x is a math major

∃x ¬(F(x) V M(x))

@SavoirFaire, I was trying to use the three-place predicate mainly because this problem is just part C of parts A-E all revolving around the members of this calculus class, their class years, and majors. I wanted to define one predicate to use for all parts of the question to make my solutions more concise, but it was just confusing the heck out of me. This works.

gasman's avatar

“A little learning is a dangerous thing.” Sorry – next time I won’t even try to guess…

SavoirFaire's avatar

@gasman It was a fine guess. And like I said, a lot of it is a matter of preference since—as you mentioned—the two formulations are logically equivalent.

@Mariah I think you’ll find that three-place predicates are only useful for three-place relations, just as two-place predicates are only useful for two-place relations. If you want to say Jim is taller than Carol, you would use a two-place predicate because being taller than is a relationship that holds between two things:

Let:

Txy = x is taller than y
c = Carol
j = Jim

Tjc

Similarly, if you wanted to say that Jim is between Carol and Susan, you would use a three-place predicate because being between is a relationship that holds among three things:

Let:

Bxyz = x is between y and z
c = Carol
j = Jim
s = Susan

Bjcs

Alternatively, if you’d like the formula to visually represent the physical ordering rather than the linguistic ordering, you could define B differently:

Let:

Bxyz = y is between x and z
c = Carol
j = Jim
s = Susan

Bcjs

This is again a matter of personal preference. The point, though, is just that predicates are most effective when their definitions can be easily grasped. I applaud you for thinking about elegance, but I’m not sure how much elegance there can be with an awkward predicate.

By the way, your formula looks good. If you wanted to leave your universe more open, however, you could have done the following:

Let:

Cx = x is a student in the calculus class
Fx = x is a freshman
Mx = x is a math major

(∃x)(Cx & ¬(Mx v Fx))

LostInParadise's avatar

It might make more sense to set up the predicates as having two values. You originally introduced variables for class and major, which suggests another way of setting up the predicates. Let M(s,m) mean student s majors in m. Let C(s,c) mean that student s is in class c. Then we could have:

(∃s ∃c ∃m) M(s,m) & C(s,c) & ¬(equals(m,math) V equals(c,freshman))

If we want to allow for the possibility that the student has not yet declared a major, then we could write:
(∃s ∃c) C(s,c) & ¬(M(s,math) V equals(c,freshman))

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther