Which of the following sets of boolean functions is functionally complete? Let us have two sets of boolean functions:
$F_1 = (M \setminus T_0) \cup (S \setminus L)$
$F_2 = (M \setminus T_0) \cup (L \setminus S)$
where $M$ is the set of all monotonic functions, $T_0$ is the set of all falsity-preserving functions, $S$ is the set of all self-dual functions and $L$ is the set of all linear functions.
Formal definitions:
The set of all boolean functions: B = {$f: J^2_n \to J_2, n = 1,2,...\}$
Vectors of variables of length n: $\alpha = \{x_1, x_2, ..., x_n\}, \beta = \{y_1, y_2, ..., y_n\}, ...$
$T_0 = \{\forall f \in B: \alpha = \{0,0,...,0\}, f(\alpha) = 0\}$ - falsity preserving
$T_1 = \{\forall f \in B: \alpha = \{1,1,...,1\}, f(\alpha) = 1\}$ - truth preserving
$L = \{\forall f \in B: f \text{ can be represented as } f=a_0\oplus (a_1 \wedge x_1)\oplus(a_2 \wedge x_2)\oplus...\oplus(a_n \wedge x_n)\}$ - linear
$S = \{\forall f \in B: f(\alpha)=\overline{f(\bar{\alpha})}\}$ - self-dual
$M = \{\forall f \in B: \alpha \leq \beta, f(\alpha) \leq f(\beta)\}$ - monotonic
I've been thinking for a while and I can't seem to begin from anywhere.
 A: Ok, so what I've tried so far is using Post's theorem for functional completeness to prove that $F_1$ and $F_2$ are complete.
Post's theorem states that a set of boolean functions $F$ is complete iff
$F \not\subseteq T_0 \;\&\; F \not\subseteq T_1 \;\&\; F \not\subseteq L \;\&\; F \not\subseteq M \;\&\; F \not\subseteq S$
or in other words there's at least one function in $F$ for each of $\{T_0, T_1, L, M, S\}$ which doesn't belong  to the corresponding set.
Let's try to prove that $F_1$ is complete.
$F_1=(M\setminus T_0)\cup(S\setminus L) = (M\cup S)\setminus(T_0\cup L)$
From this we know that $F_1$ doesn't contain any functions from $T_0$ or $L$.  So it's true that $F_1 \not\subseteq T_0 \;\&\; F_1 \not\subseteq L$.
All that's left to prove is that
$F _1\not\subseteq T_1 \;\&\;  F_1 \not\subseteq M \;\&\; F_1 \not\subseteq S$
Let's try to prove that $F_1 \not\subseteq S$ or in other words
$\exists f\in F_1: f\not\in S$.
From our original problem we can safely assume that if such $f$ exists,
$f \in (M\setminus T_0)$. So for that $f$ we have
$f \in M \;\&\; f\not\in S \;\&\; f\not\in T_0$.
So if our $f$ exists - or a set of functions with these qualities exists - its definition will be as follows
$\{f \in B: \forall \alpha, \beta : \alpha \leq \beta, f(\alpha)\leq f(\beta) \;\&\; f(\alpha) \neq \overline{f(\bar \alpha)} \;\&\; f(0,0,...,0)=1\}$
I'm stuck here. I don't know how to find such function. If I manage to do so, I think I can use the method for all other sets in the problem.
