Is there a simplifying algorith m for a formula in Disjunctive Normal Form?

Question

Apologies if this question has been asked before. Please point me to it. I could not find it.

Given a propositional formula which is Disjunctive Normal Form, is there an algorithm which outputs an equivalent formula which uses a minimal umber of connectives? The connectives in the output can only be those in $\{ \lnot, \lor, \land \}$.

It is the exclusion of $\implies $ and $\iff$ that makes me think there could be such an algorithm.

---

In an Exercise in Enderton's A Mathematical Introduction to Logic, I am required to find a wff that is equivalent to $ ( \lnot p \land \lnot q \land \lnot r ) \lor ( p \land \lnot q \land \lnot r ) \lor ( \lnot p \land q \land \lnot r ) \lor ( \lnot p \land \lnot q \land r ) $ in which connective symbols ($ \lnot, \lor $ and $\land$ only) occur in less than $5 $ places.

Answer 1

I've found the answer to the question in Enderton thought I'd put it in here.

The formula essentially represents a case of "disagreeing" with the majority. That is return true if a majority of $p, q, r$ are false and vice versa. So we can consider the formula

$$ \lnot ( (p \land q) \lor (p \land r) \lor (q \land r) ) $$

which will be false when two or more of $p, q, r$ is true and true when at least two of $p, q, r$ is false.

Now I applied the distributive law to the sub-formula $(p \land q) \lor (p \land r) $ to obtain the logically equivalent formula

$$ \lnot ( (p \land (q \lor r)) \lor (q \land r) ) $$

which has not more than $5$ of the logical connectives allowed.