On a quasi-ordering on Boolean functions

Details On a quasi-ordering on Boolean functions On a quasi-ordering on Boolean functions

2006-01-10

arxiv.org/abs/math/0601218v1

Mathematics

Combinatorics

14 pages

Scientific paper

It was proved few years ago that classes of Boolean functions definable by means of functional equations \cite{EFHH}, or equivalently, by means of relational constraints \cite{Pi2}, coincide with initial segments of the quasi-ordered set $(\Omega, \leq)$ made of the set $\Omega$ of Boolean functions, suitably quasi-ordered. The resulting ordered set $(\Omega/\equiv, \sqsubseteq)$ embeds into $([\omega]^{<\omega}, \subseteq)$, the set -ordered by inclusion- of finite subsets of the set $\omega$ of integers. We prove that $(\Omega/\equiv, \sqsubseteq)$ also embeds $([\omega]^{<\omega}, \subseteq)$. We prove that initial segments of $(\Omega, \leq)$ which are definable by finitely many obstructions coincide with classes defined by finitely many equations. This gives, in particular, that the classes of Boolean functions with a bounded number of essential variables are finitely definable. As an example, we provide a concrete characterization of the subclasses made of linear functions.

Affiliated with

Also associated with

No associations

Rating

On a quasi-ordering on Boolean functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a quasi-ordering on Boolean functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a quasi-ordering on Boolean functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-214532