数理逻辑与集合论教案(离散数学)

离散数学高等教育出版社第一部分数理逻辑第二部分集合论第三部分代数结构第四部分图论第一章命题逻辑基本概念第二章命题逻辑等值演算第三章命题逻辑的推理理论第四章一阶逻辑基本概念第五章一阶逻辑等值演算与推理第六章集合代数第七章二元关系第八章函数第九章集合的基数第十章代数系统第十一章半群与群第十二章环与域第十三章格与布尔代数第十四章图的基本概念第十五章欧拉图与哈密顿图第十六章树第十七章平面图及图的着色第十八章支配集、覆盖集、独立集与匹配第一节命题与联结词第二节命题公式及其赋值习题课第一节等值式第二节析取范式与合取范式第三节联结词的完备集习题课第一节推理的形式结构第二节自然推理系统P习题课第一节一阶逻辑命题符号化第二节一阶逻辑公式及解释习题课第一节一阶逻辑等值式与置换规则第二节一阶逻辑前束范式第三节一阶逻辑的推理理论习题课第一节集合的基本概念第二节集合的运算第三节集合恒等式习题课第一节有序对与笛卡儿积第二节二元关系第三节关系的运算第四节关系的性质第五节关系的闭包第六节等价关系与划分第七节偏序关系习题课第一节函数的定义与性质第二节函数的复合与反函数习题课第一节集合的等势与优势第二节集合的基数习题课第一节二元运算及其性质第二节代数系统习题课第一节半群与独异点第二节群的定义与性质第三节子群第四节陪集与拉格朗日定理第五节正规子群与商群第六节群的同态与同构第七节循环群与置换群习题课第一节环的定义与性质第二节整环与域习题课第一节格的定义与性质第二节子格与格同态第三节分配格与有补格第四节布尔代数习题课第一节图第二节通路与回路第三节图的连通性第四节图的矩阵表示习题课第一节欧拉图第二节哈密顿图第三节带权图与货郎担问题习题课第一节无向树及其性质第二节生成树第三节根树及其应用习题课第一节平面图的基本概念第二节欧拉公式第三节平面图的判断第四节平面图的对偶图第五节图中顶点的着色第六节地图的着色与平面图的点着色第七节边着色习题课第一节支配集、点覆盖集与点独立集第二节边覆盖集与匹配第三节二部图中的匹配习题课一、主要内容命题逻辑基本概念命题逻辑等值演算命题逻辑推理理论一阶逻辑基本概念一阶逻辑等值演算与推理理论二、学习要求深刻理解命题、联结词、复合命题、命题公式、等值式、等值演算、推理及证明等概念熟练进行等值演算与构造证明第一部分数理逻辑本章的主要内容：命题、联结词、复合命题命题公式、赋值、命题公式的分类本章与后续各章的关系本章是后续各章的准备或前提第一章命题逻辑基本概念一、命题及其分类1.命题与真值(1)命题—判断结果惟一的陈述句(2)命题的真值—判断的结果(3)真值的取值：真与假(4)真命题与假命题注意：感叹句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题第一节命题与联结词例下列句子中那些是命题？(1）是有理数.（2）2+5＝7.（3）x+5＞3.（4）你去教室吗？（5）这个苹果真大呀！（6）请不要讲话！（7）2005年元旦下大雪.不难看出：（1）是假命题，（2）是真命题.（7）是真命题，它的真值现在不知道，到2005年元旦就知道了.可见命题的真值是客观存在的，不以我们是否知道而改变22.命题的分类（1）简单命题（也称原子命题）（2）复合命题3.简单命题符号化（1）用小写英文字母p，q，r，…，pi，qi，ri（i≥1）表示简单命题（2）用“1”表示真，用“0”表示假例如，令p：是有理数，则p的真值为0，q：2+5=7，则q的真值为1在本小节要弄清命题、命题的真值、真命题、假命题、简单（原子）命题、复合命题等概念2二、联结词与复合命题1．否定式与否定联结词“”定义1.1设p为命题，符合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p为真当且仅当p为假.2.合取式与合取联结词“∧”定义1.2设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p∧q，∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真.使用合取联结词时要注意两点：(1)描述合取式的灵活性与多样性(2)分清简单命题与复合命题例将下列命题符号化.（1）吴颖既用功又聪明.（2）吴颖不仅用功而且聪明.（3）吴颖虽然聪明，但不用功.（4）张辉与王丽都是三好生.（5）张辉与王丽是同学.（1）—（3）说明描述合取式的灵活性与多样性（4）—（5）要求分清联结词“与”联结的复合命题与简单命题将各命题符号化3.析取式与析取联结词“∨”定义1.3设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例将下列命题符号化（1）2或4是素数.（2）2或3是素数.（3）4或6是素数.（4）小元元只能拿一个苹果或一个梨.（5）王小红生于1975年或1976年.（1）—（3）为相容或（4）—（5）为排斥或在符号化时（5）可有两种形式，而（4）则不能4.蕴涵式与蕴涵联结词“”定义1.4设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.说明：（1）pq的逻辑关系：q为p的必要条件（2）“如果p,则q的不同表述法很多：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q，否则非p，…．（3）当p为假时，pq为真，可称为空证明（4)常出现的错误：不分充分与必要条件例设p：天冷，q：小王穿羽绒服，将下列命题符号化（1）只要天冷，小王就穿羽绒服.（2）因为天冷，所以小王穿羽绒服.（3）若小王不穿羽绒服，则天不冷.（4）只有天冷，小王才穿羽绒服.（5）除非天冷，小王才穿羽绒服.（6）除非小王穿羽绒服，否则天不冷.（7）如果天不冷，则小王不穿羽绒服.（8）小王穿羽绒服仅当天冷的时候.注意：pq与qp等值（真值相同）（1），（2），（3），（6）符号化为pq其余的符号化为qp5.等价式与等价联结词“”定义1.5设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并规定为真当且仅当p与q同时为真或同时为假.（1）pq的逻辑关系：p与q互为充分必要条件（2）pq为真当且仅当p与q同真或同假例求下列复合命题的真值（1）2+2＝4当且仅当3+3＝6.（2）2+2＝4当且仅当3是偶数.（3）2+2＝4当且仅当太阳从东方升起.（4）2+2＝4当且仅当美国位于非洲.（5）函数f(x)在x0可导的充要条件是它在x0连续.它们的真值是显而易见的.第一节小结本小节中p,q,r,…均表示命题.联结词集为{,,,,}，每个联结词联结的p,pq,pq,pq,pq为基本复合命题.其中pq最难理解，要特别注意.反复使用{,,,,}中的联结词组成更为复杂的复合命题.设p:是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转则复合命题(pq)((rs)p)是假命题.联结词的运算顺序：,,,,,同级按先出现者先运算.2一、命题变项与合式公式1．命题变项（或命题变元）（1）命题常项（2）命题变项（3）常项与变项均用p,q,r,…,pi,qi,ri,…,等表示.2．合式公式（简称公式）定义1.6合式公式的递归定义：（1）原子合式公式（单个命题变项）（2）若A是合式，则(A)也是（3）若A,B是合式，则(AB),(AB),(AB),(AB)也是（4）只有有限次地应用（1）—（3）形成的符号串才是公式第二节命题公式及其赋值几点说明：归纳或递归定义元语言与对象语言外层括号可以省去３．合式公式的层次定义1.7（1）若公式A是单个的命题变项，则称A为0层合式.（2）称A是n+1(n≥0)层公式是指下面情况之一：(a)A=B,B是n层公式；(b)A=BC,其中B,C分别为i层和j层公式，且n=max(i,j)；(c)A=BC,其中B,C的层次及n同(b)；(d)A=BC,其中B,C的层次及n同(b)；(e)A=BC,其中B,C的层次及n同(b).（3）若公式A的层次为k,则称A为k层公式.公式A=p,B=p,C=pq,D=(pq)r,E=((pq)r)(rs)分别为0层，1层，2层，3层，4层公式.二、公式的赋值（或解释）与真值表1.公式的赋值定义1.8（1）赋值（解释）（2）成真赋值（3）成假赋值几点说明：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1,p2,…,pn，给A赋值12…n是指p1=1,p2=2,…,pn=nA中仅出现p,q,r,…,给A赋值123…是指p=1,q=2,r=3…含n个变项的公式有2n个赋值.易知000,010,101,110是(pq)r的成真赋值，而001,011,100,111是成假赋值.2.公式的类型定义1.9（1）重言式（也称永真式）（2）矛盾式（也称为永假式）（3）可满足式（不是矛盾式的公式）注意：重言式是可满足式，但反之不真.易知(pp)q,(pp)q,pq分别为重言式、矛盾式、可满足式.问：（1）如何判断公式的类型？（2）如何求出公式A的全部成真与成假赋值？3．真值表定义1.10A的真值表A的取值情况列成的表（1）写真值表的过程（见下面例题）例写出下列公式的真值表A=(pq)rB=(qp)qpC=(pq)qA的真值表pqrpqr(pq)r000001010011100101110111001111111010101011101010从上表看出A的成真与成假赋值及它的类型B的真值表pqqp(qp)q(qp)qp00011011101100011111从表看出B是那种类型公式？C的真值表pqppq(pq)(pq)q000110111100110100100000C是那种类型?几点说明熟练之后，真值表的中间有些层次可不写真值表的用途（1）有了公式A的真值表就知道了A的一切信息（2）其它用途待续一、第一章的内容与要求1．主要内容命题、真值、命题的分类、命题符号化联结词,,,,及复合命题符号化命题公式及层次公式的类型真值表及应用2．要求深刻理解各联结词的逻辑关系会求复合命题的真值熟练地将复合命题符号化准确地求公式的真值表，并用它求公式成真与成假赋值及判断公式类型第一章习题课二、练习题1．将下列命题符号化（1）豆沙包是由面粉和红小豆做成的.（2）苹果树和梨树都是落叶乔木.（3）王小红或李大明是物理组成员.（4）王小红或李大明中的一人是物理组成员.（5）由于交通阻塞，他迟到了.（6）如果交通不阻塞，他就不会迟到.（7）他没迟到，所以交通没阻塞.（8）除非交通阻塞，否则他不会迟到.（9）他迟到当且仅当交通阻塞.分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及必要充分条件答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）请分别写出（1）—（4）的符号化形式设p:交通阻塞，q:他迟到（5）pq,（6）pq或qp（7）qp或pq,（8）qp或pq（9）pq或pq可见（5）与（7），（6）与（8）相同（等值）提示：2．设p:2是素数q:北京比天津人口多r:美国的首都是旧金山求下面命题的真值（1）(pq)r（2）(qr)(pr)（3）(qr)(pr)（4）(qp)((pr)(rq))p,q为真命题，r是假命题反复用基本复合命题的真值求解（心算即可）答案：真值分别为0,1,0,0提示：3．用真值表判断下面公式的类型（1）pr(qp)（2）((pq)(qp))r（3）(pq)(pr)按层次写真值表，由最后一列判类型答案：（1）为矛盾式，（2）为重言式，（3）为可满足式提示：本章的主要内容：等值式与基本的等值式等值演算与置换规则析取范式与合