1.1-2 命题符号化 联结词 命题公式

1离散数学2主要内容数理逻辑集合论代数结构图论组合分析初步形式语言和自动机初步3教材与教学参考书教材：耿素云、屈婉玲、张立昂，离散数学（第三版），清华大学出版社,2004.教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（修订版），清华大学出版社，2004.4数理逻辑部分第1章命题逻辑第2章一阶逻辑5第1章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范试1.5推理理论61.1命题符号化及联结词命题与真值原子命题复合命题命题常项命题变项联结词7命题与真值命题:判断结果惟一的陈述句命题的真值:判断的结果真值的取值:真与假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题8例下列句子中那些是命题？(1)是无理数.(2)2+5＝8.(3)x+5＞3.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)~(7)都不是命题29命题的分类简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题10简单命题符号化2用小写英文字母p,q,r,…,pi,qi,ri(i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p的真值为0q：2+5=7，则q的真值为111联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p为真当且仅当p为假2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题12例将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1)p∧q(2)p∧q(3)p∧q.13例(续)令r:张辉是三好学生，s:王丽是三好学生(4)r∧s.(5)令t:张辉与王丽是同学，t是简单命题.说明:(1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是句子的主语成分，因而(5)中句子是简单命题.14联结词与复合命题(续)定义设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年.3.析取式与析取联结词“∨”15解令p:2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3)均为相容或.分别符号化为:p∨r,p∨q,r∨s,它们的真值分别为1,1,0.而(4),(5)为排斥或.令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为(t∧u)∨(t∧u).令v:王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧w)∨(v∧w),又可符号化为v∨w,为什么?16联结词与复合命题(续)定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.4.蕴涵式与蕴涵联结词“”17pq的逻辑关系：q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q,否则非p，当p为假时，pq为真常出现的错误：不分充分与必要条件联结词与复合命题(续)18例设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.注意：pq与pq等值（真值相同）pqpqpqpqqpqpqpqp19联结词与复合命题(续)定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并pq规为真当且仅当p与q同时为真或同时为假.说明:(1)pq的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假5.等价式与等价联结词“”20例求下列复合命题的真值(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连续.它们的真值分别为1，0，1，0，0.21联结词与复合命题(续)以上给出了5个联结词：,,,,，组成一个联结词集合{,,,,}，联结词的优先顺序为：,,,,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算.注意:本书中使用的括号全为圆括号.221.2命题公式及分类命题变项与合式公式公式的赋值真值表命题的分类重言式矛盾式可满足式23命题变项与合式公式命题常项：简单命题命题变项：真值不确定的陈述句定义合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项p,q,r,…,pi,qi,ri,…,0,1是合式公式(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式说明:元语言与对象语言,外层括号可以省去24合式公式的层次定义(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).25合式公式的层次(续)例如公式p0层p1层pq2层(pq)r3层((pq)r)(rs)4层26公式的赋值定义给公式A中的命题变项p1,p2,…,pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值说明：赋值=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个赋值.27真值表真值表:公式A在所有赋值下的取值情况列成的表例给出公式的真值表A=(qp)qp的真值表pqqp(qp)q(qp)qp0001101110110001111128例B=(pq)q的真值表pqppq(pq)(pq)q000110111100110100100000实例29例C=(pq)r的真值表pqrpqr(pq)r00000101001110010111011100111111101010101110101030公式的类型定义设A为一个命题公式(1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A=(qp)qp，B=(pq)q，C=(pq)r