Find 4 formulas. Each pair has exactly one common model. Three of them have no common models

Question

I want to find 4 formulas. Each pair of them must have exactly one common model. Three of them should not have any common models.

I really don't know how to start with this.

Answer 1

$I: ABC+ABC'+AB'C$

$II: ABC+AB'C'+A'BC$

$III: ABC'+AB'C'+A'BC'$

$IV: AB'C+A'BC+A'BC'$

For those not used to boolean algebra notation, that's:

$I: (A \land B \land C) \lor (A \land B \land \neg C) \lor (A \land \neg B \land C)$

$II: (A \land B \land C) \lor (A \land \neg B \land \neg C) \lor (\neg A \land B \land C)$

$III: (A \land B \land \neg C) \lor (A \land \neg B \land \neg C) \lor (\neg A \land B \land \neg C)$

$IV: (A \land \neg B \land C) \lor (\neg A \land B \land C) \lor (\neg A \land B \land \neg C)$

Here is how I got to this. For any pair of formulas, there should be a model that makes those two formulas true, but not any of the others. This requires $6$ distinct models:

\begin{array}{c|cccc} Model & I & II & III & IV\\ \hline 1 & T & T & F & F\\ 2 & T & F & T & F\\ 3 & T & F & F & T\\ 4 & F & T & T & F\\ 5 & F & T & F & T\\ 6 & F & F & T & T\\ \end{array}

Well, that sure looks like a truth-table, and indeed in a truth-table each row corresponds to a different model. So, how do we get at least $3$ rows in a truth-table? With at least $3$ variables. So, I am looking for:

\begin{array}{ccc|cccc} A & B & C & I & II & III & IV\\ \hline T & T & T & T & T & F & F\\ T & T & F & T & F & T & F\\ T & F & T & T & F & F & T\\ T & F & F & F & T & T & F\\ F & T & T & F & T & F & T\\ F & T & F & F & F & T & T\\ F & F & T & F & F & F & F\\ F & F & F & F & F & F & F\\ \end{array}

(note I just set all the statements to False for the two extra rows)

OK, and now you can just read off what the formulas should look like from this truth0table specification. For example, formula $I$ should be True just whenever all of $A$, $B$, and $C$ are true, or when $A$ and $B$ are True but $C$ is False, or when $A$ and $C$ are True but $B$ is False, giving you $ABC + ABC' + AB'C$ (or, in more traditional notation: $(A\land B\land C) \lor (A\land B\land \neg C) \lor (A\land \neg B\land C)$)

Answer 2

Here's another approach, less efficient than Bram28's (I use 4 propositional variables rather than 3) but maybe easier to see. Using propositional variables $p_1,p_2,p_3,p_4$, build a formula $\phi$ that is true if and only if exactly two of the four $p_i$'s are true. Then define sentences $\psi_i$ for $i=1,2,3,4$ to be $p_i\land\phi$. Any two of these $\psi$'s have exactly one common model, because to satisfy $\psi_i$ and $\psi_j$ you have to make $p_i$ and $p_j$ true and the other two $p$'s false. And no truth assignment can satisfy three of the $\psi$'s.