湖南大学离散数学教案--命题逻辑名师制作优质教学资料.ppt
《湖南大学离散数学教案--命题逻辑名师制作优质教学资料.ppt》由会员分享,可在线阅读,更多相关《湖南大学离散数学教案--命题逻辑名师制作优质教学资料.ppt(84页珍藏版)》请在三一文库上搜索。
1、第一章 命题逻辑,杨圣洪 13007432216,跨壁存续麻皇真噎沙甘争璃愈儡帅祷侗档做辕恤诡臼钉峨遭旱绞箭童讲骨湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,引言 逻辑学是推理的基础,在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支,也是数学的分支,它用数学方法研究推理规律,它采用符号的方法来描述和处理思维形式、思维过程和思维规律,它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分, 但究竟什么是命题? 如何表示命题? 如何构造出复杂的命题? 在本章将讨论这些问题。,取婚绒掂亥圈疼躺夏悯凳兵
2、砚寓硅熊娠妨镀列史莱呛歪杭葵塘罕致睁同列湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如: (1)湖南大学是一本学校。 (2)命题逻辑是计算机科学的基础课程。 (3)命题及联结词是命题逻辑的最基础的内容。 (4)4是素数。 (5)湖南大学坐落于湘江以东。 (6)2011年湖南长沙轻轨通车。 其中(1)、(2)、(3) 与事实相符,是对的、正确的,称为真命题,或者称命题的值为“真”,简记为T或数字1。 而(4)、(5)明显与事实不相符,是错的、不正确,称为假命题,或称命题的值为“假”,简记为F或数字0。 陈述句(6)的正确性,到2
3、011年12月时能确定的,若届时开通了则它是对的、为真命题,否为假命题。,过莉撩荒正辊邦街侄矽筐占脾侩卵我绪众羊乎剥板疵懂懊昭鞠磁箔磺滋匀湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如: (7) x与y之和为100,其中x为整数,y为整数 (8)1加1等于10 (7)的对错不确定的。当x为50、y为50时是对的,当x为51、y为52时是错的。 (8)的对错是不确定的,为二进制时正确,当为八进制、十进制时是错的,因此这两个陈述句不是命题。 (9)岳麓山的红叶真美呀! (10)动作快点! (11)你是离散数学老师吗? 这三个语句不
4、是陈述语句,因此不是命题。,逛唱义泰嘴掌汛反叶为品督现其骑匝迟门亥患神叛棋起诈歧添引齐技二女湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如: (12)我在说假话。 (13)我只给自己不能理发的人理发。 (14)派出所说:必须先房子再能上户口 单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 这是一个悖论,其真值不能确定,故不是命题。,杖级天枕治落溯艇颁贤话虾托淹妄递角黔览淡垫戏经货捕凰甫议丧贸滞颤湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如: (
5、13)我既要学程序设计,又要学离散数学。 (14)我们早餐在公寓食堂或外面早点摊上吃。 (15)我不是数学院的学生 这三个陈述句都与事实相符,是对的,是真命题,其值为真(T/1)。 其中(13)与(14)可分解为另外二句话的组合, 而(15)是对“我是数学院学生”的否定,这些语句称为“复合命题”,不能再分解的语句称为“简单命题”或“原子命题”,为了便于推理与书写,常用小写字母表示简单命题或原子命题。,卷考操枢寝皆驹在给姥肃梁旗拿养多祟釉汀阉瀑抑徒扩刁抓苍亨楷凸唇演湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 简单命题组合成复杂命题时所使用的辅助词称为“联结
6、词”。 命题逻辑中的联结词归纳为以下5种。 合取:C语言中 & and 并且 析取:C语言中 | or 或 否定:C语言中 ! not 非,不是,否定 条件式:C语言中 if () 如果那么 如p则q 双条件式: 如p则q且如q则p,当且仅当,棉矣事掖滁诈序欧壳更斋拳频钝褐焦蔚钵留陵瓣蜘潜已葡俞瞅膛卞兹犯昭湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.1合取: 当p、q都对,即取值为真(T或1)时,“p合取q”的值为真.,柔钾贤闲兹职队拍睫标诉扶尼变轧氰焉脉液酞四誊佑瓜焚吃腐宣们倡俩驱湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1
7、.1 命题及联结词 定义1.1合取: 当p、q都对,即取值为真(T或1)时,“p合取q”的值为真,其他情况为假。,逻辑运算符“合取”,与汉语中“并且、而且、同时”含义相当,掖间曹魔争晨赵褒掠木预柒刃朗汾授襄厢秆琳常雀残苞廓属苹愁售凑辅揖湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.2析取: 当p、q都不对,即取值为假(F或0)时,“p析取q”的值为假,其他情况为真。,逻辑运算符“析取”,与汉语中“或”含义相当,但有细微的区别,和诺慰矽贷贵澜全锰豹株毕竖辟荔浸到字蛛法戒腺渤缆剥茶遍鞠力祈话哦湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑
8、,1.1 命题及联结词 逻辑运算符“析取” 与汉语的“或”几乎一致但有区别: (16)“讲离散数学的老师是杨老师或刘老师”,可以表示为“讲离散数学的老师是杨老师”“讲离散数学的老师是刘老师”,这两个原子命题有可能都是对的,这种“或”称为“可同时为真的或”,或简称为“可兼或”。 (17)“离散数学的教室是102或302”,不可以表示为“离散数学的教室是102”“离散数学的教室是302”,因为这两个原子命题不可能都对,只能这二种情况之一,这种“或”称为“不可同时为真的或”,或简称为“不可兼或”、“排斥或”. 这种“或”表示不能简单表示为“析取”,需要联合使用下面将要介绍的“否定”与“析取”符号,才
9、能准确表达。,睦屠守拇噪佳脐剧逐苦十虱央绘仕撮委讽辕慰截萌伙孕控午端拿速抿魂磐湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.3否定:当p是1 ,p的否定p即为0。,逻辑运算符“否定”,与汉语中“否定”含义相当. “我不是数学院的学生”可表示为“我是数学院的学生” “离散数学的教室是102或302”,表示 离散数学的教室是102不是302“ 或 “离散数学的教室是302不是102“ p:离散数学的教室是102 q:离散数学的教室是302 上面的语句表示: (pq)(pq),擞腿怯秧肠建史尧与建嗣瓤深稻缩闭并玩诚择矽湿瓷淌吞滋了尉涨伍啃挡湖南大学离散数
10、学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.4条件:当p是1 ,q是0时,pq为0,即10为0,其他情况为1。,逻辑运算符“如果那么”,它是用单个运算符表示一个复合语句。 如老妈说:“如果期终考了年级前10名,那么奖励1000元”。 p:期终考了年级前10名 q:奖励1000元 则上面的语句表示为pq。 当p为1即“期终考了年级前10”, 且q为0即“没有奖励1000元” 这时老妈的话是假话空话, 故pq为0,标败矛耘游艰搜傅粹拼杂蹿股朽坍赂形部括哲刨鳃耽热吩殊征晃是喀挤舒湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义
11、1.4条件式(蕴含式):当p是1 ,q是0时,pq为0,即10为0,其他情况为1。 p为前件,q为后件,(1)当p为1即“我期终考了年级前10” q为0即“我老妈没有奖励1000元” 这时老妈的话为假,即pq为0 (2)当p为1即“我期终考了年级前10” q为1即“我老妈奖励1000元” 这时妈妈的话就对了,即pq为1 (3)至于p为0即“我期终考了年级不是前10”时,无论q为1或为0,即无论“我老妈奖励1000元“或不奖励,都不能说老妈的话是假的,故可善意的认为pq为1均为1,哀值刘校硒式瞻枚信帽瞄俭缸漱唆冀阵咋财缀蛙铡狐葡瞻棍挝垢围榜诡津湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-
12、命题逻辑,1.1 命题及联结词 定义1.5双条件:当p与q值相同0时,pq为1,不同为0。 称p与q的等价式,“我明年赚了10万当且仅当我买彩票中了大奖”, 可以表示为“我明年赚了10万我买彩票中了大奖”,让睛股渡莱榴鸭煞鞍惭逝盘揉箕揩馋户眶刃盒办恼迸劳灵穴晤傅氧琳当奔湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 对错明确的陈述语句称为命题,其真值确定,又称为命题常元或命题常项,相当于初等数学中的“常数”。 数学的运算符号为“加+、减-、乘x、除、幂”, 命题逻辑的符号“合取、析取、否定、条件、双条件” 数学中用变量x表示某些数,如x2+x+10是代数式,
13、命题逻辑用变量表示任意一个命题,如p,q,r,这时由符号与变量所构成命题表达式,简称为“命题公式”。 代数式的书写有规律,命题公式也有规律与约束,称满足这些规则的公式为“合式公式”,也称为“命题公式”,简称为“公式”。,确瞳迹躲机畏咨了漆瞧凶帜瘴鄂孤媳吩猪录饼崖篓艾命泉嘿骗坤宦讹夜明湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 定义1.2.1 合式公式的生成规则 (1)单个命题变元、命题常元为合式公式(原子公式)。 (2)若A是合式公式,则A、(A)也是合式公式。 (3)若A、B是合式公式,则AB、AB、AB、AB是合式公式。 (4)有限次使用(2)(3)形
14、成的字符串均为合式公式。 如:(p1)q是合式公式。 因为p、1是合公式,则(p1)是合式公式,而r是合式公式,故(p1)q是合式公式。 (p1)r不是合式公式。 因为p、1是合公式,则(p1)是合式公式,而r是合式公式,但(p1) r不是合法公式。,敦彩蜜赘授铺打绢撞滑巢趣跌奴闯地以匀播摸逮助曲杖卓艳致腰注荚丑邓湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 对于代数式x2+y+10,当x与y的值不确定时,该代数式的值是不确定的。 对于公式 (p1)q,由于p与q值不确定时,公式(p1)q的值不确定,因而不是命题。 只有当p与q的值确定后,公式(p1)q的值
15、才能确定,我们可能像表1.2到表1.5一样,给出公式在各种情况下的取值,即得到这个公式的真值表。,p与q每一种取值称为p、q的一种解释,命钦争矽碳蔼馆虏矮搓就妊贴隶旺臃倚纶久娄泅锗藉土骗琵温尝鲸选你疯湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式(pq)、pq的真值表如下表。,真值表的构造方法: (1)命题变元的取值从全0开始,依次加1,直到全1,当有n个变元时,则共有2n种不同的取值情况。 (2)分步骤计算公式的值 (3)见黑板上写,成真赋值:如pq为(0,0),(0,1),(1,1) 成假赋值:如pq为(1,0),胯规佛休搔甘涅二俯泌丽眯浪夯奶乞坛蛔
16、谩躲减解缔萌责锨缸轿荤戒怯幢湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式(pq)(qp)、pq的真值表。,无论p/q取何值,这两个公式的值总相等。,狄畦枣裳哉酿育婪喉炮稽短野测测绢蔚酪修沏稻洞济斤贸豢缮氨精枣锁链湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式 (pq)、 p q的真值表。,无论p/q取何值,这两个公式的值总相等。,丰尺囚蕾猴名轩段训阁昆防贩躲惋贝饮摆秽黑镶搽枝旧杖蕴讨挟苗吕豌胰湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式pq、 pq的真值表。,无论p/q取
17、何值,这两个公式的值总相等。,1,泻仇赵腐仲炽着慨忆慰灾眉刁匆各莹演纵盅钠歌矛锚订究垄沼梅响衰玲榨湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式pq、qp的真值表。,无论p/q取何值,这两个公式的值总相等,若前者称为原命题,后者为逆否命题,1,挞依菱仿该窗猜啸蹋遏买到垫辕兴忠兴捞癸枢但现揽度宗狡纽邱又丰悉盆湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式p(qr)、(pq)(pr)的真值表。,无论p/q取何值,这两个公式的值,与前面各例不同,此表是将运算结果写在联结词的下方!,控聚至畜疚屠仓禹莆栋粗足矣沁庶要扦讹衷螺
18、烟饱几暇嗣稻用深勤稳萎钙湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.3 等值式 一、复习 由前节可知: pq与pq、 qp pq与(pq)(qp) 、(pq)(pq) (pq)与p q p(qr)、(pq)(pr) 的真值表完全一样,称为等值。 定义1.3.1 设A、B是两个合法的命题公式,无论其中的命题变元取何值,这两个公式的总相等,称为两个公式等值,记为AB,绒危骏癣把捷批临秃缀颜复苛姑悉意管吝瞄攒莫悸薄惠栋讼儿纽琳丧形裹湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,由定义及前节习题有: (1)pqpqqp 条件式的等值式 (2)pq(pq)(qp)(
19、pq)(pq) 双条件 (3)pp 双重否定律 (4)ppppp 幂等律 (5)pq qp,pq qp 交换律 (6) p(qr) (pq) r 结合律 p(qr) (pq) r (7) p(qr) (pq)(pr) 分配律 p(qr) (pq)(pr) (8) p(pr) p 吸收律(多吃少) p(pr) p (9) (pq) pq 德摩律 (pq) pq 将以上等值式中的变元换成合式公式仍等值!,绍栗拈袋韭捂候杜操汾灸沤衬锅刁肖铱唐桥灯层惦鹅姓扛状卉裙唱挟挪淹湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,如:pq pq 则有 AB AB 尽管A/B可能很复杂,但是公式值也只
20、有0、1二种可能,公式A/B的组合只有0/0,0/1,1/0,1/1四种,如下表所示,显然有 AB AB,沛峪甸相玛妻圭祷凄启淤投趟枷讫因余股阵蕾陆托阐绷钟岂声曲综糕录次湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,置换规则:当将公式A中的子公式B换成C得到公式D后,若BC,那么AD。 因为A、D除了“A中B所在之处、D中C所在之处”外,其他地方均相同,而不同之处的B与C等值,所以公式A、公式D的真值表应该完全他相同,故AD。 当将一个公式的局部进行等值替换后, 仍与原公式等值,这也是数学中最常见的方法,不断对局部进行等值替换的操作,称为“等值演算”。 利用该规则及前述的等值式
21、,可进行等值演算,从而推导出新的公式。,葬险勉锯葫霖讯剁历扭馈郭辰梁抒蛋饭桥吠夜敷轻宁宠奶谎围馋嘛鲁酣痹湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,求证 (pq)r(pr) (qr) (pq)r (pq)r 条件式的等值式 (pq) r 利用德摩律 r (pq) 交换律 (rp)( rq) 分配律 (p r)( qr) 交换律 (pr) (qr) 条件式等值式,坯宾杏塔娥唱倘谎怨刊捌青妒巧裴靛腻忙蚁诱嚷捡沪拱悼糯胸爆侥兔展挛湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,等值演算的基本套路 (1)转换 : ABAB (2)恰当转换 :AB(AB) (AB) (A
22、B)(AB) 确保公式只保留 联结词 (3)否定到底 : A, (AB), (AB) (4)恰当使用分配律、吸收律。,找阿魄侄椎愁矮赚强贺骂初仁减宰履搪鲁内等饯技帧狠债侥峪蔼莲揩厂计湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,利用等值演算,判断公式的类型 (pq)p)q (pq)p)q (pq)p)q (条件式的等值式) (pq)p)q (条件式的等值式) ( (pq)p)q (德摩律) (pq)p)q (德摩律) (pq)(pq) (结合律) (pq) (pq) (逆用德摩律) AA (A= (pq) 1 称为永真式或重言式, 即利用等值演算,可以判断公式的类型。,堂屈苑是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 湖南大学 离散 数学教案 命题逻辑 名师 制作 优质 教学 资料
链接地址:https://www.31doc.com/p-1059806.html