论逻辑图的表达能力

On Expressiveness of Logical Diagrams

随着新句法机制的引入,逻辑图的表达能力不断得到提高:文恩图在表达能力上等价于不带等词的一元一阶逻辑,蜘蛛图等价于带等词的一元一阶逻辑,而建立在约束图基础上的"可视一阶逻辑"被证明具有一阶谓词逻辑的表达能力。研究逻辑图表达能力的一个重要意义在于,图式逻辑可能有望为一阶逻辑产生重要的可判定片段。

Introducing new syntactical objects increases the expressiveness of logical diagrams. The ex-pressiveness of Venn diagrams, spider diagrams and ＂ visual FOL＂ based on constraint diagrams is equivalent to monadic FOL without equality, monadic FOL with equality and full FOL respectively. Studying on the expressiveness of logical diagrams is of importance for exploring new decidable fragments of FOL.