We consider a 2-valued non-deterministic connective $\wedge \hskip-5.5pt \vee$ defined by the table resulting from the entry-wise union of the tables of conjunction and disjunction. Being half conjunction and half disjunction we named it platypus. The value of $\wedge \hskip-5.5pt \vee$ is not completely determined by the input, contrasting with usual notion of Boolean connective. We call non-deterministic Boolean connective any connective based on multi-functions over the Boolean set. In this way, non-determinism allows for an extended notion of truth-functional connective. Unexpectedly, this very simple connective and the logic it defines, illustrate various key advantages in working with generalized notions of semantics (by incorporating non-determinism), calculi (by allowing multiple-conclusion rules) and even of logic (moving from Tarskian to Scottian consequence relations). We show that the associated logic cannot be characterized by any finite set of finite matrices, whereas with non-determinism two values suffice. Furthermore, this logic is not finitely axiomatizable using single-conclusion rules, however we provide a very simple analytical multiple-conclusion axiomatization using only two rules. Finally, deciding the associated multiple-conclusion logic is coNP-complete, but deciding its single-conclusion fragment is in P.
翻译:我们认为,由于组合和脱节的表格的起始式结合,表格中定义了价值为2的、非决定性的连接 $\wengge\hskip-5.5p-5.5pt\vee$。作为半结合和半脱节,我们称之为platypus。 输入并不完全决定$wedge\hskip-5.5pt\vee$的价值,这与Boolean连接的通常概念不同。我们称之为非决定性的Boolean连接,任何基于布林集多重功能的连接。在这种方式中,非确定主义允许扩大真相-功能联系的概念。我们所定义的这种非常简单的连接和逻辑,说明了与通用的语义概念(通过纳入非确定性联系)、计算性(通过允许多重封闭规则)甚至逻辑(从Tarskian移动到Scottian后果关系)合作的各种关键优势。我们显示,相关的逻辑不能用任何固定的、固定的、多层次的逻辑来描述,而我们所定义的、不完全的、多层次的双重的逻辑是使用一个固定的、最后的逻辑。