zbMATH — the first resource for mathematics

On the density and the structure of the Peirce-like formulae. (English) Zbl 1355.03009
Fifth colloquium on mathematics and computer science. Lectures from the colloquium, Blaubeuren, Germany, September 22–26, 2008. Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS). Discrete Mathematics and Theoretical Computer Science Proceedings AI, 461-474 (2008).
Summary: Within the language of propositional formulae built on implication and a finite number of variables \(k\), we analyze the set of formulae which are classical tautologies but not intuitionistic (we call such formulae Peirce’s formulae). We construct the large family of so called simple Peirce’s formulae, whose sequence of densities for different \(k\) is asymptotically equivalent to the sequence \(\frac{1}{2k^2}\). We prove that the densities of the sets of remaining Peirce’s formulae are asymptotically bounded from above by \(\frac{c}{k^3}\) for some constant \(c \in \mathbb R\). The result justifies the statement that in the considered language almost all Peirce’s formulae are simple. The result gives a partial answer to the question stated in the recent paper by H. Fournier et al. [Lect. Notes Comput. Sci. 4646, 177–193 (2007; Zbl 1179.03015)] – although we have not proved the existence of the densities for Peirce’s formulae, our result gives lower and upper bound for it (if it exists) and both bounds are asymptotically equivalent to \(\frac{1}{2k^2}\).
For the entire collection see [Zbl 1172.05004].

03B20 Subsystems of classical logic (including intuitionistic logic)
05A16 Asymptotic enumeration
60C05 Combinatorial probability
Full Text: Link