On the density and the structure of the Peirce-like formulae

Abstract : 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}{ 2 k^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, D. Gardy, A. Genitrini and M. Zaionc - 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}{ 2 k^2}$.
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.461-474, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194671
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:54
Dernière modification le : jeudi 11 janvier 2018 - 06:21:31
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:56:48

Fichier

dmAI0131.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194671, version 1

Collections

Citation

Antoine Genitrini, Jakub Kozik, Grzegorz Matecki. On the density and the structure of the Peirce-like formulae. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.461-474, 2008, DMTCS Proceedings. 〈hal-01194671〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

103