下载费用：5 元 &
离散数学之数理逻辑.doc 第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德摩根和乔治布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯诺意曼，图灵，克林，等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。第11章命题逻辑学习要求掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。本章就是讨论逻辑学中的对象语言命题及其演算，它相当于自然语言中的语句。§111命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。例1111人总是要死的。例1112苏格拉底是人。2例1113苏格拉底是要死的。例1114中国人民是勤劳和勇敢的。例1115鸵鸟是鸟。例11161是质（素）数。例1117今天没有下雨。例1118公元二千年会出现生物计算机。例1119太阳系外的星球上有人。例11110他喜欢读书也喜欢运动。例11111他在机房里或者在图书馆里。例11112电灯不亮是灯泡或线路有毛病，或者是停电所致。例11113如果和都是正数，则也是正数。ABAB例11114当且仅当和都大于零。0?XYXY例。例11116天气多好啊例11117他来了吗例11118全体起立例11119帮帮我吧例111200。X例11121我正在说谎。上述例，例1是可以判断为对（真，成立）的陈述句，例，11114是能够判断为不对（假，不成立）的陈述句，例在人类历史发展的长河中能够判断它是真或是假的陈述句，例1根据“他”当时的情况能够判断出是真或是假的陈述句，例11115在二进制计算中为真，在十进制计算中为假，也还是可以判断为真或为假的陈述句，例11116是感叹句，例11117是疑问句，例11118是命令句，例11119是祈使句，例11120中X是一个未知数（变量），无法判断是真还是假，例11121是无法判断真假的悖论。从以上的分析可以看出，表达思想的语句有不同的类别，数理逻辑中研究的是出现较多而又比较规范的语句可以判断出真或假的陈述句。定义1111凡是能判断是真或是假的陈述句称为命题。3如前面的例都是命题，例1都不是命题。命题的值为真或假。今后约定用1表示真，0表示假，除T和F以外的大写英文字母或它们后面跟上数字如A，A1，B5，PI等或数字（如123，28，）表示命题。如PM8085芯片有40条引线，或12M8085芯片有40条引线。P或12称为命题“M8085芯片有40条引线“的标识符。当命题标识符代表一个确定的命题时（如P或12，A人总是要死的），称为命题常元，当命题标识符代表非确指的命题时，称这样的命题标识符为命题变元。注意命题变元不是命题，只有对命题变元用一个确定的命题代入后，才能确定其值是1还是0。定义1112用一个确定的命题代入一个命题标识符（如P），称为对P进行指派（赋值，或解释）。再看前面的例，这些命题不能再分解为更简单的能判断其值为1或0的陈述句了，这类命题称为原子命题。在例1117中，如果表示今天下雨为原子命题P，则今天没有下雨是P的否定；例10可分解为原子命题P他喜欢读书，Q他喜欢运动，用联结词“也”联结起来；例11111可分解为原子命题P他在机房里，Q他在图书馆里，用联结词“或者”联系起来；例11113可分解为原子命题PA是正数，QB是正数，RAB是正数，用联结词“和”与“如果，则”联系起来；例11114可分解为原子命题PXY0，QX0，RY0，用联结词“当且仅当”与“都”联系起来，这类?用联结词，标点符号和原子命题构成的命题称为复合命题。二、逻辑联结词日常生活、工作和学习中，自然语言里我们常常使用下面的一些联结词，例如非，不，没有，无，并非，并不等等来表示否定；并且，同时，以及，而（且），不但而且，既又，尽管仍然，和，也，同，与等等来表示同时；虽然也，可能可能，或许或许，等和“或（者）”的意义一样；若则，当则与“如果那么”的意义相同；充分必要，等同，一样，相同与“当且仅当”的意义一样。即是说在自然语言中，这些逻辑联结词的作用一般是同义的。在数理逻辑中将这些同义的联结词也统一用符号4表示，以便书写、推演和讨论。现定义常用联结词如下定义1113在命题P的适当地方插入“不”或者“没有”产生的新命题称为P的否定，记为?P读成“非P”。?P的取值依赖于P的取值，即定义运算表为命题P?P10真值01例如P2是一个质数（值为1），?P2不是一个质数（值为0）或2是一个和数。注意1不同的陈述句可能确定同一个命题；2否定是一个一元运算。定义1114两个命题P和Q产生的一个新命题记为P?Q，读成“P与Q”或“P和Q的合取”。合取的运算表为命题PQP?Q真值000如例11110，P他喜欢读书，Q他喜欢运动，P和Q的合取为P?Q他喜欢读书也喜欢运动。又如A猫吃鱼，B220，则A?B猫吃鱼而且220。注意1数理逻辑中的联结词“合取”只考虑命题之间的形式关系，不考虑命题内容的实际含义，只有在研究取值时才加以考虑。2合取是一个二元运算。定义1115两个命题P或Q产生一个新命题，记为P?Q，读成“P析取Q”，析取的运算表为命题PQP?Q真值000如例11112，P他在机房里，Q他在图书馆里，P?Q他在机房或图5书馆里。又如P1他是游泳冠军，P2他百米是赛冠军，P1?P2他是游泳冠军或百米赛跑冠军。A猫吃鱼，B220，A?B猫吃鱼或者220。注意1析取可细分为两种，一种是“不可兼或”如前面例11112，一种是“可兼或”，如P1?P2。有的将不可兼或记为“”，可兼或记为“?”。显然“?”包含“”为其特殊情况。故我们着重考虑“?”的情形。2在自然语言或形式逻辑中，用来析取联结的对象往往要求属于同一类事物，但是在数理逻辑中不作这种限制，例如A?B猫吃鱼或者220是允许存在的命题。3析取是一个二元运算。定义1116设P，Q是两个命题，“若P则Q”是一个新命题，记为P→Q，读成P推出Q（或Q是P的必要条件，P是Q的充分条件），P称为条件联结词“→”的前件，Q为→后件。如P河水泛滥，Q周围的庄稼被毁。P→Q若河水泛滥，则周围的庄稼被毁。A20及命题X和Y都大于零用双条件联结词产生的命题，这个命题取值为0。又如，我没有收到信当且仅当没有人给我写信，它的值为1。约定在整数范围内讨论，P220，QIBMPC是一种微型计算机，P?Q220当且仅当IBMPC是一种微型计算机，此命题取值为0。注意1双条件联结词联系的命题不限定属于同一类事物。2双条件是一个二元运算。这五种逻辑联结词也可以称为逻辑运算，与一般数的运算一样，可以规定运算的优先级，我们规定的优先级顺序依次为?，?，?，?，?。如果出现的逻辑联结词相同，又没有括号时，从左到右顺序运算。如果遇到有括号时就先进行括号中的运算。考察例11112．令P电灯亮，Q灯泡有毛病，R线路有毛病，S停电。则可将该语句符号化为Q?R?S??P。三、命题运算的真值表定义1118在命题公式中，对于分量指派的各种可能组合，即确定了该命题的各种真值情况，把它汇列成表格，就是命题的真值表。任意给定一个复合命题后，用原子命题和逻辑联结词表出，再利用真值表就可以计算出复合命题的值。当复合命题用原子命题变元、逻辑联结词和括号组成时，可以得出该复合命题变元的真值表。例11122求P?P?Q，P??P，P??P的真值表。解PQP?QP?P?Q0000P?PP??P7例11123求Q?R?S??P的真值表。解PQRSR?SQ?R?S?PQ?R?S??P124求?P?Q??P??Q的真值表。解PQP?Q?P?Q?P??Q?P?Q??P??Q111习题1．举出原子命题和复合命题的例子五个以上。2．将下列命题符号化P?PP??P81我一边看书一边听音乐。2天下雨了，我不去上街。3实函数可微当且仅当连续。此命题的真值是什么XFXF4除非你努力，否则你就会失败。5合肥到北京的列车是中午十二点半或下午五点五十分开。6优秀学生应做到思想身体学习都好。3．求下列各式的真值表1P?Q?P。?2P?Q?R?P??R?Q。3P→Q→P?P→P→Q。4P→Q?RP→Q?P→R。5P→Q?R→QP?R→Q。6P→Q→R→?P→?Q→?R。7?P?Q。4．设命题A1，A2的真值为1，A3，A4两命题的真值为0，求下列命题的真值1。4321321???2。???3。431321AAA??4。2135．将下列语句符号化1占据空间的，有质量而且不断变化的称之为物质。2占据空间的，有质量者称为物质，而物质是不断变化的。3如果你来了，那么他唱歌与否要看你是否伴奏而定。4我们不能既划船又跑步。9§112命题公式与真值函数由命题变元，括号，逻辑联结词按下列规定形成的符号串是我们讨论的对象。一、命题演算公式定义1121由命题变元，逻辑联结词和括号构成的下述表达式称为命题合式公式（WELLFORMEDFORMULA）或命题演算公式，简称公式，记为WFF1单个原子命题变元是WFF；2若P，Q是WFF，则都是,,,,QPQP?????WFF；3只有有限次使用1,2得到的表达式才是WFF。为了书写和输入计算机，以及进行运算方便起见，规定1的括号，?整个WFF的最外层括号可以省略，2已定好逻辑联结词的优先级后，优先级的括号可省略。,,,,RPQPRQPQP???????等都是WFF。但就不是WFF，因为前一表达式R与TRSS之间没有逻辑联结词，后一表达式中括号不配对，故不符合定义1121。按BNF（BACKUSNAURFORM）符号，WFF的语法定义为WFF||?，〈原子公式〉|{〈WFF〉}???||定义1122令A为WFF，对A中出现的全部原子命题变元P1，P2，，PN分别赋以真值0或1所得到的一组真值（N个）称为A的一个指派或解释。从§111的例1可以看出，对命题变元作指派，再利用逻辑联结词的真值表（即逻辑运算规则）可以演算出WFF的真值表。下面再看几个例子。例1121求P→Q?Q→P的真值表。10解例1122P→Q?P→Q的真值表为解例1123P→Q?P?Q的真值表为?二、真值函数定义1123以{真，假}为定义域和值域的函数为真值函数。如由五个逻辑联结词产生的所有WFF都是真值函数，因此有无穷多个真值函数，显然最基本而重要的真值函数还是。QPQP?????,,,,当真值函数的变元为N个时，共有2个指派。通过列出真值表也可以定N义真值函数。例1124确定下列真值表对应的真值函数PQRF1P,Q,RF2P,Q,R0001PQP?QQ?PP?Q?Q?P）PQP?QP?Q?PP?Q?P?QPQP?QP??QP?Q?P??Q以F1（P，Q，R）来考虑，表的第一行说明F1的值为1，且指派中P，Q，R都取值为1，可用项P∧Q∧R，表示，表的第三行说明F1的值为1，此时指派中P，R取值为1，Q取值为0，即Q取值为1，可用表示，?RQP??此时P，Q，R的其它指派都使P?Q?R，或为0，同理可用R?分别表示表第四、七行的1，???,故F1（P，Q，R）QP?????同理F2（P，Q，R）。RRP??注意由真值表确定的真值函数不一定是最简单的WFF，不一定只有一个表达式。例如PQRP?R?RP??Q?Q?RP?R?P??Q??Q?R1000将这个真值表与F1（P，Q，R）的真值表相比较，对变元的任一指派，可以看到与（）这两个表达式可代表同一个真值R????函数，而此两式相比，就不是最简单的WFF。三、重言式与矛盾式我们注意到例和例。对命题变元无论作什么样的指派，例1122中的WFF永远取值为1，这种类型的WFF称为重言永真式；例1123中的WFF永远取值为0，这种类型的WFF称为矛盾（永假）式；而例中的WFF则对有的指派取值为1。对另外指派又取值为0，这种类型的WFF称为可满足公式。显然重言式（或永真函数）是可满足公式，矛盾式是不可满足公式。12定义1124对WFF的命题变元无论作什么指派，公式均取值1时，称之为重言式，记为T；公式均取值0时称之为矛盾式（或不可满足式），记为F。若有指派使WFF取值1，则称该公式为可满足公式。定理1121任意两个重言（矛盾）式的合取或析取仍然是一个重言（矛盾）式。由定义1124及析取、合取的真值表立即可以证明此定理。112习题1．下列符号串哪些是合式公式哪些是重言式或矛盾式哪些是可满足公式1；2；QP??QP?3；4；??????5；??6。P?2．用真值表证明下列各式为重言式1RQ????3P4?5QRQ??6?,7TPFP?8??,9Q?10PQ2?134??1315QP????6RP7；18SQSR?；9P??。,20PQ?§113公式的等价与蕴涵在§112中我们已经看到真值函数F1P,Q,R的表达式有14或RQPRQPRQP?????????，又如和代表同一真值函数，对同R?（?一真值函数的几个不同的WFF有下面的定义。定义1131设P1，P2，，PN为出现在两个WFFA和B中的原子命题变元。如果对P1，P2，，PN的任意真值指派，A和B的真值都相同，则称A和B逻辑相等或说A和B等价，记为）。或（??例如，用真值表和定义1131可以得到下列基本等Q??价式对合律1P幂等律,2?交换律3PQQ?结合律,4RQRRP????分配律5P???吸收律,6P?德摩根律7QP????同一律,8TF??零一律9F?否定律,10PP条件等价式Q???双条件等价式。2??当WFF中出现的原子命题变元很多时，用真值表和定义1131来判断两个WFF是否等价就显得麻烦，因而可利用上述基本等价式和下面的定理1131就可以得到一些复杂的等价式。定义1132若WFFX是WFFA的子串，则称X为A的子公式。定理1131X是WFFA的一个子公式，WFFY与X等价，则将A中的X用Y来代替所得的WFFB，必有A与B等价（替换规则）。证明因为在命题变元的任意指派下X与Y的真值相同，故用Y代替X后所得的WFFB与A在任意相应的指派下也有相同的真值，故A与B等价。例1131由吸收律和替换规则可知15PQPQ????例1132证明TPSR?证明R???SPQP?R??S????PQP??SRT???Q??T定理1132在一个重言（矛盾）式中对同一命题变元都用任意一个WFF去替换，仍可得一个重言（矛盾）式。证明因为重言（矛盾）式的真值永为1（0），与变元的指派无关，故对同一变元用任一WFF替换后，其值仍为1（0），所以结果为一个重言（矛盾）式。例1133因为，，当P以某WFF替换后仍为TP???F?重言矛盾式，例如P以去代替，则有SRQS?定理1133合式公式A和B等价当且仅当AB为重言式。证明必要性若A与B等价，则对出现在A，B中的原子命题变元的任意指派A和B有相同的真值，即AB永远取值1，即AB为重言。充分性若AB为重言（矛盾）式，则无论任何指派AB均取值1，即A，B的真值相同，故AB。例1134证明。PQP???16证明TQPQPQPP?????????????故由定理1133得证。例1135P→Q→R?P?Q→R证明RQPRP????????容易验证WFF等价具有下列性质1反身（自反）性。A2对称性若则。B3传递性若，则。?,C定义1133设合式公式A和B中出现的原子命题变元为，如NP,21?果对它们的指派使A取值为1时B也取值为1，则称A蕴涵B（或称B是A的逻辑结果），记为。?例1136。QP??证明PQ?PP?Q0011从上面的真值表可知，使?P取值1的指派0，1和0，0它也使P→Q取值为1，根据定义1133得证?PP→Q。例1137。RPQ???证明PQRP?QQ?RP?Q?Q?RP?R由真值表可知使P→Q?Q→R取值为1的指派1，1，1；0,1,1；0,0,1；（0，0，0）也使P→R取值为1，根据定义1133知。RPQP??定理1134合式公式A?B当且仅当A?B是重言式。证明必要性由A?B的定义知当A取值为1时，B取值也为1。再由A?B的运算表知，当A取值为1时，B取值也为1，A?B为重言式。充分性因为A?B为重言式，所以，当A取值为1时，B的真值必为1否则A?B真值为假，与题设矛盾，所以A?B。例1138PQ??证明TPPQQ??????由定理1134得证。??用定义1133及定理1134易证下列常用的基本蕴涵式1P?Q?P，P?Q?Q；2P?P?Q，Q?P?Q；3?P?P→Q；4Q?P→Q；5?P→Q?P；?P→Q??Q；6P?P→Q?Q；分离规则7?Q?P→Q??P；8?P?P?Q?Q；9P→Q?Q→R?P→R；10P?Q?P→R?Q→R?R；1811P→Q?R→S?P?R→Q?S；12PQ?QR?PR。蕴涵具有下列常用性质1A为重言式，A?B，则B必为重言式；2自反性A?A；3反对称性若A?B且B?A则A?B；4传递性若A?B且B?C则A?C；5若A?B且A?C则A?B?C。6若A?B且C?B，故A?C?B。证明1、2由A?B的定义即可知。3因为A?B且B?A，所以A?B与B?A为重言式，由基本等价式12知A?B为重言式，所以A?B。4由A?B且B?C知A→B?B→C为重言式，据基本蕴涵式9知A→B?B→C?A→C，由性质1知A→C为重言式，故AC。5因A?B且A?C，故A→B，B→C都为重言式，如果A取值为1，则B和C都取值为1，因而B?C取值为1；如果A取值为0，无论B?C取值为1还是取0，A→B?C取值均为1，故A→B?C为重言式，所以A?B?C。6因A?B且C?B故A→B?C→B?T。即?A?B??C?B?T，即?A??C?B?T，即?A?C?B?T，即A?C→B?T，故A?C?B。113习题1．证明（A?B）?（B?C）?（C?A）?（A?B）?（B?C）?（C?A）。2．不要构造真值表证明下列蕴涵式1；QPP?2；?3；Q?4；SP?5；R?196。QPRRPQ?????3．若是否有CBA??BA若是否有?若是否有?4．证明时。5．证明时┐，反之也对。BA§114命题逻辑的推理理论逻辑是研究思维结构和规则的科学，要求能够提供正确的思维规律，提供判定一个论断之有效的准则。数理逻辑则研究正确的推理规则，研究论断的有效性,但要注意到论断的正确性涉及到实践的检验。20什么是论断的有效性呢回忆§113中命题公式的蕴涵概念，并把它推广。定义1141和B为合式公式，若A1?A2??ANB，NA,,21??则称B为前提的有效结论，或说B是的逻辑结果，N,21?N,,?或者说共同蕴涵B。,?例1141证明R→S是P→Q→S，?R?P，Q的有效结论。证明即要证P→Q→S??R?P?Q?R→S，也就是要证明P→Q→S??R?P?Q?R→S为重言式。当然可以应用真值表验证，也可以用等价是验证，往往是比较麻烦的。因此判定论断的有效性，需要有其他论证方法，希望有比较简明的过程，还要有正确的依据。定理1141若，则CBAN??21。AN???21证明已知，故为重言?CBAN???21式。即为重言式，即N??21?为重言式，即为重言CB??21AN??式，所以。AN???21定义1142设S为若干公式的集合（称为前提集合）。如果有公式的有限序列其中AI?S或AI是中某些N,,21?121,,?IA?公式的有效结论，且，则称B是S的逻辑结果或有效结论，或者说从S演AN?绎出B。定理1142设S为公式集，B是一个公式，S能演绎出B的充分必要条件是B是S的逻辑结果。证明充分性因为B是S的逻辑结果，由定义1142知存在公式的有限序列,BAI?S,B是,的逻辑结果，因而由定义11NA,21?NA,21?42得证S演绎出B。必要性设S演绎出B，则存在公式的有限序列其中ANB且N,,21?21AI?S或AI是中某些公式的逻辑结果。121,,?IA?下面用归纳法证明，因为，A1?S且A1?A1，故A1是S的逻辑结果（归纳基础）。设AII2,QXX0论域为{1}；???3APA,FBPB,FA，BXYPY,X，CYXPY,X，?54EXYPX,YPFX,FY，??ABF2F3P2,2P2,3P3,2P3,论域为{2，3}。7．给定公式XPXXPX??1当D为论域单元集时，证明公式在解释下真值必为1；2当D{A,B}时，找出一个解释I使该公式真值为0。8．设论域D只含两个元素，在某个解释下，已知XPXQX，??YPYQY的真值为1，能否断言ZPZQZ真值为1又能??否断言ZPZQZ的真值为1为什么?9．将下列语句符号化1矩阵A是一个有20行30列的整数组，A的所有元素都是非负整数，有些元素是0。若元素AIJ和AIK的JN时有???00XFN则称函数序列{FNX}在区间A,B内收敛于FX。3{FNX}是一个函数序列，FX为一个函数，对任意〉0都存在正整数?N使NN时，对所有，X?A,B有???FN则称{FNX}在区间A,B内一致收敛于FX。55§123谓词公式的等价与蕴涵§122已给出了谓词公式解释的定义，而谓词公式经过解释后就成为命题，能够确定其真值为真还是假，因此，可以讨论谓词公式的等价与蕴涵。定义1231设谓词公式A和B有相同的论域D，若对A和B的任一解释下所得命题的真值都相同，则称A和B在D上等价，记为。如果D?不产生混淆的话，也可记为AB。?定义1232设谓词公式A的论域为D。若在对A的任一解释下，A的真值为真（1），则A在D上是永真（有效）的；若论域D也是任意，则称A为永真（重言）式。若在对A的任一解释下，A的真值为假（0），则称A在D上是永假的；若论域D也是任意的，则称A为不可满足公式（永假式）。56定义1233设谓词公式A的论域为D，若至少有一个解释使A取值1，则称A可以满足公式。由此定义可知重言式是可满足公式。又由定义1231易知A?B当且仅当AB为重言式。?定义1234设D为谓词公式A和B的论域，若在A和B的任一解释下，由A所得的命题真值为1时，由B所得命题的真值也是1，则称A蕴涵B，记为。D?故当且仅当在D上AB为重言式。?由于谓词公式在解释下变为命题，而前一章已指明，在命题逻辑中，任一重言式里同一命题变元用一个合式公式替换后所得结果仍然是重言式，因此命题逻辑中的基本等价式和基本蕴涵式可以推广到谓词逻辑中使用。例如XPXQX?XPXQX，?????XPXYRX,Y??XPX?YRX,Y，????XAX?XAX?F,?XAX?XAX?T。但是，应该注意含有量词的命题和不含量词的命题两者的否定是有区别的，也需要考察量词和其它逻辑联结词的关系。例如，设论域为人的集合。PXX来校上课，则PXX没有来上课。XPX所有的人来校上课，而??XPX不是所有的人来校上课，其意思也是有人没有来校上课，符号化?就是X?PX；反之X?PX有人没有来校上课，其意思就是不是所有??的人来校上课，符号化就是?XPX，因此?XPX?X?PX。?定理1231量词与否定联结词之间的关系为?XPX?X?PX；??XPX?X?PX。?证明若解释I使?XPX取值1；则I使XPX取值0，故对任意X?D（D为论域）PX?F，即对任意X?D，PX?T，这表明I使XPX???取值1。又，若解释I使?XPX取值0，则I使XPX取值1，即有X0?D使?PX01，故有X0?D使PX00，即解释I使XPX取值为0。??57根据定义1231?XPX?XPX。???同理可证另一式。这个定理说明，当否定一个谓词公式时，可以把量词和（视为对偶的）??互换，并把原来量词的辖域中公式换为其否定。定理1232量词辖域的扩张与收缩如下1XPX?Q?XPX?Q；?2XPX?Q?XPX?Q；3XPX?Q?XPX?Q；??4XPX?Q?XPX?Q；5Q?XPX?XQ?PX；?6Q?XPX?XQ?PX；7XPX?Q?XPX?Q；?8XPX?Q?XPX?Q。?证明1设I是PX和Q的一个解释。若XPX?Q在I下取值为1，?则在I下，对任意X?D（论域），PX?Q取值为1。如果Q取值为1，显然XPX?Q取值1，如果Q取值为0，则必有XPX取值为1，即在I下XPX???Q取值1。若XPX?Q在解释I下取值为0，则在I下对任意X?D有PX?Q取值为0。即Q取值0，且对任意X?D，PX取值为0，即Q取值0且XPX取值0，故在I下XPX?Q取值为0。?根据定义1231得?XPX?Q??XPX?Q。同理可证2，3，4。现证明5。Q??XPX??Q??XPX??XPX??Q??XQ?PX。同理可证6。再证明7。XPX?Q?XPX?Q?XPX?Q???X?PX?Q?XPX?Q。同理可证8。注意定理2中的Q可以含有其它变元，只是不含量词中的相应指导变元。58定理1233量词与逻辑连接词?，?有下列基本等价式9?XPX??XQX??XPX?QX；10?XPX??XQX??XPX?QX；11?XPX?XQX?XYPX?QX；12XPX?XQX?XYPX?QY证明9设WFF?XPX??XQX与?XPX?QX的论域为D，在指派I下①若XPX?XQX的真值为1，则XPX和XQX的真值同时为1，即对任意X?D，PX与QX真值同时为1，IE对任意X?D，PX?QX真值为1，IE?XPX?QX真值为1。②若XPX?XQX的真值为0，则XPX与XQX至少有一个?为0。若XPX为0，即?X0?D使得PX00，IE?X0?D使得PX0?QX00，IE?XPX?QX0；若XQX为0，即?X1?D使得QX10，IE?X1?D使得PX1?QX10，IE?XPX?QX0；若XPX与XQX同时为0，即?X2,X3?D使得PX2与QX3的真值均为0，IE?X2,X3?D使得PX2?QX20或PX3?QX30。所以，?XPX?QX真值为0。由①，②知在指派I下?XPX??XQX与?XPX?QX的真值相同，根据的等价的定义就有?XPX??XQX??XPX?QX。10设WFF?XPX??XQX与?XPX?QX的论域为D，在指派I下①若?XPX??XQX的真值为1，则?XPX与?XQX至少有一真值为1，若?XPX的真值为1，则?X0?D使得PX0＝1，IE?X0?D使得PX0?QX0＝1，所以?XPX?QX的真值为1；若?XQX的真值为1，则?X1?D使得QX1＝1，IE?X1?D使得PX1?QX1＝1，所以?XPX?QX的真值为1；若?XPX与?XQX的真值同时为1，则?X2,X3?D使得PX2＝159且QX31，IE?X2?D使得PX2?QX2＝1或PX3?QX3＝1，所以?XPX?QX的真值为1；所以在指派I下，当?XPX??XQX为真时?XPX?QX也为真。②若?XPX??XQX的真值为0，则?XPX与?XQX真值都为0，即?X?D，PX?QX真值为0，所以?XPX?QX的真值为0。由①,②知在指派I下，WFF?XPX??XQX与?XPX?QX的真值相同，根据等价的定义即得?XPX??XQX??XPX?QX。11?XPX??XQX??XPX??YQY换名??X?YPX?QY由112?XPX??XQX?XPX??YQY换名??X?YPX?QY。4定理1234量词与逻辑联结词?有下列基本等价式13?XPX?QX??XPX??XQX。证明?XPX?QX??X?PX?QX??X?PX??XQX???XPX??XQX??XPX??XQX。定理1235量词与逻辑联结词有下列基本蕴涵式14?XPX??XQX??XPX?QX；15?XPX?QX??XPX??XQX；16?XPX?QX??XPX??XQX；17?XPX??XQX??XPX?QX；18?XPX?QX??XPX??XQX。证明14设在解释I之下?XPX??XQX真值为1,则对任意X?D论域,PX真值为1或对任意X?D,QX真值为1,即对任意X?D,PX?QX真值为1,故在I下?XPX?QX真值为1,由定义1234即的证14。15对任意谓词公式14都成立，则对谓词公式?PX和?QX，14也成立，即?X?PX??X?QX??X?PX??QX。但是，?X?PX??X?QX???XPX???XQX???XPX??XQX?X?PX??QX???XPX?QX，60故??XPX??XQX???XPX?QX。因此由原命题和逆否命题同时为真可得?XPX?QX??XPX??XQX。16若在解释I下?XPX?QX为真，即对任意X?D（D为论域），PX?QX为真，IE?X?D，PX为真时QX也为真，即在I下?XPX??XQX为真，由定义即得?XPX?QX??XPX??XQX17?XPX??XQX???XPX??XQX??X?PX??XQX??X?PX?QX??XPX?QX。18?XPX?QX??XPX?QX?QX?PX??XPX?QX??XQX?PX??XPX??XQX??XQX??XPX??XPX??XQX，即?XPX?QX??XPX??XQX。前面只考虑了一个量词合式公式的等价与蕴涵。对于有多个量词的公式，情况要复杂得多，我们已知量词在公式的次序不能随意排列，有些时候交换量词顺序还是等价的，但多数情形下是不等价的。为了说明问题，这里只举两个量词的情况，量词更多时，可使用类似的方法讨论。两个量词的公式有下列八种情况,YXA?,YXA???,,。YXYX它们之间的等价与蕴涵关系如下之定理。定理12361,,YXAYXA???2??3,,?4YXAYX5,,???616,,YXAYX????78,,9YXAYX?证明用定义1231类似于定理1231可以证明1和2。39可以用定义1234证明。这里给出另一种证法。例如对于3可以如下证明,,YXYX???A???,,?定理12362YXYX?定理123210,,?定理1231）A???TY,?故,YXXA???为了记忆上述等价式与蕴涵式，现图示如下注意一阶谓词逻辑的重言式和不可满足公式是考虑了对所有的解释分别使该公式真值为1和0，解释有依赖于论域D。D可能为无限集，故“所有的解释”实际上是无法具体实现的，因而一阶谓词逻辑公式的重言或不可满足的判断问题是非常困难的。直到1936年丘奇（CHURCH）和图灵（TURING）才各自XYX??Y??Y?XXYX?62独立地证明了一阶谓词逻辑的永真（永假）性的判定问题是不可解的。但是后来证明了只要公式是永真的，就有算法在有限步之内验证出该公式是永真的。这里一再强调的“一阶”谓词逻辑只限于讨论客体变元的量词。如果还考虑谓词变元的量词，如那么，由这样的公式组成的系统就是高阶谓,XA?词逻辑了，有关高阶谓词逻辑的研究，可参阅数理逻辑的专著。123习题1．判断下列推证是否正确XQPXQXP????????????2．证明下列各式1YQXPYQXPY???2?3??4,,YXPYXP????3．举例说明下列各蕴涵式1ABAABA??2XQXX???3????4BABA4．下列各式是否成立，说明理由1XQPXXP????2??3??63§124谓词逻辑的推理理论在§123节中已证明了谓词逻辑中的一些基本等价式和基本蕴涵式，有些公式是命题逻辑中有关公式的推广，因此，命题逻辑里的P，T推理规则等在谓词中可以同样地使用。但是谓词合式公式中由于有了量词，等价和蕴涵的情况就不完全与命题逻辑相同，故需要对量词的一些特性再作进一步地讨论，以便解决谓词逻辑的推理问题。定义1241设X是谓词合式公式A的一个客体变元，若以Y代替X后不产生变元的新的约束出现，则称AX关于Y是自由的。定理1241设X是谓词合式公式A的一个客体变元，A的论域为D，AX关于Y是自由的，则1??64证明设解释I使取值1，则在I下对任意取值1，而XA?,XAD?关于Y是自由的，故在I下对任意取值1，因此1成立。特别XA,YA地2??1，2称为全称特定化全称量词消去规则，记为US。定理1242设X是谓词合式公式A的一个客体变元，A的论域为D，AX关于Y是自由的，则3Y?Y为D的某些元素。证明设解释I使取值1，如果取值0，Y是D的某些元素，XA则对任意有取值0（否则对任意有AY取值1，于是对D的?YY?某些元素Y有AY取值1了），于是取值0了，这与假设矛盾，故必X?取值1，其中Y是D的某些元素，因此3成立。A3称为存在特定化存在量词消去规则，记为ES。定理1243设X是谓词合式公式A的一个客体变元，A的论域为D，AX关于Y是自由的，则4XY??证明设解释I使AY取值1，如果取值0，则对任意X?D，在I下AX取值为0（否则，若对任意X?D，AX取值为1，则取值为1了）A?，故Y?D时在I下AY取值为0，这与假设矛盾，故?XAX取值为1，因而4成立。4称为存在推广存在量词引入规则，记为EG。定理1244设X是谓词合式公式A和B的客体变元，A和B的论域为D，且X非B的自由变元，则5XXB???证明设解释I使取值为1，则在I下对任意取,D?XA?值1，又已知X不是B的自由变元，据定理1232的5式知XAXA??因此取值为1，故5成立。B?特别地，重言式T不以X为自由变元，故?即AA???65即XAFX???即6A6称为全称推广全称量词引入规则，记为UG。US，ES实质上是在关于Y自由的条件下用蕴涵式去掉量词，UG，EGX是在关于Y自由，或X非B的自由变元的假定条件下用蕴涵式加上量词，X这样的推理规则使谓词逻辑的推理简化和精确化。我们得到这些规则后，在谓词逻辑的推理中就可以使用P，T，US，ES，UG，EG和CP规则。但是使用US，ES，UG，EG规则时必须注意到应满足的条件；在使用CP规则时，如果所要证明的结论其前件含自由变元，则对该前件绝对不能使用UG规则，因为定理1244要求使用UG规则时，变元不能为自由变元。关于谓词合式公式集S演绎出（或逻辑蕴涵）一个谓词合式公式的定义与命题逻辑中的定义是相同的，这里就不再给出定义了。下面给出几个推理证明的实际例子。例1241证明人都是要死的，苏格拉底是人，所以苏格拉底是要死的。证明引入谓词如下MXX是人，MORTALXX是要死的，
文档加载中……请稍候！
下载文档到电脑，查找使用更方便
5 元 &&0人已下载
还剩页未读，继续阅读
<a href="UserManage/CopyrightAppeal.aspx?bid=5676235" title="版权申诉" class="fLeft works-manage-item works-manage-report" target="_blank"
关&键&词： 离散数学 数理逻辑 DOC 离散数学数理逻辑 DOC DOC
& 我的文库所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
本文标题：离散数学之数理逻辑.doc 链接地址：
当前资源信息
类型： 共享资源
格式： DOC
大小： 1.96MB
上传时间：