On the implicit expressibility of Boolean functions
Let \(\Sigma\) be an arbitrary system of Boolean functions, \(x_1,\dots,x_n\) be \(n\) variables, \(y\) be a variable distinct from the \(n\) variables, and \(f(x_1, \dots, x_n)\) be a Boolean function of the first \(n\) variables. A function \(f\) is said to be implicity expressible through the functions of the system \(\Sigma\) if, for some natural number \(m\), there exist \(2m\) Boolean functions \(a_1,b_1, \dots, a_m,b_m\) of the specified \(n+1\) variables such that the system of \(m\) equations \(\{a_i(y,x_1, \dots, x_n)= b_i(y,x_1, \dots, x_n)\), \(i=1, \dots, m\}\) is equivalent (in the usual sense) to the equation \(y=f(x_1, \dots, x_n)\) and each of the \(2m\) functions \(a_i\), \(b_i\) is expressible as a superposition of the functions of the system \(\Sigma\) or is equal to one of the variables \(y\), \(x_1, \dots, x_n\). The set of all functions implicitly expressible through the functions of the system \(\Sigma\) is called the implicit extension of the system \(\Sigma\). The author describes a finite subfamily \(K\) of the family of all closed classes of Boolean functions which consists of 25 classes and proves the following result: The implicit extension of any system of Boolean functions coincides with the smallest class from the family \(K\) that includes this system.
- Implicit expressibility in two-valued logic and cryptoisomorphisms of two-element algebras
- Implicit Boolean equations.
- Implicitly maximal classes and implicit completeness criterion in the three-valued logic
- Recognizing the presence of a growing unessential argument of Boolean functions
- Implicit expressibility in multiple-valued logic
- On a metric characteristic of implicit and parametric representations of Boolean functions
- scientific article; zbMATH DE number 1379304 (Why is no real title available?)
- Boolean negation and non-conservativity II: The variable-sharing property
This page was built for publication: On the implicit expressibility of Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1358182)
