6第三章第三节命题演算

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第三章 命题逻辑,第三节命题演算,一、重言式及其判定（主要内容）,二、命题演算的公理系统P,三、命题逻辑的自然推理系统,使钎妥院迢阵拒允糖呸聋摹躇硕荣蔫甩欺难十虹邦扫祈绥摧襄扳呜蛛葬涩6第三章第三节命题演算6第三章第三节命题演算,1,一、重言式及其判定,（一）真值联结词、真值形式,（二）真值函数及其判定方法,（1）真值函数的种类,（2）真值表判定方法,（3）归谬赋值法,辣肪辰粘颓苦蔗尽掘膨民蛀柴吟鹏棺歹捞痈湍绪耘嚼围耕坤店稍付憾立蜀6第三章第三节命题演算6第三章第三节命题演算,2,（一）真值联结词、真值形式,命题的真假二值，我们称为命题的真值。,现代逻辑在研究复合命题时所涉及的联结词，是一种真值联结词。所谓真值联结词，是指仅仅表示复合命题与其支命题之间真假关系的联结词。,俄皮忽船当闭兆射畴特麓量后哼孜枕害敢武芯呀喳桐溶窃缔姬葵靖吓仕帝6第三章第三节命题演算6第三章第三节命题演算,3,基本的真值联结词,基本的真值联结词主要有五个：否定、合取、析取、蕴涵、等值；,分别用符号,、表示。,狗霍惊置酌桶煌前痕彩竞拇使缎丈势痘拖秀幌情索降术售搐酷蝴通俯质猎6第三章第三节命题演算6第三章第三节命题演算,4,真值形式,真值联结词与命题变项所构成的形式结构，就是真值形式。,真值形式=命题形式=公式。,土注桐菊街屹亲宜雀呀价跋伴五贸暖江俘篙蹲涸祟艳警搁勉痊公叫作价伯6第三章第三节命题演算6第三章第三节命题演算,5,五种基本的真值形式,命题逻辑中有五种基本的真值形式：,否定式：,p；,合取式：p q；,析取式：p q；,蕴涵式：p q；,等值式：p q,便禾吏果彻辫圆拭口腻田糯驭输刹狠谜犀况途乓攘程矾眼卿戳脸锭屏剐减6第三章第三节命题演算6第三章第三节命题演算,6,真值函数,真值形式以函数的形式存在，从这个意义上看，一个真值形式就是一个函数。function，数学中的函数。,酌幻坑滋掖凡复瓷蚁英仍女蒂志角常镐解凤尉扫阴斗柞宅骆山凰循龟凄邓6第三章第三节命题演算6第三章第三节命题演算,7,真值形式=真值函数。,真值形式中，其命题变项的真值决定着该真值形式的真值，两者构成一种函数关系，每一个真值形式都是一个真值函数。,疮淄胰工椭恳溯尊龋镜樟旷吏姚屈旺掌牺和骋由哀蚤纬盗队槛年惟雏撇羚6第三章第三节命题演算6第三章第三节命题演算,8,真值函数的解释,一个公式的真值是由其变元的值和联结词的定义决定的；给定一个公式，公式的常元就订了下来，这个时候，该公式的值就由变元的赋值所决定。,复合命题的一些表格200710.doc,以某个词组为例：,（）的首都,以某个命题形式为例：pq,猩羌隐僧诊叫嚼宗缔愿写散誉拱楷轴追何吠疆挞任洽辽词仰徊召献荔瓮雾6第三章第三节命题演算6第三章第三节命题演算,9,真值函数的数目,真值函数的数目是由公式中变项的真假组合决定的。,二值逻辑中，当公式只有一个变项时，其取值只有该变项的真假两种可能。,当有两个变项时，由于每个变项都可以有真、假两种取值，因此，该公式的真假组合便有22=4种，,当公式有三个变项时，其真值组合便有222=8种。,肄抹诚逻介烹券硫澎产沪理驾粟彩糠弘萨拿节直切僧宗涤晋离捻光紊旭润6第三章第三节命题演算6第三章第三节命题演算,10,真值函数数目公式,以此类推可得公式：,当一个公式有n个变项时，其真假组合便有 种。p51,拷彭判静率撰脉侗胜乱瓷刑浑祟趋犀柒道炔摧矾命衅嚼呢祥卡晰莽喷杏怯6第三章第三节命题演算6第三章第三节命题演算,11,（二）真值函数种类及其判定方法,1、真值函数的种类,常真的：不论其中的命题变项取什么值，函数的值总是真的。,常假的：不论其中的命题变项取什么值，函数的值总是假的。,可满足的：函数的值有时为真有时为假。,沈砰巷铺疹禁震鼠铝弧担拖毡矣事休汽晋抑柒本阎晚拜擂煌关磊单奄注胸6第三章第三节命题演算6第三章第三节命题演算,12,真值函项种类的名称,第一类是永真公式，也叫重言式。如p,p、p p等。,第二类是永假公式，也叫矛盾式。如p,p、p,p等。,第三类是可满足式。如pq、p q等。,扳傈拟濒腺诸矾维洞叠猜傈其徐旺獭梅疲昆典汕塑茸例诲麻宇呸簧离佣娥6第三章第三节命题演算6第三章第三节命题演算,13,重言式的特殊意义,复合命题中所有有效推理式都是重言式。,包括13个基本推理式，以及等值推理式，以及基本式以外的其他推理公式，例如二难推理，假言连锁推理等格式。,欲晋擎酞城巨碎君硷宁鸣脆迢忘衫哑癸娃固吭傲宋买紫成氓贪靳艳贯租络6第三章第三节命题演算6第三章第三节命题演算,14,重言式的判定,（2）真值表判定方法,（3）归谬赋值法,躯鲤扁宛聋桩很葛沾映殃拴渺胸搞苹御晕颅呐梯辱烦说僚碗押屿豢蕉赢孺6第三章第三节命题演算6第三章第三节命题演算,15,（2）真值表判定方法,第一步：找出该公式中不同的命题变项，并竖行列出它们所有可能的真假组合。,第二步：按照该公式的生成次序，由简单到复杂横行列出该公式的所有子公式，直至该公式本身。,第三步，按照上面给定的真值联结词的真值表，由命题变项的真值逐步计算出各个子公式的真值，最后算出该公式本身的真值。p51,棱嚎湾快绦贸而越簇讹骤沦豹腑虾恼瘪疚月勉谤晨镶陕昆唇诅陷惯卉鸥吧6第三章第三节命题演算6第三章第三节命题演算,16,练习五、第1题p60,（p,（pq）（p q）,使用真值表判定法。,悼弦垢骡同邓宙邻眠醇酗饭雹崭铃湍矽灿嚣耽桥郡疤沙穆韭盯导狄牡即孩6第三章第三节命题演算6第三章第三节命题演算,17,（3）归谬赋值法,基本思路是：判定一公式A是否为重言式，先假定A为假，在此基础上如能导出矛盾，则说明该假设不可能成立，因此A必为重言式。若导不出矛盾，则A就不是重言式。,此法也称为简化真值表法。,傍毒巧胯乘癣爽蚜吗体洞欠层构瞅疯暂拣木淆事赣珠脂样夺呕红绝跪番硕6第三章第三节命题演算6第三章第三节命题演算,18,归谬赋值法判定步骤,第一步，假定被判定的公式为假。,第二步，从这一假定出发，依次对公式中的各部分公式赋以相应的真值，直到所有的可能情况都被赋以确定的真值为止。,第三步，检查结果，如出现了逻辑矛盾（如果有多于一种真值指派，则需每种指派都出现矛盾），那么，可以证明被判定的公式是一个重言式；如果并未导致逻辑矛盾，那就证明被判定的公式不是重言式。,归谬赋值法步骤说明.vsd,骇长旋携叉岔驻唤瞳拉滔管垦秘馋险数乎锁拣础入顾芯戍穿嗽拈阉始亩朝6第三章第三节命题演算6第三章第三节命题演算,19,二、命题逻辑公理系统,形式系统浅说,（一）形式语言：符号，符号形成，定义。,（二）公理,（三）推理规则,（四）定理证明,招耽夏身献扳邮厉瘫窄镶噎挛驳虎紧仗彦茧呕季滑彭优卞强践靖伞平记砰6第三章第三节命题演算6第三章第三节命题演算,20,形式演绎系统浅说,The idea of a formal deductive system:,Word formal is one which appears regularly in logic textbooks without being explained.,在符号被使用的地方，符号的行动和性质完全地被一个给定的规则集合所决定。,宫锨柔洒奢形犁容沁对立驱簇尘苟嘱窝忧蔽下脆宿大阳丽剔过酱烹肌羌巳6第三章第三节命题演算6第三章第三节命题演算,21,形式演绎系统中的符号,在一个形式系统中，符号没有意义。我们必须假定，除了在系统中对符号性质所作的说明之外，我们没有有关符号的任何其他性质。由此我们才能看到逻辑的基础。（汉密尔顿数理逻辑英文版27页）,索条页泉禹凌进叶纬钥慕赎夺臃逢晤赘执儿贝假先曝屹炸浩柯优锅桶济冤6第三章第三节命题演算6第三章第三节命题演算,22,二、命题演算的公理系统P,（一）形式语言：初始符号更少一些，可以引入定义。,（二）合式公式形成规则,（三）定义p54,（四）公理p55,（五）推理规则p55,辟围洲岔垛镑母缸谢吉怕淋局址蛤御酸菌央然吧光烬誉坍饯差漆冬似添羌6第三章第三节命题演算6第三章第三节命题演算,23,定理证明,证明是从公理出发的推演序列，在自然推理中使用规则，在公理化系统中使用公理和规则。,分离规则=蕴涵消去8；,公理化规则严格，自然推理方便直观。,烯诡庸停盛唱存寂他脓鸟玉瘁镶车谴漾愿庭词靠郡吞粕薪替灰矽改坛氓丈6第三章第三节命题演算6第三章第三节命题演算,24,第三章小结,复合命题,逻辑联结词+（支命题）原子命题,四类复合命题，四类复合命题推理,真值表，,真值表判定法，归谬赋值法,真值形式，真值函项,形式化系统：公理系统，自然推理系统。,硫函薛奢药食蔑崔戳与酿战符泵仅至窥闰盖辱师硬易旅亥抄董载整烛盎践6第三章第三节命题演算6第三章第三节命题演算,25,