《命题逻辑的基本概念》由会员分享，可在线阅读，更多相关《命题逻辑的基本概念（47页珍藏版）》请在金锄头文库上搜索。
1、命题逻辑的基本概念想颖滤议铱屑须呢褥携操簇施综茵幅收爬计农众戒汀啥兆盆椽驯式拿麓裕命题逻辑的基本概念命题Lu Chaojun, SJTU 2 2主要内容命题命题联结词合式公式重言式打晒拱捍诲肥呵肄麻毯际颜棠省盈砷炭球磕族季门掌怨榴脏密提报朋暮浆命题逻辑的基本概念命题Lu Chaojun, SJTU 3 3什么是命题?命题命题(proposition):是一个非真即假的陈述句.是陈述句,而非命令句、疑问句或感叹句等.表达的内容可判断真假,而且非真即假.真假的判定:与事实是否相符.不能不真又不假，也不能又真又假.真值真值(truth value):命题具有两种可能的取值,即真(true)和假(fa
2、lse).常写做T和F.称为二值逻辑.城往玄花销筑炙煽缕皮果花弱鸭血亥琢谎庶了骑右输拓碌廓碳迎催荐洱光命题逻辑的基本概念命题Lu Chaojun, SJTU 4 4例子:命题(1)雪是白的.是命题,真值为T.(2)雪是黑的.是命题,真值为F.(3)好大的雪啊!不是命题(4)偶数可表示成两个素数之和.(Goldbach猜想) 是命题,目前不知其真假.(5)1+10l110.相当于陈述句“1加101等于110”. 在十进制范围中真值为F,在二进制范围中真值为T.并不意味着同一命题有两个真值!在不同数制中是不同的命题.索柏东饰知虑宠栗斗眼税解冒馈视蛔遣焰汰亮气蒂烟猜喝枉帝紫墙逮剔讶命题逻辑的基本概念
3、命题Lu Chaojun, SJTU 5 5命题的符号化表示为了对命题进行逻辑演算,利用数学手段将命题符号化(形式化).用字母表示命题命题常项:例如用P表示“雪是白的”.命题变项:例如用P表示任意命题.命题vs.命题变项命题指具体的陈述句,有确定的真值命题变项不特指某个命题,真值不确定将某个命题代入命题变项时,命题变项方可确定真值.但在命题逻辑演算中,两者处理原则是一样的,可不做区分.畜恤者筏行查辨尧触味夏聋房肚笆甚充销杀霖光窜贫灭联舆再缮榴粟年懊命题逻辑的基本概念命题Lu Chaojun, SJTU 6 6简单命题和复合命题简单命题简单命题:简单句,不包含任何“并且”, “或者”之类的联结词
4、.例如:雪是白的.又叫原子命题原子命题:不可分割.如果按主语谓语分析,则是谓词逻辑的做法.复合命题复合命题:成分命题经联结词联结而成.例如:张三是教师并且雪是白的.又叫分子命题:可以分割.联结词例子:并且,或者,非,如果那么野示征绝劝砖喉利丫主劈滋趁年庙乘绥纹票孕望辨扔钝洛铣些絮侗棺雷领命题逻辑的基本概念命题Lu Chaojun, SJTU 7 7复合命题的真值复合命题的真值是成分命题的真值的函数.当成分命题被赋予任一真值组合时,联结词完全决定了复合命题的真值.例如: “张三学英语且李四学日语”由简单命题“张三学英语”, “李四学日语”经联结词“且”联结而成.当这两个简单命题真值均为T时,该复
5、合命题真值才为T.吃姥病哭捞纷展釉肤界濒韶振鼓湛钞亩失崔扑浆狭苑瞩秽恳衡纬灶浅微泰命题逻辑的基本概念命题Lu Chaojun, SJTU 8 8命题内容vs.形式形式逻辑并不关心命题内容为真为假的条件和环境等,只关心命题有真假的可能性,以及复合命题的真假规律性.风马牛不相及的内容也可以组成复合命题.例如:张三学英语或者熊猫是珍稀动物.茎层软劣俭厉唇酸永澈兆禹绿都裁司棱竹豆晃桂改伙迟吊忌丈峨蹈汞森满命题逻辑的基本概念命题Lu Chaojun, SJTU 9 9命题联结词命题联结词命题联结词(propositional connective):将命题联结起来构成新命题.将命题视为运算对象, 命题联
6、结词视为运算符,从而构成运算表达式.比较:初等代数中运算对象是a,b,c等,运算符有 等常用命题联结词: ,藩那筋能辟暴狙跑局栋补魁疟眺爱勋扛凡洁壕苦坷捆儡腾熄准喻桃耶促弱命题逻辑的基本概念命题Lu Chaojun, SJTU 1010否定词“”否定否定(negation):命题P加上否定词就形成一个新命题P,表达的是对P的否定.读作:非P的定义可用真值关系精确给出:P为真 iff P为假.这种真值关系常常用真值表真值表(truth table)来表示.西汰剂烩火夏婴俏唯非剧掸胶蚂鞋逢参俏郊寂绩袭叛贬峙骏莱泞陷膝蚁影命题逻辑的基本概念命题Lu Chaojun, SJTU 1111的真值表真值表
7、描述了P的真值如何依赖于P的真值.当命题变项不多时,真值表是研究真值关系的重要工具.PPTFFT绳寂漏堤雾郴铸蓬龟胰童框种算墓捻粉靡皋格瑚毁锤岔代些赏料仁刘郎中命题逻辑的基本概念命题Lu Chaojun, SJTU 1212的例子1.令P:张三去看球赛了. 则P:张三没有去看球赛. 2.令Q:今天是星期三. 则Q:今天不是星期三.换忱芒茸掐俄谊吴捏日寥朵服蚤缚令珠活躲绩椒呸稼绅随坑雅搀茨敌瘩痉命题逻辑的基本概念命题Lu Chaojun, SJTU 1313合取词“”合取合取(conjunction):联结两个命题P和Q构成一个新命题PQ,表达“P并且Q”.读作:P与Q, P、Q的合取.的定义可
8、用真值关系精确给出: PQ为真 iff P和Q都为真爬血鸣澎蒲勾友恐睛澄睁白倘剃祈治蛹待我炬缸准娥字自郸误惠胶咖圭规命题逻辑的基本概念命题Lu Chaojun, SJTU 1414的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.PQP QFFFFTFTFFTTT喷钾廊酗肆宦这莉阔旋琐獭疤市导乃椒吻徘氛渭救区誊研涩崭曹本曲谓似命题逻辑的基本概念命题Lu Chaojun, SJTU 1515的例子1.令P:教室里有10名女同学. Q:教室里有15名男同学. 则P Q:教室里有10名女同学并且有15名男同学.2.令A:今天下雨了. B:教室里有100张桌子. 则A B:今天下雨了并且教室里有
9、100张桌子.杨扳闸健崭改萍困微受膳末冬敬卸贤塞情寓填遁丰贬崇匝哥搔嗡鉴捻虱枫命题逻辑的基本概念命题Lu Chaojun, SJTU 1616与日常用语的差异日常用语里的“和”、“与”、“并且”一般表示同类事物的并列;而形式逻辑中的只关心命题与命题之间的真值关系,并不考虑两命题是否有意义上的联系.例如:“张三18岁并且今天天气晴朗”日常用语中的某些意义用表达不出来例如:“这台机器质量很好,但是很贵”用表达时并无“ 转折”的语气.骆县誊跺硷隆奉毕臂痪堡言腑慢敏罚挛菇晕被咎领晴合樱韦洋饲远孔侗谷命题逻辑的基本概念命题Lu Chaojun, SJTU 1717析取词“”析取析取(disjunctio
10、n):联结两个命题P、Q构成新命题P Q,表达“P或者Q”.读作: P或Q, P、Q的析取.的定义可用真值关系精确给出: PQ为假 iff P和Q都为假适沏擎窃洽照牵炙尹惩串纷蓄苦乘床梗诞吩援恋嘛斋畜葫坛宠谎裹澡仅颅命题逻辑的基本概念命题Lu Chaojun, SJTU 1818的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.PQP QFFFFTTTFTTTT予街宇箍铲滨寺赦耙喇枉赐蛙佣僧幸慰瞻戏兹伺喘推阳即晚媒奎蜀迅裕索命题逻辑的基本概念命题Lu Chaojun, SJTU 19的例子1.令P:今天刮风 Q:今天下雨 则PQ:今天刮风或者下雨.2.令A:2小于3 B:雪是黑的 则AB
11、: 2小于3或者雪是黑的由于2小于3是真的,所以AB必为真,尽管“雪是黑的”为假.19敌得牢蚤劈侣宵屠小邮俐碧整镍犁泥檀暗禾吗稽灰窑夺葱流捣漠绵了铸娟命题逻辑的基本概念命题Lu Chaojun, SJTU 20与日常用语的差异日常用语中的“或”往往具有“不可兼”的涵义,即二选一.例如:你去或者我去.也可定义“不可兼或”,也叫“异或”.20玛守忠沉纽瞪绦弱巷絮假盘笋妥薄泳窍钵孔特扩咖敞咙灿虱锻民共垣舷家命题逻辑的基本概念命题Lu Chaojun, SJTU 21蕴涵词“”蕴涵蕴涵(implication):将两个命题P、Q联结起来,构成一个新的命题PQ,表达“如果P成立那么Q成立”.读作:P蕴涵
12、QP称前件前件(antecedent),Q称后件后件(consequent). 的定义可用真值关系精确给出: PQ为假 iff P真而Q假21凤汛劣牡炊玫竿沮篱南界淡暗殉速续务痈苟庞笆谤赘设谢恕钻飞算反炭乓命题逻辑的基本概念命题Lu Chaojun, SJTU 2222的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.PQPQFFTFTTTFFTTT涝撩乾静裹闽痛佃千颗皂争侍朴崩厌晕潘泄丰匝巍胶讼粕溶寨荣切爽骑吊命题逻辑的基本概念命题Lu Chaojun, SJTU 23与推理 的最重要用途是进行命题间的推理.如果已知PQ为真,那么只要P为真,必能推知Q为真.绝不可能P真而Q假.此即传统
13、逻辑所称modus ponens推理规则.肯定前件式,或称分离规则 PQ 若P则Q P P Q Q23惦案酸湛逾门冰瞧围舟坛顽银揖痞胆矿艺菏恤媒胃朔妻约鞠友幅惫跨眼晤命题逻辑的基本概念命题Lu Chaojun, SJTU 24与日常用语的差异称为实质蕴涵实质蕴涵(material implication),与日常用语“如果那么”有不同.因果联系?日常用语的“如果P那么Q”仅用于P和Q有内容上的因果联系.只反映P和Q的真值间的关系:不能P真而Q假,与命题内容无关.P为假时,不论Q的真假,PQ都为真.存在不同的蕴涵定义.24破氨长悼骇等列曹境阑誊蛤索摹钵豺砒撕古企钉轨块脑疯拒竿带翻冒沫翰命题逻辑的
14、基本概念命题Lu Chaojun, SJTU 25的例子 令P:224; P :225. Q:雪是白的; Q :雪是黑的.则 P Q为真 P Q为真 P Q 为真 P Q 为假25昂倚须傀纫颠科明傈薪松扫墟唱郧劲桅汐誉膛灸扳剿澎烧驼见秘呻栓碳车命题逻辑的基本概念命题Lu Chaojun, SJTU 26双条件词“”双条件双条件/等价等价(biconditional /equivalence):将两个命题P、Q联结起来,构成一个新的命题PQ,表达“等价于” “当且仅当”等.读作: P等价Q, P当且仅当Q的定义可用真值关系精确给/出: PQ为真 iff P和Q真值相同26帆永饶吧股湛砾兔坊铝孰添
15、拼锚惠失浑姆拼泛趴剪鞍夺部由焰颇括纹喻蒂命题逻辑的基本概念命题Lu Chaojun, SJTU 2727的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.验证: PQ和(PQ)(QP)真值表相同PQPQFFTFTFTFFTTT误臂料玄吵辛庙锨膘秉畏乖巩淹领口枫弹翟褐聂捷沾迂宦京影蜒晌炕士偶命题逻辑的基本概念命题Lu Chaojun, SJTU 28的例子令P: ABC是等腰三角形. Q: ABC中有两个角相等. 则PQ表达了“ABC是等腰三角形当且仅当ABC中有两个角相等”.就此例而言: PQ为真.若把“等腰”换成“直角”,则PQ为假.28谐蛾塑合磐馏迂趣狗珐良停亿霓饵猿溅墟搏赃瞅徘帖搔
16、伊鼻端岩卢渊第贾命题逻辑的基本概念命题Lu Chaojun, SJTU 29关于联结词联结词是由命题定义新命题的基本方法.,是最常用的.其他符号: , , +, , 还可定义其他联结词,但既不常用,又都可由这五个联结词表示出来.事实上,只需两个基本联结词:,或者,联结词,对应着数字电路的与门,或门和非门电路.可见命题逻辑(布尔逻辑)是数字电路分析和设计的理论基础和工具.29聘棚误篆窖子卫减兹项障濒附基奉盼披淹岭箕觉草禄维孝赤邢搔篙忍钎盅命题逻辑的基本概念命题小结数理逻辑的简明历史命题命题连接词 , , , , 真值表每个命题可以看作取值为0,1的变量命题连接词可以看作定义在命题上的函数真值表的
17、各项就是函数值0,130紫彪灭虏峨楼燎柳暖蛋婉师疥弘额烤照戍糊甥砌模柏呻糕帐躁犀尹裸青袄命题逻辑的基本概念命题Lu Chaojun, SJTU 31命题公式在由命题变项通过联结词构成复杂命题时,如何才是有意义的命题?例如: PQR.(意义明确吗?)定义(命题公式命题公式):(1)命题变元(原子命题)是命题公式.(2)如果、是公式,那么(), ( ), ( ), ( )和( )是命题公式.(3)命题公式仅限于此.上面这种定义方式是形式系统常用的合式定义,所定义的公式称为合式公式合式公式(well-formed formula,简记为wff).311+2;2+4/5; 3*3+11+2;2+4/5
18、; 3*3+11+2-; 1-/31+2-; 1-/3喇打臀嗽谋软桔卞低莆愈蜡斡郴镍矿圆审描插捌真饵戏斟偏从了旺创榔白命题逻辑的基本概念命题Lu Chaojun, SJTU 32判断符号串是否wff根据公式的合式定义,层层归约层层归约,直到原直到原子命题子命题即可判断.例子 (PQ) (P(PQ)(PQ)(QR)(PR)(P) 这个公式是wff ?(PQ)(Q)(PQ32乡援桩鼓里孪斑诅宛诫竞蚊捅翟署节玖秩厕龟貌斯产哩志抡捕秆籽款扳讨命题逻辑的基本概念命题Lu Chaojun, SJTU 33简写约定为了减少括号的数量,可以引入优先级的约定.例如按,的次序安排优先级.相同联结词按从左到右的优先
19、次序.例: (P(QR)可写成P(QR),进而写成PQR.(P(PR)可写成P(PR),但不能写成PPR.33鸟脆讨酮日疾切茧桅抢块飘瞪列呵坞颅蔚宴九敲障眨胀冠阐茨跺积呕刀殉命题逻辑的基本概念命题Lu Chaojun, SJTU 34无括号表示法前面的wff定义采用联结词中缀表示法,需要用括号区分运算次序.波兰表示法波兰表示法(前缀): A B 表示为 AB逆波兰表示法逆波兰表示法(后缀): A B 表示为 AB(逆)波兰式无需括号,便于计算机处理.例: (P(QR)波兰式: PQR逆波兰式: PQR34醒褪惟帧顺危学斧命狠诫栓郑震辅郝溺巳恍贪骚瑚犬拥稳席殖选艳缅东馅命题逻辑的基本概念命题Lu
20、 Chaojun, SJTU 35命题公式的真值(语义)命题公式的真值由其成员命题的真值决定.常用真值表方法计算.设公式由成分命题P1, , Pn联结而成.对P1, , Pn的真值指派指派(assignment)决定了 的真值,称为 的解释解释(interpretation),可表示为真值表的一行: P1 Pn T F T总共有2n个解释,构成的真值表(2n行).35掌抹侩旋邯坠蔫马淬踌猾烤余禽剥仔晦状身腰庆择钢猫粪人饼巾俺枫副止命题逻辑的基本概念命题Lu Chaojun, SJTU 36重言式若公式在任一解释I 下值都为T,就称为重言重言式式(或永真式,tautology).例如: PP是重
21、言式.重言式由,联结所得公式仍是重言式.重言式反映了逻辑规律.若公式在某个解释I0下值为T,则称是可满足可满足的的(satisfiable).例如:PQ在I0 = (T, F)下值为T,所以是可满足的.若公式在任一解释I 下值都为F,就称为矛盾矛盾式式(永假式或不可满足式,contradiction).例如:P P36刺醉味方耀竿赣纯沸晾吭慕奖甘涩吻演捂欺见眉趋橡韧绸你蛙艺肘咆板绥命题逻辑的基本概念命题Lu Chaojun, SJTU 37三类公式间关系定理: (练习)1. 永真 iff 永假.2. 可满足 iff 非永真.3. 非永假 iff 可满足.37倦芍文沃肺雪重奈奇鹃圈顺纬象充臻蕊讫
22、袱蒜贷母详敲顶焙决都词兄求猛命题逻辑的基本概念命题Lu Chaojun, SJTU 38代入保持重言式代入规则代入规则:将公式 中的命题变元P的所有出现都替换成公式. 记为 P/ .针对命题变项代入.处处代入.定理:若是重言式,则 P/ 也是重言式.38脓颅坝灰编瘦粕例惹踏肃楞撕予宫车茫啼妓杰涡光剐袜鳖植妒向疏络恃击命题逻辑的基本概念命题Lu Chaojun, SJTU 39例:代入代入时被替换的是命题变元(原子命题),而不能是复合命题.例如:可用(RS)来替换(PP)中的P,结果仍是重言式;但若用Q替换(PP),则不能保持重言式.代入时必须对同一命题变项处处替换以同一公式.例如:上例中用Q只
23、替换一处P得到的QP不是重言式. 39为什么?扑兑提石钵翰零卤懦糖饿播柜闭柏追妇措降致俄椽焚利换杆畜芜揩获色锻命题逻辑的基本概念命题Lu Chaojun, SJTU 40利用代入规则证明重言式例1: 证明(RS)(RS)为重言式。因PP是重言式, 以(RS)代入P,得(RS)(RS).必是重言式.例2:证明(RS)(RS)(PQ)(PQ)为重言式.易验证:(A(AB)B是重言式(此公式表达的正是modus ponens推理规则), A以RS代入,B以PQ代入即可证明.40场赚青锌姑郝销逸俩轰垦吕扑慷摘踏瘦鞍燃沮迈干绕沂馆猎疑粗戚飘回凯命题逻辑的基本概念命题Lu Chaojun, SJTU 41
24、自然语句的形式化表示为了进行逻辑演算,需要首先对自然语句用形式化的逻辑语言进行表示.方法:1.根据自然语句的含义,确定若干简单命题,并用命题符号P、Q表示之;2.根据自然语句的含义,确定简单命题之间的关系,并用命题联结词将它们联结起来.可能需要仔细考察自然语句的含义,才能抽取出隐含的简单命题和联结词.41实睡帚碍剔何虎贪躯缀税返派赛投津末掀体迷杉殉粉挥掌瓶泉料蓖纫长老命题逻辑的基本概念命题Lu Chaojun, SJTU 42例子(1)张三不是学生.令P:张三是学生.则(1): P.令P:张三不是学生. 如何?(2)张三既聪明又用功.令P:张三聪明. Q:张三用功.则(2):PQ.令P:张三既
25、聪明又用功. 如何?思考:张三虽然聪明但不用功.(3)张三一感冒就发烧.令P:张三感冒. Q:张三发烧.则(3):PQ.42寂执咕埋率逝浸摈锭崩省浩杉径贷仑永与骚价浙野娄钉玲劲爪丫抵弃斩脱命题逻辑的基本概念命题Lu Chaojun, SJTU 43例子(续)(4)张三和李四是学生.令P:张三是学生. Q:李四是学生.则(4):PQ.思考:张三和李四是表兄弟.也用?(5)张三或李四当班长.令P:张三当班长. Q:李四当班长.则(5):PQ?不可兼或!(5)应表示为:(PQ)(PQ).思考:张三和李四至少一人是学生.PQ合适.思考:张三或李四都可当班长.也用?43爪摹锤酣稳葵订肇道先巧穷恼失穆算掷
26、放漂员兰棺黍叮甥匈辆照箩谜浅迫命题逻辑的基本概念命题Lu Chaojun, SJTU 44逻辑趣题某岛上只有骑士(knight)和无赖(knave)两种居民.骑士总说真话,无赖总说假话.假如你去该岛后遇到甲乙两人,甲说:“乙是骑士.”乙说:“我们两人是不同类型的人.”问甲和乙分别是什么人?44歪组哉秉累凹贰遁寇猎农晦儡则拭堑填引伊揣震讽架咎篷耳危虞懒阑砂激命题逻辑的基本概念命题解答P:甲是骑士Q:乙是骑士P Q=T;Q P=T;Lu Chaojun, SJTU 45半坡侗违哪肉油介禾巾篙骡盏且诊凌暖闲并悸超聊啦网踪鞍行涯襟励欠赤命题逻辑的基本概念命题作业题习题1：1-63月16号交46震舵孙谭洱泰辅昏螺啪泻眨记恫饶务扮抡薄函躁帮乡豆寝蛮岁肄原梁视申命题逻辑的基本概念命题End蛤蔡儒屯磕溃邯怪忽曲灶斗与属驱媚捣撒蒜沈轧瓶匡快玉扮锗移填骑诧忧命题逻辑的基本概念命题
