Complexity and Limiting Ratio of Boolean Functions over Implication

DOI10.1007/978-3-540-85238-4_28MaRDI QIDQ3599140zbMATH OpenOpenAlexFDO

Authors Danièle Gardy, Antoine Genitrini, Bernhard Gittenberger, Hervé Fournier

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_28

zbMATH Keywords

analytic combinatoricsBoolean functionscomplexityimplicational formulaslimiting ratioprobability distribution

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Boolean functions (06E30) Combinatorial probability (60C05)

Recommendations

• The fraction of large random trees representing a given Boolean function in implicational logic
• Probabilities of Boolean functions given by random implicational formulas
• Random Boolean expressions
• Complexity and Probability of Some Boolean Formulas
• Asymptotic probability of values of random Boolean expressions

Cites work

• A natural prior probability distribution derived from the propositional calculus
• Analytic combinatorics
• And/Or Trees Revisited
• Asymptotic density for equivalence
• Boltzmann oracle for combinatorial systems
• Classical and Intuitionistic Logic Are Asymptotically Identical
• Coloring rules for finite trees, and probabilities of monadic second order sentences
• Density of truth in modal logics
• Finite range random walk on free groups and homogeneous trees
• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• On asymptotic divergency in equivalential logics
• On the asymptotic density of tautologies in logic of implication and negation
• On the density of truth of implicational parts of intuitionistic and classical logics
• Random Boolean expressions
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• Short monotone formulae for the majority function
• Some typical properties of large AND/OR Boolean formulas
• Statistical properties of simple types
• Statistics of implicational logic
• Statistics of intuitionistic versus classical logics
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• Using amplification to compute majority with small majority gates

Cited in

(5)

• Associative and commutative tree representations for Boolean functions
• Complexity of implementation of parity functions in the ``implication-negation basis
• The fraction of large random trees representing a given Boolean function in implicational logic
• Tautologies over implication with negative literals
• Probabilities of Boolean functions given by random implicational formulas

This page was built for publication: Complexity and Limiting Ratio of Boolean Functions over Implication

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