离散数学之数理逻辑

1第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，…等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。第1-1章命题逻辑学习要求:掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。§1-1-1命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。例1-1-1.1人总是要死的。例1-1-1.2苏格拉底是人。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如果a和b都是正数，则ab也是正数。例1-1-1.140xy当且仅当x和y都大于零。例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.20x=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是无法判断真假的悖论。从以上的分析可以看出，表达思想的语句有不同的类别，数理逻辑中研究的是出现较多而又比较规范的语句—可以判断出真或假的陈述句。3定义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：xy0，Q：x0，R：y0，用联结词“当且仅当”与“都”联系起来，这类用联结词，标点符号和原子命题构成的命题称为复合命题。二、逻辑联结词日常生活、工作和学习中，自然语言里我们常常使用下面的一些联结词，例如：非，不，没有，无，并非，并不等等来表示否定；并且，同时，以及，而（且），不但…而且…，既…又…，尽管…仍然，和，也，同，与等等来表示同时；虽然…也…，可能…可能…，或许…或许…，等和“或（者）”的意义一样；若…则…，当…则…与“如果…那么…”的意义相同；充分必要，等同，一样，相同与“当且仅当”的意义一样。即是说在自然语言中，这些逻辑4联结词的作用一般是同义的。在数理逻辑中将这些同义的联结词也统一用符号表示，以便书写、推演和讨论。现定义常用联结词如下：定义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真值1111010110005如例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：23，B:今天阳光明媚。A→B：若23，则今天阳光明媚。条件联结词的运算表为命题PQPQ真值111100011001注意：(1)条件联结词联结的前件与后件不限定于同一类事物。(2)从真值表定义可知，前件取假值时无论后件的取值是真还是假，条件联结词产生的新命题都取为真，即采取的是“善意的推定”。(3)条件联结词为一个二元运算。定义1-1-1.7设P，Q是两个命题，“P当且仅当Q”是一个新命题，记为PQ，“”称为双条件，它的运算表为:6命题PQPQ真值111100010001双条件是数学上考虑最多，也是大家比较熟悉的，可以举出许多例子。例如例1-1-1.14是原子命题xy0及命题：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P1001000100107例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．将下列命题符号化：PPPP1011010110118(1)我一边看书一边听音乐。(2)天下雨了，我不去上街。(3)实函数)(xf可微当且仅当)(xf连续。此命题的真值是什么？(4)除非你努力，否则你就会失败。(5)合肥到北京的列车是中午十二点半或下午五点五十分开。(6)优秀学生应做到思想身体学习都好。3．求下列各式的真值表(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。4．设命题A1，A2的真值为1，A3，A4两命题的真值为0，求下列命题的真值：(1)))()(())((4321321AAAAAAA。(2))))((()(4321321AAAAAAA。(3)))()(()(4313321AAAAAAA。(4))()))(((421321AAAAAA