《离散数学课件：第1章 命题逻辑1》由会员分享，可在线阅读，更多相关《离散数学课件：第1章 命题逻辑1（33页珍藏版）》请在金锄头文库上搜索。
1、1离散数学离散数学2主要内容主要内容n数理逻辑数理逻辑n集合论集合论n图论图论n组合分析初步组合分析初步n代数系统简介代数系统简介n形式语言和自动机初步形式语言和自动机初步3教材与教学参考书教材与教学参考书n教材：教材：耿素云、屈婉玲、张立昂，离散数学（第五版）耿素云、屈婉玲、张立昂，离散数学（第五版），清华大学出版社，清华大学出版社, 2013. n教学参考书：教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（第屈婉玲、耿素云、张立昂，离散数学题解（第五版），清华大学出版社，五版），清华大学出版社，2013. 4数理逻辑部分数理逻辑部分n第第1章章 命题逻辑命题逻辑n第第2章章 一阶逻辑一阶
2、逻辑5第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 范式范式1.5 联结词全功能集联结词全功能集1.6 组合电路组合电路1.7 推理理论推理理论61.1 命题符号化及联结词命题符号化及联结词 n命题与真值命题与真值n原子命题原子命题n复合命题复合命题n命题常项命题常项n命题变项命题变项n联结词联结词 7命题与真值命题与真值 命题命题: 能够确定对错的、表达判断能够确定对错的、表达判断的的陈述句陈述句命题的真值命题的真值: 判断的对错结果判断的对错结果真值的取值真值的取值: 真与假真与假真命题真命题:
3、 真值为真的命题真值为真的命题假命题假命题: 真值为假的命题真值为假的命题注意注意:陈述句中的陈述句中的悖论悖论以及判断结果以及判断结果不确定（不确定（不是未不是未知知）的不是命题；的不是命题；当当然然，感感叹叹句句、祈祈使使句句、疑疑问问句句都都不不是是命命题题（因因为为没有表达判断没有表达判断）8 例例 下列句子中那些是命题？下列句子中那些是命题？ (1) 是无理数是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？你有铅笔吗？ (5) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (6) 请不要讲话！请不要讲话！ (7) 本句真值为假本句真值为假.真命题真命题
4、假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题9命题符号化命题符号化 用小写英文字母用小写英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示）表示简单命题简单命题( (概念后述概念后述) )；用；用“1”表示真，表示真， “0”表示表示假假例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为 0 q：2 + 5 = 7，则，则 q 的真值为的真值为 1 10命题的分解与组合命题的分解与组合 简单简单( (原子原子) )命题命题即不可再分解即不可再分解： 简单陈述句构成的命题简单陈述句构成的命题
5、 相应地有，相应地有，复合命题复合命题： 由简单命题与由简单命题与联结词联结词按一定规则复合按一定规则复合 而成的命题而成的命题 11联结词与复合命题联结词与复合命题 1.否定式否定式 否定联结词否定联结词“ ” 定义定义 设设p为命题，复合命题为命题，复合命题 “非非p”(或或“p的否定的否定”)称称 为为p的的否定式否定式，记作，记作 p. . 符号符号 称作称作否定联结词否定联结词，规定规定 p 为真当且仅当为真当且仅当p为假为假. .2.合取式合取式 合取联结词合取联结词“” 定义定义 设设p, ,q为二命题为二命题, ,复合命题复合命题“p并且并且q”( (或或“p与与q”) )称称
6、 为为p与与q的的合取式合取式，记作，记作pq. . 称作称作合取联结词合取联结词，规定规定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注注意意两两点点：合合取取式式在在自自然然语语言言中中叙叙述述的的灵灵活活性性与与多多样样性性； 分清简单命题与复合命题分清简单命题与复合命题 12 例例 将下列命题符号化将下列命题符号化. (1) 王晓既用功又聪明王晓既用功又聪明. (2) 王晓不仅聪明，而且用功王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生张辉与王丽都是三好生. (5) 张辉与王丽是同学张辉与王丽是同学. 解解 令令
7、 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1) pq (2) pq (3) p q.13 例例 (续续) 令令 r : 张辉是三好学生，张辉是三好学生，s :王丽是三好学生王丽是三好学生 (4) rs. (5) 令令 t : 张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题 .说明说明: (1)(4)题说说明明自自然然语语言言叙叙述述合合取取命命题题的的灵灵活活性性与多样性与多样性. 第第(5)题题 中中“与与”不不可可分分解解，句句子子表表达达的的是是联联结结的的是是两两个个名名词词之之间间的的关关系系，整整个个句句子子是是一一个个简单命题简单命题.14联结词
8、与复合命题联结词与复合命题( (续续) ) 定定义 设 p,qp,q为二二命命题，复复合合命命题“p p或或q q”称称作作p p与与q q 的的析取式析取式，记作作p pq q. . 称作称作析取析取联结词规定定p pq q为假当且假当且仅当当p p与与q q同同时为假假. .例例 将下列命题符号化将下列命题符号化 (1) 2或或4是素数是素数. (2) 2或或3是素数是素数. (3) 4或或6是素数是素数. * (4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨. * (5) 王晓红生于王晓红生于1975年或年或1976年年. 3.析取式析取式 析取联结词析取联结词“”15解
9、解 令令 p:2是素数是素数, q:3是素数是素数, r:4是素数是素数, s:6是素数是素数, , 则则 (1), (2), (3) 均为均为相容或相容或. . 分别符号化为分别符号化为: : pr , pq, rs, 它们的真值分别为它们的真值分别为 1, 1, 0. (4), (5) 为为排斥或排斥或. 令令 t :小元元拿一个苹果，小元元拿一个苹果，u:小元元拿一个梨，小元元拿一个梨， 则则 (4) 符号化为符号化为 (t u) ( tu). 令令v :王晓红生于王晓红生于1975年年, ,w: :王晓红生于王晓红生于1976年年, ,则则 (5) 既可符号化为既可符号化为 (v w)
10、( vw), 又可又可符号化为符号化为 vw . 16联结词与复合命题联结词与复合命题( (续续) ) 定定义义 设设 p,qp,q为为二二命命题题，复复合合命命题题 “如如果果p,p,则则q q” 称称作作p p与与q q的的蕴蕴涵涵式式，记记作作p pq q，并并称称p p是是蕴蕴涵涵式式的的前前件件，q q为为蕴蕴涵涵式式的的后后件件. . 称称作作蕴蕴涵涵联联结词结词规规定定，p pq q为为假假 当当且且仅仅当当 p p 为为真真 q q 为为假假（即即其他情况下都为真）其他情况下都为真）4.蕴涵式蕴涵式 蕴涵联结词蕴涵联结词“”17pq 的逻辑关系：的逻辑关系：q 为为 p 的必要
11、条件的必要条件“如果如果 p，则，则 q ” 的不同表述法很多：的不同表述法很多： 若若 p，就（则），就（则）q 只要只要 p，就，就 q p 仅当仅当 q 只有只有 q 才有才有 p （但并没有但并没有说 有有q 必有必有p） 除非除非 q, 才才 p 或或 除非除非 q, 否则非否则非 p. .特别注意：当特别注意：当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件联结词与复合命题联结词与复合命题( (续续) )18 例例 设设 p p: :天冷，天冷，q q: :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1)
12、只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意： pq 与与 qp 等值（真值相同）等值（真值相同） pqpqpqpqqp qpqpqp1
13、9联结词与复合命题联结词与复合命题( (续续) )定定义义 设设p，q为为二二命命题题，复复合合命命题题 “p当当且且仅仅当当q”称称作作p与与q的的等价式等价式，记作，记作pq. 称作称作等价联结词等价联结词. 规定规定 pq为真当且仅当为真当且仅当p与与q同为真或同为假同为真或同为假.pq 是判断是判断 p与与q互为充分必要条件的命题表达互为充分必要条件的命题表达5. 等价式等价式 等价联结词等价联结词“”20例例 求下列复合命题的真值求下列复合命题的真值 (1) 2 + 2 4 当且仅当当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数. (3) 2
14、+ 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起. (4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲. (5) 函数函数 f (x) 在在x0 可导的充要条件是它在可导的充要条件是它在 x0连续连续.11000例例21联结词与复合命题联结词与复合命题( (续续) )以上给出的以上给出的5个联结词：个联结词： , , , , （为了讨（为了讨论的方便，我们统一念为：论的方便，我们统一念为： 非，且，或，仅当，当且仅当）非，且，或，仅当，当且仅当）, ,组成一个联结词集组成一个联结词集 , , , , ，联结词的优先顺序为：联结词的优先顺序为： , , , , ; 如果
15、出现的联结词同级，又无括号时，则如果出现的联结词同级，又无括号时，则按从左到右的顺序运算按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算若遇有括号时，应该先进行括号中的运算.应适当使用括号提高清晰度适当使用括号提高清晰度 221.2 命题公式及分类命题公式及分类命题变项与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类 重言式重言式 矛盾式矛盾式 可满足式可满足式n真值函数真值函数23命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题命题变项命题变项：真值可确定但未确定的陈述句：真值可确定但未确定的陈述句合式公式合式公式 (命题
16、公式命题公式, 公式公式) 的的递归定义如下：递归定义如下：(1) 单个命题常项或变项单个命题常项或变项 p,q,r, ,pi ,qi ,ri ,0,1 是是合式公式合式公式(2) 若若A是合式公式，则是合式公式，则 A也是合式公式也是合式公式(3) 若若A, B是是合合式式公公式式，则则A B, A B, AB, AB也是合式公式也是合式公式(4) 只只有有有有限限次次地地应应用用(1)(3)形形成成的的符符号号串串才才是是合合式公式式公式24合式公式的层次合式公式的层次 定义定义 (1) 若公式若公式A是单个的命题变项是单个的命题变项, 则称则称A为为0层公式层公式.(2) 称称A是是n+
17、1(n0)层公式是指下面情况之一：层公式是指下面情况之一： (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=BC, 其中其中B,C的层次及的层次及n同同(b)； (e) A=BC, 其中其中B,C的层次及的层次及n同同(b). 25合式公式的层次合式公式的层次 (续续) 例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 ( p q) r)( r s) 4层层26公式的赋值公式的赋值
18、定义定义 给公式给公式A中的命题变项中的命题变项 p1, p2, , pn指定指定一组真值称为对一组真值称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值: 使公式为真的赋值使公式为真的赋值成假赋值成假赋值: 使公式为假的赋值使公式为假的赋值赋值的表示：赋值的表示： 赋值赋值 = 1 2 n（ i=0或或1，之间不加标点）之间不加标点） 若若A中中出出现现 p1, p2, , pn，给给A赋赋值值 1 2 n是是指指 p1= 1, p2= 2, , pn= n 若若A中出现中出现 p, q, r, , 给给A赋值赋值 1 2 3是指是指p= 1,q= 2 , r= 3 （即按字母序）（即
19、按字母序） 含含n个变项的公式共有个变项的公式共有2n个赋值个赋值. 27真值表真值表 真值表真值表: 公式公式A在所有赋值下的取值列成的表在所有赋值下的取值列成的表 例例 给出公式的真值表给出公式的真值表 （1）A= (qp) qp 的的真值表真值表 p q qp (qp) q (qp) qp 0 00 11 01 1 1011 0001 111128（2）B = ( p q) q 的的真值表真值表 p q p p q ( p q) ( p q) q0 00 11 01 1 110011010010000029（3） C= (p q) r 的的真值表真值表 p q r p q r (p q)
20、r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 1110101030公式的类型公式的类型 定义定义 设设A为一个命题公式为一个命题公式 (1) 若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式( (也称也称永真式永真式) ) (2) 若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式( (也称也称永假式永假式) ) (3) 若若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真. .前例中，前例中，A= (qp) qp 为重言式
21、为重言式 B = ( p q) q 为矛盾式为矛盾式 C= (p q)r 为可满足式为可满足式问问题题：所所有有含含相相同同的的n个个命命题题变变项项的的公公式式产产生生的的不不相相同的真值表共有多少个？（无限？有限？）同的真值表共有多少个？（无限？有限？）定义定义 称定义域为称定义域为000, 001, , 111，值域，值域为为0,1的的函函数数是是n元元真真值值函函数数，定定义义域域中中的的元元素素（共共有有2n个个) )是是长长度度为为n的的0/1串串. 常常用用F:0,1n0,1 表表示示F是是n元真值函数元真值函数. 例如例如 F:0,120,1，且，且F(00)=F(01)=F(
22、11)=0，F(10)=1，则，则F为一个确定的为一个确定的2元真值函数元真值函数. 明明显地地 F 对应一个真一个真值表表 共有共有 个个n元真值函数元真值函数.31真值函数真值函数 含含n个个命命题题变变项项的的命命题题公公式式有有无无数数个个，而而n元元真真值值函函数数个个数数有有限限，每每一一个个n元元真真值值函函数数F必必对应多多个个公公式式的的真真值表表；反反过来来，任任一一含含n个个命命题题变变项项的的命命题题公公式的真值表惟一对应某一个式的真值表惟一对应某一个n元真值函数元真值函数F。真值表对应同一个真值函数的公式称为等值公式真值表对应同一个真值函数的公式称为等值公式.下表给出
23、所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表, 每一个含每一个含2 2个命题变项的公式的真值表都可以在其中找到个命题变项的公式的真值表都可以在其中找到. 例例如如：pq, p q, ( p q) ( (pq) q) 等等都对应表中的都对应表中的32命题公式与真值函数命题公式与真值函数 332元真值函数对应的真值表元真值函数对应的真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
