Determining whether a truth function can be defined in terms of another Given an $n$-ary truth function $f$ and $m$-ary truth function $g$, is there a way to determine whether $g$ can be defined in terms of $f$? In other words, is there a systematic procedure that can answer whether there exists some formula $F$ which consists entirely of $f$ and propositional variables, and also $g = \lambda p_1 \dots p_m .F$?
There are some special cases in which this question becomes trivial. For instance, if $f$ is a Sheffer function, it can be used to define any truth function. Also, if $f(\top,...,\top) = \top$, it cannot define $\bot$. But I'm curious whether this question can be answered generally.
It seems that the most interesting case arises when $f$ is a dual of itself. Then it follows that any truth function defined in terms of $f$ must be self-dual as well. Given that $g$ is also self-dual, are there other tests we can apply to see whether $g$ is definable with $f$? 
 A: Here is an observation that is a little bit too long for a comment: given $f$ and $g$, it is computable whether or not this is possible. We can recursively generate all $m$-ary truth functions that we can make using only $f$ and atoms by the following procedure: start with the set of all atoms; run through the set of all $n$-tuples of truth functions currently in our set, and applying $f$ to them; if this produces a new truth function (which we can check), then add it to the list; repeat the last two steps until no new functions are added to the set; then check whether $g$ is in the set.
This answers what you actually asked -- "is there a way to determine whether $g$ can be defined in terms of $f$" -- of course, this is not a practical procedure for any but the simplest $f,g$. My intuition says that there is no efficient algorithm for this, but I might be wrong.
(In fact, if we decide that the way that $f$ and $g$ are given is by formulas in terms of standard connectives $\land,\lor,\neg,\to$, rather than $2^n,2^m$ truth values respectively, then the problem is at least NP-hard, because checking whether or not a formula $f$ can make the constant true function is basically SAT.)
