TransWikia.com

Which of the following sets of boolean functions is functionally complete?

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.

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP