数理逻辑课件(离散数学)

第一部分数理逻辑1数理逻辑部分主要内容：命题逻辑1.1命题符号化及联结词1.2命题公式及分类2.1等值演算2.2范式2.3联结词的完备集3.1-3.2推理理论一阶逻辑（谓词逻辑）4.1一阶逻辑命题符号化4.2一阶逻辑公式及解释5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论2第一章命题逻辑基本概念31.1命题与联结词命题与真值原子命题的符号化复合命题联结词重点内容：命题的符号化4例1：下列句子中哪些是命题？并判断真值(1)清华大学是一所全国重点大学.(2)2+5＝8.(3)你有铅笔吗？(4)这只兔子跑得真快呀！(5)请不要讲话！真命题假命题疑问句感叹句祈使句一、命题与真值（例题）5一、命题与真值命题:判断结果惟一的陈述句命题的真值:判断的结果真值的取值:真、假真命题:真值为真的命题假命题:真值为假的命题6一、命题与真值（例题）例2：判断下列语句是否是命题明年我将去欧洲下个月十五号是晴天x－y2是命题不是命题不确定真值不知道真值7一、命题与真值（例题）例3：“我正在说假话”，这句话是命题吗？如果这句话是“真”的如果这句话是“假”的根据这句话的意义推得这句话是“假”的这句话是“真”的该陈述句为悖论该陈述句不是命题8一、命题与真值（小结）1.感叹句、祈使句、疑问句属于非陈述句，所以都不是命题；2.如果陈述句的判断结果不惟一确定，那么该陈述句也不是命题；3.陈述句中的悖论也不是命题。9二、命题符号化“是有理数”，是命题，且真值为0或F；2+5=7，是命题，且真值为1或T；2上述命题不能再分解为更简单的命题。定义：一个命题不能再分解为更简单的命题，则称该命题为原子命题，也称简单命题。命题逻辑中研究的最基本单位10二、命题符号化用小写英文字母p，q，r，…，pi，qi，ri(i≥1）等表示简单命题（原子命题）。例：令p:2+5=7用“1”或“T”表示真，用“0”或“F”表示假。11二、命题符号化令t：我来自西安，s：我是一名教师。问题：如何表示“我是一名教师，并且我来自西安”？复合命题定义：由简单命题与联结词按一定规则复合而成的命题。12三、复合命题及联结词1.否定式与否定联结词“”定义：设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词。p真值表pp011013三、复合命题及联结词例如：p:上海是一个城市。p:上海不是一个城市。规则：(p)等价于pp:上海是一个大城市。p:上海是一个小城市。p:上海不是一个大城市。14三、复合命题及联结词“p与q”记作p∧q称为p、q的合取式∧为合取联结词2.合取式与合取联结词“∧”pqp∧q00001010011115三、复合命题及联结词（例题）例4：将下列命题符号化。(1)王晓既用功又聪明。(2)王晓不仅聪明，而且用功。(3)王晓虽然聪明，但不用功。(4)张辉与王丽都是三好生。(5)张辉与王丽是同学。简单命题p∧qp∧qp∧(q)r∧s令p：王晓用功；q：王晓聪明；r:张辉是三好学生s:王丽是三好学生16三、复合命题及联结词p∧pp∧1p∧0p∧(p)等价于p等价于p等价于0等价于0关于“合取”的相关规则例5：计算下列命题的真值(1∧0)1∧(p∧0)((p∧0))∧100117三、复合命题及联结词合取满足交换律。p∧q等价于q∧p合取满足结合律。p∧(q∧r)等价于(p∧q)∧r18三、复合命题及联结词“p或q”记作p∨q称作p与q的析取式∨称作析取联结词3.析取式与析取联结词pqp∨q00001110111119三、复合命题及联结词（例题）例6：将命题“2或4”是素数符号化p∨q令p:2是素数;q:4是素数；例7：将下列命题符号化小元元只能拿一个苹果或一个梨。王晓红生于1975年或1976年。t:小元元拿一个苹果;u:小元元拿一个梨；v:王晓红生于1975年;w:王晓红生于1976年。20三、复合命题及联结词（例题续）分析：在例6中，构成复合命题的两个原子命题之间没有排斥性，即两个原子命题有同时为真的可能性。例7中，构成复合命题的两个原子命题之间存在排斥性。相容或排斥或21三、复合命题及联结词（例题续）“排斥或”的复合命题该如何符号化呢？小元元只能拿一个苹果或一个梨。符号化为(t∧u)∨(t∧u)王晓红生于1975年或1976年。符号化为(v∧w)∨(v∧w)也可以表示成：v∨w可以用异或来表示注意对比这两个“排斥或”的不同注意对比这两个“排斥或”的不同22三、复合命题及联结词小结：自然语言中的“或”是多义的，主要有以下两种情况：可兼或（相容或）：二者至少有一个发生，不排斥二者都发生的情况。同析取联结词的含义完全相同。排斥或：非此即彼，二者不可兼得。23三、复合命题及联结词p∨pp∨1p∨0p∨(p)等价于p等价于1等价于p等价于1关于“析取”的相关规则析取也满足交换律合结合律。24三、复合命题及联结词例8：假设e表示“Alice高兴”，r表示“Tom高兴”，那么将下列自然语言的陈述转换成逻辑命题。如果Alice高兴，那么Tom高兴；除非Alice高兴，Tom才高兴；25三、复合命题及联结词4.蕴涵式与蕴涵联结词“”“如果p,则q”称作p、q的蕴涵式记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件。称作蕴涵联结词，或条件联结词。26三、复合命题及联结词pqpq001011100111pq真值表善意的推定27三、复合命题及联结词pq的逻辑关系：p是q的充分条件；q为p的必要条件。“如果…则…”的不同表述法有：“只要…就…”，“…仅当…”，“除非…才…”等。28三、复合命题及联结词（例题）例9：将下列命题符号化（1）只有努力才能取得成功（2）只要努力过就不后悔设：p:努力q:成功s：努力过t：不后悔qpst29三、复合命题及联结词（例题）例10：设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服。(2)因为天冷，所以小王穿羽绒服。(3)若小王不穿羽绒服，则天不冷。(4)只有天冷，小王才穿羽绒服。pqpqqpqp30三、复合命题及联结词（例题续）(5)除非天冷，小王才穿羽绒服。(6)除非小王穿羽绒服，否则天不冷。(7)如果天不冷，则小王不穿羽绒服。(8)小王穿羽绒服仅当天冷的时候。pqqppqqp31三、复合命题及联结词小结：只有…才、除非…才、仅当表达的是必要条件；只要…就、如果…就（则）表达的是充分条件；课堂练习：习题832三、复合命题及联结词5.等价式与等价联结词“”“p当且仅当q”记作pq称作p、q的等价式也称作双条件式称作等价联结词。pqpq00101010011133三、复合命题及联结词需要注意以下两点：等价联结词即通常的“充分必要条件”;pq为真当且仅当p与q同真或同假，也称“同或”。34三、复合命题及联结词（例题）例11：求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6。(2)2+2＝4当且仅当3是偶数。(3)2+2＝4当且仅当太阳从东方升起。(4)2+2＝4当且仅当美国位于非洲。1010复合命题的真值取决于构成它的各原子命题的真值，而与它们的内容、含义无关。35三、复合命题及联结词等价联结词具有以下性质：满足结合律(pq)r等价于p(qr)满足交换律pq等价于qppp的真值永远为“真”pp的真值永远为“假”36三、复合命题及联结词有关联结词优先级如下：联结词的优先顺序为：,,,,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;有括号时，应该先进行括号中的运算。37三、复合命题及联结词（1）与含义相同（2）与含义相同（3）与含义相同qpq)p(rqpr)qp(rqp)rq(p由联结词的优先级可得：38例题例12：利用联结词，将下述语句符号化：“如果你走路时看书，那么你一定会成为近视眼”。解：令p：你走路；q：你看书；r：你是近视眼。则上述语句可以符号化为：(pq)r39例题例13：将下列命题符号化（1）他努力而且聪明，这不是真的。令p:他努力；q:他聪明)qp(（2）虽然天气很冷，老王还是来了。令p:天气很冷；q:老王来了qp40例题（3）不经一事，不长一智令p:经一事；q:长一智qp（4）若两个圆面积相等，那么它们的半径相等；反之亦然。令p:两个圆面积相等；q:两个圆半径相等qp41例题例14：符号化下列两个命题如果你和他都不固执己见的话，那么不愉快的事也不会发生了。如果你和他不都固执己见的话，那么不愉快的事也不会发生了。r)qp(r)qp(42例题例15：将下列命题符号化，并讨论各命题的真值。若今天是星期一，则明天是星期二若今天是星期一，则明天是星期三43作业习题一：14，15441.2命题公式及其赋值命题常项和命题变项合式公式公式的赋值真值表公式的分类45一、命题常项和命题变项命题常项：一个确定的具体的简单命题称作命题常项。也称命题常元。命题变项：当p所代表的只是一个抽象的命题，它可以表示任意的命题，称p为命题变项。也称命题变元。命题变项不是命题。p:天气很冷46一、命题常项和命题变项当用一个特定的命题取代命题变元时，才能确定其真值：真或假。这种取代称作对该命题变元指派真值。p:太阳从东边升起p:太阳从东边升起47二、合式公式1.合式公式的一般化定义：将命题变项用联结词和括号按一定逻辑关系联结起来的符号串称作合式公式，也称命题公式，简称公式。公式通常用字母A、B、C等表示。例：((pq)r)(rs)48二、合式公式2.合式公式的递归定义：(1)单个命题常项或变项p,q,r,…是合式公式；(2)若A是合式公式，则(A)也是合式公式；(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)~(3)形成的包含命题变元、联结词和括号的符号串才是合式公式。此处的A、B等称作元语言符号，代表抽象的公式49二、合式公式3.子公式定义：若A为合式公式，B为A的一部分，且B也是合式公式，则称B为A的子公式。例：(pq)r是合式公式A，pq是合式公式B，B是A的一部分。称B是A的子公式。50三、公式的赋值pq是一个合式公式，但是真值是多少呢？若令p:2是偶数，q：2是素数，则pq真值为真；若令p:3是偶数，q：3是素数，则pq真值为假；定义：给公式A中的命题变项p1,p2,…,pn给予一定的解释，使其获得一组确定的真值，这个过程称为对A的一个赋值或解释。51三、公式的赋值例1：公式B=(pq)q的真值表pqppq(pq)(pq)q00011011110011010010000052pqrpqr(pq)r000001010011100101110111001111111010101011101010例2：C=(pq)r的真值表含n个变项的公式有2n个赋值。成假赋值53四、公式的层次公式((pq)r)(rs)p0层p1层pq2层(pq)r3层((pq)r)(rs)4层54四、公式的层次合式公式的层次定义(1)若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1层公式是指下面情况之一：(a)A=B，B是n层公式；(b)A=BC；(c)A=BC；(d)A=BC；(e)A=BC.其中B、C分别为i层和j层公式，且n≥0，n=max(i,j)；55五、公式的分类定义：设A为一个命题公式若A无成假赋值，则称A为重言式(或永真式)若A无成真赋值，则称A为矛盾式(或永假式)若A不是矛盾式，则称A为可满足式。注意：重言式是可满足式，但可满足式不一定是重言式。56五、公式的分类重言式的特点：重言式的否定是矛盾式，矛盾式的否