On the implicit expressibility of Boolean functions
type: Item
instance of: scholarly article
title: On the implicit expressibility of Boolean functions
zbMATH Open document ID: 0877.06007
author: O. M. Kasim-Zade
published in: Moscow University Mathematics Bulletin
publication date: 1997-07-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06E30
zbMATH DE Number: 1027894
zbMATH Keywords: Boolean functions
zbMATH Keywords: equations
zbMATH Keywords: implicit extension
zbMATH Keywords: closed classes
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1027894