Questions about Boolean logic

Question

1. Is there a systematic way to show that a set of Boolean operators is complete? Or is it more of an art than a science?

2. Similarly, is there a systematic way to convert any Boolean expression in terms of said operators? For example if I am only allowed to use NAND, etc.

Answer 1

Post's theorem on functional completeness gives a complete answer to this question (it tells you how to recognise functionally complete sets and the proof, at least in principle, gives a systematic approach to representing a given boolean function in terms of a given complete set of connectives). See https://en.wikipedia.org/wiki/Functional_completeness and https://en.wikipedia.org/wiki/Post%27s_lattice.

For example, consider the operation NAND which I will write $\uparrow$. Post's theorem tells you that $\{\uparrow\}$ it is functionally complete (because it is not monotonic, affine, etc.). Once you know that, it is worth working by trial and error to see how to represent other standard operations using $\uparrow$: you will find that $\lnot A$ is $A \uparrow A$ and $A \lor B$ is $\lnot A \uparrow \lnot B$. (This now gives a direct proof that $\{\uparrow\}$ is functionally complete assuming that you already know that $\{\lnot, \lor\}$ is functionally complete.)