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

1、第一部分 数理逻辑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第一章第一章 命题逻辑基本概念命题逻辑基本概念3 1.1 命题与联结词

2、命题与联结词 l命题与真值命题与真值l原子命题的符号化原子命题的符号化l复合命题复合命题l联结词联结词 重点内容：重点内容：命题的符号化命题的符号化4 例例1 1： 下列句子中哪些是命题？并判断真值下列句子中哪些是命题？并判断真值 (1) 清华大学是一所全国重点大学清华大学是一所全国重点大学. (2) 2 + 5 8. (3) 你有铅笔吗？你有铅笔吗？ (4) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (5) 请不要讲话！请不要讲话！真命题真命题假命题假命题疑问句疑问句感叹句感叹句祈使句祈使句一、命题与真值（例题）一、命题与真值（例题） 5一、命题与真值一、命题与真值l命题命题: 判断结果惟一

3、的陈述句判断结果惟一的陈述句l命题的真值命题的真值: 判断的结果判断的结果l真值的取值真值的取值: 真、假真、假l真命题真命题: 真值为真的命题真值为真的命题l假命题假命题: 真值为假的命题真值为假的命题6一、命题与真值（例题）一、命题与真值（例题）例例2：判断下列语句是否是命题：判断下列语句是否是命题l明年我将去欧洲明年我将去欧洲l下个月十五号是晴天下个月十五号是晴天lxy2是命题是命题不是命题不是命题不确定真值不确定真值不知道真值不知道真值7一、命题与真值（例题）一、命题与真值（例题）例例3：“我正在说假话我正在说假话”，这句话是命题吗？，这句话是命题吗？如果这句话如果这句话是是“真真”的

4、的如果这句话如果这句话是是“假假”的的根据这句话的意义推根据这句话的意义推得这句话是得这句话是“假假”的的这句话是这句话是“真真”的的该陈述句为该陈述句为悖论悖论该陈述句不是命题该陈述句不是命题8一、命题与真值（小结）一、命题与真值（小结）1.感叹句、祈使句、疑问句属于感叹句、祈使句、疑问句属于非陈述非陈述句句，所以都不是命题；，所以都不是命题；2.如果陈述句的如果陈述句的判断结果不惟一确定判断结果不惟一确定，那么该陈述句也不是命题；那么该陈述句也不是命题；3.陈述句中的陈述句中的悖论悖论也不是命题。也不是命题。 9二、命题符号化二、命题符号化“ 是有理数是有理数”，是命题，且真值为，是命题，

5、且真值为 0或或F；2 + 5 = 7，是命题，且真值为，是命题，且真值为 1或或T；2上述命题不能再分解为更简单的命题。上述命题不能再分解为更简单的命题。 定义：定义：一个命题不能再分解为更简单的命题，一个命题不能再分解为更简单的命题，则称该命题为则称该命题为原子命题原子命题，也称简单命题。，也称简单命题。命题逻辑中研究命题逻辑中研究的最基本单位的最基本单位10二、命题符号化二、命题符号化l用小写英文字母用小写英文字母 p，q，r， ，pi，qi，ri (i1）等表示简单命题（原子命题）。）等表示简单命题（原子命题）。 例：例： 令令p: 2 + 5 = 7l用用“1”或或“T”表示真，用表

6、示真，用“0”或或“F”表表示假。示假。11二、命题符号化二、命题符号化令令 t：我来自西安，：我来自西安， s：我是一名教师。：我是一名教师。问题：问题：如何表示如何表示“我是一名教师，并且我是一名教师，并且我来自西安我来自西安”？复合命题复合命题 定义：定义：由简单命题与联结词按一定规则由简单命题与联结词按一定规则复合而成的命题。复合而成的命题。12三、复合命题及联结词三、复合命题及联结词 1.否定式与否定联结词否定式与否定联结词“ ”定义：定义：设设p为命题，复为命题，复合命题合命题 “非非p”（或（或 “p的否定的否定”）称为）称为p的的否否定式定式，记作，记作 p，符号，符号 称作否

7、定联结词。称作否定联结词。 p真值表真值表p p011013三、复合命题及联结词三、复合命题及联结词例如：例如：p:上海是一个城市。上海是一个城市。 p:上海不是一个城市。上海不是一个城市。规则：规则： ( p)等价于等价于pp:上海是一个大城市。上海是一个大城市。 p:上海是一个小城市。上海是一个小城市。 p:上海不是一个大城市。上海不是一个大城市。14三、复合命题及联结词三、复合命题及联结词 “p与与q”记作记作pq 称为称为p、q的的合取式合取式 为合取联结词为合取联结词2. 合取式与合取联结词合取式与合取联结词“”pqp q00001010011115三、复合命题及联结词（例题）三、复

8、合命题及联结词（例题）例例4： 将下列命题符号化。将下列命题符号化。 (1) 王晓王晓既既用功用功又又聪明。聪明。(2) 王晓王晓不仅不仅聪明，聪明，而且而且用功。用功。(3) 王晓王晓虽然虽然聪明，聪明，但但不用功。不用功。(4) 张辉张辉与与王丽都是三好生。王丽都是三好生。(5) 张辉与王丽是同学。张辉与王丽是同学。简单命题简单命题pqpqp( q)rs令令 p：王晓用功；：王晓用功；q：王晓聪明；：王晓聪明； r : 张辉是三好学生张辉是三好学生 s : 王丽是三好学生王丽是三好学生16三、复合命题及联结词三、复合命题及联结词p pp 1p 0p ( p)等价于等价于 p等价于等价于p等

9、价于等价于0等价于等价于 0关于关于“合取合取”的相关规则的相关规则 例例5：计算下列：计算下列命题的真值命题的真值 ( 1 0 )1( p 0 )( ( p 0 ) ) 100117三、复合命题及联结词三、复合命题及联结词合取满足交换律。合取满足交换律。p q 等价于等价于q p 合取满足结合律。合取满足结合律。p (q r) 等价于等价于(pq) r 18三、复合命题及联结词三、复合命题及联结词 “p或或q”记作记作pq称作称作p与与q的的析取式析取式称作析取联结词称作析取联结词3.析取式与析取联结词析取式与析取联结词pqp q00001110111119三、复合命题及联结词（例题）三、复

10、合命题及联结词（例题） 例例6 6：将命题：将命题“2或或4”是素数符号化是素数符号化 pq令令p:2是素数是素数;q:4是素数；是素数；例例7：将下列命题符号化：将下列命题符号化l小元元只能拿一个苹果或一个梨。小元元只能拿一个苹果或一个梨。l王晓红生于王晓红生于1975年或年或1976年。年。 t :小元元拿一个苹果小元元拿一个苹果;u:小元元拿一个梨；小元元拿一个梨； v :王晓红生于王晓红生于1975年年;w:王晓红生于王晓红生于1976年。年。20三、复合命题及联结词（例题续）三、复合命题及联结词（例题续） 分析：分析：在例在例6中，构成复合命题的两个中，构成复合命题的两个原子命题之间

11、没有排斥性，即两个原子原子命题之间没有排斥性，即两个原子命题有同时为真的可能性。命题有同时为真的可能性。 例例7中，构成复合命题的两个原子命题之中，构成复合命题的两个原子命题之间间存在排斥性。存在排斥性。相容或相容或排斥或排斥或21三三、复合命题及联结词（例题续）、复合命题及联结词（例题续）“排斥或排斥或”的复合命题该如何符号化呢？的复合命题该如何符号化呢？l小元元只能拿一个苹果或一个梨。小元元只能拿一个苹果或一个梨。 符号化为符号化为 (t u) ( tu)l王晓红生于王晓红生于1975年或年或1976年。年。 符号化为符号化为 (v w) ( vw) 也可以表示成：也可以表示成：v w可以

12、用可以用异异或或来表示来表示注意对比这注意对比这两个两个“排斥排斥或或”的不同的不同注意对比这注意对比这两个两个“排斥排斥或或”的不同的不同22三三、复合命题及联结词、复合命题及联结词 小结：小结：自然语言中的自然语言中的“或或”是多义的，主是多义的，主要有以下两种情况：要有以下两种情况：l可兼或（相容或）可兼或（相容或）：二者至少有一个发生，：二者至少有一个发生，不排斥二者都发生的情况。同析取联结词不排斥二者都发生的情况。同析取联结词的含义完全相同。的含义完全相同。l排斥或排斥或：非此即彼，二者不可兼得。：非此即彼，二者不可兼得。23三三、复合命题及联结词、复合命题及联结词p pp 1p 0

13、p ( p)等价于等价于p等价于等价于1等价于等价于p等价于等价于1关于关于“析取析取”的相关规则的相关规则析取也满足析取也满足交换律交换律合合结合律结合律。24三三、复合命题及联结词、复合命题及联结词 例例8：假设：假设e表示表示“Alice高兴高兴”，r表示表示“Tom高兴高兴”，那么将下列自然语言的，那么将下列自然语言的陈述转换成逻辑命题。陈述转换成逻辑命题。如果如果Alice高兴，高兴，那么那么Tom高兴；高兴；除非除非Alice 高兴，高兴， Tom 才才高兴；高兴；25三三、复合命题及联结词、复合命题及联结词 4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“” “如果如果p,则则q” 称

14、作称作p、q的的蕴涵式蕴涵式 记作记作pq，并称，并称p是蕴涵式的是蕴涵式的前件前件，q为为蕴涵式的蕴涵式的后件后件。 称作称作蕴涵联结词蕴涵联结词，或条件联结词。，或条件联结词。26三三、复合命题及联结词、复合命题及联结词pqp q001011100111p q真值表真值表善意的善意的推定推定27三三、复合命题及联结词、复合命题及联结词lp q 的逻辑关系：的逻辑关系： p是是q的充分条件；的充分条件；q 为为 p 的必要条件。的必要条件。l“如果如果则则 ” 的不同表述法有：的不同表述法有：“只只要要 就就”，“仅当仅当”，“除非除非才才 ”等。等。28三三、复合命题及联结词（例题）、复合

15、命题及联结词（例题） 例例9：将下列命题符号化：将下列命题符号化（1）只有努力才能取得成功）只有努力才能取得成功（2）只要努力过就不后悔）只要努力过就不后悔设：设： p p: :努力努力 q q: :成功成功 s：努力过：努力过 t：不后悔：不后悔qpst29三三、复合命题及联结词（例题）、复合命题及联结词（例题） 例例10：设：设 p p: :天冷，天冷，q q: :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1) 只要只要天冷，小王天冷，小王就就穿羽绒服。穿羽绒服。 (2) 因为因为天冷，天冷，所以所以小王穿羽绒服。小王穿羽绒服。 (3) 若小王不穿羽绒服，则天不冷。

16、若小王不穿羽绒服，则天不冷。 (4) 只有只有天冷，小王天冷，小王才才穿羽绒服。穿羽绒服。pqpq q pqp 30三三、复合命题及联结词（例题续）、复合命题及联结词（例题续） (5) 除非除非天冷，小王天冷，小王才才穿羽绒服。穿羽绒服。 (6) 除非除非小王穿羽绒服，小王穿羽绒服，否则否则天天不不冷。冷。 (7) 如果如果天不冷，天不冷，则则小王不穿羽绒服。小王不穿羽绒服。 (8) 小王穿羽绒服小王穿羽绒服仅当仅当天冷的时候。天冷的时候。pqqp p qqp31三三、复合命题及联结词、复合命题及联结词 小结：小结：l只有只有才、除非才、除非才、仅当表达的是才、仅当表达的是必必要要条件；条件；

17、l只要只要就、如果就、如果就（则）表达的是就（则）表达的是充充分分条件；条件；课堂练习：习题课堂练习：习题832三三、复合命题及联结词、复合命题及联结词5.等价式与等价联结词等价式与等价联结词“” “p当且仅当当且仅当q”记作记作pq 称作称作p、q的的等价式等价式 也称作也称作双条件式双条件式称作称作等价联结词等价联结词。pqp q00101010011133三三、复合命题及联结词、复合命题及联结词 需要注意以下两点：需要注意以下两点：l 等价联结词等价联结词即通常的即通常的“充分必要条充分必要条件件”;l pq为真当且仅当为真当且仅当p与与q同真或同假，也同真或同假，也称称“同或同或”。3

18、4三三、复合命题及联结词（例题）、复合命题及联结词（例题）例例1111：求下列复合命题的真值：求下列复合命题的真值(1) 2 + 2 4 当且仅当当且仅当 3 + 3 6。(2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数。(3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起。太阳从东方升起。(4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲。1010复合命题的真值取决于构成它的各原子命题复合命题的真值取决于构成它的各原子命题的真值，的真值，而与它们的内容、含义无关。而与它们的内容、含义无关。 35三三、复合命题及联结词、复合命题及联结词 等价联结词具有以下性质：等

19、价联结词具有以下性质：l满足结合律满足结合律(p q) r等价于等价于p (q r)l满足交换律满足交换律p q等价于等价于 q plp p的真值永远为的真值永远为“真真”lp p的真值永远为的真值永远为“假假”36三三、复合命题及联结词、复合命题及联结词 有关联结词优先级如下：有关联结词优先级如下：l联结词的优先顺序为：联结词的优先顺序为： , , , , ; l如果出现的联结词同级，又无括号时，如果出现的联结词同级，又无括号时，则按从左到右的顺序运算则按从左到右的顺序运算; l有括号时，应该先进行括号中的运算有括号时，应该先进行括号中的运算。37三三、复合命题及联结词、复合命题及联结词（1

20、） 与与 含义相同含义相同（2） 与与 含义相同含义相同（3） 与与 含义相同含义相同qp q)p( rqp r)qp( rqp )rq(p 由联结词的优先级可得：由联结词的优先级可得：38例题例题 例例12：利用联结词，将下述语句符号化：利用联结词，将下述语句符号化：“如果你走路时看书，那么你一定会成如果你走路时看书，那么你一定会成为近视眼为近视眼”。解：令解：令 p：你走路；：你走路； q：你看书；：你看书； r：你是近视眼。：你是近视眼。 则上述语句可以符号化为：则上述语句可以符号化为： (p q) r 39例题例题 例例13：将下列命题符号化：将下列命题符号化（1）他努力而且聪明，这不

21、是真的。）他努力而且聪明，这不是真的。 令令 p:他努力；他努力；q:他聪明他聪明)qp( （2）虽然天气很冷，老王还是来了。）虽然天气很冷，老王还是来了。 令令 p:天气很冷；天气很冷；q:老王来了老王来了qp 40例题例题（3）不经一事，不长一智）不经一事，不长一智 令令 p:经一事；经一事；q:长一智长一智qp （4）若两个圆面积相等，那么它们的半）若两个圆面积相等，那么它们的半径相等；径相等；反之亦然反之亦然。 令令 p:两个圆面积相等；两个圆面积相等； q:两个圆半径相等两个圆半径相等qp 41例题例题 例例14：符号化下列两个命题：符号化下列两个命题l如果你和他都不固执己见的话，那

22、么不如果你和他都不固执己见的话，那么不愉快的事也不会发生了。愉快的事也不会发生了。l如果你和他不都固执己见的话，那么不如果你和他不都固执己见的话，那么不愉快的事也不会发生了。愉快的事也不会发生了。r)qp( r)qp( 42例题例题 例例15：将下列命题符号化，并讨论各命：将下列命题符号化，并讨论各命题的真值。题的真值。l若今天是星期一，则明天是星期二若今天是星期一，则明天是星期二l若今天是星期一，则明天是星期三若今天是星期一，则明天是星期三43作业作业习题一：习题一：14，15441.2 命题公式及其赋值命题公式及其赋值l命题常项和命题变项命题常项和命题变项l合式公式合式公式l公式的赋值公式

23、的赋值l真值表真值表l公式的分类公式的分类45一、命题常项和命题变项一、命题常项和命题变项 命题常项命题常项：一个确定的具体的简单命题称作命一个确定的具体的简单命题称作命题常项。也称命题常元。题常项。也称命题常元。 命题变项命题变项：当：当p p所代表的只是一个抽象的命题，所代表的只是一个抽象的命题，它可以表示任意的命题，称它可以表示任意的命题，称p p为命题变项。也称为命题变项。也称命题变元。命题变元。命题变项不是命题。命题变项不是命题。p:天气很冷天气很冷46一、命题常项和命题变项一、命题常项和命题变项 当用一个特定的命题取代命题变元当用一个特定的命题取代命题变元时，才能确定其真值：真或假

24、。这种取时，才能确定其真值：真或假。这种取代称作对该命题变元代称作对该命题变元指派真值指派真值。p:太阳从东边升起太阳从东边升起p:太阳从东边升起太阳从东边升起47二、合式公式二、合式公式1.合式公式的一般化定义：合式公式的一般化定义： 将命题变项用联结词和括号按一将命题变项用联结词和括号按一定逻辑关系联结起来的定逻辑关系联结起来的符号串符号串称作称作合合式公式式公式，也称，也称命题公式命题公式，简称，简称公式公式。公式通常用字母公式通常用字母A、B、C等表示。等表示。例：例：( p q) r)( r s)48二、合式公式二、合式公式2.合式公式合式公式 的递归定义：的递归定义：(1) 单个命

25、题常项或变项单个命题常项或变项 p,q,r,是合式公式；是合式公式；(2) 若若A是合式公式，则是合式公式，则 ( A)也是合式公式；也是合式公式；(3) 若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)也是合式公式；也是合式公式；(4) 只有有限次地应用只有有限次地应用(1)(3)形成的包含命题变元、联结词形成的包含命题变元、联结词和括号的符号串才是合式公式。和括号的符号串才是合式公式。此处的此处的A、B等称等称作元语言符号，作元语言符号，代表抽象的公式代表抽象的公式49二、合式公式二、合式公式3.子公式子公式 定义定义：若：若A为合式公式，为合式公式

26、，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, ,

27、pn给给予一定的解释，使其获得一组确定的真值，这予一定的解释，使其获得一组确定的真值，这个过程称为对个过程称为对A的一个的一个赋值赋值或或解释。解释。51三、公式的赋值三、公式的赋值例例1： 公式公式B = ( p q) q 的真值表的真值表 p q p p q ( p q) ( p q) q0 00 11 01 1 110011010010000052 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010例例2：C= (p q) r 的的真值表真值表含含n个变项的公式有个变项的公式有2n个赋值。个赋值。成成假假赋赋值值53四、公式的层次四、公式的层次 公式公式( p q) r)( r s) p 0