离散数学之数理逻辑

PAGE/NUMPAGES第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，…等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。第1-1章命题逻辑学习要求:掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。§1-1-1命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。例1-1-1.1人总是要死的。例1-1-1.2苏格拉底是人。例1-1-1.3苏格拉底是要死的。例1-1-1.4中国人民是勤劳和勇敢的。例1-1-1.5鸵鸟是鸟。例1-1-1.61是质（素）数。例1-1-1.7今天没有下雨。例1-1-1.8公元二千年会出现生物计算机。例1-1-1.9太阳系外的星球上有人。例1-1-1.10他喜欢读书也喜欢运动。例1-1-1.11他在机房里或者在图书馆里。例1-1-1.12电灯不亮是灯泡或线路有毛病，或者是停电所致。例1-1-1.13如果和都是正数，则也是正数。例1-1-1.14当且仅当和都大于零。例1-1-1.15101+1=110。例1-1-1.16天气多好啊？例1-1-1.17他来了吗？例1-1-1.18全体起立！例1-1-1.19帮帮我吧！例1-1-1.20=0。例1-1-1.21我正在说谎。上述例1-1-1.11-1-1.4，例1-1-1.12～1-1-1.13是可以判断为对（真，成立）的陈述句，例1-1-1.5，1-1-1.6，1-1-1.14是能够判断为不对（假，不成立）的陈述句，例1-1-1.7～1-1-1.9在人类历史发展的长河中能够判断它是真或是假的陈述句，例1-1-1.10～1-1-1.11根据“他”当时的情况能够判断出是真或是假的陈述句，例1-1-1.15在二进制计算中为真，在十进制计算中为假，也还是可以判断为真或为假的陈述句，例1-1-1.16是感叹句，例1-1-1.17是疑问句，例1-1-1.18是命令句，例1-1-1.19是祈使句，例1-1-1.20中x是一个未知数（变量），无法判断是真还是假，例1-1-1.21是无法判断真假的悖论。从以上的分析可以看出，表达思想的语句有不同的类别，数理逻辑中研究的是出现较多而又比较规范的语句—可以判断出真或假的陈述句。定义1-1-1.1凡是能判断是真或是假的陈述句称为命题。如前面的例1-1-1.1～1-1-1.15都是命题，例1-1-1.16～1-1-1.21都不是命题。命题的值为真或假。今后约定用1表示真，0表示假，除T和F以外的大写英文字母或它们后面跟上数字如A，A1，B5，Pi等或[数字]（如[123]，[28]，……）表示命题。如P：M8085芯片有40条引线，或[12]：M8085芯片有40条引线。P或[12]称为命题“M8085芯片有40条引线“的标识符。当命题标识符代表一个确定的命题时（如P或[12]，A：人总是要死的），称为命题常元，当命题标识符代表非确指的命题时，称这样的命题标识符为命题变元。注意：命题变元不是命题，只有对命题变元用一个确定的命题代入后，才能确定其值是1还是0。定义1-1-1.2用一个确定的命题代入一个命题标识符（如P），称为对P进行指派（赋值，或解释）。再看前面的例1-1-1.1～1-1-1.6，这些命题不能再分解为更简单的能判断其值为1或0的陈述句了，这类命题称为原子命题。在例1-1-1.7中，如果表示今天下雨为原子命题P，则今天没有下雨是P的否定；例10可分解为原子命题P：他喜欢读书，Q：他喜欢运动，用联结词“也”联结起来；例1-1-1.11可分解为原子命题P：他在机房里，Q：他在图书馆里，用联结词“或者”了解起来；例1-1-1.13可分解为原子命题P：a是正数，Q：b是正数，R：ab是正数，用联结词“和”与“如果…，则…”了解起来；例1-1-1.14可分解为原子命题P：xy0，Q：x>0，R：y>0，用联结词“当且仅当”与“都”了解起来，这类用联结词，标点符号和原子命题构成的命题称为复合命题。二、逻辑联结词日常生活、工作和学习中，自然语言里我们常常使用下面的一些联结词，例如：非，不，没有，无，并非，并不等等来表示否定；并且，同时，以及，而（且），不但…而且…，既…又…，尽管…仍然，和，也，同，与等等来表示同时；虽然…也…，可能…可能…，或许…或许…，等和“或（者）”的意义一样；若…则…，当…则…与“如果…那么…”的意义相同；充分必要，等同，一样，相同与“当且仅当”的意义一样。即是说在自然语言中，这些逻辑联结词的作用一般是同义的。在数理逻辑中将这些同义的联结词也统一用符号表示，以便书写、推演和讨论。现定义常用联结词如下：定义1-1-1.3在命题P的适当地方插入“不”或者“没有”产生的新命题称为P的否定，记为P读成“非P”。P的取值依赖于P的取值，即定义运算表为命题PP真值1001例如P:2是一个质数（值为1），P：2不是一个质数（值为0）或2是一个和数。注意：(1)不同的陈述句可能确定同一个命题；(2)否定是一个一元运算。定义1-1-1.4两个命题P和Q产生的一个新命题记为PQ，读成“P与Q”或“P和Q的合取”。合取的运算表为命题PQPQ真值111100010000如例1-1-1.10，P：他喜欢读书，Q:他喜欢运动，P和Q的合取为PQ：他喜欢读书也喜欢运动。又如A：猫吃鱼，B：2+2=0，则AB：猫吃鱼而且2+2=0。注意：(1)数理逻辑中的联结词“合取”只考虑命题之间的形式关系，不考虑命题内容的实际含义，只有在研究取值时才加以考虑。(2)合取是一个二元运算。定义1-1-1.5两个命题P或Q产生一个新命题，记为PQ，读成“P析取Q”，析取的运算表为命题PQPQ真值111101011000如例1-1-1.12，P：他在机房里，Q：他在图书馆里，PQ：他在机房或图书馆里。又如P1：他是游泳冠军，P2：他百米是赛冠军，P1P2：他是游泳冠军或百米赛跑冠军。A：猫吃鱼，B：2+2=0，AB：猫吃鱼或者2+2=0。注意：(1)析取可细分为两种，一种是“不可兼或”如前面例1-1-1.12，一种是“可兼或”，如P1P2。有的将不可兼或记为“”，可兼或记为“”。显然“”包含“”为其特殊情况。故我们着重考虑“”的情形。(2)在自然语言或形式逻辑中，用来析取联结的对象往往要求属于同一类事物，但是在数理逻辑中不作这种限制，例如AB：猫吃鱼或者2+2=0是允许存在的命题。(3)析取是一个二元运算。定义1-1-1.6设P，Q是两个命题，“若P则Q”是一个新命题，记为P→Q，读成P推出Q（或Q是P的必要条件，P是Q的充分条件），P称为条件联结词“→”的前件，Q为→后件。如P：河水泛滥，Q：周围的庄稼被毁。P→Q：若河水泛滥，则周围的庄稼被毁。A：2<3，B:今天阳光明媚。A→B：若2<3，则今天阳光明媚。条件联结词的运算表为命题PQPQ真值111100011001注意：(1)条件联结词联结的前件与后件不限定于同一类事物。(2)从真值表定义可知，前件取假值时无论后件的取值是真还是假，条件联结词产生的新命题都取为真，即采取的是“善意的推定”。(3)条件联结词为一个二元运算。定义1-1-1.7设P，Q是两个命题，“P当且仅当Q”是一个新命题，记为PQ，“”称为双条件，它的运算表为:命题PQPQ真值111100010001双条件是数学上考虑最多，也是大家比较熟悉的，可以举出许多例子。例如例1-1-1.14是原子命题xy>0及命题：x和y都大于零用双条件联结词产生的命题，这个命题取值为0。又如，我没有收到信当且仅当没有人给我写信，它的值为1。约定在整数范围内讨论，P：2+2=0，Q：IBM-PC是一种微型计算机，PQ：2+2=0当且仅当IBM-PC是一种微型计算机，此命题取值为0。注意：(1)双条件联结词了解的命题不限定属于同一类事物。(2)双条件是一个二元运算。这五种逻辑联结词也可以称为逻辑运算，与一般数的运算一样，可以规定运算的优先级，我们规定的优先级顺序依次为，，，，。如果出现的逻辑联结词相同，又没有括号时，从左到右顺序运算。如果遇到有括号时就先进行括号中的运算。考察例1-1-1.12．令P：电灯亮，Q：灯泡有毛病，R：线路有毛病，S：停电。则可将该语句符号化为QRSP。三、命题运算的真值表定义1-1-1.8在命题公式中，对于分量指派的各种可能组合，即确定了该命题的各种真值情况，把它汇列成 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 ，就是命题的真值表。任意给定一个复合命题后，用原子命题和逻辑联结词表出，再利用真值表就可以计算出复合命题的值。当复合命题用原子命题变元、逻辑联结词和括号组成时，可以得出该复合命题变元的真值表。例1-1-1.22求P(PQ)，PP，PP的真值表。解：PQPQP(PQ)1111100101000000PPPP100100010010PPPP101101011011例1-1-1.23求QRSP的真值表。解：PQRSRSQRSPQRSP11111100111001001101010010111100110001001010000110010001100000010111111101100111010101110011111101000111001000110001001100000011例1-1-1.24求(PQ)PQ的真值表。解：PQPQ(PQ)PQ(PQ)PQ1110011010010110010001111-1-1习题举出原子命题和复合命题的例子五个以上。将下列命题符号化：(1)我一边看书一边听音乐。(2)天下雨了，我不去上街。(3)实函数可微当且仅当连续。此命题的真值是什么？(4)除非你努力，否则你就会失败。(5)合肥到北京的列车是中午十二点半或下午五点五十分开。(6)优秀学生应做到思想身体学习都好。求下列各式的真值表(1)P(QP)。(2)(P(QR))((PR)Q)。(3)(P→(Q→P))↔(P→(P→Q))。(4)(P→(QR))↔(P→Q)(P→R)。(5)(P→Q)(R→Q)↔(PR)→Q。(6)P→(Q→(R→(P→(Q→R))))。(7)PQ。设命题A1，A2的真值为1，A3，A4两命题的真值为0，求下列命题的真值：(1)。(2)。(3)。(4)。将下列语句符号化：(1)占据空间的，有质量而且不断变化的称之为物质。(2)占据空间的，有质量者称为物质，而物质是不断变化的。(3)如果你来了，那么他唱歌与否要看你是否伴奏而定。(4)我们不能既划船又跑步。§1-1-2命题公式与真值函数由命题变元，括号，逻辑联结词按下列规定形成的符号串是我们讨论的对象。一、命题演算公式定义1-1-2.1由命题变元，逻辑联结词和括号构成的下述表达式称为命题合式公式（well—formedformula）或命题演算公式，简称公式，记为wff：(1)单个原子命题变元是wff；(2)若P，Q是wff，则都是wff；(3)只有有限次使用(1),(2)得到的表达式才是wff。为了书写和输入计算机，以及进行运算方便起见，规定：(1)的括号，整个wff的最外层括号可以省略，(2)已定好逻辑联结词的优先级后，优先级的括号可省略。等都是wff。但就不是wff，因为前一表达式R与S之间没有逻辑联结词，后一表达式中括号不配对，故不符合定义1-1-2.1。按BNF（Backus—NaurForm）符号，wff的语法定义为：wff：：=<命题>|<命题>|<命题><二元运算符><命题><二元运算符>：：=，<命题>：：=〈原子公式〉|{〈wff〉}*定义1-1-2.2令A为wff，对A中出现的全部原子命题变元P1，P2，…，Pn分别赋以真值0或1所得到的一组真值（n个）称为A的一个指派或解释。从§1-1-1的例1-1-1.22～1-1-1.24可以看出，对命题变元作指派，再利用逻辑联结词的真值表（即逻辑运算规则）可以演算出wff的真值表。下面再看几个例子。例1-1-2.1求(P→Q)(Q→P)的真值表。PQPQQP(PQ)QP）11111100100110000111解：例1-1-2.2(P→Q)P→Q的真值表为解：PQPQ(PQ)P(PQ)PQ11111100010110100101例1-1-2.3(P→Q)(PQ)的真值表为PQPQPQ(PQ)(PQ)11100100100110000100二、真值函数定义1-1-2.3以{真，假}为定义域和值域的函数为真值函数。如由五个逻辑联结词产生的所有wff都是真值函数，因此有无穷多个真值函数，显然最基本而重要的真值函数还是。当真值函数的变元为n个时，共有2个指派。通过列出真值表也可以定义真值函数。例1-1-2.4确定下列真值表对应的真值函数：PQRf1(P,Q,R)f2(P,Q,R)1111111000101101001001100010000011000001以f1（P，Q，R）来考虑，表的第一行说明f1的值为1，且指派中P，Q，R都取值为1，可用项P∧Q∧R，表示，表的第三行说明f1的值为1，此时指派中P，R取值为1，Q取值为0，即Q取值为1，可用表示，此时P，Q，R的其它指派都使PQR，或为0，同理可用分别表示表第四、七行的1，故f1（P，Q，R）=同理f2（P，Q，R）=。注意：由真值表确定的真值函数不一定是最简单的wff，不一定只有一个表达式。例如：PQRPRRPQQR(PR)(PQ)(QR)1111000111001000101101111000110101100000010010000010001100001000将这个真值表与f1（P，Q，R）的真值表相比较，对变元的任一指派，可以看到与（*）这两个表达式可代表同一个真值函数，而此两式相比，(*)就不是最简单的wff。三、重言式与矛盾式我们注意到例1-1-2.2，1-1-2.3和例1-1-2.1，1-1-2.4。对命题变元无论作什么样的指派，例1-1-2.2中的wff永远取值为1，这种类型的wff称为重言(永真)式；例1-1-2.3中的wff永远取值为0，这种类型的wff称为矛盾（永假）式；而例1-1-2.1，1-1-2.4中的wff则对有的指派取值为1。对另外指派又取值为0，这种类型的wff称为可满足公式。显然重言式（或永真函数）是可满足公式，矛盾式是不可满足公式。定义1-1-2.4对wff的命题变元无论作什么指派，公式均取值1时，称之为重言式，记为T；公式均取值0时称之为矛盾式（或不可满足式），记为F。若有指派使wff取值1，则称该公式为可满足公式。定理1-1-2.1任意两个重言（矛盾）式的合取或析取仍然是一个重言（矛盾）式。由定义1-1-2.4及析取、合取的真值表立即可以证明此定理。1-1-2习题下列符号串哪些是合式公式？哪些是重言式或矛盾式？哪些是可满足公式？(1)；　(2)　；(3)　；　(4)；(5)；(6)。用真值表证明下列各式为重言式：；；。§1-1-3公式的等价与蕴涵在§1-1-2中我们已经看到真值函数f1(P,Q,R)的表达式有：或，又如和代表同一真值函数，对同一真值函数的几个不同的wff有下面的定义。定义1-1-3.1设P1，P2，…，Pn为出现在两个wffA和B中的原子命题变元。如果对P1，P2，…，Pn的任意真值指派，A和B的真值都相同，则称A和B逻辑相等或说A和B等价，记为例如，用真值表和定义1-1-3.1可以得到下列基本等价式：(对合律)(幂等律)(交换律)(结合律)(分配律)(吸收律)(德.摩根律)　(同一律)　(零一律)　(否定律)(条件等价式)(双条件等价式)当wff中出现的原子命题变元很多时，用真值表和定义1-1-3.1来判断两个wff是否等价就显得麻烦，因而可利用上述基本等价式和下面的定理1-1-3.1就可以得到一些复杂的等价式。定义1-1-3.2若wffX是wffA的子串，则称X为A的子公式。定理1-1-3.1X是wffA的一个子公式，wffY与X等价，则将A中的X用Y来代替所得的wffB，必有A与B等价（替换规则）。证明:因为在命题变元的任意指派下X与Y的真值相同，故用Y代替X后所得的wffB与A在任意相应的指派下也有相同的真值，故A与B等价。例1-1-3.1由吸收律和替换规则可知例1-1-3.2证明证明:定理1-1-3.2在一个重言（矛盾）式中对同一命题变元都用任意一个wff去替换，仍可得一个重言（矛盾）式。证明:因为重言（矛盾）式的真值永为1（0），与变元的指派无关，故对同一变元用任一wff替换后，其值仍为1（0），所以结果为一个重言（矛盾）式。例1-1-3.3因为，，当P以某wff替换后仍为重言(矛盾)式，例如P以去代替，则有定理1-1-3.3合式公式A和B等价当且仅当A↔B为重言式。证明:必要性：若A与B等价，则对出现在A，B中的原子命题变元的任意指派A和B有相同的真值，即A↔B永远取值1，即A↔B为重言。充分性：若A↔B为重言（矛盾）式，则无论任何指派A↔B均取值1，即A，B的真值相同，故AB。例1-1-3.4证明。证明:故由定理1-1-3.3得证。例1-1-3.5P→(Q→R)(PQ)→R证明：容易验证wff等价具有下列性质：(1)反身（自反）性:。(2)对称性:若则。(3)传递性:　若，则。定义1-1-3.3　设合式公式A和B中出现的原子命题变元为，如果对它们的指派使A取值为1时B也取值为1，则称A蕴涵B（或称B是A的逻辑结果），记为。例1-1-3.6。证明:　PQPPQ1101100001110011从上面的真值表可知，使P取值1的指派0，1和0，0它也使P→Q取值为1，根据定义1-1-3.3得证PP→Q。例1-1-3.7。证明:PQRPQQR(PQ)(QR)PR11111111101000101010110001000111111010100100111110001111由真值表可知使(P→Q)(Q→R)取值为1的指派(1，1，1)；(0,1,1)；(0,0,1)；（0，0，0）也使P→R取值为1，根据定义1-1-3.3知。定理1-1-3.4　合式公式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。例1-1-3.8　证明：　由定理1-1-3.4得证。用定义1-1-3.3及定理1-1-3.4易证下列常用的基本蕴涵式：(1)PQP，PQQ；(2)PPQ，QPQ；(3)PP→Q；(4)QP→Q；(5)(P→Q)P；(P→Q)Q；(6)P(P→Q)Q；(分离规则)(7)Q(P→Q)P；(8)P(PQ)Q；(9)(P→Q)(Q→R)P→R；(10)(PQ)(P→R)(Q→R)ÞR；(11)(P→Q)Ù(R→S)(PÙR)→(QÙS)；(12)(P↔Q)Ù(Q↔R)P↔R。蕴涵具有下列常用性质：(1)A为重言式，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。1-1-3习题1．证明（AB）（BC）（CA）（AB）（BC）（CA）。2．不要构造真值表证明下列蕴涵式：(1)；(2)；(3)；(4)；(5)；(6)。3．若是否有？若是否有？若是否有？4．证明时。5．证明时┐，反之也对。§1-1-4命题逻辑的推理理论逻辑是研究思维结构和规则的科学，要求能够提供正确的思维规律，提供判定一个论断之有效的准则。数理逻辑则研究正确的推理规则，研究论断的有效性,但要注意到：论断的正确性涉及到实践的检验。什么是论断的有效性呢？回忆§1-1-3中命题公式的蕴涵概念，并把它推广。定义1-1-4.1和B为合式公式，若A1A2…ÙAnB，则称B为前提的有效结论，或说B是的逻辑结果，或者说共同蕴涵B。例1-1-4.1证明R→S是P→(Q→S)，RP，Q的有效结论。证明：即要证(P→(Q→S))(RP)QR→S，也就是要证明(P→(Q→S))(RP)Q(R→S)为重言式。当然可以应用真值表验证，也可以用等价是验证，往往是比较麻烦的。因此判定论断的有效性，需要有其他论证方法，希望有比较简明的过程，还要有正确的依据。定理1-1-4.1若，则。证明：已知，故为重言式。即为重言式，即为重言式，即为重言式，所以。定义1-1-4.2设S为若干公式的集合（称为前提集合）。如果有公式的有限序列其中AiS或Ai是中某些公式的有效结论，且，则称B是S的逻辑结果或有效结论，或者说从S演绎出B。定理1-1-4.2设S为公式集，B是一个公式，S能演绎出B的充分必要条件是：B是S的逻辑结果。证明：充分性：因为B是S的逻辑结果，由定义1-1-4.2知存在公式的有限序列,B(AiS),B是,的逻辑结果，因而由定义1-1-4.2得证S演绎出B。必要性：设S演绎出B，则存在公式的有限序列其中An=B且AiS或Ai是中某些公式的逻辑结果。下面用归纳法证明，因为，A1ÎS且A1A1，故A1是S的逻辑结果（归纳基础）。设Ai(i