Publications > Artigos ou Capítulos em Livros Editados

An infinite descending chain of Boolean subfunctions consisting of threshold functions

Lehtonen, Erkko

Contributions to General Algebra 17, Proceedings of the Vienna Conference 2005 (AAA70), Verlag Johannes Heyn, Klagenfurt, (2006), 145-148


For a class C of Boolean functions, a Boolean function f is a C-subfunction of a Boolean function g, if f=g(h1,...,hn), where all the inner functions hi are members of C. Two functions are C-equivalent, if they are C-subfunctions of each other. The C-subfunction relation is a preorder on the set of all functions if and only if C is a clone. An infinite descending chain of U_\infty-subfunctions is constructed from certain threshold functions (U_\infty denotes the clone of clique functions).