Representations of normalized formulas

DOI10.33048/DAIO.2022.29.751MaRDI QIDQ5878634zbMATH OpenFDO

Authors K. L. Rychkov

Publication date 21 February 2023

Full work available at URL http://mathnet.ru/eng/da1310

zbMATH Keywords

\( \Pi \)-partition\( \Pi \)-schemeBoolean functionlower bound for complexityminimal formulanormalized formularepresentation of formula

Mathematics Subject Classification ID

Classical propositional logic (03B05)

Recommendations

• On minimal -schemes for linear Boolean functions
• Representation of logic formulas by normal forms.
• System of transformations of certain representations of Boolean functions
• Disjunctive and conjunctive normal forms of pseudo-Boolean functions
• scientific article; zbMATH DE number 107561

Cites work

• A simplified proof of a lower complexity estimate
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Complexity of the realization of a linear Boolean function in the class of -schemes
• Complexity of the realization of a linear function in the class of -circuits
• Computation complexity of a ternary linear function
• Formula complexity of a linear function in a \(k\)-ary basis
• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 855574 (Why is no real title available?)
• scientific article; zbMATH DE number 3089101 (Why is no real title available?)
• Lower bounds on the formula complexity of a linear Boolean function
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Sufficient conditions for the local repetition-freeness of minimal -schemes realizing linear Boolean functions
• The Shrinkage Exponent of de Morgan Formulas is 2

Cited in

(1)

• On the structure of one class of perfect \(\Pi \)-partitions

This page was built for publication: Representations of normalized formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5878634)