Section 1.5: Problem 1 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Let be the following three-place Boolean function.
(a) Find a wff, using at most the connectives , , and , that realizes G.
(b) Then find such a wff in which connective symbols occur at not more than five places.
(a) Using the disjunctive normal form, .
(b) The meaning of this formula is “no more than one is true”, in other words, this corresponds to the “minority connective”. Currently we use 20 connective symbols. One way to rewrite this wff is to join some parentheses: , but still 9 connective symbols. If we try something like then we have 11 connective symbols. Another idea is to express it as the negation of the majority rule: . By doing this, we already have 6 connectives only, and we can further use the distribution law: . Now we have only 5 connective symbols.
We could have also obtained the same expression in a different way. The majority rule, which is the opposite to the function above, can be expressed as “either and are both true, or and at least one of and must be true”. Using a similar interpretation of the majority rule “one of and must be true, and either they are both true or is true”, we can obtain another wff for , namely, , which is, basically, the previous one with all sentential symbols and interchanged.
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 . 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 and on sentence symbols or their negations. So, suppose we have a wff representing that uses no more than four connective symbols from . At least one of them has to be , as otherwise if all sentence symbols are assigned , so is . Hence, uses no more than three connective symbols from . Then, represents the majority rule using no more than three connective symbols from (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 tautologically equivalent to such that negation is applied to sentence symbols only. Moreover, according to our proof of the exercise, the transformation from to 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 existed, would be a wff using no more than three connective symbols from on sentence symbols and their negations and representing the majority rule, which is not possible. Hence, any representing that uses connective symbols from only has at least five of them.
The remaining question is then, whether there is a wff representing that uses no more than four unary and binary connective symbols some of which are not in the set . The answer is positive, and all we need is to transform our previous expressions using “nand” and “nor”: and . Of course, these use some “exotic” binary connective symbols, and one can try to use four “standard” connective symbols from , 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 . 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: or . Again, one can try to use four connective symbols of two types to represent .