IMI/Publicaţii/BASM/Ediţii/BASM n.2 (8), 1992/

Description of classically complete chain systems of pseudo-Boolean functions. (Russian)

Authors: Malaj V. P., Ratsa M. F.


A system $\Sigma$ of function from the set $K$ is called a chain (completive) system in $K$, if the set of closed systems $K'$, such that $\Sigma \subseteq K'\subseteq K$, forms a chain with respect to the inclusion (is finite). A system $\Sigma \subseteq K$ is precompletive in $K$, if $\Sigma$ is not completive in $K$, but for every function $f$ of $K$, which is not expressible via $\Sigma$, the system $\Sigma U\{f\}$ is completive in $K$. Let the classes $J^{\mu}_1,\dots ,J^{\mu}_4$ be the classes of the pseudo-Boolean functions, which preserve respectively the predicates:
$(x_1\ne \tau)\& \dots \& (x_{\mu}\ne \tau)\& ((x_1\& \dots \& x_{\mu +1})\ne \tau)$;
$(x_1\ne \tau)\& \dots \& (x_{\mu}\ne \tau)\& ((x_1 \vee \dots \veex_{\mu +1})\ne \tau)$;
$(x_1 \ne \tau)\& ((x_1 \vee \dots \vee x_{\mu +1})\ne \tau)\&(\neg x_2=\dots =\neg x_{\mu +1})$;
$((x_1\vee \dots \vee x_{\mu+1})\ne \tau)\& (\neg x_1=\dots =\neg x_{\mu +1})$ \ on the set $\{0,\tau, 1\}$, where $\mu = 1,2,\dots$. Let $J^{\infty}_i = J^1_i\cap J^2_i \cap \dots$ $(i=1,\dots, 4)$. Then the systems $J^{\infty}_1,\dots ,J^{\infty}_4$ \ are the only classically complete chain and completive ones in the set of all the pseudo-Boolean functions. In the paper it is proved that these systems have a finite basis. Some examples of bases are presented.