数理逻辑的若干应用

第38卷第9期高师理科学刊Vol.38No.92018年9月JournalofScienceofTeachers′CollegeandUniversitySep.2018文章编号：1007-9831（2018）09-0056-05数理逻辑的若干应用杜君花，梁红梅，马艳萍（齐齐哈尔大学理学院，黑龙江齐齐哈尔161006）摘要：研究了数理逻辑的若干应用，即利用数理逻辑证明某些数学证明方法的合理性，证明集合论中的某些关系，证明数学分析中的“一致”与“处处”的关系，证明某些推理形式的正确性，证明命题的等价性及在社会科学中的应用．关键词：数理逻辑；逻辑公式；推理形式；等价；反证法中图分类号：O142∶G642.0文献标识码：Adoi：10.3969/j.issn.1007-9831.2018.09.013SeveralapplicationsofmathematicallogicDUJun-hua，LIANGHong-mei，MAYan-ping（SchoolofScience，QiqiharUniversity，Qiqihar161006，China）Abstract：Severalapplicationsofmathematicallogicarestudied．Forexample，usingmathematicallogictoprovethevalidityofcertainmathematicalproofmethods，provecertainrelationsinsettheory，provetherelationshipbetweenconformityandeverythinginmathematicalanalysis，andprovecertaincorrectnessofthereasoningform，theequivalenceofproofpropositionsanditsapplicationinsocialsciences．Keywords：mathematicallogic；logicalformula；reasoningform；equivalent；proofsbycontradiction数理逻辑是离散数学的重要组成部分之一，是计算机科学的数学基础，其内容主要侧重于逻辑演算，即命题逻辑演算和一阶谓词逻辑演算．这些内容是构成数理逻辑其它分支的共同基础，数理逻辑是用数学方法研究思维形式与规律的科学[1-6]，它在自然科学、计算机科学、企业管理、社会科学及日常生活中都有着广泛的应用[7-10]．1证明数学证明方法的合理性在数学证明中常用证明方法（如反证法和归纳法等）的合理性用语言叙述起来显得生硬、麻烦．但如果用命题逻辑或一阶逻辑的知识来证明就比较容易．例1证明反证法的合理性．证明定理的一般形式为pQ®，若定理为真，则1pQ®=．若用反证法证明，即如果Q不真，连同条件p一起产生矛盾（=0pQÙØ）．只需证10pQpQ®=ÛÙØ=．事实上，1pQpQ®=ÛØÚ=1()00pQpQÛØØÚ=ÛÙØ=．例2证明数学归纳法的合理性．证明设论域={自然数}，命题是()px．只需证(1)p，()(1)pkpk®+蕴涵()npn．收稿日期：2018-03-05基金项目：黑龙江省省属高等学校基本科研业务费科研项目（135209250）；齐齐哈尔大学教育科学研究项目（2017028）；齐齐哈尔大学教育科学研究项目（2015109）作者简介：杜君花（1975-），女，黑龙江齐齐哈尔人，副教授，硕士，从事代数学、复杂系统控制与估计研究．E-mail：[e-mail]第9期杜君花，等：数理逻辑的若干应用57（反证）（1）0n$，0()pnØ（假设）（2）()(1)pkpk®+（前提）（3）()(1)pkpkØÚ+（（2））（4）(1)()pkpk+ÚØ（（3））（5）(1)()pkpkØ+®Ø（（4））（6）00()(1)pnpnØ®Ø-（（5））（7）0(1)pnØ-（（1）（6））按以上方法依次做下去，得到（m）(1)pØ（m+1）(1)p（前提）（m+2）(1)(1)ppÙØ（（m）（m+1））得到矛盾式，说明()npn．2证明集合论中的某些关系用数理逻辑的有关知识还可以证明一些集合的运算性质，如设全集为I，A，B，C为I的任意子集，则有：（1）ABBAÈ=È，ABBAÇ=Ç；（2）()()ABCABCÈÈ=ÈÈ，()()ABCABCÇÇ=ÇÇ；（3）()()()ABCABBCÈÇ=ÈÇÈ，()()()ABCABACÇÈ=ÇÈÇ；（4）AAAÈ=，AAAÇ=；（5）AAjÈ=，AIAÇ=；（6）AIIÈ=，AjjÇ=；（7）~AAIÈ=，~AAjÇ=；（8）~(~)AA=；（9）()AABAÈÇ=，()AABAÇÈ=；（10）~()~~ABABÈ=Ç，~()~~ABABÇ=È．以上等式均可用逻辑公式来证明．这里仅以式（3）和式（10）为例进行说明．证明（3）由于()()()()xABCxAxBxCxAxBxAxCxÎÈÇÛÎÚÎÙÎÛÎÚÎÙÎÚÎÛÎ()()[()()ABxACxABACÈÙÎÈÛÎÈÇÈ，故()[()()]ABCABACÈÇ=ÈÇÈ．同理可证()()()ABCABACÇÈ=ÇÈÇ．（10）由于~(B)[)]()()()(~)(~)xAxABxAxBxAxBxAxBÎÈÛØÎÈÛØÎÚÎÛØÎÙØÎÛÎÙÎÛ（(~~)xABÎÇ，故~()~~ABABÈ=Ç．同理可证~()~~ABABÇ=È．用逻辑公式还可以证明关于集合的恒等式，而且有时比利用集合的知识证明要简单．例3证明()()()ABCABAC-ÈÛ-Ç-．证明由于[()](())()()xABCxAxBCxAxBxCxAxBxCÎ-ÈÛÎÙØÎÈÛÎÙØÎÚÎÛÎÙÎÙÎÛ()()()()[()()]xAxBxAxCxABxACxABACÎÙÎÙÎÙÎÛÎ-ÙÎ-ÛÎ-Ç-，故()()ABCAB-È=-Ç()AC-．例4()()()ABCABACÇ-=Ç-Ç．证明由于()()()()()xABCxAxBxCxAxBxCxABÎÇ-ÛÎÙÎÙÎÛÎÙÎÙØÎÛÎÇÙ(())()())(()())xACxABxACxABACØÎÇÛÎÇÙÎÇÛÎÇ-Ç，故()()()ABCABACÇ-=Ç-Ç．3证明分析中的一致与处处的关系例5证明函数列{}()nSx一致收敛于()Sx，其中：(,)xabÎ，则它必处处收敛于()Sx．例５的结论用数学分析的知识证明起来很繁琐，如果用数理逻辑的知识证明就比较容易．证明设论域为R，则{}()nSx在任意(,)xabÎ处收敛于()Sx，即(0((,)xNnxabee®$ÎÙ|()()|))nnNSxSxe³®-，由{}()nSx一致收敛于()Sx，则得0(0((,)Nxnxabnee®$ÎÙ³0|()()|))nNSxSxe®-．若函数列{}()nSx一致收敛于()Sx，则由双重量词的关系式(,)(,)NxPNxxNPNx$Þ$可知，一致收敛必处处收敛．58高师理科学刊第38卷4证明某些推理形式的正确性推理形式有多种，如三段论推理、选言推理和类比推理等．这些推理形式的正确性都可以用数理逻辑知识加以证明．例6证明三段论推理形式的正确性．证明三段论推理的一般形式为(()())()()xQxRxQaRa®Ù®．（1）(()())xQxRx®（前提）（2）()()QaRa®（（1））（3）()Qa（前提）（4）()Ra（（2），（3））选言推理包括相容选言推理和不相容选言推理．这里以不相容选言推理的否定肯定式为例进行证明．例7证明不相容选言推理的否定肯定式的正确性．证明不相容选言推理的否定肯定式的一般形式为12npppÚÚÚL，1pØ211iinippppp-+ØØØØÞLL(1)in££（1）12npppÚÚÚL（前提）（2）1pØ（前提）（3）121()nppppÚÚÙØL（（1），（2））（4）1121()[()]npppppÙØÚÚÚÙØL（（3））（5）21()npppÚÚÙØL（（4））（6）2nppÚÚL（（5））（7）2pØ（前提）（8）232()nppppÚÚÚÙØL（（6），（7））（9）2232()[()]npppppÙØÚÚÚÙØL（8）（10）32()npppÚÚÙØL（9）（11）3nppÚÚL（10）以此类推，可得（m）inppÚ（（1m-））（1m+）npØ（前提）（2m+）()innpppÚÙØ（（m），（1m+））（3m+）()()innnppppÙØÚÙØ（（2m+））（4m+）inppÙØ（（3m+））（5m+）ip（（4m+））5证明命题的等价性一个命题的４种形式的关系见图１．原命题与其逆否命题是等价的，一个命题的逆命题与其否命题也是等价的．这２种等价关系均可用数理逻辑知识加以证明．例8证明一个命题与其逆否命题是等价的．证明命题的一般形式为pQ®，其逆否命题形式为QpØ®Ø，只需证明pQQp®ÛØ®Ø．事实上，pQpQQpQ®ÛØÚÛØØÚØÛØp®Ø．逆命题原命题否命题逆否命题互逆互逆互否互否等价图１一个命题４种形式的关系第9期杜君花，等：数理逻辑的若干应用596在社会科学中的应用一篇好的文章是有严密的逻辑结构的，尤其是议论文，它的论证过程是符合数理逻辑的．例9一篇写“按劳分配规律具有客观性”的文章是分以下４个部分写的：（a）一切科学规律都具有客观性；（b）政治经济学规律是科学规律；（c）按劳分配规律是政治经济学规律；（d）所以说，按劳分配规律具有客观性．试判断论证过程是否符合数理逻辑．解令()Sx：x是科学规律；()Px：x有客观性；()Qx：x是政治经济学规律；a：按劳分配规律．则（a）：(()())xSxpx®；（b）：(()())xQxSx®；（c）：()Qa；（d）：()pa验证（1）()Qa（（c））（2）(()())xQxSx®（（b））（3）()()QaSa®（（2））（4）()Sa（（1），（3））（5）(()())xSxpx®（（a））（6）()()Sapa®（（5））（7）()pa（（4），（6））说明由（a）、（b）、（c）可得到（d），所以论证过程是符合数理逻辑的．文章中的一段话也是一样，应具有严密的逻辑关系．例10“人的正确思想是从哪里来的？是从天上掉下来的吗？不是，是自己头脑里固有的吗？不是，人的正确思想只能从社会实践中来”，试判断论证过程是否符合数理逻辑．解令p：人的正确思想是从天上掉下来的；Q：人的正确思想是自己头脑里固有的；R：人的正确思想是从社会实践中来的，则有pQRÚÚ，pØ，QØ．由于()pQRpQpQRÚÚÙØÙØ=ØÙØÙ．所以说人的正确思想只能从社会实践中来．因此论证过程是符合数理逻辑的．7在日常生活中的应用数理逻辑的知识除上述应用之外，在日常生活中，不经意地就会用它来解决一些问题．例11有时某人说一段话繁杂，甚至有些还是多余的，这样使语言不易被人理解，这时可以利用数理逻辑的知识来帮助理解其含义．看一段话：“如果张红去打球则王敏不去，如果王敏去则李明就不去，如果张红不去则李明去，如果张红去则李明不去．”，从这段话中，不能马上判断出王敏到底去不去打球，但可作如下分析：令p：张红去打球；Q：王敏去打球；R：李明去打球，则有pQ®Ø；QR®Ø；pRØ®；pR®Ø．（1）pQ®Ø（已知）（2）pRØ®（已知）（3）QR®Ø（已知）（4）QRØÚØ（（3））（5）RQØÚØ（（4））（6）RQ®Ø（（5））（7）pQØ®Ø（（2），（6））（8）pQÚØ（（7））（9）pQØÚØ（（3））（10）()()pQpQÚØÙØÚØ（（8），（9））（11）()QppØÚÙØ（（10））（12）QØ（（11））所以，无论谁去或不去，王敏都不去，而且从证明中还可以看出，“如果张红去则李明不去”这句活是多余的，由前3句话就可以说明王敏不去打球．60高师理科学刊第38卷例12某珠宝店钻石被盗，共有４人是嫌疑犯，在