Both i) networks of digital-logic gates and ii) logical formulas realize Boolean functions. Many familiar gates correspond to familiar sentential connectives, such as '~', '/\', and '\/'.
Some sets of connectives, such as {'~', '/\'} and {'~', '\/'} are _complete_, in the sense that any Boolean function can be realized by a logical formula using only these connectives.
'M' is the ternary minority connective. 'Mpqr' is true iff a minority of 'p', 'q', and 'r', is true. 'F' is the nullary connective that is always false.
a) Show that {'M', 'F'} is complete.
Hint: Synthesize a set of connectives that you know is complete.
i) Synthesize '~' from {'M', 'F'}. ans: ~p |= =| ___ ___ ___ ___ ___
ii) Synthesize a useful nullary connective from {'M', 'F'}. ans: ___ |= =| ___ ___ ___ ___ ___
iii) Synthesize '/\' using one or more of the first four connectives. ans: p /\ q |= =| ___ ___ ___ ___ ___
b) Show that {'M'} is not complete.
Hint: Where does the sequence of steps in a) break down, and why does this stop you from going further?
i) Synthesize '~' from {'M'}. ans: ~p |= =| ___ ___ ___ ___ ___
ii) Synthesize a useful nullary connective from {'M'}. ans: ___ |= =| ___ ___ ___ ___ ___
iii) Synthesize '/\' using one or more of the first three connectives. ans: p /\ q |= =| ___ ___ ___ ___ ___