|
This article is cited in 1 scientific paper (total 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.
Received: 26.08.2022 Revised: 26.08.2022 Accepted: 31.08.2022
Citation:
K. L. Rychkov, “Representations of normalized formulas”, Diskretn. Anal. Issled. Oper., 29:4 (2022), 77–103
Linking options:
https://www.mathnet.ru/eng/da1310 https://www.mathnet.ru/eng/da/v29/i4/p77
|
Statistics & downloads: |
Abstract page: | 80 | Full-text PDF : | 18 | References: | 22 | First page: | 4 |
|