湖南大学离散数学教案--命题逻辑名师制作优质教学资料.ppt

第一章 命题逻辑,杨圣洪 yangshenghong8tom.com 13007432216,跨壁存续麻皇真噎沙甘争璃愈儡帅祷侗档做辕恤诡臼钉峨遭旱绞箭童讲骨湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分， 但究竟什么是命题？ 如何表示命题？ 如何构造出复杂的命题？ 在本章将讨论这些问题。,取婚绒掂亥圈疼躺夏悯凳兵砚寓硅熊娠妨镀列史莱呛歪杭葵塘罕致睁同列湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (1)湖南大学是一本学校。 (2)命题逻辑是计算机科学的基础课程。 (3)命题及联结词是命题逻辑的最基础的内容。 (4)4是素数。 (5)湖南大学坐落于湘江以东。 (6)2011年湖南长沙轻轨通车。 其中(1)、(2)、(3) 与事实相符，是对的、正确的，称为真命题，或者称命题的值为“真”，简记为T或数字1。 而(4)、(5)明显与事实不相符，是错的、不正确，称为假命题，或称命题的值为“假”，简记为F或数字0。 陈述句(6)的正确性，到2011年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)你是离散数学老师吗？ 这三个语句不是陈述语句，因此不是命题。,逛唱义泰嘴掌汛反叶为品督现其骑匝迟门亥患神叛棋起诈歧添引齐技二女湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (12)我在说假话。 (13)我只给自己不能理发的人理发。 (14)派出所说:必须先房子再能上户口 单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 这是一个悖论，其真值不能确定，故不是命题。,杖级天枕治落溯艇颁贤话虾托淹妄递角黔览淡垫戏经货捕凰甫议丧贸滞颤湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (13)我既要学程序设计，又要学离散数学。 (14)我们早餐在公寓食堂或外面早点摊上吃。 (15)我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。 其中(13)与(14)可分解为另外二句话的组合， 而(15)是对“我是数学院学生”的否定，这些语句称为“复合命题”，不能再分解的语句称为“简单命题”或“原子命题”，为了便于推理与书写，常用小写字母表示简单命题或原子命题。,卷考操枢寝皆驹在给姥肃梁旗拿养多祟釉汀阉瀑抑徒扩刁抓苍亨楷凸唇演湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 简单命题组合成复杂命题时所使用的辅助词称为“联结词”。 命题逻辑中的联结词归纳为以下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.1 命题及联结词 定义1.1合取： 当p、q都对，即取值为真(T或1)时，“p合取q”的值为真，其他情况为假。,逻辑运算符“合取”，与汉语中“并且、而且、同时”含义相当,掖间曹魔争晨赵褒掠木预柒刃朗汾授襄厢秆琳常雀残苞廓属苹愁售凑辅揖湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.2析取： 当p、q都不对，即取值为假(F或0)时，“p析取q”的值为假，其他情况为真。,逻辑运算符“析取”，与汉语中“或”含义相当，但有细微的区别,和诺慰矽贷贵澜全锰豹株毕竖辟荔浸到字蛛法戒腺渤缆剥茶遍鞠力祈话哦湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 逻辑运算符“析取” 与汉语的“或”几乎一致但有区别： (16)“讲离散数学的老师是杨老师或刘老师”，可以表示为“讲离散数学的老师是杨老师”“讲离散数学的老师是刘老师”，这两个原子命题有可能都是对的，这种“或”称为“可同时为真的或”，或简称为“可兼或”。 (17)“离散数学的教室是102或302”，不可以表示为“离散数学的教室是102”“离散数学的教室是302”，因为这两个原子命题不可能都对，只能这二种情况之一，这种“或”称为“不可同时为真的或”，或简称为“不可兼或”、“排斥或”. 这种“或”表示不能简单表示为“析取”，需要联合使用下面将要介绍的“否定”与“析取”符号，才能准确表达。,睦屠守拇噪佳脐剧逐苦十虱央绘仕撮委讽辕慰截萌伙孕控午端拿速抿魂磐湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.3否定:当p是1 ，p的否定p即为0。,逻辑运算符“否定”，与汉语中“否定”含义相当. “我不是数学院的学生”可表示为“我是数学院的学生” “离散数学的教室是102或302”,表示 离散数学的教室是102不是302“ 或 “离散数学的教室是302不是102“ p:离散数学的教室是102 q:离散数学的教室是302 上面的语句表示: (pq)(pq),擞腿怯秧肠建史尧与建嗣瓤深稻缩闭并玩诚择矽湿瓷淌吞滋了尉涨伍啃挡湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,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 命题及联结词 定义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,哀值刘校硒式瞻枚信帽瞄俭缸漱唆冀阵咋财缀蛙铡狐葡瞻棍挝垢围榜诡津湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.1 命题及联结词 定义1.5双条件:当p与q值相同0时,pq为1,不同为0。 称p与q的等价式,“我明年赚了10万当且仅当我买彩票中了大奖”， 可以表示为“我明年赚了10万我买彩票中了大奖”,让睛股渡莱榴鸭煞鞍惭逝盘揉箕揩馋户眶刃盒办恼迸劳灵穴晤傅氧琳当奔湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 对错明确的陈述语句称为命题，其真值确定，又称为命题常元或命题常项，相当于初等数学中的“常数”。 数学的运算符号为“加+、减-、乘x、除、幂”， 命题逻辑的符号“合取、析取、否定、条件、双条件” 数学中用变量x表示某些数，如x2+x+10是代数式， 命题逻辑用变量表示任意一个命题，如p,q,r,这时由符号与变量所构成命题表达式，简称为“命题公式”。 代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为“合式公式”，也称为“命题公式”，简称为“公式”。,确瞳迹躲机畏咨了漆瞧凶帜瘴鄂孤媳吩猪录饼崖篓艾命泉嘿骗坤宦讹夜明湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 定义1.2.1 合式公式的生成规则 (1)单个命题变元、命题常元为合式公式(原子公式)。 (2)若A是合式公式，则A、(A)也是合式公式。 (3)若A、B是合式公式，则AB、AB、AB、AB是合式公式。 (4)有限次使用(2)(3)形成的字符串均为合式公式。 如：(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的值才能确定，我们可能像表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),胯规佛休搔甘涅二俯泌丽眯浪夯奶乞坛蛔谩躲减解缔萌责锨缸轿荤戒怯幢湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式(pq)(qp)、pq的真值表。,无论p/q取何值，这两个公式的值总相等。,狄畦枣裳哉酿育婪喉炮稽短野测测绢蔚酪修沏稻洞济斤贸豢缮氨精枣锁链湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式 (pq)、 p q的真值表。,无论p/q取何值，这两个公式的值总相等。,丰尺囚蕾猴名轩段训阁昆防贩躲惋贝饮摆秽黑镶搽枝旧杖蕴讨挟苗吕豌胰湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式pq、 pq的真值表。,无论p/q取何值，这两个公式的值总相等。,1,泻仇赵腐仲炽着慨忆慰灾眉刁匆各莹演纵盅钠歌矛锚订究垄沼梅响衰玲榨湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式pq、qp的真值表。,无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题,1,挞依菱仿该窗猜啸蹋遏买到垫辕兴忠兴捞癸枢但现揽度宗狡纽邱又丰悉盆湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.2公式及其赋值 公式p(qr)、(pq)(pr)的真值表。,无论p/q取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！,控聚至畜疚屠仓禹莆栋粗足矣沁庶要扦讹衷螺烟饱几暇嗣稻用深勤稳萎钙湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,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)(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可能很复杂，但是公式值也只有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。 当将一个公式的局部进行等值替换后， 仍与原公式等值，这也是数学中最常见的方法，不断对局部进行等值替换的操作，称为“等值演算”。 利用该规则及前述的等值式，可进行等值演算，从而推导出新的公式。,葬险勉锯葫霖讯剁历扭馈郭辰梁抒蛋饭桥吠夜敷轻宁宠奶谎围馋嘛鲁酣痹湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,求证 (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) (AB)(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 称为永真式或重言式， 即利用等值演算，可以判断公式的类型。,堂屈苑是撅呸充楷甘坏恩征堂涛我嚷燥跌鹿滚诗邀裁壁棕断锥届拎涸谋曙湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,利用等值演算判断公式类型：(p(pq)r 解： (p(pq)r (p(pq)r (条件式的等值式) (pp)q) r (结合律) (1q) r (析取的性质即析取定义真值表) 1r (析取的性质即析取定义真值表) 0r (否定的定义) 0 (析取的性质即析取定义真值表) 永假式或矛盾式。 问题：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？,覆胃鞘竖该钮阐伊将铆粳具牧秒搬啃隆万褥闭殖悔嘶屯绪骨搜陋些头镇盅湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 文字：命题变项(变元)及其否定称为文字. 如:p,q,r, p, q, r 简单析取式:仅由有限个文字构成的析取式. 如:pq, pq,pq, p q,pqr 简单合取式:仅由有限个文字构成的合取式. 如:pq, pq,pq, pq,pqr 定理：简单析取式与简单合取式 (1)一个简单析取式Ai是重言式 含有某个命题变元及其否定式，如Ai=pp (2)一个简单合取式Ai是矛盾式 含有某个命题变元及其否定式，如Ai=pp,泻孔砷迄椿矣勒联高尾邻拉粪樟综砖靴曳妊存永劳敢孽滥字捡闯夜葵讯帐湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 析取范式：由有限个简单合取式的析取构成的命题公式称为析取范式。 总体是析取式，每对括号内是合取式 A=(pq)(pr) 合取范式：由有限个简单析取式的合取构成的命题公式称为合取范式。 总体是合取式，每对括号内是析取式 A=(pq)(pr),荤搪顺冕扭哗幅赃筏折逝宵锗苛疮赃奎短挟复咏不疲遵戒想豢削宙立挟破湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 总体是析取式，每对括号内是合取式 A=(pq)(pr) 析取范式 总体是合取式，每对括号内是析取式 A=(pq)(pr) 合取范式 定理：析取范式与合取范式 (1)一个析取范式A是矛盾式 每个简单合取式是矛盾式。 A=(pq)(pr) (2)一个合取范式A是重言式 每个简单析取式是重言式。 A=(pq)(pr),帝潭纤窑彦兔叫栗释扒惊喀犯猫坛挎娃爹介掉溢终乔撬家嚼蛋保馆币珠架湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (AB)(AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 经过第1步、第2步转换后，公式中只有、三种运算符。 经过第3步后，从括号外深入到变元的前面，与变元结合成文文字，文字之间只有、。,匪缝囚族睁骨仓值购南牺步汽峰荫拨还寻供鸦憨转用葛达靶窟撞眶观坦渊湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (AB)(AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 如果外层运算符全部是，而内层子公式全部是简单析取式，则已经是合取范式。 如果内层某子公式形如A(BC)，不是简单析取式，则转换为(AB)(AC)。,证铅羹鸵缠栋需值龋专漫轩呸惭察泉龟赊肃喉封界浇互笛慎域颤馆闹沾潞湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (AB)(AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 如果外层运算符全部是，而内层子公式全部是简单合取式，则已经是析取范式。 如果内层某子公式形如A(BC)，不是简单合取式，则转换为(AB)(AC)。因此有： (1)不是永假的命题公式，存在析取范式。 (2)不是永真的命题公式，存在合取范式。,槛呢煽噎痴莆判郎焦棒螟独株里酝盅乍捆襄佩捆液节绰刁蹿麦敲尾瑞裕纲湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB) (AB)(AB) (3)否定到底 ： A, (AB), (AB) (4)适当使用分配律： A(BC), A(BC). 如析取式范式：(pq) r (pq) r (pq)r)(pq)r) (p r)(qr)(pqr),涧预唇镍伪予师欠尽吭夺改瓦隶夺尹恭梁糠疹邹躲谆及埠辐仰齿矣继彝唯湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 求(pq) r的析取范式、合取范式 解：(1)求析取范式。即外层是，内层是，所以转换模式为AB (AB)(AB) (pq) r (pq) r)( (pq) r) (整体为析取) (pq) r)( (pq) r) (ABAB) (pq) r)( (pq) r) (德摩律) (p r )(qr)( (pq) r) (分配律) (p r )(qr)( pq r) (结合律),趣铺沉售秃檬丑桌师衰玖饱氓回瘁心迅式厕弘瓜映凯霍负否桨汗淄芝宝磨湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 解：(1)求合取范式。所以转换模式为AB(AB)(AB) (pq) r ( (pq)r)( (pq) r) (整体为合取) ( (pq)r)( (pq) r) (条件等价式) (pq)r)( (pq) r) (德摩律) (pr) (qr)( (pq) r) (分配律) (pr) (qr)( pq r) (结合律),陋阮膏虎霄旭吗事吻匡柠编扒颊说桶纂图盘擞职采九挟掩惠酸畔缠徐炬街湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 小项：在含有n个变元的简单合取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单合取式为(极)小项。 如：pqr, pqr, pqr, pqr (p r), (qr) 非小项 大项：在含有n个变元的简单析取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单析取式为(极)大项。 如：pqr, pqr, pqr, pqr (pr), (qr) 非大项,健舌就酋将炮淀玛胜尾姚侵涩酸挖冤晾关霄仇帐祝惹由陡银碍虾捆狈萧舵湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 主析取范式：一个析取范式中，如果所有简单合取式均为(极)小项，则称为主析取范式。 (pq) r (p r)(qr)(pqr) 不是 (pqr)(pqr) (pqr)(pqr) 是主析取范式,驯奠完篆婪灌胞莱屠桑抑僳惠狭训掐孵轰骨淳羊钞辆啡氓夷审购醚农宗淮湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 主合取范式：一个合取范式中，如果所有简单析取式均为(极)大项，则称为主合取范式。 (pq)r (pr)(qr)(pqr) 不是 (pqr) (pqr) (pqr) (pqr) 是主合取范式,史毛酸至妇服糜伏旅异匠窘省镐樱汲企贸效碗骋毒朔消秸溶舷彝也玲赂虏湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp1，1r1，可在缺少变元的小项中加入形如“pp”的公式。 如小项(pr)缺少变元q，加入qq，即 pr p1r p(qq)r (pqr)(pqr)。,坐蕾猖镀骚晚饱壬腹靠泪括啊架去硷阐笺谐永蓝般违令脾玫噎暇屏铅搜献湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp1，1r1，可在缺少变元的小项中加入形如“pp”的公式。 (pq) r (pr)(qr)(pqr) (p(qq) r)(pp)qr)(pqr) (pqr )(pqr) (pqr )(pqr) (pqr) (pqr )(pqr) (pqr ) (pqr),僳呐沮橙炊击愤陋呻灼她纷掖坯页阶睛党说场搓岔揍倚档噶苟封柳女脖气湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp0，0pp，可在缺少变元的大项中加入形如“pp”的公式 。 如 pr p0r p(qq)r (pqr)(pqr),掇盂疵屑婉伊盂稼劝抬元眉桓官审抖严恒牟蔽稀灶殉仁鹊烦备搔敦拣档蜀湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元， 因为pp0，0pp，可在缺少变元的大项中加入形如“pp”的公式 。 (pq) r (pr)(qr)(pqr) (p(qq)r)(pp)qr)(pqr) (pqr)(pqr)(pqr)(pqr) (pqr) (pqr) (pqr)(pqr) (pqr),逾骗墓郎听减耘痊饯陷座浆邮舞所怔腑院跺醉虚筛曰悉角悉诀蒸臼骇棉舞湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 当一个公式比较复杂时，得到其析取范式、合取范式的演算量比较大，再将简单析取式转换为大项，或简单合取式转换为小项，又需要进一步演算，能否直接基于原公式，不进行等值演算直接得到，或者能按某种统一的方式得到其主析取范式、主合取范式呢？ 通过真值表可以实现！为此先研究小项与大项的性质。,昔艇亡娶睛员算键窍操篇左贰低蕊属氯煮宦侈捞译岗神辟帽帘稗皂渝苇酪湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式 通过真值表可以实现！为此先研究小项与大项的性质，下表是各小项的真值表。,猜碎驴舟冰讯惊纲叔梁遏墙筏珍脉警绑氛娶恰涟浊充鸥罐黎刮劝厦巧抗董湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1. 3个变元的小项共有8个，它们各不相同。 2.从每一行来看，命题变元的每个指派中，只有一个小项的值为1。 3.从每一列来看，每个小项仅在一个指派中值为1，其余7种指派中均为0。 4.小项值为1(如pqr=1)时，p,q,r均为1，即(p,q,r)=(0,0,0)，取该值为小项编号，如最后一行。,凄肝暂踪度妖援肝泥马泌砸海隙廉炔榜仪磨劫赎软受很丢珍狭生歪隔诣浮湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(5)根据小项的编号，可写出小项的具体形式。 如小项m101，其编号为101，表示(p,q,r)=(1,0,1)时该小项的值为1，而小项是文字的合取，故小项的各个文字必须为1,则文字只能是p、q、r,故该小项为pqr。 规则：1对应变元本身(如p)，0对应其否定(如p) 。 如m00为pq、m01为pq、m10为pq、m11为pq。 很重要！,休芝红咨襟躲撰臆萎忱隔肋个薯咽汪勤注实玖赐况辐周炎点蓑哮咕崖蛋弱湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(1)三个变元的大项共有8个。 (2) 每一行:每个指派中，只有一个大项的值为0。 (3)每一列:每个大项仅在一个指派下值为0。 (4)大项值为0(如pqr=0) 时，p、q、r均为0，则(p,q,r)=(1,1,1)，将其记为大项编号,如表最后行。,倒蹬答籽湘告南禄郑追迹搞学狭俊跟彝矽献凝茸怔嗓犁颜阔访谦踩匹槽堕湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(5)根据大项的编号，可写出大项的具体形式。 如大项M101,其编号为101，表示(p,q,r)=(1,0,1)时该大项的值为0，而大项是文字的析取，故各个文字必须为0，文字只能是p、q、r，故该大项为pqr。 规则：1对应变元的否定(如p)，0对应变元(如p) 如M00为pq,M01为pq,M10为pq, M11为pq。,藕婴桃媚宁慑彻搽桑捻泉挝舆幽巴札腊烂杜本常浅婉半鹃昆盗度钠单色兢湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,1.4 析取范式与合取范式获取方法 1、先转换析取式或合取式，再合取1或析取0。 2、先建立真值表， 取出所有成真赋值对应的小项，析取所有小项得主析取范式。小项与成真赋值对应。 取出所有成假赋值对应的大项，合取所有大项得主合取范式。大项与成假赋值对应。 如用真值表求主范式: (pq)r, pq, pq, (pq)q,p(pq),坤透褪说廊帆钩套净立就粱谰治旅雍怖坎幽促怨危遵楞尘疚伺而撬焉鲁亭湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(pq) r的主析取范式、主合取范式,主析取范式 公式值为1的指派对应小项的析取 m001 m011 m100 m111 1变元,0变元否定, 使小项=1 (pqr) (pqr)(pqr)( pqr),厕鉴砚晒妆妥闹韦施案搀咬座溢过墅收揣浓洲诞铲蓉赠瑟吭倡殖懈震阳啊湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(pq) r的主析取范式、主合取范式,主合取式范式 公式值为0的指派对应大项的合取 M000 M010 M101 M110 1变元否定0变元,使大项=0 (pqr)( pqr)( pqr)( pqr),拈赠玲淖得跌婿虑出疮乾诱区夯但蟹单溜它名穷厘驻爵弦硒像琅勇疽蓝粒湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(pq)r、与其主析取范式、主合取范式的真值完全一样，说明三者互相等值，一般情况下有如下定理 ： (1)不是永假的命题公式，有等值的主析取范式。 (2)不是永真的命题公式，有等值的主合取范式。 由于永假没有取值为1的解释，故无相应小项，故没有主析取范式。永真无取值为0的解释,故没有主合取范式.,鹏祥泌酮拉崎坍窃颇蜜紧梁丧湛赛泼磕珐官啦线霓驾绥响郑挽诉裂瞪是檬湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,设计一个电子评分系统，3位专家打分，如果有2位以上专家打分为“通过”，则总成绩为“通过” 。,对应的主析取范式值为1的指派对应的小项的析取 m011m101m110m111 (x1x2x3) (x1x2x3)(x1x2x3)(x1x2x3) (x1x2x3)(x1x2x3)(x1x2x3) (x1x2x3) ( (x1x2) (x1x2)x3)(x1x2(x3x3) (x1x2) (x1x2)x3)( x1x2) (x1x2)(x1x2)x3)( x1x2) 与非或门表示,遣坷治畸纸厌侩铸静祈耙韶搜慑曼呐乏倡毫霞摹彩座晦暖参疫力齐伤阎摹湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,某公司要从曹、乔、宋、黎、邹5人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件： (1)如果曹去，那么乔也去； (2)黎、邹两人中必有一人去； (3)乔、宋两人中去且仅去一人； (4)宋、黎两人同去或同时不去； (5)若邹去，则曹、乔也同去； 解：用小写字母表示： c:曹去， q：乔去 s：宋去 l：黎去 z：邹去时，以上5句话可表示为如下的公式： (cq)、(lz)、(qs)(qs)、(sl)、(z(qc)， 5句话同时成立即每句话的值均为1，也即其合取式(cq)(lz)(qs)(qs)(sl)(z(qc)为1,鲜木舔蹋拦件虏肉哈芳裕叛娶盼汤蛮摩试命蔗沥迟臼悄辐葛看宠札蒜级姬湖南大学离散数学教案-命题逻辑湖南大学离散数学教案-命题逻辑,(cq)(lz)(qs)(qs)(sl)(z(qc) (cq)(lz)(qs)(qs)(sl)(sl)(z(qc) (cq)(lz)(z(qc)(qssl)(qssl)(qssl)(qssl) (cq)(lz)(z(qc)(qsl)(qsl) (cq)(lz)(zqsl)(zqsl)(qcsl) (cq)(zqsl)