[logic]Give sample of 3-element set M so that M is not satisfiable, but every 2-element subset of M is satisfiable.

Question

This is the Exercise 7 in 《Logic for Computer Scientist》(Uwe Schoning)

Exercise 7: Give an example of a 3-element set M so that M is not
satisfiable, but every 2-element subset of M is satisfiable. Generalize your
example to n-element sets.

I am stuck in this question for a while. I intuitively thought it was easy, while it was not for me at least :(.

I think there may be something wrong in my understanding and this answer should help me a lot .

Thanks.

Answer 1

For $3$ elements: $$a,b,(\text{not }(a \text{ and } b))$$ For $n$ elements: $$a_1,a_2,\ldots,a_{n-1},(\text{not }(a_1 \text{ and } a_2 \text{ and }\ldots\text{ and }a_{n-1}))$$

Answer 2

After a few hours thinking regarding the answers of quasi & Fabio, here is my answer.

I am willing to find a "pattern" or "constraint" so that any set of formulas meeting this "pattern" will apply to the question.

My induction :

1. from the first premise " 3 element is not satisfiable", so there are the constraints : $(A\wedge{B}\rightarrow\neg{C}) \wedge (A\wedge{C}\rightarrow\neg{B}) \wedge (B\wedge{C}\rightarrow\neg{A}) $ . After equivalence, it shows the same thing : $A\wedge{B}\rightarrow\neg{C}$.

2. from the second premise " any 2 elements subset is satisfiable", so we have the constraints: $A\rightarrow{B}, B\rightarrow{C},C\rightarrow{A},B\rightarrow{A},C\rightarrow{B},C\rightarrow{A} i.e. (C\leftrightarrow{B})\vee(A\leftrightarrow{B})\vee(A\leftrightarrow{C})$

3. join the constraints from step1/step2, we finally get the constraint $A\wedge{B}\rightarrow\neg{C}$.

So for any formula set which met this constraint will apply to the question.

By testing the samples given by quasi&Fabio, it is valid solutions.