Mathematics Asked by Play4u on December 8, 2021
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_0oplus (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.
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 notsubseteq T_0 ;&; F notsubseteq T_1 ;&; F notsubseteq L ;&; F notsubseteq M ;&; F notsubseteq 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=(Msetminus T_0)cup(Ssetminus L) = (Mcup S)setminus(T_0cup 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 notsubseteq T_0 ;&; F_1 notsubseteq L$. All that's left to prove is that $F _1notsubseteq T_1 ;&; F_1 notsubseteq M ;&; F_1 notsubseteq S$
Let's try to prove that $F_1 notsubseteq S$ or in other words $exists fin F_1: fnotin S$.
From our original problem we can safely assume that if such $f$ exists, $f in (Msetminus T_0)$. So for that $f$ we have $f in M ;&; fnotin S ;&; fnotin 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.
Answered by Play4u on December 8, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP