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.