Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates

N. G. Parvatov

Tomsk State University, 36 Lenin Avenue, 634050 Tomsk, Russia

Abstract: Given a class $K$ of partial Boolean functions and a partial Boolean function $f$ of $n$ variables, a subset $U$ of its variables is called sufficient for the implementation of $f$ in $K$ if there exists an extension of $f$ in $K$ with arguments in $U$. We consider the problem of recognizing all subsets sufficient for the implementation of $f$ in $K$. For some classes defined by relations, we propose the algorithms of solving this problem with complexity of $O(2^nn^2)$ bit operations. In particular, we present some algorithms of this complexity for the class $P_2^*$ of all partial Boolean functions and the class $M_2^*$ of all monotone partial Boolean functions. The proposed algorithms use the Walsh–Hadamard and Möbius transforms. Bibliogr. 21.

Keywords: partial Boolean function, sufficient subset of variables, Walsh–Hadamard transform, Möbius transform.

UDC: 519.97

Received: 20.06.2019
Revised: 05.11.2019
Accepted: 27.11.2019

DOI: 10.33048/daio.2020.27.664

 English version: Journal of Applied and Industrial Mathematics, 2020, 14:1, 186–192

Bibliographic databases:

•