In this note, we give a linear-size translation from formulas of first-order logic into equations of the calculus of relations preserving validity and finite validity. Our translation also gives a linear-size conservative reduction from formulas of first-order logic into formulas of the three-variable fragment of first-order logic.
翻译:本文提出一种线性规模的翻译方法,将一阶逻辑公式转换为关系演算中的等式,同时保持公式的有效性与有限有效性。该翻译方法还提供了一种线性规模的保守归约,可将一阶逻辑公式归约为三变量片段中的公式。