1

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.

Play4u
  • 41
  • 5
  • have you had a look at https://en.wikipedia.org/wiki/Functional_completeness ? – Jean Marie Jul 23 '20 at 08:18
  • @JeanMarie I've edited my post since I had copied the problem wrong – Play4u Jul 23 '20 at 08:51
  • I am not very familiar with this subject, but it seems to me that you should 1) mention the number of variables involved 2) recall the meaning of some terms : for example, I am unable to figure out what you call "linear" – Jean Marie Jul 23 '20 at 08:58
  • @JeanMarie alright I will make sure to edit my answer to include the definitions – Play4u Jul 23 '20 at 09:07
  • 1
    @JeanMarie done – Play4u Jul 23 '20 at 10:42
  • I imagine that the definition of $\alpha \le \beta$ is $\forall k, \alpha_k \le \beta_k, \ \ k=1,\cdots n$. – Jean Marie Jul 23 '20 at 13:51
  • @JeanMarie Yes, forgot to add that. – Play4u Jul 23 '20 at 18:40
  • Connected : https://victoramelkin.com/ta/cs40/posts-criterion.pdf – Jean Marie Jul 23 '20 at 20:44
  • @JeanMarie I know this stuff in theory as we had to learn it for our Discrete Mathematics class and I've mainly tried using Post's theorem to prove that F1 and F2 are complete but I always get stuck. I wanted to ask the question without adding anything from my attempts to solve it so that I don't misdirect any potential answers – Play4u Jul 24 '20 at 07:02
  • I don't think that on this site there is a risk of misdirecting potential "answerers". On the contrary, a greater risk is, like I have done with the document I had found, to rediscover things that you already know. Therefore, I advise you to give all the pertinent information you have now (for example the kind of lecture notes/books you are working on), and where you are blocked. – Jean Marie Jul 24 '20 at 07:55
  • @JeanMarie I've posted my progress so far as a separate answer since it was exceeding the comment limit by a lot. Also I'm currently not working on anything in particular.. I've taken discrete mathematics a couple of years ago and now I'm just practicing for my graduation exam – Play4u Jul 24 '20 at 12:39

1 Answers1

1

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.

Play4u
  • 41
  • 5