Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. And/or tree probabil ...
Conference paper

And/or tree probabilities of Boolean functions

Danièle Gardy ORCID (1), Alan Woods (2)
(1) Parallélisme, Réseaux, Systèmes, Modélisation
(2) School of Mathematics and Statistics [Crawley, Perth]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Proceedings
DOI
10.46298/dmtcs.3355
License
https://about.hal.science/hal-authorisation-v1
Indicators
577
Views
478
Downloads

And/or tree probabilities of Boolean functions

Danièle Gardy ORCID (1), Alan Woods (2)
(1) Parallélisme, Réseaux, Systèmes, Modélisation
(2) School of Mathematics and Statistics [Crawley, Perth]
Abstract
We consider two probability distributions on Boolean functions defined in terms of their representations by $\texttt{and/or}$ trees (or formulas). The relationships between them, and connections with the complexity of the function, are studied. New and improved bounds on these probabilities are given for a wide class of functions, with special attention being paid to the constant function $\textit{True}$ and read-once functions in a fixed number of variables.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]
  • tree enumeration
  • tautology
  • And/Or tree
  • Boolean formula
Cited by

Source: OpenCitations

  • Tautologies over implication with negative literals

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Marek Zaionc ORCID

    Journal reference : Volume 56, 2010, pp. 388-396

    DOI : 10.1002/malq.200810053

  • Intuitionistic vs. Classical Tautologies, Quantitative Comparison

    Lecture notes in computer science

    Authors : Antoine Genitrini ORCID, Jakub Kozik ORCID, Marek Zaionc ORCID

    Journal reference : Volume , 2008, pp. 100-109

    DOI : 10.1007/978-3-540-68103-8_7

  • Implicational Tautologies with One Variable and Its Negation in Fuzzy Logics

    WSEAS TRANSACTIONS ON MATHEMATICS

    Authors : Zofia Kostrzycka ORCID

    Journal reference : Volume 24, 2025, pp. 620-630

    DOI : 10.37394/23206.2025.24.61

  • Fuzzy logics – quantitatively

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Zofia Kostrzycka ORCID, Marek Zaionc ORCID

    Journal reference : Volume 34, 2023, pp. 97-132

    DOI : 10.1080/11663081.2023.2269645

  • Classical and Intuitionistic Logic Are Asymptotically Identical

    Lecture notes in computer science

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Marek Zaionc ORCID

    Journal reference : Volume , 2007, pp. 177-193

    DOI : 10.1007/978-3-540-74915-8_16

  • On density of truth of the intuitionistic logic in one variable

    Discrete Mathematics & Theoretical Computer Science

    Authors : Zofia Kostrzycka ORCID

    Journal reference : Volume DMTCS Proceedings vol. AI,..., 2008, pp.

    DOI : 10.46298/dmtcs.3583
Preview
Loading PDF preview...