|国家预印本平台
首页|Boolean basis, formula size, and number of modal operators

Boolean basis, formula size, and number of modal operators

Boolean basis, formula size, and number of modal operators

来源:Arxiv_logoArxiv
英文摘要

Is it possible to write significantly smaller formulae when using Boolean operators other than those of the De Morgan basis (and, or, not, and the constants)? For propositional logic, a negative answer was given by Pratt: formulae over one set of operators can always be translated into an equivalent formula over any other complete set of operators with only polynomial increase in size. Surprisingly, for modal logic the picture is different: we show that elimination of bi-implication is only possible at the cost of an exponential number of occurrences of the modal operator $\lozenge$ and therefore of an exponential increase in formula size, i.e., the De Morgan basis and its extension by bi-implication differ in succinctness. Moreover, we prove that any complete set of Boolean operators agrees in succinctness with the De Morgan basis or with its extension by bi-implication. More precisely, these results are shown for the modal logic $\mathrm{T}$ (and therefore for $\mathrm{K}$). We complement them showing that the modal logic $\mathrm{S5}$ behaves as propositional logic: the choice of Boolean operators has no significant impact on the size of formulae.

Christoph Berkholz、Dietrich Kuske、Christian Schwarz

10.46298/lmcs-21(3:10)2025

数学

Christoph Berkholz,Dietrich Kuske,Christian Schwarz.Boolean basis, formula size, and number of modal operators[EB/OL].(2025-07-25)[2025-08-05].https://arxiv.org/abs/2408.11651.点此复制

评论