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?

  • $\begingroup$ 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? $\endgroup$ – Peter Smith Apr 22 '17 at 14:44
  • 1
    $\begingroup$ @Javiator You say propositional logic but this looks like predicate logic. $\endgroup$ – Bram28 Apr 22 '17 at 15:15
  • $\begingroup$ 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}$ $\endgroup$ – Mauro ALLEGRANZA Apr 22 '17 at 15:46
  • $\begingroup$ The "general" formula for the case $n=3$ will be the conjunction of the three formulas above (for $i=1,2,3$). $\endgroup$ – Mauro ALLEGRANZA Apr 22 '17 at 15:48
  • $\begingroup$ @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. $\endgroup$ – Javiator Apr 23 '17 at 8:41

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})$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.