离散数学1.1-2

1离散数学张波E-mail：[e-mail]手机：[phone]办公室：行政楼B2122主要内容数理逻辑（又称符号逻辑）集合论代数结构图论组合分析初步形式语言和自动机初步3数理逻辑部分第1章命题逻辑第2章一阶逻辑4第1章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范式1.5推理理论51.1命题符号化及联结词命题与真值原子命题复合命题命题常项命题变项联结词6命题与真值命题:判断结果惟一的陈述句命题的真值:判断的结果真值的取值:真与假真命题:真值为真的命题假命题:真值为假的命题注意:1.感叹句、祈使句、疑问句都不是命题；2.陈述句中的悖论不是命题；3.判断结果不惟一确定的不是命题7例下列句子中那些是命题？(1)是无理数.(2)2+5＝8.(3)x+5＞3.(4)你今天偷菜了吗？(5)这只兔子跑得真快呀！(6)诚湖内不许滑冰！(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)~(7)都不是命题28例下列句子中那些是命题？(8)明年10月1日是晴天.(9)地球外的星球上也有人.（10）11＋1＝100.（8）、（9）的真值虽然现在还不知道，但它的真值是唯一的，因而是命题。（10）在二进制中为真，在十进制中为假，需根据上下文才能确定其真值，因而不是命题。9命题的分类1.简单命题(原子命题)简单构成的命题(不能分解成更简单的陈述句)简单命题的真值是确定的，又称为命题常项或命题常元2.复合命题由简单命题与联结词按一定规则复合而成的命题3.命题变项（命题变元）真值不确定的陈述句，如:x+35注意：命题变元不是命题！10简单命题符号化2用小写英文字母p,q,r,…,pi,qi,ri(i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p的真值为0q：2+5=7，则q的真值为1命题变项：也用小写英文字母p,q,r,…,pi,qi,ri(i≥1）表示11联结词与复合命题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)q∧p.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)王晓红生于1989年或1990年.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例（7）小王现在在宿舍或图书馆里.令v:小王在宿舍,w:小王在图书馆则(7)符号化为v∨w例（6）选小王或小李中的一人当班长.解令t:小王当班长，u:小李当班长则(6)符号化为(t∧u)∨(t∧u).17定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.注意：1.p与q不一定有内在联系2.前件p为假时，pq为真4.蕴涵式与蕴涵联结词“”18pq的逻辑关系：p为q的充分条件，q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q,否则非p，常出现的错误：不分充分与必要条件19例设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.注意：pq与qp等值（真值相同）pqpqpqpqqpqpqpqp20定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并pq规为真当且仅当p与q同时为真或同时为假.说明:(1)pq的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假(3)pq与(pq)(qp)等值5.等价式与等价联结词“”21例求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝4当且仅当美国位于非洲.(5)2+2≠4当且仅当3不是奇数.（6）两圆面积相等当且仅当它们的半径相等.它们的真值分别为1，0，1，0，1,122复合命题符号化：第一步：分析出各简单命题，并将它们符号化第二步：使用合适的连接词，把简单命题逐个联结起来例1.小王是500米速滑冠军或1000米速滑冠军2.小王现在在宿舍或在图书馆里3.选小王或小李中的一人当班长4.如果我上街，我就去书店看看，除非我很累r（pq）或（r∧p)q5.小王是计算机系学生，他生于1990年或1991年，他是三好学生23联结词与复合命题以上给出了5个联结词：,,,,，组成一个联结词集合{,,,,}，联结词的优先顺序为：,,,,;如果出现的联结词同级，又无括号时，则按从左到右的字典顺序运算;若遇有括号时，应该先进行括号中的运算.注意:本书中使用的括号全为圆括号.241.2命题公式及分类命题变项与合式公式公式的赋值真值表命题公式的分类重言式矛盾式可满足式25命题变项与合式公式命题常项：简单命题,真值确定的陈述句命题变项：真值不确定的陈述句定义合式公式(命题公式,公式)递归定义如下：(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)形成的符号串才是合式公式26合式公式的层次定义(1)若公式A是单个的命题变项或命题常项（包括0，1）,则称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).27合式公式的层次例如公式p0层p1层pq2层(pq)r3层((pq)r)(rs)4层28公式的赋值定义给公式A中的命题变项p1,p2,…,pn，给p1,p2,…,pn各指定一个真值（0或1），称为对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个赋值.29真值表真值表:公式A在所有赋值下的取值情况列成的表（1）列出所有命题变项，列出所有可能赋值（2）按从低到高的顺序写出各层次；（3）对应每个赋值，计算命题公式各层次的值，直到命题公式的值例给出公式的真值表A=(qp)qp的真值表pqqp(qp)q(qp)qp0001101110110001111130例B=(pq)q的真值表pqppq(pq)(pq)q000110111100110100100000实例31例C=(pq)r的真值表pqrpqr(pq)r00000101001110010111011100111111101010101110101032公式的类型定义设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真值表－－判断命题公式类型的一种方法