逻辑之间的语义忠实语义满翻译

翻译在计算机科学中的一个重要应用是实现一个逻辑与另一个逻辑在表达能力上的比较,以及利用目标逻辑的推理机实现源逻辑的推理.现有逻辑之间的翻译理论和性质没有深入研究逻辑的语义翻译,以及翻译是否保持不可满足性等问题.该文研究了一类同时保持公式的可满足性和不可满足性的翻译——语义忠实语义满翻译,给出了语义忠实语义满翻译的定义,比较了语义忠实语义满翻译与已有文献中翻译定义的区别和联系,讨论了逻辑的可靠性、完备性、可判定性、紧致性、公式的逻辑等价性,以及模型的初等等价性在语义忠实语义满翻译下被保持的问题.运用语义忠实语义满翻译的定义给出了逻辑之间的同义性定义,并证明了同义关系是逻辑之间的一个等价关系.

不同逻辑间翻译的逻辑性质

如果考虑逻辑间模型的翻译并且一个逻辑的模型类被翻译为另一个逻辑的模型类的真子类,那么可靠的(the soundness)和完备的(the completeness)翻译可以将不可满足的公式翻译为可满足的公式.针对上述问题,该文提出了语义忠实(the faithfulness)和语义满(the fullness)两条逻辑性质来确保可满足的公式翻译为可满足的公式,不可满足公式翻译为不可满足公式.该文例证了二阶逻辑在标准语义下到一阶逻辑的翻译是语义忠实的但不是语义满的,在Henkin语义下是语义忠实的和语义满的.

谓词模态逻辑到对应物理论的翻译

对应物理论(counterpart theory)是一阶逻辑的一种理论.Lewis利用谓词模态逻辑到对应物理论的翻译来研究谓词模态逻辑的性质,但是Lewis的翻译存在把不可满足的公式翻译为可满足公式的情况.针对这个问题,提出了一种扩展语义的谓词模态逻辑,建立了扩展语义后谓词模态逻辑模型与对应物理论模型的一一对应关系,并在此基础上建立了谓词模态逻辑到对应物理论的语义忠实语义满翻译(faithful and full translation),其可确保将谓词模态逻辑的可满足公式和不可满足公式分别翻译为对应物理论的可满足公式和不可满足公式.由对应物理论是可靠的、完备的一阶逻辑的理论且语义忠实语义满翻译保持可靠性和完备性,进一步证明了扩展语义的谓词模态逻辑也是可靠和完备的.