有限域上关系的功能完全性和原始正分解

摘要 我们给出了有限域上高元关系的原始正分解到二元关系的新而基本的构造。这种分解在约束满足问题、克隆理论和关系数据库的应用中出现。该构造通过将关系解释为部分定义的多值“函数”的图形，利用了多值逻辑中2输入函数的功能完全性。然后，这些“函数”是从普通函数以通常的意义组合而成。该构造在计算上是有效的，并依赖于功能分解的成熟方法，但仅将关系简化为三元关系。额外的构造将三元关系有效地分解为二元关系，通过将某些析取转化为存在量化形式。结果为Peirce在有限域上的简化论提供了统一的证明，并显示任何Sheffer函数的图形能够组合所有的关系.