RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2022 Volume 29, Issue 4, Pages 77–103 (Mi da1310)

This article is cited in 1 paper

Representations of normalized formulas

K. L. Rychkov

Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia

Abstract: A class of objects called $\Pi$-partitions is defined. These objects, in a certain well-defined sense, are the equivalents of formulas in a basis consisting of disjunction, conjunction and negation, in which negations are possible only over variables (normalized formulas). $\Pi$-partitions are seen as representations of formulas, just as equivalents and graphical representations of the same formulas can be considered $\Pi$-schemes. Some theory of such representations has been developed which is essentially a mathematical apparatus focused on describing a class of minimal normalized formulas implementing linear Boolean functions. Bibliogr. 18.

Keywords: Boolean function, normalized formula, minimal formula, representation of a formula, $\Pi$-scheme, $\Pi$-partition, lower bound for the complexity.

UDC: 519.714

Received: 26.08.2022
Revised: 26.08.2022
Accepted: 31.08.2022

DOI: 10.33048/daio.2022.29.751



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024