This is another “private communication” problem that I couldn’t find an obvious reduction for online. I’ve used the holidays as an excuse to not put up a post so I could work on this problem, but even with the extra time, this problem has stumped me.

**The problem: **Truth-Functionally Complete Connectives. This is problem LO10 in the appendix.

**The description: **Given a set U of variables, and a set C of well-formed Boolean expressions over U, is C truth-functionally complete? In other words, can we find a finite set of unary and binary operators D = {θ_{1}..θ_{k}} such that for each θ_{i} we can find an expression E in C, and a substitution s: U->{a,b} such that s(E) ≡ aθ_{i}b (if θ_{i} is binary) or s(E) ≡ θ_{i}a (if θ_{i} is unary)?

**Example: **So, “Truth-Functionally Complete” means that you can use the operations in D to generate all possible truth tables. So some possible candidates for D are {AND, NOT} or just {NAND}.

So, if U = {x,y} and C = {~x, x∧y}, then I can just choose D to be {NOT, AND} and use the obvious substitution. I think the hard part here is that the problem asks if such a D exists- I think the substitutions are probably always straightforward, once you get the functionally complete set D that gives you the best mapping..

**Reduction: **As I said above, this is a “Private Communication” problem, and so after a lot of searching, I found this paper by Statman, which I’m honestly am not even sure is the correct one. It at least talks about substitutions and deterministic polynomial time algorithms and things, but it very quickly goes into advanced Mathematical Logic that I wasn’t able to follow. If someone out there knows more about this than I do and wants to chime in, let me know!

**Edited Jan 22, 2020**: Thanks to Thinh Nguyen for the help in coming up with the idea for the reduction- please check it out in the comments!

**Difficulty: **10. This is why we have the level 10 difficulty- for problems I can’t even follow.