Finding Two Bits

To make things a little easier, notice that NAND, NOR, XNOR, and IMPBY give the same info about the inputs as AND, OR, XOR, and IMP. We can ignore these negated functions initially to make this a little easier.

We specifically wish to determine the values of two ordered bits, so we must have a way to differentiate 1,0 and 0,1. Of these functions, only IMP has this capability, so we must include it.

With that out of the way, we just have to differentiate 0,0 , 1,1 , and (unordered) 0,1. Note that each of AND, OR, and XOR can tell one of these cases from the others. If AND outputs 1, you have 1,1; if OR outputs 0, you have 0,0; and if XOR outputs 1, you have 1,1. Picking two of these three functions is sufficient because being able to single out two cases implies the third (if AND is 0 and OR IS 1, you have 1,0 , without using XOR). Since we already had IMP, adding two more functions brings us to 3.

But wait! We had all the negated functions to work with too! Each member of our new triplet can be replaced with its negated form, and the triplet still works the same. For example, NAND can still pick out the 1,1 case, it’s just when the output is 0, instead of 1 like with AND. This gives a total of 3 ways to construct the base triplet, by 2x2x2 ways to use the negated functions, for 24 possibilities.

However, there is one more sneaky way to create more triplets: use IMP and IMPBY. Using these two in conjunction allows you to recognise the unordered 0,1 case, as well as distinguishing the ordered ones. (Note: although I’m referring to IMPBY as the negation of IMP, my understanding is that they are just the same function with the inputs reversed. So, they agree if the inputs are the same, but disagree when they’re different. Negated IMP should be called NIMP anyway)

So, using IMP and IMPBY together, we can recognise 0,1 and 1,0 , so we just need a function which can tell 1,1 and 0,0 apart. AND, NAND, OR, and NOR all can, so this gives four additional triplets, for a total of $\boxed{28}$