离散数学第3章命题逻辑.ppt
《离散数学第3章命题逻辑.ppt》由会员分享,可在线阅读,更多相关《离散数学第3章命题逻辑.ppt(192页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第3章章 命题逻辑命题逻辑3.1 命题的有关概念命题的有关概念本讲内容什么是命题什么是命题1命题的真值命题的真值2原子命题与复合命题原子命题与复合命题3逻辑常量与逻辑变量逻辑常量与逻辑变量4命题之间的命题之间的还有些什么关系还有些什么关系?认知关系认知关系:我知道我知道偏好关系偏好关系:他喜欢他喜欢逻辑关系Chapter 3 命题逻辑命题逻辑逻辑学是研究思维形式及思维规律尤其是逻辑学是研究思维形式及思维规律尤其是推理的学科推理的学科.逻辑推理无处不在逻辑推理无处不在.亚里士多德亚里士多德(Aristotle,公元前公元前384公元前公元前322)是形式逻辑的创始人是形式逻辑的创始人.数学数学
2、,物理学物理学,化学化学,天文学天文学,地学地学,生物学生物学,逻辑学逻辑学.(MBA,MPA,招聘等招聘等)莱布尼茨莱布尼茨(G.Leibniz,1647-1716)是是数理逻数理逻辑辑的创始人的创始人.传统的数理逻辑传统的数理逻辑(内容包括逻辑演算、公理内容包括逻辑演算、公理化集合论、模型论、递归论和证明论化集合论、模型论、递归论和证明论).应用逻辑应用逻辑,如多值逻辑、模态逻辑、如多值逻辑、模态逻辑、归纳逻归纳逻辑辑、时序逻辑、动态逻辑、模糊逻辑、非、时序逻辑、动态逻辑、模糊逻辑、非单调逻辑、缺省逻辑、数字逻辑、电路逻单调逻辑、缺省逻辑、数字逻辑、电路逻辑、算法逻辑及程序逻辑等辑、算法逻
3、辑及程序逻辑等,这些都与计算这些都与计算机科学密切相关机科学密切相关.计算机如何进行逻辑思维的计算机如何进行逻辑思维的计算思维培计算思维培养养.命题逻辑与谓词逻辑是数理逻辑的基础部命题逻辑与谓词逻辑是数理逻辑的基础部分分.本章学习命题逻辑本章学习命题逻辑.命题逻辑的研究对象是命题命题逻辑的研究对象是命题.3.1 命题的有关概念命题的有关概念计算机的计算过程就是推理过程计算机的计算过程就是推理过程,而每一步而每一步推理离不开判断推理离不开判断,判断的对象就是命题判断的对象就是命题.1.什么是命题什么是命题?命题是能判断出真假的语句命题是能判断出真假的语句.从三个方面去理解:从三个方面去理解:(1
4、)命题必须是一个完整的句子命题必须是一个完整的句子,包括用数包括用数学式子如代表的语句学式子如代表的语句.(2)所给语句具有真假意义所给语句具有真假意义,即有是否符合即有是否符合客观实际或是否客观实际或是否合理合理之分之分.一般来说一般来说,只有只有陈述句才具有真假意义陈述句才具有真假意义,祈使句、疑问句和祈使句、疑问句和感叹句不具有真假意义感叹句不具有真假意义;(3)能判断出真假能判断出真假.要是将来某时候能判断要是将来某时候能判断出真假也行出真假也行.例例3-1 判断下列语句是否是命题判断下列语句是否是命题.(1)辽宁舰是中国的第一首航空母舰辽宁舰是中国的第一首航空母舰.(2)我喜欢智能手
5、机和平板电脑我喜欢智能手机和平板电脑.(3)x 3.(4)立正!立正!(5)这朵花真漂亮!这朵花真漂亮!(6)你要我的手机号码是想给我充话费你要我的手机号码是想给我充话费?(7)火星上有生物火星上有生物.(美国美国Discovery号号:火星上有水火星上有水?2012年着陆火星的年着陆火星的Curiosity号号,1+1=2)(8)我说的都是假话我说的都是假话.(9)小王和小李是同学小王和小李是同学.(10)你只有刻苦学习你只有刻苦学习,才能取得好成绩才能取得好成绩.歌德巴赫猜想歌德巴赫猜想:至今已至今已200多年多年.(1)1+1=2:大于大于4 4的偶数是两个奇素数之的偶数是两个奇素数之和
6、和.6=3+3;8=3+5;10=3+7=5+5;12=5+7;(2)任何大于任何大于7 7的奇数是三个奇素数之和的奇数是三个奇素数之和.9=3+3+3;11=3+3+5;13=3+3+7;15=3+5+7;陈景润陈景润(1966)的的“陈式定理陈式定理”:1+2=3,任何充分任何充分大的偶数是一个素数与两个素数乘积之和大的偶数是一个素数与两个素数乘积之和.2007年年11月月15日重庆商报日重庆商报,大坪大坪67岁罗仁德破解岁罗仁德破解.1935年出生的河北的何宝起自称破解年出生的河北的何宝起自称破解,奔波奔波8年年无人理无人理.2.命题的真值命题的真值(truth)命题的真值就是命题的逻辑
7、取值命题的真值就是命题的逻辑取值.经典逻辑值只有两个经典逻辑值只有两个:1和和0,它们是表示事物状态它们是表示事物状态的两个量的两个量.若一个命题是真命题若一个命题是真命题,其真值为其真值为1;若一若一个命题是假命题个命题是假命题,其真值为其真值为0.实际上在数理逻辑中实际上在数理逻辑中,更多时候逻辑真是用更多时候逻辑真是用T(True)或或t,逻辑假用逻辑假用F(False)或或f表示的表示的.3.原子命题与复合命题原子命题与复合命题若一个命题不包含有更小的命题若一个命题不包含有更小的命题,则称其为原子则称其为原子命题命题(atom)当时认为原子最小当时认为原子最小?或简单命题或简单命题,否
8、否则称为复合命题则称为复合命题(compound proposition).原子原子命题是命题逻辑研究的基本单位命题是命题逻辑研究的基本单位,区分原子命题区分原子命题在后面命题的符号化时是很重要的在后面命题的符号化时是很重要的.通常用小写英文字母通常用小写英文字母p,q,r,s,或带下标或带下标p1,p2,p3,等来表示原子命题等来表示原子命题,如用如用p:2+3=5,q:今天今天我们上课我们上课.4.逻辑常量与逻辑变量逻辑常量与逻辑变量把把1和和0称为逻辑常量称为逻辑常量(logical constant).在逻辑表达式中出现的在逻辑表达式中出现的p,q,r或或p1,p2,p3 等等称为命题
9、变元称为命题变元(proposition variable)或逻或逻辑变量辑变量(logical variable).命题变元可以代命题变元可以代表任意命题表任意命题,从取值的角度看从取值的角度看,命题变元既命题变元既可以取可以取1又可以取又可以取0.课堂练习课堂练习 习题习题3.1 1,2.小结小结命题的概念命题的概念命题的真值命题的真值原子命题与复合命题原子命题与复合命题逻辑常量与逻辑变量逻辑常量与逻辑变量第第3章章 命题逻辑命题逻辑3.2 逻辑联结词逻辑联结词本讲内容 p,p q,p q12p q,p q,p q3p q,pq,pq3.2 逻辑联结词逻辑联结词逻辑联结词就是逻辑运算逻辑联
10、结词就是逻辑运算:复合命题是由原子命题构成的复合命题是由原子命题构成的,它需要联结词它需要联结词.给定了原子命题给定了原子命题,使用逻辑联结词可以构成复使用逻辑联结词可以构成复合命题合命题.逻辑联结词类似于自然语言中的连词逻辑联结词类似于自然语言中的连词.1.否定否定(not)联结词联结词 :p p:2+3=5,p:2+3 5.p是数理逻辑中的是数理逻辑中的标准符号标准符号,也可记为也可记为p,C语言语言!p,在计算机其他课程中用在计算机其他课程中用 ,对应对应于于逻辑逻辑门电路中的门电路中的“非门非门”.pp10012.合取合取(and)联结词联结词 :p q p:小李能歌小李能歌,q:小李
11、善舞小李善舞.p q:小李能歌且善舞小李能歌且善舞.合取合取“”相当于相当于“并且并且”,“和和”,“与与”,“以及以及”等等.pqp q111100010000Remark(1)“小王和小李是同学小王和小李是同学”中的中的“和和”没有没有合取之意合取之意.(2)在数理逻辑中在数理逻辑中,合取联结词可以将合取联结词可以将任意任意两个命题联结起来以构造出新的命题两个命题联结起来以构造出新的命题,如用如用p:2+3=5,q:今天上课今天上课,则则p q:2+3=5且今天上课且今天上课.下面要介绍的其他联结词都是下面要介绍的其他联结词都是这样理解这样理解.(3)p:小李结婚了小李结婚了q:小李有小孩
12、了小李有小孩了p q,q p?p q:p&q,p&q,p q=pq,对应于对应于“与与门门”.3.析取析取(or)联结词联结词 :p q p:这学期我选修人工智能课程这学期我选修人工智能课程,q:这学期我选修模式识别课程这学期我选修模式识别课程.p q:这学期我选修人工智能课程或者模式这学期我选修人工智能课程或者模式识别课程识别课程.析取析取“”相当于相当于“或者或者”.p|q,p|q,p+q(“或门或门”).pqp q111101011000本讲内容 p,p q,p q12p q,p q,p q3p q,pq,pq4.异或异或(exclusive or,XOR)联结词联结词 :p q自然语言
13、中的自然语言中的“或或”:(1)“可兼或可兼或”(inclusive or),它表示两者它表示两者可同时为真可同时为真,用析取表示即可用析取表示即可.(2)“不可兼或不可兼或”,它表示两者不能同时为它表示两者不能同时为真真,换句话说换句话说,两者同时为真是假命题两者同时为真是假命题.这这就需要异或联结词就需要异或联结词.p:明天去深圳的飞机是上午八点起飞明天去深圳的飞机是上午八点起飞,q:明天去深圳的飞机是上午八点半起飞明天去深圳的飞机是上午八点半起飞.p q:明天去深圳的飞机是上午八点或上午明天去深圳的飞机是上午八点或上午八点半起飞八点半起飞.本学期张三本学期张三或或李四当选为班长李四当选为
14、班长.今天晚上在寝室上自习或去今天晚上在寝室上自习或去电影院电影院看看3D电电影影.(都在寝室都在寝室?7:30?)与异或联结词对应的门电路为与异或联结词对应的门电路为“异或门异或门”.一般来说一般来说,只要不是非常明显的不可兼就使只要不是非常明显的不可兼就使用用.pqp q1101010110005.条件条件(conditional)联结词联结词:p q p:我有时间我有时间,q:我去看望我的父母我去看望我的父母.pq:如果我有时间如果我有时间,那么我去看望我的父母那么我去看望我的父母.“”相当于相当于“如果如果那么那么”,“若若则则”,等等.p q 可读作可读作“(若若)p则则q”.pqp
15、 q111100011001蕴涵联结词也可以称为蕴涵联结词也可以称为条件联结词条件联结词.在在p q中中,p称为前件称为前件,q称为后件称为后件.当当 p=1,q=1时时p q=1;当当 p=1,q=0时时p q=0,这是比较好理解的两种情形这是比较好理解的两种情形.规定的合理性见下面的例子规定的合理性见下面的例子.(1)如果太阳从西边出来如果太阳从西边出来,那么那么2+3=5.(2)如果太阳从西边出来如果太阳从西边出来,那么那么2+3=4.实际上实际上,在根据子集的定义证明在根据子集的定义证明1.1节的定节的定理理:对于任意集合对于任意集合A,有有 A时时,就要用到就要用到上述实质蕴涵的定义
16、上述实质蕴涵的定义.同样同样,在理解关系的在理解关系的自反、反自反、对称、反对称及传递性质自反、反自反、对称、反对称及传递性质时时,也要用到上述实质蕴涵的定义也要用到上述实质蕴涵的定义.当然当然,在现代逻辑中在现代逻辑中,对蕴涵的不同理解会对蕴涵的不同理解会得到不同的逻辑系统得到不同的逻辑系统,如由如由严格蕴涵严格蕴涵得出模得出模态逻辑系统态逻辑系统.6.双条件双条件(biconditional)联结词联结词:p q p:四边形是平行四边形四边形是平行四边形,q:四边形的对边四边形的对边平行平行.p q:四边形是平行四边形当且仅当四边四边形是平行四边形当且仅当四边形的对边平行形的对边平行.p
17、q:可读作可读作“p当且仅当当且仅当q”.双条件双条件联结词联结词“”相当于自然语言中的相当于自然语言中的“当且仅当当且仅当”、“充分必要条件充分必要条件”,其英文为其英文为if and only if,缩写为缩写为iff.“p当且仅当当且仅当q”有两层含义:有两层含义:(1)“p当当q”是是指指q p.(2)“p仅当仅当q”是指是指p q.正因为正因为此此,等价联结词又可以称为等价联结词又可以称为双蕴涵联结词双蕴涵联结词或或双条件联结词双条件联结词.数字逻辑等课程数字逻辑等课程 的的“同同”,并用并用“”表表示示.pqp q111100010001本讲内容 p,p q,p q12p q,p
18、q,p q3p q,pq,pq7.与非与非(NOT AND)联结词联结词 :p q在数字逻辑以及计算机组成原理中在数字逻辑以及计算机组成原理中“”没没有专用的运算符号有专用的运算符号,“p与非与非q”直接记为直接记为 ,对应的门电路为对应的门电路为“与非门与非门”.8.或或非非(NOT OR)联结词联结词 :p q在数字逻辑以及计算机组成原理中在数字逻辑以及计算机组成原理中“”没没有专用的运算符号有专用的运算符号,“p或非或非q”直接记为直接记为 ,对应的门电路为对应的门电路为“或非门或非门”.9.条件否定条件否定(NOT-IF-THEN)联结词联结词 :读作读作“p条件否定条件否定q”,其中
19、其中n表示否定表示否定not.“p条件否定条件否定q”可直接记为可直接记为上面介绍了上面介绍了1个一元逻辑运算、个一元逻辑运算、8个二元逻个二元逻辑运算辑运算.后面将证明:不同的一元逻辑运算后面将证明:不同的一元逻辑运算和二元逻辑运算共和二元逻辑运算共9个个.要求要求 理解记忆上述理解记忆上述9 9个个,特别是最前面的特别是最前面的6 6个联结词的运算表个联结词的运算表.思考思考 如何定义三元逻辑运算如何定义三元逻辑运算?课堂练习课堂练习 习题习题3.2 16.小结小结 p,p q,p qp q,pq,pqp q,p q,p q第第3章章 命题逻辑命题逻辑3.3 命题公式及其真值表命题公式及其
20、真值表本讲内容命题公式的定义命题公式的定义1命题的符号化命题的符号化2命题公式的真值表命题公式的真值表3命题公式的类型命题公式的类型43.3 命题公式及其真值表命题公式及其真值表有了前面的两节内容有了前面的两节内容,就可以得到命题逻辑就可以得到命题逻辑的符号体系的符号体系.1.命题公式命题公式(proposition formula)的定义的定义逻辑函数逻辑函数(logical function)逻辑表达式逻辑表达式(logical expression),其中的常其中的常量是逻辑常量量是逻辑常量1和和0,其中的变元是命题变元其中的变元是命题变元或逻辑变量或逻辑变量.命题公式是由命题常量、命题
21、变元、逻辑命题公式是由命题常量、命题变元、逻辑联结词、左圆括号及右圆括号构成的有意联结词、左圆括号及右圆括号构成的有意义义(well-formed)的符号串的符号串,其严格定义需其严格定义需借助于递归定义方式给出借助于递归定义方式给出.Definition (1)1,0,p,q,r,(2)A (A)(3)A,B (4)有限次应用有限次应用(1)(2)(3)所得到的符号串所得到的符号串是仅有的命题公式是仅有的命题公式.命题公式命题公式可称为可称为合式公式合式公式(Well-Formed Formula,WFF)或简称为或简称为公式公式,其全称为其全称为命命题合式公式题合式公式,是书写正确、含义清
22、楚的表达是书写正确、含义清楚的表达式或者说符号串式或者说符号串.借助于借助于函数函数给命题公式下定义给命题公式下定义.可以省略可以省略括号的约定括号的约定:(1)最外层的括号可以省略最外层的括号可以省略.在形成最终的命题公式时在形成最终的命题公式时,所有的中间过程所有的中间过程得到的命题公式得到的命题公式,包含其本身包含其本身,都称为该命都称为该命题公式的题公式的子公式子公式.(2)9个联结词运算的优先顺序依次为个联结词运算的优先顺序依次为:符合本约定的有些括号符合本约定的有些括号可以可以不写不写.如命题公如命题公式式 Remark 这种规定不是唯一的这种规定不是唯一的.(3)同级运算从左至右
23、依次进行同级运算从左至右依次进行.如如 实际上实际上,在对命题进行符号化时在对命题进行符号化时,只要书写只要书写正确的逻辑函数都是命题公式正确的逻辑函数都是命题公式.2.命题的符号化命题的符号化命题的符号化就是使用符号命题的符号化就是使用符号命题变元、命题变元、逻辑联结词和括号将所给出的命题表示出逻辑联结词和括号将所给出的命题表示出来来.符号体系来源于实际问题符号体系来源于实际问题.给出进一步学习逻辑演算系统的语义解释时的给出进一步学习逻辑演算系统的语义解释时的一种标准模型一种标准模型.命题的符号化的步骤命题的符号化的步骤:Step 1 找出所给命题的所有原子命题找出所给命题的所有原子命题,并
24、用并用小写英文字母或带下标表示;小写英文字母或带下标表示;Step 2 确定应使用的联结词确定应使用的联结词,进而将原命题进而将原命题用符号表示出来用符号表示出来.例例3-7 将下列命题符号化将下列命题符号化.(1)天气很好或很热天气很好或很热.(2)如果张三和李四都不去如果张三和李四都不去,那么我就去那么我就去.(3)仅当你走仅当你走,我留下我留下.(4)我今天进城我今天进城,除非天下雨除非天下雨.(5)你只有刻苦学习你只有刻苦学习,才能取得好成绩才能取得好成绩.Solution(1)用用p:天气很好天气很好,q:天气很热天气很热“天气很好或很热天气很好或很热”可符号化为可符号化为(2)用用
25、p:张三去张三去,q:李四去李四去,r:我去我去.则原命题可符号化为则原命题可符号化为(3)用用p:你走你走,q:我留下我留下则则“仅当仅当你走你走,我留下我留下”可符号化为可符号化为(4)p:我今天进城我今天进城,q:天下雨天下雨.除非除非=如果不如果不.(5)p:你刻苦学习你刻苦学习,q:你取得好成绩你取得好成绩.只有只有p,才才q?本讲内容命题公式的定义命题公式的定义1命题的符号化命题的符号化2命题公式的真值表命题公式的真值表3命题公式的类型命题公式的类型43.命题公式的真值表命题公式的真值表命题公式的真值表就是命题公式的取值情命题公式的真值表就是命题公式的取值情况表况表.若对中出现的每
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 命题逻辑
限制150内