Abstract | ||
---|---|---|
We consider logical expressions built on the single binary connector of implication and a finite number of literals (Boolean variables and their negations). We prove that asymptotically, when the number of variables becomes large, all tautologies have the following simple structure: either a premise equal to the goal, or two premises which are opposite literals. (C) 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim |
Year | DOI | Venue |
---|---|---|
2010 | 10.1002/malq.200810053 | MATHEMATICAL LOGIC QUARTERLY |
Keywords | Field | DocType |
Implicational expressions,boolean formulae,tautologies,analytic combinatorics | Discrete mathematics,Analytic combinatorics,Combinatorics,Tautology (logic),Finite set,Negation,Expression (mathematics),Premise,Boolean data type,Mathematics,Binary number | Journal |
Volume | Issue | ISSN |
56 | 4 | 0942-5616 |
Citations | PageRank | References |
3 | 0.40 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hervé Fournier | 1 | 185 | 18.10 |
Danièle Gardy | 2 | 411 | 76.32 |
Antoine Genitrini | 3 | 68 | 12.06 |
Marek Zaionc | 4 | 111 | 17.27 |