zbMATH — the first resource for mathematics

Asymptotic density for equivalence. (English) Zbl 1272.03062
Lescanne, Pierre (ed.) et al., Proceedings of the 2nd workshop on computational logic and applications (CLA 2004), Lyon, France, June 17–18, 2004. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 140, 81-91 (2005).
Summary: We study the asymptotic behavior of the fraction of true formulas against all formulas over $$k$$ propositional variables with equivalence as the only connective in the language. We consider two ways of measuring the asymptotic behavior. In the first case we investigate the size of the tautology fraction of length $$n$$ against the number of all formulas of length $$n$$. The second case is very similar and we investigate the size of the tautology fraction of length at most n against the number of all formulas of length at most $$n$$. In both cases we are interested in finding the limit (which is often called “density” and “cumulative density”, respectively) of each fraction when $$n\to\infty$$.
It was already proved that the asymptotic density for $$k=1$$ exists for all binary connectives except equivalence. In this paper we prove that for every $$k$$ there are exactly two accumulation points for the language based on equivalence: $$0$$, $$1/2^{k-1}$$ for asymptotic density and $$1/2^{k-1})4k+1$$, $$4k/2^{k-1})4k+1$$ for cumulative asymptotic density.
For the entire collection see [Zbl 1272.03003].

MSC:
 03B05 Classical propositional logic
Full Text: