0
$\begingroup$

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?

$\endgroup$
8
  • $\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$ Commented Apr 22, 2017 at 14:44
  • 1
    $\begingroup$ @Javiator You say propositional logic but this looks like predicate logic. $\endgroup$
    – Bram28
    Commented Apr 22, 2017 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$ Commented Apr 22, 2017 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$ Commented Apr 22, 2017 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$
    – Said Savci
    Commented Apr 23, 2017 at 8:41

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .