Translating english to predicate logic

[maxsthekat]

Homework Statement

I've been given a problem: "C(x,y) is x and y have chatted over the internet. The domain is students in a class. Express there are two students who combined have chatted with all of the students in the class".2. The attempt at a solution
I think this is the correct answer, but I'm not certain.

\exists x,y \forall z (C(x,z) \wedge \neg C(y,z)) \vee (C(y,z) \wedge \neg C(x,z)) \vee (C(x,z) \wedge C(y,z))

The part I'm uncertain about is the last statement, C(x,z) ^ C(y,z). I think this states there exists an x and y, where x has spoken with z and y has spoken with z, but I could also see this as saying there is an x that has spoken with all z and there is a y that has spoken with all z.

Would anyone be willing to double check my work?

Thanks! :)

-Max

 

[ystael]

I think in the first disjunct you meant to write (C(x,z) \wedge \neg C(y, z)) rather than (C(x, z) \wedge \neg C(y, x)). Given that small correction, your formula is correct, but it is not the shortest possible. You wrote the large disjunction so that the three alternatives are mutually exclusive, but they need not be. If you allow your disjuncts to overlap, you can write a much shorter formula.

The part I'm uncertain about is the last statement, C(x,z) ^ C(y,z). I think this states there exists an x and y, where x has spoken with z and y has spoken with z, but I could also see this as saying there is an x that has spoken with all z and there is a y that has spoken with all z.

Your first thought is correct. When the quantifier \forall z lies outside the disjunction, it applies to the entire disjunction, not separately to each clause: there exist x and y such that, for each z, at least one of the three alternatives holds; but which holds can vary from z to z.

 

[maxsthekat]

Thanks for your help :) You were right, and I corrected the formula above to reflect what was meant.

Thinking about your suggestion of simplifying this based on the overlap, I think this should just be an disjunction of the students x and y have chatted with. As such, can I write this as:

\exists x,y \forall z (C(x,z) \vee C(y,z))

If I'm waaaay off, I'd appreciate any insight you'd care to share :)

Thanks again

-Max

 

[ystael]

You now have the simple correct answer.

 

[JSuarez]

If you want to state that the two students are distinct (that is, you want to rule out the possibility of just one chatted with all the others), you must add \lnot\left(x=y\right).