On the implicit expressibility of Boolean functions (Q1358182): Difference between revisions

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.