Chernov, A. V. Complexity of sets obtained as values of propositional formulas. (English. Russian original) Zbl 1114.03004 Math. Notes 75, No. 1, 131-139 (2004); translation from Mat. Zametki 75, No. 1, 142-150 (2004). Summary: Interpretation of logical connectives as operations on sets of binary strings is considered; the complexity of a set is defined as the minimum of the Kolmogorov complexities of its elements. It can be easily seen that the complexity of a set obtained by the application of logical operations does not exceed the complexity of the conjunction of their arguments (up to an additive constant). In this paper, it is shown that the complexity of a set obtained by a formula \(\Phi\) is small (bounded by a constant) if \(\Phi\) is deducible in the logic of weak excluded middle, and attains the specified upper bound otherwise. Cited in 1 Document MSC: 03B05 Classical propositional logic 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) Keywords:Kolmogorov complexity; logical connectives; law of weak excluded middle; deducibility; intuitionistic logic; propositional calculus PDFBibTeX XMLCite \textit{A. V. Chernov}, Math. Notes 75, No. 1, 131--139 (2004; Zbl 1114.03004); translation from Mat. Zametki 75, No. 1, 142--150 (2004) Full Text: DOI