How would I go from DNF to a simplified formula with less symbols?

Question

Here's a DNF: $$(\neg A_1 \land \neg A_2 \land \neg A_3 ) \lor (A_1 \land \neg A_2 \land \neg A_3 ) \lor (\neg A_1 \land \neg A_2 \land A_3 ) \lor (\neg A_1 \land A_2 \land \neg A_3 )$$

And the problem states "Find a wff for this DNF in which there are at most 5 connective symbols."

I've spent the past hour distributing & using De Morgan's laws and I'm not really getting anywhere. Is there some obvious process that I am missing here?

Answer 1

1. The formula is true when at most one of $A_1, A_2$ and $A_3$ is true (and only then).
2. Hence it is the negation of 'At least two of $A_1, A_2$ and $A_3$ are true'.
3. Write 'at least two of $A_1, A_2$ and $A_3$ are true' with five connectives. There is a very natural way of doing this.
4. Now rewrite what you got above with four connectives.
5. Negate what you got on 4.

Answer 2

For reasons of space we shall represent the three entities $A_1,A_2,A_3$ by $a, b, c$, and their negations using the bar notation, $\bar a, \bar b, \bar c$.

$\small{\begin{align} & (\bar a\wedge\bar b\wedge \bar c)\vee(a\wedge\bar b\wedge\bar c)\vee(\bar a\wedge \bar b\wedge c)\vee(\bar a\wedge b\wedge \bar c) & \text{as given} \\ \iff & \bigl((\bar a\wedge\bar b\wedge \bar c)\vee(\bar a\wedge\bar b\wedge \bar c)\bigr)\vee(a\wedge\bar b\wedge\bar c)\vee(\bar a\wedge \bar b\wedge c)\vee(\bar a\wedge b\wedge \bar c) & \text{idempotent} \\ \iff & \bigl((\bar a\wedge\bar b\wedge \bar c)\vee(a\wedge\bar b\wedge\bar c)\bigr)\vee\bigl((\bar a\wedge\bar b\wedge \bar c)\vee(\bar a\wedge \bar b\wedge c)\vee(\bar a\wedge b\wedge \bar c)\bigr) & \text{commute and associate} \\ \iff & (\bar b\wedge \bar c)\vee\bigl((\bar a\wedge\bar b\wedge \bar c)\vee(\bar a\wedge \bar b\wedge c)\vee(\bar a\wedge b\wedge \bar c)\bigr) & \text{resolve} \\ \iff & (\bar b\wedge\bar c)\vee\Bigl(\bar a\wedge \bigl((\bar b\wedge \bar c)\vee(\bar b\wedge c)\vee(b\wedge \bar c)\bigr)\Bigr) & \text{distribute} \\ \iff & (\bar b\wedge\bar c)\vee\Bigl(\bar a\wedge \bigl(\bar b\vee(b\wedge \bar c)\bigr)\Bigr) & \text{resolve} \\ \iff & (\bar b\wedge\bar c)\vee\bigl(\bar a\wedge (\bar b\vee \bar c)\bigr) & \text{distribute and absorb} \\ \iff & (\bar b\wedge\bar c)\vee(\bar a\wedge \bar b)\vee(\bar a\wedge \bar c) & \text{distribute} \end{align}}$