第编数理逻辑.ppt
《第编数理逻辑.ppt》由会员分享,可在线阅读,更多相关《第编数理逻辑.ppt(84页珍藏版)》请在三一文库上搜索。
1、1,第 3 编 数 理 逻 辑,第 6 章 命 题 逻 辑,2,6.1 命题的概念与表示,命题 日常语言不确切,具有二义性需引入目标语言、公式符号。 目标语言:表达判断的一些语言的汇集。 判断:肯定、否定的思维形式。 命题:能表达判断,具有确定真值的陈述句。,3,真值:命题的判断结果称为真值。只有“真”和“假”两种,记为“T”和“F”,或“1”和“0”。,没有判断无所谓是非的句子感叹句、疑问句、祈使句不是命题。 原子命题:不能分为更简单的陈述句。 复合命题:由联结词、标点符号和原子命题复合构成的命题。 用大写字母A,B,.,P,Q,.或Ai,12等表示命题。例 P: 今天下雨。12: 今天刮风
2、。 命题标识符:表示命题的符号。,4,例:,1,0,?,(悖论),?,5,命题常量:一个命题标识符表示确定的命题。,命题变量:一个命题标识符仅表示任意命题的位置标志(无真值)。 原子变元:命题变元表示原子命题。,6,6. 2 命题联结词,复合命题原子命题+联结词 否定 定义 设P为命题,P的否定是一个新的命题,记为P。若P为T,则P为F;若P为F,则P为T。,例:P:上海是大城市。 P:上海不是大城市。 或上海是不大的城市。 一元联结词。,7,合取(并且),定义 两个命题P、Q的合取是一个复合命题,记作PQ。当且仅当P、Q同为T时,PQ为T ;在其它情况下,PQ的真值为F。,例: P: 今天下
3、雨. Q: 明天下雨. PQ: 今天下雨且明天下雨。 今天明天都下雨。 这两天都下雨。 二元联结词。,8,与自然语言不同。,P:我们去看电影。Q:房间里有十张桌子。 PQ:我们去看电影且房间里有十张桌子。 仍是新命题。 可将若干个命题联结一起。 P:高中毕业。 Q:上分数线。 R:被某大学录取。 PQR:大学生。,9,析取(或者),定义 两个命题P、Q的析取是一个复合命题,记作PQ。当且仅当P、Q同为F时,PQ为F ;在其它情况下,PQ的真值为T。,例: P: 今天下雨. Q: 今天刮风. PQ: 今天下雨或者刮风。 二元联结词。,10,日常语言中的“或者”可分“可兼或”与“不可兼或”两种:,
4、例1:今天晚上我在家看电视或去剧院看戏。 (不可兼或) 例2:他可能是100米或400米赛跑的冠军。 (可兼或) 析取是可兼或。 例3:P: 他中了大奖。Q: 他中了小奖。 PQ: 他中了大奖或者中了小奖。 (也可能两奖都中),11,不可兼析取 (排斥析取),定义 设P、Q是两个命题,复合命题P Q称为P、Q的不可兼析取。P Q的真值为T当且仅当P与Q的真值不相同;否则,P Q的真值为F。,例: P: 他坐船去大连。 Q: 他乘车去大连。 P Q: 他坐船或乘车去大连。 二元联结词。 P Q (PQ)(PQ),12,蕴含(条件),定义 两个命题P、Q的蕴含是一个复合命题,记作PQ。当且仅当P的
5、真值为T,Q的真值为F时,PQ的真值为F ;在其它情况下,PQ的真值为T。,例1: “如果某动物为哺乳动物,则它必胎生”。将命题符号化。 设P: 某动物为哺乳动物。 Q: 某动物胎生。 命题符号化:PQ。 且命题为真:PQ 1。 二元联结词。,13,例2: “如果我得到这本小说,那么我今天就读完它”。将命题符号化,并求命题的真值。,解 设P: 我得到这本小说. Q: 我今天就读完它. 命题符号化:PQ。 且命题的真值有以下四种实际情况: (1) 我得到这本小说,我今天读完它。(T) (2) 我得到这本小说,我今天没有读完。(F) (3) 我没有得到这本小说,我今天读完它。(T) (4) 我没有
6、得到这本小说,我今天没有读完。(T),14,例3: “如果雪是黑的,那么太阳从西方出”。将命题符号化,并求命题的真值。,解 设P: 雪是黑的。Q: 太阳从西方出。 命题符号化:PQ。 且命题的真值:PQ 1. ,例4: “如果雪是黑的,那么太阳从东方出”。将命题符号化,并求命题的真值。,解 设P: 雪是黑的。Q: 太阳从东方出。 命题符号化:PQ。 且命题的真值:PQ 1. ,15,PQ中P称为前件,Q称为后件。,自然语言中,若前提为假,无论结论为真或假,往往无法判断。,在条件命题中,当前提为假时,结论都为真 称“善意的推定”。,PQ“如果P那么Q” “只要P则Q” “从P推出Q” “P仅当Q
7、” “只有Q才P” “P蕴含Q”,16,等价(双条件),定义 给定两个命题P和Q,复合命题PQ称为双条件命题。当P、Q的真值相同时,PQ的真值为T ;在其它情况下,PQ的真值为F。,例1: “两个三角形全等当且仅当对应边相等”。 设P: 两个三角形全等。 Q: 三角形对应边相等。 命题符号化:PQ。 且命题为真:PQ 1。 二元联结词。,17,例2: “燕子飞回南方,春天来了”。将命题符号化,并求命题的真值。,解: 设P: 燕子飞回南方。Q: 春天来了。 命题符号化:PQ。 且命题的真值:PQ 1. ,例3: “2+2 = 4 当且仅当雪是白的”。将命题符号化,并求命题的真值。,解 设P: 2
8、+2 = 4。Q: 雪是白的。 命题符号化:PQ。 且命题的真值:PQ 1. ,18,复合命题:设 A1,A2,An是命题,用五种逻辑联结词将这n个命题联结起来,得到一个新命题,称为复合命题。,19,练习1. 设命题P,Q的真值为1,命题R,S的真值为0,试确定下面命题的真值: (PQR)(PQ)(RS);,解: (PQR)(PQ)(RS) (110)(11)(00) (10)(10) 00 01 1 ,20,6.3 命题公式的翻译与解释,用大写英文字母代表一个抽象命题, 而不代表一个具体命题, 这个抽象命题称为命题符号. 原子:命题符号称为原子.,定义 合式公式是如下定义的一个符号串 (1)
9、 原子是合式公式; (2) 若G, H是合式公式,则如下符号串(G), (GH), (GH), (GH), (GH), (G H)是合式公式; (3) 所有公式都是有限次使用(1)(2)得到的符号串。,21,命题公式:由命题变项、联结词、括号按一定规则组成的合式公式为命题公式。,例:如下符号串 (P (Q R) (Q (S) R) 就是公式。,五种逻辑联结词的优先级按如下次序递减 , , , , 故上例可写成: P(QR)Q(SR) 对公式中的每个原子赋值后,公式就有一个真值。对原子一组赋值称公式的一个解释。,22,定义 设G是公式,A1, A2, An 是出现在G中的所有原子, 指定 A1,
10、A2,An 一组真值, 则这组真值称为G的一组赋值(解释、指派), 记作I。,例:G PQR. G的真值记为 TI (G)1.,一般地G是具有n个不同原子的公式, 则G有2n 个不同的赋值。 对一个公式G, 将它在所有赋值下所取的真值列成一个表, 称为G的真值表。,6.4 真值表与等价公式,23,例: 求G P (Q R) 的真值表。,成真赋值,成假赋值,24,有时赋值 0, 0, 0 写成 P, Q, R, 0, 0, 1 写成 P, Q, R, 0, 1, 0 写成 P, Q, R, 1, 1, 1 写成 P, Q, R,25,定义:如果公式G,H在任一组赋值 I 下真值相同,则称公式G,
11、H等值,记作 G H。 “ ”不是联结词,它表示两个公式的关系。,逻辑等价,26,可见在所有赋值 I 下真值相同, PQ PQ . ,例:用真值表证明公式 PQ 和 PQ等值.,证:由真值表:,27,例:证明 P Q (PQ)(PQ)。,证:由真值表,可见在所有赋值 I 下真值相同, P Q (PQ)(PQ)。 ,28,共学了六个联结词:,全功能联结词组:任一命题公式都可用组中的联结词表示,这样的联结词组称全功能联结词组。如,. 由于PQ (PQ)(QP) ,也是全功能联结词组。 由于P Q (PQ)(PQ) ,也是全功能联结词组。 由于PQ PQ ,也是全功能联结词组。,29,并非所有联结词
12、都是必要的,公式中有些联结词可由其它联结词代替。,最小联结词组:任一命题公式可由这些联结词表示,但不能再少一个。 如 ,。 因为 PQ (PQ) 如 ,。 因为 PQ (PQ),30,常用的逻辑等价式, A B (A B) (B A) (等价式) A B A B (蕴含式) A A A, A A A (幂等律) A B B A, A B B A (交换律) A (B C) (A B) C A (B C) (A B) C (结合律) A (A B) A,A (A B) A (吸收律) A (B C) (A B) (A C) A (B C) (A B) (A C) (分配律) A 0 A, A 1
13、 A (同一律) A 0 0, A 1 1 (零律) A A 1, A A 0 (否定律) (A B) A B, (A B) A B (德摩根律),31, A A (双重否定律), A B B A (假言易位) A B A B (等价否定式) (A B)(A B) A (归谬律) A B (A B) (A B) (异或等值式),32,以上公式的证明有两种方法:(1)真值表;(2)利用公式。,例:证明吸收律A (A B) A。 证一:,A (A B) A。,33,证二:A (A B) (A 1) (A B), A (1 B) A 1 A A (A B) A。 ,34,代换规则 在等值式中某命题变
14、项用新的命题公式取代,得到新的等值式。 如由 A A A 可产生 (P Q) (P Q) (P Q) 等等。 等值演算:从某公式A推导出新公式B,且使 A B。 由基本等值式可以产生无数个不同等值式。,35,重言式、永真式:G在所有的赋值下都是真的。 矛盾式、永假式:G在所有的赋值下都是假的。 可满足式:除矛盾式以外的公式。 仅可满足式:除重言式和矛盾式以外的公式。,6.5 重言式与蕴含式,36,例: G P PQ 1, G 是重言式。, K P(PQ) K是可满足式。(仅可满足式), H P PQ 0 H 是矛盾式。,37,重言蕴含式的三种等价定义,定义1:设G,H是两个公式,如果对任意赋值
15、I,都有TI(G) TI(H),则称G重言蕴含H,记作G H. 定义2:设G,H是两个公式,对任意赋值I,如果G为真,必有H为真,则称G重言蕴含H,记作G H. 定义3:设G,H是两个公式,如果(GH)是恒真公式,则称G重言蕴含H,记作G H.,例1: 证P PG. 证1:,由定义1得证.,证2: 若P 1, 则PG 1G 1由定义2得证.,证3: P(PG) P(PG) PPG 1G 1 由定义3得证.,38,(1) 证明两个公式等值,化简公式; (2) 判别公式的类型; (3) 解决实际问题。,等值式的推演能够解三类问题:,39,例1 证明 (1) (PQ)(PQ) P (2) P(QR)
16、 (PQ)R,证: (1) (PQ)(PQ) P(QQ) P1 P (PQ)(PQ) P (2) P(QR) P(QR) PQR (PQ)R (PQ)R P(QR) (PQ)R ,40,例2 化简 (AB)(BA)C.,解: BA BA AB AB。 (AB) (BA)C (AB) (AB)C 1C (由等价的定义:当P、Q的真值相 同时,PQ的真值为 1 ) C. ,41,例3 判别下列公式的类型: (1) Q(PQ)P).,解:Q(PQ)P) Q(PQ)P) PQ(PQ) 1. 公式Q(PQ)P)为重言式。,42,(2) (PP)(QQ)R).,解:(PP)(QQ)R) 1(0R) 10
17、0. 公式(PP)(QQ)R)为矛盾式。 (3) (PQ)P. 解:(PQ)P (PQ)P P 当P1, 公式 0;当P0, 公式 1。 公式(PQ)P是可满足式。 ,43,对偶式,对偶式:在一个不含联结词和的公式里, 将换成, 换成, 1 换成0, 0换成1, 得一新公式, 称为原公式的对偶式. 将一个等值式的等号两端换成其对偶式, 得到一新等值式, 称为原等值式的对偶式. 对偶性质: 如果一个等值式是成立的, 其对偶等值式也成立.,6.6 范式,44,公式的形式千变万化:G G (G H) G G G 1等等,是否有标准形式?,定义:有限个命题变项或其否定构成的析取式称为简单析取式。有限个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数理逻辑
链接地址:https://www.31doc.com/p-2541853.html