In (b), we found two wffs using no more than five connective symbols from those used in (a), even though the problem does not explicitly asks to use these connective symbols only. So, the question is whether we can use no more than four arbitrary unary or binary connective symbols.

But first, we will try to see whether we can use no more than four connective symbols from $\{\neg,\vee,\wedge\}$ . According to Example 1 and Exercise 1 of Section 1.6, we cannot hope to realize the majority rule using three (or less) connective symbols $\vee$ and $\wedge$ on sentence symbols or their negations. So, suppose we have a wff $\alpha$ representing $G$ that uses no more than four connective symbols from $\{\neg,\vee,\wedge\}$ . At least one of them has to be $\neg$ , as otherwise if all sentence symbols are assigned $T$ , so is $\alpha$ . Hence, $\alpha$ uses no more than three connective symbols from $\{\vee,\wedge\}$ . Then, $\neg\alpha$ represents the majority rule using no more than three connective symbols from $\{\vee,\wedge\}$ (and some number of negation symbols). Now, according to Exercise 16-A of Section 1.2 (which is an extra exercise stated on the website), we can find a formula $\phi$ tautologically equivalent to $\neg\alpha$ such that negation is applied to sentence symbols only. Moreover, according to our proof of the exercise, the transformation from $\neg\alpha$ to $\phi$ is carried out in such a way that the number of binary connectives does not increase (only the number of negations can change). Therefore, in this case, if $\alpha$ existed, $\phi$ would be a wff using no more than three connective symbols from $\{\vee,\wedge\}$ on sentence symbols and their negations and representing the majority rule, which is not possible. Hence, any $\alpha$ representing $G$ that uses connective symbols from $\{\neg,\vee,\wedge\}$ only has at least five of them.

The remaining question is then, whether there is a wff representing $G$ that uses no more than four unary and binary connective symbols some of which are not in the set $\{\neg,\vee,\wedge\}$ . The answer is positive, and all we need is to transform our previous expressions using “nand” and “nor”: $(A\vert(B\vee C))\wedge(B\vert C)$ and $(A\downarrow(B\wedge C))\vee(B\downarrow C)$ . Of course, these use some “exotic” binary connective symbols, and one can try to use four “standard” connective symbols from $\{\neg,\vee,\wedge,\rightarrow,\leftrightarrow\}$ , those we used in all initial definitions.

Another interesting (or, maybe, practical) question is whether we can use no more than four (or, maybe, five) connective symbols of two types only. That is, suppose, similar to the next section, that we can produce two types of devices (connective symbols) only, and we need to choose which ones to produce so that we can use the minimal number of them to represent $G$ . So far, in all our solutions with four and five connective symbols, we used three different types of connective symbols. At the same time, there are easy solutions using five connective symbols of two types: $(A\vert B)\wedge(B\vert C)\wedge(C\vert A)$ or $(A\downarrow B)\vee(B\downarrow C)\vee(C\downarrow A)$ . Again, one can try to use four connective symbols of two types to represent $G$ .