离散数学第一章命题逻辑.

离散数学胡海涛软件工程教研主楼E707电话：[e-mail]第一章命题逻辑1.1命题与联结词1.2命题公式与翻译1.3真值表与等价公式1.4对偶原理与蕴含式1.5联结词的扩充与功能完全组1.6范式1.7命题逻辑的推理理论命题的概念、判定命题的表示命题的真值五个联结词的定义及真值表所谓命题，是指具有真假意义的陈述句。也就是说能够确定或能够分辨其真假的陈述句，且真或假二者必居其一，也只能居其一。简言之，命题就是非真即假的陈述句。判断下列语句是否为命题？（1）离散数学好学吗？（2）我真开心！（3）禁止吸烟！（4）我是学生。（5）6不是自然数。（6）火星上有生物。（7）现在是八点钟。（8）2012年奥林匹克运动会将在英国举行。（9）如果天气好，那么我去散步。（10）本命题为假。在上面的例子中，（1）、（2）、（3）不是陈述句，因而不是命题。（4）、（5）、（6）、（7）、（8）、（9）是命题。其中（4）的真假意义要根据具体的“我”而定；（7）要根据“现在”具体的时间而定；（5）是假命题；（6）在目前可能无法判定真假，但从事物的本质而言，它本身是有明确真假意义的，只不过我们现在还不知道，所以我们承认这也是一个命题；（8）是真命题；（9）由两句话组成，有明确的真假意义，因而是命题；（10）无法确定它的真假，当“本命题”假时，它便真，当“本命题”真时它便假，这种断言叫悖论。一些不能分解为更简单的陈述句的命题，称为原子命题。如上面的（4）、（5）、（6）、（7）、（8）都是原子命题。反之，称为复合命题，即由联结词，标点符号和原子命题复合而成的命题。如上面的（9）为复合命题。联结词的概念将在下一小节给出。一个命题的真或假称为命题的真值，简称值，真用T或1表示；假用F或0表示。由于命题只有真、假二个真值，所以命题逻辑也称二值逻辑。一个原子命题，一般用大写字母或带下标的大写字母，如P，Q，R，…，或Pi，Qi，Ri，…，等表示，把表示原子命题的符号，称为命题标识符，简称命题符。例如P：北京是中国的首都。其中“:”是表示的意思。一个命题标识符P，如果表示一个确定的命题，则称P为原子命题常元，简称命题常元；若P只表示任意命题的位置标志，或表示不确定的命题，或以原子命题为值的变元P，就称P为原子命题变元，简称命题变元。命题变元是以命题的真值为值的变元。显然，命题变元不是命题。将一个命题变元P用一个特定命题去代替，才能确定它的真值，这时也称为对P进行指派或对P进行解释。1.否定┐2.合取∧3.析取∨4.条件→5.双条件⇆6.合取非↑7.析取非↓8.条件非↛9.双条件非基本联结词扩充联结词1.1.2联结词(1)否定联结词设P是一个命题，由联结词┐和命题P构成┐P，称为命题P的否定式复合命题。┐P读做“非P”。联结词┐是自然语言中的“非”、“不”和“没有”等的逻辑抽象。否定联结词是一个一元运算。如；P：离散数学是计算机及相关专业的基础课。┐P：离散数学不是计算机及相关专业的基础课。(2)合取联结词令P和Q是两个命题，由联结词∧把P，Q连接成P∧Q，称为P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P合取Q”。联结词∧是自然语言中的“和”，“与”，“并且”，“既…又…”等的逻辑抽象。合取联结词是一个二元运算。例如：P：今天下雨。Q：明天下雨。P∧Q：今天与明天都下雨。(3)析取联结词设P和Q是两个命题，由联结词∨把P，Q连接成P∨Q，称为P和Q的析取式复合命题，P∨Q读做“P或Q”，或“P析取Q”。析取联结词∨是自然语言中的“或”的逻辑抽象。但它与自然语言中的“或”的意义并不完全相同，自然语言中的“或”既可以表示“排斥或”，也可以表示“可兼或”。例如：P：今天晚上我在家里看电视或去剧场看戏。Q：他可能是100米或200米赛跑的冠军。命题P中的“或”是“排斥或”，命题Q中的“或”是“可兼或”，而析取联结词表示的是“可兼或”。关于“排斥或”，我们会在1.5节给出它的定义。析取联结词是一个二元运算。(4)条件联结词设P和Q是两个命题，由联结词→把P，Q连接成P→Q，称P→Q为P和Q的条件式复合命题，把P和Q分别称为P→Q的前件和后件，或者前提和结论。P→Q读做“若P，则Q”或“P条件Q”。联结词→是自然语言中“如果…，则…”，“若…，才能…”等的逻辑抽象。条件联结词是一个二元运算。在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在命题逻辑中，当P为F时，无论Q为T还是为F，都规定P→Q为T，这称为“善意推定”。例如：P：雪是黑的。Q：太阳从西方升起。R：3＋3＝6。P→Q：如果雪是黑的，那么太阳从西方升起。P→R：如果雪是黑的，那么3＋3＝6。P为假命题，Q为假命题，R为真命题，而P→Q和P→R都是真命题。(5)双条件联结词令P和Q是两个命题，由联结词⇆把P，Q连接成P⇆Q，称P⇆Q为P和Q的双条件式复合命题，P⇆Q读做“P当且仅当Q”。双条件联结词也可以用符号来表示。双条件联结词⇆是自然语言中的“充分必要条件”、“当且仅当”等的逻辑抽象。双条件联结词是一个二元运算。例如：P：两个三角形全等。Q：两个三角形的三组对应边相等。P⇆Q：两个三角形全等，当且仅当这两个三角形的三组对应边相等。关于这五个联结词的定义，可以通过如表1-1的真值表给出，关于真值表的定义，我们将在1.3节详细说明。表1-1五个联结词的真值表PQ┐PP∧QP∨QP→QP→←QTTFTTTTTFFFTFFFTTFTTFFFTFFTT需要注意：①复合命题的真值只取决于构成它们的各原子命题的真值，而与它们的内容、含义无关，与联结词所连接的两原子命题之间是否有关系也无关。②∧，∨和⇆具有对称性，而┐，→没有。③联结词都有从已知命题得到新的命题的作用，从这个意义上讲，它们具有操作或运算的意义。因此，可以把它们看作是一种运算或是一种函数。④关于→和⇆有的数学书或逻辑学的书籍中有其他的说法，如称→为蕴含，称⇆为等价等，本书中将避免使用这种称呼，因为在后面的章节我们将另外定义“蕴含”和“等价”这两个概念。命题公式命题的翻译联结词、原子命题变元、圆括号“(”、“)”，可进行有限次地连接，得到许多字符串，那些有意义的字符串，称为命题逻辑中的合式公式，简称命题公式或公式。定义1.1单个的命题常元和命题变元，统称为原子命题公式，简称原子公式。下面，我们使用递归来定义命题逻辑中的合式公式（wff）。定义1.2命题逻辑中的合式公式是由下列规则形成的字符串：①原子命题公式和真值T、F都是一个合式公式。②若A是合式公式，则(┐A)是合式公式。③若A和B是合式公式，则(A∧B)、(A∨B)、(A→B)和(A⇆B)都是合式公式。④经过有限次地使用①、②、③所得到的包含原子命题公式、联结词和圆括号的字符串都是合式公式。例1.1(┐P)∨Q，(P→(Q∧R))都是合式公式，而(P→Q)→(∧Q)，(P，(P→Q)⇆(∧R))都不是合式公式。为方便计，对于圆括号的使用和联结词的优先级做如下约定：①公式最外层的圆括号可省略，如把(P→(Q∨R))写成P→(Q∨R)。②┐只作用于邻接后的原子命题变元，如把(┐P)∨Q写成┐P∨Q。③联结词的优先级从高到低依次为┐，∧，∨，→，⇆。定义1.3如果A1是公式A的一部分，且A1是一个公式，称A1是A的子公式。例1.2设公式A为(P→Q)→(Q∨R)，则P→Q，Q∨R都是A的子公式。需要注意的是，命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。此外，并不是由命题变元，连接词和一些括号组成的字符串都能构成命题公式，如例1.1中的(P→Q)→(∧Q)和(P，(P→Q)⇆(∧R))就都不是命题公式。有了合式公式的概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为翻译，也称符号化。例1.3张明正在睡觉或游泳。解：设P：张明正在睡觉。Q：张明正在游泳。本例的“或”是“不可兼或”，而析取联结词是“可兼或”，因此不能直接对两命题析取。构造表1-2如下：从表中可以看出原命题不能用上节的五个联结词单独写出，但是如用命题和联结词组合，可以把本命题表示为：┐(P⇆Q)。PQ原命题P→←Q┐(P→←Q)P∧┐Q┐P∧Q(P∧┐Q)∨(┐P∧Q)TTFTFFFFTFTFTTFTFTTFTFTTFFFTFFFF1.5节给出其他联结词的定义后，本例也可以直接用异或联结词给出。另外本例也可这样理解：张明正在睡觉而不在游泳或张明正在游泳而不在睡觉。因而可符号化为：(P∧┐Q)∨(┐P∧Q)，由表1-2可以看出，它与┐(P⇆Q)的真值相同。例1.4符号化下列命题：①他既聪明又用功。②他虽聪明但不用功。③除非你努力，否则你将失败。④除非天气好，我才骑自行车上班。⑤小王晚上要回家，除非下大雨。⑥只有睡觉才能恢复疲劳。⑦只要我还有口气，我就要战斗。⑧A中没有元素，A就是空集。⑨张明或者李强都可以做这件事。⑩张明和李强都做这件事了。解：①设P：他聪明。Q：他用功。本例可以表示为P∧Q。②设P：他聪明。Q：他用功。本例可以表示为P∧┐Q。③设P：你努力。Q：你将失败。本例可以表示为┐P→Q。④设P：天气好。Q：我骑自行车上班。本例可以表示为┐P→┐Q或Q→P。⑤设P：小王晚上要回家。Q：下大雨。本例可以表示为┐Q→P。解：⑥设P：睡觉。Q：恢复疲劳。本例可以表示为Q→P。一般地，对于“只有P才Q”这样的语句，P是Q的必要条件，或Q是P的充分条件。⑦设P：我还有口气。Q：我要战斗。本例可以表示为P→Q。一般地，对于“只要P就Q”这样的语句，P是Q的充分条件，或Q是P的必要条件。⑧设P：A中没有元素。Q：A是空集。本例可以表示为P⇆Q。⑨设P：张明可以做这件事。Q：李强可以做这件事。本例可以表示为P∨Q。⑩设P：张明做了这件事。Q：李强做了这件事。本例可以表示为P∧Q。例1.5公式(P∧┐Q)→┐R，其中P：李强是体育爱好者，Q：李强是文艺爱好者，R：李强是文体爱好者，试用自然语言把它叙述出来。解：如果李强是体育爱好者而不是文艺爱好者，那么他不是文体爱好者。符号化应该注意下列事项：①首先确定给定句子是否为命题。②句子中的连词是否为命题联结词。③正确地表示原子命题和适当选择命题联结词。为了便于正确表达命题间的相互关系，有时也采用列出“真值表”的方法，进一步分析各原子命题，以此寻找合适的逻辑联结词，使原来的命题能够正确地用形式化符号予以表达，如例1.3中。下节我们将详细讨论真值表。真值表公式分类等价公式代入规则和替换规则定义1.4对于命题公式A中每个命题变元P，任给一个指派或解释，得到一种真值的组合，称为A的一个真值指派，或称为A的一种解释。若A的指派为T，称该指派为A的成真指派或说A的解释为真。类似地可以定义A的成假指派（或称A的解释为假）。定义1.5设A为一命题公式，对其中出现的命题变元做所有可能的每一组真值指派，连同公式A的相应的真值汇列成表，称为A的真值表。为了能更规范、更方便地构造真值表，特做如下约定：①命题变元按字典顺序排列。②对公式的每个解释，以二进制数从小到大或者从大到小顺序列出。③若公式复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所给公式的真值。例1.6求(P→Q)⇆(┐P∨Q)的真值表。解：表1-3PQP→Q┐P┐P∨Q(P→Q)⇆(┐P∨Q)111011100001011111001111例1.7求(P→Q)∧┐R的真值表解：表1-4PQRP→Q┐R(P→Q)∧┐R1111001101111010001000100111000101110