1
$\begingroup$

Find an infinite set of (propositional logic) formula, $S$, which satisfies:

  • If you take any $2$ elements from $S$, they are satisfiable.
  • If you take any $3$ elements from $S$, they are unsatisfiable.

As an illustration, a finite set of formula $S' = \{a, b \land c, a \implies \neg b\}$ satisfies the conditions as:

  • Taking $a$ and $b \land c$, they are satisfiable with $a = 1$, $b = 1$, $c = 1$.
  • Taking $a$ and $a \implies \neg b$, they are satisfiable with $a = 1$, $b = 0$, $c = any$.
  • Taking $b \land c$ and $a \implies \neg b$, they are satisfiable with $a = 0$, $b = 1$, $c = 1$.
  • Taking three of them, they are unsatisfiable.

Credit to my professor, to be honest I haven't solved this.

$\endgroup$

closed as off-topic by JMP, ManyPinkHats, rhsquared, boboquack, Quintec Dec 9 '18 at 22:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – JMP, ManyPinkHats, rhsquared, boboquack, Quintec
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I am not too sure, but can anyone tell me whether this is off-topic, or seems to be a homework that should not be solved at puzzling.se? Thanks! $\endgroup$ – Omega Krypton Dec 9 '18 at 6:31
  • $\begingroup$ Now I'm not sure if this is off-topic or not. But this is just a puzzle my professor gave on the class (as exercise), and everyone may try to solve it. $\endgroup$ – athin Dec 9 '18 at 6:51
5
$\begingroup$

Imagine an infinite number of people standing in line all facing one way towards the finite end. So, the first person sees nobody, the second person sees just the first person, the third person sees those two, and so on.

Each person is either wearing a hat or not (who knew this was a hat puzzle?!). Each one claims:

I'm wearing a hat, and I see no more than 1 person wearing a hat.

It's possible for any pair of people to be telling the truth, with them and only them wearing a hat. But, no three of them can be all telling the truth, since whoever is furthest back in line must see the other two wearing hats.

I'll leave you the formal step of translating the people's claims into propositional formulas. What's important is that each person sees only finitely many people, so that each statement concerns only a finite number of variables and so is finite in length.

$\endgroup$
  • $\begingroup$ This is a really great and fascinating answer! $\endgroup$ – athin Dec 9 '18 at 8:26

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