Reference no: EM132082728

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 |= =| ___ ___ ___ ___ ___