Probability distribution for simple tautologies

DOI10.1016/J.TCS.2006.01.002MaRDI QIDQ2369016zbMATH OpenOpenAlexFDO

Authors Marek Zaionc

Publication date 28 April 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.01.002

zbMATH Keywords

asymptotic probability in logicprobability distribution in logicrandom logical sentencestruth

Mathematics Subject Classification ID

Classical propositional logic (03B05) Probability and inductive logic (03B48)

Review text

The author investigates the lower bound of the proportion between the number of propositional formulas of the size \(n\) that are tautologies and the number of all propositional formulas of size \(n\). The interest lays in finding the limit, when \(n\to\infty\), of that proportion, representing `the density of truth' for the logic considered. Particularly, the author deals with implicational formulas over \(k\) propositional variables and discusses the probability that a randomly chosen implicational formula admits \(p\) premises, as well as the probability that a randomly chosen implicational simple tautology admits \(p\) premises. Apart from mathematical and logical aspects, the paper has clear philosophical impact on the understanding how much the phenomenon of truth is frequent in random logical sentences.

Recommendations

• Statistics of implicational logic
• On the asymptotic density of tautologies in logic of implication and negation
• Density of tautologies in logics with one variable
• Density of truth in modal logics
• scientific article; zbMATH DE number 1916519

Cites work

• A Remark on Stirling's Formula
• scientific article; zbMATH DE number 3477793 (Why is no real title available?)
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 2084758 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• Statistical properties of simple types
• Statistics of intuitionistic versus classical logics

Cited in

(9)

• A natural prior probability distribution derived from the propositional calculus
• Asymptotic properties of combinatory logic
• Intuitionistic vs. Classical Tautologies, Quantitative Comparison
• Density of truth in modal logics
• Tautologies over implication with negative literals
• Statistical properties of simple types
• Statistics of implicational logic
• On the asymptotic density of tautologies in logic of implication and negation
• Asymptotic densities in logic and type theory

This page was built for publication: Probability distribution for simple tautologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369016)