离散数学第一章命题逻辑.ppt
《离散数学第一章命题逻辑.ppt》由会员分享,可在线阅读,更多相关《离散数学第一章命题逻辑.ppt(51页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第一章第一章 命题逻辑命题逻辑 Proposition LogicProposition Logic1.1 命题及其表示法命题及其表示法1.2 联结词联结词1.3 命题公式与翻译命题公式与翻译1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式1.5 等价与蕴含等价与蕴含1.6 推理理论推理理论2/20/20231chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.1 命题及其表示法命题及其表示法1、命题、命题命题命题非真即假的陈述句。非真即假的陈述句。命题的真值命题的真值对,成立,则真值为真,对,成立,则真值为真,T
2、,1 错,不成立,则真值为假,错,不成立,则真值为假,F,0 断言断言是一陈述语句。一个命题命题是一个或真或假而不能两者都是的断言。如果命题是真,我们说它的真值真值为真真;如果命题是假,我们说它的真值真值是假假。2/20/20232chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例1】判定下列各语句是否为命题:判定下列各语句是否为命题:(a)巴黎在法国。巴黎在法国。(b)煤是白色的。煤是白色的。(c)3+2=5(d)别的星球上有生物。别的星球上有生物。(e)全体立正。全体立正。(f)明天是否开大会?明天是否开大会?(g)天
3、气多好啊!天气多好啊!(h)我正在说谎。我正在说谎。(i)如果天气好,那么我去散步。如果天气好,那么我去散步。(j)x3(是)(是)(是)(是)(是)(是)(是)(是)(否,祈使句)(否,祈使句)(否,疑问句)(否,疑问句)(否,感叹句)(否,感叹句)(否(否,悖论)悖论)(是(是,复合命题)复合命题)(否,不能确定真值)(否,不能确定真值)1.1 1.1 命题及其表示法命题及其表示法命题及其表示法命题及其表示法2/20/20233chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、命题的表示、命题的表示命题变元命题变元常用常
4、用P、Q、R、S等大写字母或加下标的大等大写字母或加下标的大写字母写字母P1,Q2,R10,表示来表示一个命题,称为命题变表示来表示一个命题,称为命题变元。元。如:如:P:巴黎在法国。巴黎在法国。Q:煤是白色的。煤是白色的。1.1 1.1 命题及其表示法命题及其表示法命题及其表示法命题及其表示法2/20/20234chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 3、命题相关概念、命题相关概念简单命题(原子命题)简单命题(原子命题)不能再分解的命题。不能再分解的命题。复合命题复合命题由若干个简单命题复合而成的命题。由若干个简单命
5、题复合而成的命题。真值表真值表把组成复合命题的各命题变元的真值的所有把组成复合命题的各命题变元的真值的所有组合及其相对应的复合命题的真值列成表,称为真值表。组合及其相对应的复合命题的真值列成表,称为真值表。1.1 命题及其表示法命题及其表示法2/20/20235chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例2】求公式求公式(P Q)P的真值表。的真值表。解:解:分以下步求得分以下步求得:(1)写出公式写出公式P的真值表的真值表;(2)写出公式写出公式P Q的真值表的真值表;(3)根据根据(1)和和(2),写出公式写出公
6、式(P Q)P的真值表。的真值表。为清楚起见为清楚起见,我们将这步列在一个表内我们将这步列在一个表内,见下表。见下表。1.1 命题及其表示法命题及其表示法2/20/20236chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例3】求公式求公式(PR)(QR)的真值表。的真值表。解:解:公式含有个命题变元公式含有个命题变元P、Q、R,真值表有真值表有3=8行。其真值表如下表行。其真值表如下表 所示:所示:1.1 命题及其表示法命题及其表示法2/20/20237chapter1PropositionProposition Log
7、icLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.2 1.2 联结词联结词联结词联结词 命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复复合合命命题题(Compositional Proposition)。例如:P:明天下雪,Q:明天下雨是两个命题,利用联结词“不”,“并且”,“或”等可构成新命题:“明天不下雪”;“明天下雪并且下雨”;“明天下雪或下雨”等。2/20/20238chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.2 联结词联结词即:“非P”;“P并且Q”;“P或Q”等。在代数式x+3 中,x,3 叫
8、运算对象,+叫运算符,x+3 表示运算结果。在命题演算中,联联结结词词就是命题演算中的运算符,叫逻逻辑辑运运算算符符或叫逻逻辑辑联联结结词词。常用的有以下 5 个。2/20/20239chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1、否定、否定 P是是P的否定,读作的否定,读作“非非P”,“P的否定的否定”。0110p如:如:P:成都是中国的首都。成都是中国的首都。P:成都不是中国的首都。:成都不是中国的首都。否定与汉语中的否定与汉语中的“非非”、“不是不是”、“否定否定”是一致的。是一致的。1.2 联结词联结词2/20/2
9、02310chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、合取、合取 P Q是是P和和Q的合取的合取,读做读做“P与与Q”或或“P并且并且Q”。如:如:P:王华的成绩很好。王华的成绩很好。Q:王华的品德很好。王华的品德很好。P Q:王华的成绩很好并且品德很好。王华的成绩很好并且品德很好。合取与汉语中的合取与汉语中的“和和”、“与与”、“并且并且”是一致的。是一致的。P QP Q0 00 11 01 10001 1.2 联结词联结词2/20/202311chapter1PropositionProposition Logic
10、Logic命题逻辑命题逻辑命题逻辑命题逻辑 3、析取、析取 P Q是是P和和Q的析取的析取,读做读做“P或或Q”。如:如:P:小王喜欢唱歌。小王喜欢唱歌。Q:小王喜欢跳舞小王喜欢跳舞。P Q:小王喜欢唱歌或喜欢跳舞小王喜欢唱歌或喜欢跳舞。从真值表可知从真值表可知P Q为真为真,当且仅当当且仅当P或或Q至少有一为真。至少有一为真。P QP Q0 00 11 01 10111 1.2 联结词联结词2/20/202312chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 “或”字常见的含义有两种:一种是“可兼或可兼或”,如上例中的或,它
11、不排除小王既喜欢唱歌又喜欢跳舞这种情况。一种是“排斥或排斥或”(异或)(异或),例如“人固有一死,或重于泰山,或轻于鸿毛”中的“或”,它表示非此即彼,不可兼得。运算符运算符 表示可兼或表示可兼或,排斥或以后用另一符号表达。排斥或以后用另一符号表达。如:(1)小李明天出差去上海或去广州。(2)刘昕这次考试可能是全班第一也可能是全班第二。这两例表示的均是排斥或,即两种情况不能同时出现,这时便不能仅用析取词表示。1.2 联结词联结词2/20/202313chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 4、条件、条件 PQ,读做读做“
12、如果如果P,那么那么Q”或或“P则则Q”。运算对象运算对象P叫做前提叫做前提,假设或前件假设或前件,而而Q叫做结论或后件。叫做结论或后件。P QP Q0 00 11 01 11101 1.2 联结词联结词如:如:P:雪是黑的。雪是黑的。Q:太阳从东方升起太阳从东方升起。P Q:如果雪是黑的,则太阳从东方升起如果雪是黑的,则太阳从东方升起。命题命题PQ是假是假,当且仅当当且仅当P是真而是真而Q是假。是假。2/20/202314chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 条件与汉语中条件与汉语中“如果如果,就,就”相类似,但有
13、所区别相类似,但有所区别:(1)自然语言中,自然语言中,“如果如果P则则Q”,往往,往往P和和Q有一定的因果有一定的因果关系,而条件复合命题关系,而条件复合命题PQ中中 P和和Q 可以完全不相关。可以完全不相关。(2)自然语言中,自然语言中,“如果如果P则则Q”,当,当P为为0、Q为为1时,整个时,整个句子真值难以确定;而条件复合命题句子真值难以确定;而条件复合命题PQ中,当中,当P为为0时,时,复合命题的真值为复合命题的真值为1。P则则Q的逻辑含义的逻辑含义:P是是Q的充分条件的充分条件,Q是是P的必要条件。的必要条件。所以所以,“如果如果P则则Q”,“只要只要P则则Q”,只有只有Q才才P”
14、,“仅当仅当Q则则P”都可符号化为都可符号化为PQ 的形式。的形式。1.2 联结词联结词2/20/202315chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 如:小李对小王说:如:小李对小王说:“如果天不下雨,我就来找你如果天不下雨,我就来找你”。天没下雨,小李去找了小王。天没下雨,小李去找了小王。天没下雨,小李没去找小王。天没下雨,小李没去找小王。天下雨了,小李去找了小王。天下雨了,小李去找了小王。天下雨了,小李没去找小王。天下雨了,小李没去找小王。1.2 联结词联结词【例【例4】电灯不亮是电灯坏或电路有毛病。】电灯不亮是电
15、灯坏或电路有毛病。解:设解:设P电灯不亮,电灯不亮,Q电灯坏,电灯坏,R电路有毛病。电路有毛病。上述语句应表示为上述语句应表示为:(Q R)P2/20/202316chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 5、双条件、双条件 P Q,读做读做“P当且仅当当且仅当Q”。如:如:P:两个三角形全等。两个三角形全等。Q:两个三角形的对应边相等两个三角形的对应边相等。P Q:两个三角形全等当且仅当其对应边相等两个三角形全等当且仅当其对应边相等。P当且仅当当且仅当Q的逻辑含义的逻辑含义:P和和Q互为充要条件互为充要条件。P QP
16、Q0 00 11 01 11001 1.2 联结词联结词2/20/202317chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 6、联结词的优先次序、联结词的优先次序联结词的优先级:联结词的优先级:,,括号优先。,括号优先。如:如:(P Q)R 可写成可写成:P QR (P Q)R 可写成:可写成:P QR (P Q)R)(R P)Q)可写成:可写成:(P Q R)R P Q 为方便起见,公式最外层的括号可省略。有时为了为方便起见,公式最外层的括号可省略。有时为了看起来清楚醒目看起来清楚醒目,也可保留某些原可省去的括号。也可保留
17、某些原可省去的括号。1.2 联结词联结词2/20/202318chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 单单个个命命题题变变元元和和命命题题常常元元叫叫原原子子公公式式。由以下形成规则生成的公式叫命题公式命题公式(简称公式简称公式):(1)单个原子公式单个原子公式A、B是命题公式。是命题公式。(2)如如果果A和和B是是命命题题公公式式,则则(A),(A B),(A B),(AB),(AB)是命题公式。是命题公式。(3)只只有有有有限限步步使使用用(1)和和(2)所所组组成成的的包包含含命命题题变变元元、联结词以及成对的括
18、号组成的符号串才是命题公式。联结词以及成对的括号组成的符号串才是命题公式。这种定义叫归纳定义,也叫递归定义。由这种定义产生的公式也叫合合式式公公式式(Well-Formed Formulas),简简写为写为wff。1.3 命题公式命题公式2/20/202319chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例5】判断下列表达式是否为合式公式判断下列表达式是否为合式公式:p(p q)(p q)r)(p(q r)(pq)(q r)(pq)r)(p q)r)s)(p q)r)s(是)(是)(是)(是)(否)(否)(否)(否)(否
19、)(否)(是)(是)(是)(是)1.3 命题公式命题公式2/20/202320chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例6】将下列自然语言形式化将下列自然语言形式化:(a)如果天不下雨并且不刮风,我就去书店。如果天不下雨并且不刮风,我就去书店。解解:设:设P:今天天下雨,:今天天下雨,Q:今天天刮风,:今天天刮风,R:我去书店。:我去书店。则原命题符号化为:则原命题符号化为:(P Q)R(b)小王边走边唱。小王边走边唱。解:设解:设p:小王走路,:小王走路,q:小王唱歌。:小王唱歌。则原命题符号化为:则原命题符号化
20、为:p q(c)除非除非a能被能被2整除,否则整除,否则a不能被不能被4整除。整除。解:设解:设p:a能被能被2整除,整除,q:a能被能被4整除。整除。则原命题符号化为:则原命题符号化为:p q 或或 q p1.3 命题公式命题公式2/20/202321chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 (d)此时,小刚要么在学习,要么在玩游戏。此时,小刚要么在学习,要么在玩游戏。解:设解:设p:小刚在学习,:小刚在学习,q:小刚在玩游戏。:小刚在玩游戏。则原命题符号化为:则原命题符号化为:(p q)(p q)或或 (p q)(p
21、 q)(e)如果天不下雨,我们去打篮球,除非班上有会。如果天不下雨,我们去打篮球,除非班上有会。解:设解:设p:今天天下雨,:今天天下雨,q:我们去打篮球,:我们去打篮球,r:今天班上:今天班上有会。有会。则原命题符号化为:则原命题符号化为:r (p q)1.3 命题公式命题公式2/20/202322chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1、重言式(重言式(Tautology)重言式重言式(永真式永真式)真值恒为真值恒为1的公式。如:的公式。如:P P【例例7】判断判断(P P(P Q))是否为重言式。)是否为重言式
22、。P QP QP(P Q)P P(P Q)0 00 11 01 10 0 010 0 111 1 11(P P(P Q))为重言式。)为重言式。1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式2/20/202323chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、矛盾式(矛盾式(Contradiction)矛盾式(永假式)矛盾式(永假式)真值恒为真值恒为0的公式。如:的公式。如:P P【例例8】判断判断(P Q)P是否为矛盾式。是否为矛盾式。P QP Q(P Q)P0 00 11 01 10 0 010 0 00
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第一章 命题逻辑
限制150内