Notation in propositional calculus

I'm trying to solve some exercises from my text book about mathematical logic. Currently, I'm working on exercises about propositional calculus and I'm having some difficulties with the notation. I understand the problem and I know how to solve it, but I don't know how to write it down formally.

I have the following problem from my text book.

Let $\{1,...,n\}$ represent the students in a class. Each two students of the class have a preference to work together in a group or not.

1. Construct for every $n$ a formula $\phi_n$ that is satisfied by the interpretation $I$ iff for each student there exists another student with whom the student does not want to work together in a group.

My idea so far was: For each pair $i,j$ of students, let $X_{i,j}$ denote a variable with $I(X_{i,j})=1$ iff students $i$ and $j$ want to work together in a group.

I think, I now have to express (here in predicate logic) $\forall i \in \{1,...,n\} \exists j \in \{1,...,n\} : \lnot X_{i,j}$ (i does not want to work with j)

How can I do this?

• To be honest, I think the question (the textbook's question as you state it) is rather badly phrased. Can I ask which book this is? Commented Apr 22, 2017 at 14:44
• @Javiator You say propositional logic but this looks like predicate logic. Commented Apr 22, 2017 at 15:15
• Consider the case $n=3$. Write the formula expressing the fact that for student $1$ there exists another student with whom the student does not want to work together in a group: $\lnot X_{12} \lor \lnot X_{13}$ Commented Apr 22, 2017 at 15:46
• The "general" formula for the case $n=3$ will be the conjunction of the three formulas above (for $i=1,2,3$). Commented Apr 22, 2017 at 15:48
• @PeterSmith It's the course book from the professor who teaches the course. It is German, so I had to translate in into English. I shortened some of the question, so it's probably my fault. Commented Apr 23, 2017 at 8:41

1 Answer

You're on the right track. So it would be something like this:

$$(\neg X_{1,2} \lor \neg X_{1,3} \lor ... \lor \neg X_{1,n}) \land (\neg X_{2,1} \lor \neg X_{2,3} \lor ... \lor \neg X_{2,n}) \land ... \land (\neg X_{n,1} \lor \neg X_{n,2} \lor ... \lor \neg X_{n,n-1})$$