RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2025 Volume 32, Number 2, Pages 100–109 (Mi mais843)

Discrete mathematics in relation to computer science

On extremal elements and the cardinality of the set of continuously differentiable convex extensions of a Boolean function

D. N. Barotova, R. N. Barotovb

a Financial University under the Government of the Russian Federation, Moscow, Russia
b Khujand State University named after academician Bobojon Gafurov, Khujand, Tajikistan

Abstract: In this paper we study the existence of the maximal and minimal elements of the set of continuously differentiable convex extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ and the cardinality of the set of continuously differentiable convex extensions to $[0,1]^n$ of the Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$. As a result of the study, it was established that the cardinality of the set of continuously differentiable convex extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ is equal to the continuum. It is argued that for any Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$, there is no minimal element among its continuously differentiable convex extensions to $[0,1]^n$. It is proved that for any Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$, the set of its continuously differentiable convex extensions to $[0,1]^n$ has a maximal element only if the number of essential variables of the given Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ is less than $2$.

Keywords: continuously differentiable convex extension of a Boolean function, extremal elements of a set, cardinality of a set.

UDC: 519.716.322+519.85+517.518.244

MSC: 06E30, 54C20, 03E17

Received: 19.02.2025
Revised: 01.04.2025
Accepted: 09.04.2025

DOI: 10.18255/1818-1015-2025-2-100-109



© Steklov Math. Inst. of RAS, 2025