BL命題邏輯系統的強同余關系及演繹系統

崔艷麗, 梁 穎, 吳洪博

(1. 陜西師范大學 數學與信息科學學院, 西安 710119; 2. 漢中職業技術學院， 陜西 漢中 723002)

多值數理邏輯系統的完備性是建立多值邏輯系統的必要組成部分, 其證明在多值邏輯系統的研究中至關重要. 文獻[1]在研究ukasiewicz命題邏輯系統完備性的過程中建立了多值邏輯代數: MV-代數, 并利用MV-代數向一族全序MV-代數乘積代數的嵌入定理證明了ukasiewicz命題邏輯系統的完備性. 此后, 該種方法幾乎成為證明完備性的唯一選擇[2-5]. 目前, 關于邏輯代數的研究已取得了很多成果[6-16], 但關于命題演繹系統的研究報道相對較少[17-20]. 本文進一步討論BL命題邏輯系統公式集的性質. 通過在基礎命題邏輯系統BL的公式集F(S)中引入演繹系統的概念, 證明演繹系統與結論之集的同一性; 通過在基礎命題邏輯系統BL的公式集F(S)中引入強同余關系的概念(其實質是在通常同余關系的定義中添加條件), 證明等價的公式相互等價, 并給出二者之間相互確定的方法; 最后證明演繹系統與強同余關系之間相互轉換的還原性, 進而證明二者之間的一一對應關系.

1 預備知識

定義1[2]由下列公式集、 公理集、 推理規則組成的系統稱為BL命題演算系統, 簡稱BL系統.

3) 推理規則為MP規則: 由φ,φ→ψ可得ψ.

引理2[2]在BL系統中, ?φ,ψ,χ,φ1,ψ1,φ2,ψ2∈F(S), 下列結論成立:

即HS規則成立.

2 演繹系統及其特征刻畫

定義3設F(S)是BL系統的公式集,A?F(S), 若A滿足:

1)T?A; 2) 若φ∈A,φ→ψ∈A, 則ψ∈A.

則稱A為BL命題邏輯系統的公式集F(S)的演繹系統, 或稱A為BL系統的演繹系統.

例1易證在BL系統中,T和F(S)是兩個演繹系統, 稱為平凡演繹系統.

定理1在BL系統中, 設Γ?F(S), 則D(Γ)是F(S)的演繹系統.

定理2在BL系統中, 設A?F(S), 則A是F(S)的演繹系統當且僅當A=D(A).

證明: 充分性. 由定理1知D(A)是F(S)的演繹系統, 即A是F(S)的演繹系統.

由于在BL系統的公式集F(S)中由可證關系定義的二元關系:φψ當且僅當φ→ψ僅是公式集F(S)上的預序關系, 因此不能應用文獻[12]中通過通常的同余關系在F(S)中確定演繹系統. 本文在BL命題邏輯系統的公式集F(S)中定義一種強同余關系, 并證明通過強同余關系可以決定與之對應的演繹系統.

定義4在BL系統中, 設～?F(S)2, 稱～為F(S)上的強同余關系, 如果～滿足:

1) ～是一個等價關系;

2) ～保持&,→運算, 即若φ1～φ2,ψ1～ψ2, 則φ1°ψ1～φ2°ψ2, 其中°∈{&,→};

綜合1),2)以及定義3可知,A～是F(S)上的演繹系統.

根據定理3知下列定義合理.

例3結合例2和引理3可知, 由可證等價關系誘導的F(S)上的演繹系統是定理之集T.

命題1在BL系統中, ～1和～2是F(S)上的強同余關系, 且～1?～2, 則A～1?A～2.

3 演繹系統誘導的強同余關系

定理4在BL系統中,A是F(S)上的演繹系統, ?φ,ψ∈F(S), 定義φ～Aψ當且僅當φ→ψ∈A且ψ→φ∈A. 則～A是F(S)上的強同余關系.

證明: 1) ～A是等價關系. ?φ,ψ,χ∈F(S), 有下列結論:

② 若φ～Aψ, 則φ→ψ∈A且ψ→φ∈A, 所以ψ～Aφ.

(ψ→φ)→((χ→ψ)→(χ→φ)), (φ→ψ)→((ψ→χ)→(φ→χ))∈A.

由于A是演繹系統, 根據定義3中2)得χ→φ,φ→χ∈A. 所以φ～Aχ∈A.

綜合①,②,③知, ～A是等價關系.

2) ～A保運算→,&. 設φ1,φ2,ψ1,ψ2∈F(S), 且φ1～Aφ2,ψ1～Aψ2. 由～A的定義知,φ1→φ2∈A且φ2→φ1∈A,ψ1→ψ2∈A且ψ2→ψ1∈A.

(φ1→φ2)→((ψ1→φ1)→(ψ1→φ2)), (ψ2→ψ1)→((ψ1→φ2)→(ψ2→φ2))∈A;

由φ1→φ2,ψ2→ψ1∈A,A為演繹系統和定義3中2)知, (ψ1→φ1)→(ψ1→φ2)∈A, (ψ1→φ2)→(ψ2→φ2)∈A; 再結合引理2中2)和A為演繹系統知, (ψ1→φ1)→(ψ2→φ2)∈A. 同理可得(ψ2→φ2)→(ψ1→φ1)∈A. 結合～A定義可得(ψ1→φ1)～A(ψ2→φ2).

② 再證～A保運算&. 由φ1→φ2∈A,ψ1→ψ2∈A和引理2中1), 得φ1&ψ1→φ2&ψ2∈A; 同理可得φ2&ψ2→φ1&ψ1∈A. 結合～A定義可得φ1&ψ1～Aφ2&ψ2.

綜合1)～3)可知～A是F(S)上的強同余關系.

根據定理4知下列定義合理.

定義6在BL系統中, 設A是F(S)上的演繹系統, 令

～A={(φ,ψ)∈F(S)×F(S)|φ→ψ∈A且ψ→φ∈A},

稱～A為F(S)上由演繹系統A誘導的強同余關系.

命題2在BL系統中,A1和A2是F(S)的演繹系統, 且A1?A2, 則～A1?～A2.

證明: 由定義6可知, ～A1={(φ,ψ)|φ→ψ,ψ→φ∈A1}, ～A2={(φ,ψ)|φ→ψ,ψ→φ∈A2}. ?(φ,ψ)∈～A1, 有φ～A1ψ, 即φ→ψ∈A1且ψ→φ∈A1. 由條件知A1?A2, 因此φ→ψ∈A2且ψ→φ∈A2, 即(φ,ψ)∈～A2. 所以～A1?～A2.

4 強同余關系與演繹系統相互轉換的還原性

定理5在BL系統中下列結論成立： 1) 若A是F(S)上的演繹系統, 則A～A=A; 2) 若～是F(S)上的強同余關系, 則～=～A～.

證明: 1) 由定義6知, 由演繹系統A誘導的強同余關系為

～A={(φ,ψ)∈F(S)×F(S)|φ→ψ∈A且ψ→φ∈A}.

再由定義5知, 由強同余關系～A誘導的演繹系統為

推論1在BL系統中下列結論成立: 1) 若A1,A2是F(S)上的演繹系統, 且～A1=～A2, 則A1=A2; 2) 若～1,～2是F(S)上的強同余關系, 且A～1=A～2, 則～1=～2.

證明: 1) 由于～A1=～A2, 因此A～A1=A～A2, 于是根據定理5中1)得A1=A2. 2) 由于A～1=A～2, 因此～A～1=～A～2, 于是根據定理5中2)得～1=～2.

[1] Chang C C. Algebraic Analysis of Many Valued Logic [J]. Trans Amer Math Soc, 1958, 88(2): 467-490.

[3] Esteva F, Godo L. Monoidalt-Norm Based Logic: Towards a Logic for Left-Continuoust-Norms [J]. Fuzzy Sets and Systems, 2001, 124(3): 271-288.

[4] 裴道武, 王國俊. 形式系統L*的完備性及其應用 [J]. 中國科學(技術科學), 2002, 32(1): 56-64. (PEI Daowu, WANG Guojun. The Completeness and Application of Form System L*[J]. Scientia Sinica (Technologica), 2002, 32(1): 56-64.)

[5] 吳洪博. 基礎R0-代數與基礎L*系統 [J]. 數學進展, 2003, 32(5): 565-576. (WU Hongbo. BasisR0-Algebra and BasisL*System [J]. Advances in Mathematics, 2003, 32(5): 565-576.)

[6] 吳望名. Fuzzy蘊涵代數 [J]. 模糊系統與數學, 1990, 4(1): 56-64. (WU Wangming. Fuzzy Implication Algebras [J]. Fuzzy Systems and Mathematics, 1990, 4(1): 56-64.)

[7] 徐揚. 格蘊涵代數 [J]. 西南交通大學學報, 1993, 28(1): 20-27. (XU Yang. Lattice Implication Algebras [J]. Journal of Southwest Jiaotong University, 1993, 28(1): 20-27.)

[8] 張小紅. 模糊邏輯及其代數分析 [M]. 北京: 科學出版社, 2008. (ZHANG Xiaohong. Fuzzy Logic and Its Algebraic Analysis [M]. Beijing: Science Press, 2008.)

[9] 周建仁, 吳洪博. R0-蘊涵算子所導出的邏輯函數的特征 [J]. 數學學報(中文版), 2014, 57(2): 235-248. (ZHOU Jianren, WU Hongbo. The Characteristics of Logic Functions Determined by R0-Implication Operator [J]. Acta Mathematica Sinica (Chinese Series), 2014, 57(2): 235-248.)

[10] 吳洪博, 石慧君. Heyting系統及其H-Locale 化形式 [J]. 數學學報(中文版), 2012, 55(6): 1119-1130. (WU Hongbo, SHI Huijun. Heyting System and Its H-Localification [J]. Acta Mathematica Sinica (Chinese Series), 2012, 55(6): 1119-1130.)

[11] 吳洪博, 汪寧. 基于正則FI代數的MT理想及其應用 [J]. 電子學報, 2013, 41(7): 1389-1394. (WU Hongbo, WANG Ning. MT Ideals of Regular FI Algebras with Their Applications [J]. Acta Electronica Sinica, 2013, 41(7): 1389-1394.)

[12] 周建仁, 謝晶晶, 吳洪博. 基于剩余格的一類度量空間及性質 [J]. 吉林大學學報(理學版), 2012, 50(5): 897-901. (ZHOU Jianren, XIE Jingjing, WU Hongbo. A Metric Structure and Its Properties Based on Metric Residual Lattice [J]. Journal of Jilin University (Science Edition), 2012, 50(5): 897-901.)

[13] 周建仁, 吳洪博. BL代數的一種弱化形式 [J]. 吉林大學學報(理學版), 2014, 52(2): 231-236. (ZHOU Jianren, WU Hongbo. A Weakened Form of BL-Aigebra [J]. Journal of Jilin University (Science Edition), 2014, 52(2): 231-236.)

[14] 劉春輝. 有界Heyting代數的模糊LI-理想 [J]. 工程數學學報, 2016, 33(4): 391-401. (LIU Chunhui. Fuzzy LI-Ideals in Bounded Heyting Algebras [J]. Chinese Journal of Engineering Mathematics, 2016, 33(4): 391-401.)

[15] 劉慧敏, 吳洪博. DFI代數的距離函數及其性質 [J]. 吉林大學學報(理學版), 2016, 54(2): 207-214. (LIU Huimin, WU Hongbo. Distance Function of DFI-Algebras and Its Properties [J]. Journal of Jilin University (Science Edition), 2016, 54(2): 207-214.)

[16] 汪寧, 吳洪博. SWBR0代數的蘊涵理想及其誘導的商代數 [J]. 吉林大學學報(理學版), 2013, 51(1): 21-26. (WANG Ning, WU Hongbo. Implication Ideal with Derived Quotient Algebra of SWBR0-Algebra [J]. Journal of Jilin University (Science Edition), 2013, 51(1): 21-26.)

[17] 吳洪博.ukasiewicz命題邏輯中公式的Γ- 真度理論和極限定理 [J]. 中國科學(信息科學), 2014, 44(12): 1542-1559. (WU Hongbo. The Theory of Γ-Truth Degrees of Formulas and Limit Theorem inukasiewicz Propositional Logic [J]. Scientia Sinica (Informationis), 2014, 44(12): 1542-1559.)

[18] 吳洪博. 推理閉包算子及其誘導的空間 [J]. 西北大學學報(自然科學版), 2008, 38(1): 9-14. (WU Hongbo. The Reasoning Closure Operator with Its Induced Space [J]. Journal of Northwest University (Natural Science Edition), 2008, 38(1): 9-14.)

[19] 王國俊, 折延宏. 二值命題邏輯中理論的發散性、 相容性及其拓撲刻畫 [J]. 數學學報, 2007, 50(4): 841-850. (WANG Guojun, ZHE Yanhong. Topological Description of Divergency and Consistency of Two-Valued Propositional Theories [J]. Acta Mathematica Sinica, 2007, 50(4): 841-850.)