《命题逻辑的基本概念.ppt》由会员分享，可在线阅读，更多相关《命题逻辑的基本概念.ppt（47页珍藏版）》请在三一文库上搜索。
1、命题逻辑的基本概念,Lu Chaojun, SJTU,2,2,主要内容,命题 命题联结词 合式公式 重言式,Lu Chaojun, SJTU,3,3,什么是命题?,命题(proposition):是一个非真即假的陈述句. 是陈述句,而非命令句、疑问句或感叹句等. 表达的内容可判断真假,而且非真即假. 真假的判定:与事实是否相符. 不能不真又不假，也不能又真又假. 真值(truth value):命题具有两种可能的取值,即真(true)和假(false). 常写做T和F. 称为二值逻辑.,Lu Chaojun, SJTU,4,4,例子:命题,(1)雪是白的. 是命题,真值为T. (2)雪是黑的.
2、 是命题,真值为F. (3)好大的雪啊! 不是命题 (4)偶数可表示成两个素数之和.(Goldbach猜想) 是命题,目前不知其真假. (5)1+10l110. 相当于陈述句“1加101等于110”. 在十进制范围中真值为F,在二进制范围中真值为T. 并不意味着同一命题有两个真值!在不同数制中是不同的命题.,Lu Chaojun, SJTU,5,5,命题的符号化表示,为了对命题进行逻辑演算,利用数学手段将命题符号化(形式化). 用字母表示命题 命题常项:例如用P表示“雪是白的”. 命题变项:例如用P表示任意命题. 命题vs.命题变项 命题指具体的陈述句,有确定的真值 命题变项不特指某个命题,真
3、值不确定 将某个命题代入命题变项时,命题变项方可确定真值. 但在命题逻辑演算中,两者处理原则是一样的,可不做区分.,Lu Chaojun, SJTU,6,6,简单命题和复合命题,简单命题:简单句,不包含任何“并且”, “或者”之类的联结词. 例如:雪是白的. 又叫原子命题:不可分割. 如果按主语谓语分析,则是谓词逻辑的做法. 复合命题:成分命题经联结词联结而成. 例如:张三是教师并且雪是白的. 又叫分子命题:可以分割. 联结词例子:并且,或者,非,如果那么,Lu Chaojun, SJTU,7,7,复合命题的真值,复合命题的真值是成分命题的真值的函数. 当成分命题被赋予任一真值组合时,联结词完
4、全决定了复合命题的真值. 例如: “张三学英语且李四学日语”由简单命题“张三学英语”, “李四学日语”经联结词“且”联结而成.当这两个简单命题真值均为T时,该复合命题真值才为T.,Lu Chaojun, SJTU,8,8,命题内容vs.形式,形式逻辑并不关心命题内容为真为假的条件和环境等,只关心命题有真假的可能性,以及复合命题的真假规律性. 风马牛不相及的内容也可以组成复合命题. 例如:张三学英语或者熊猫是珍稀动物.,Lu Chaojun, SJTU,9,9,命题联结词,命题联结词(propositional connective):将命题联结起来构成新命题. 将命题视为运算对象, 命题联结词
5、视为运算符,从而构成运算表达式. 比较:初等代数中运算对象是a,b,c等,运算符有 等 常用命题联结词: ,Lu Chaojun, SJTU,10,10,否定词“”,否定(negation):命题P加上否定词就形成一个新命题P,表达的是对P的否定. 读作:非P 的定义可用真值关系精确给出: P为真 iff P为假. 这种真值关系常常用真值表(truth table)来表示.,Lu Chaojun, SJTU,11,11,的真值表,真值表描述了P的真值如何依赖于P的真值. 当命题变项不多时,真值表是研究真值关系的重要工具.,Lu Chaojun, SJTU,12,12,的例子,1.令P:张三去看
6、球赛了. 则P:张三没有去看球赛. 2.令Q:今天是星期三. 则Q:今天不是星期三.,Lu Chaojun, SJTU,13,13,合取词“”,合取(conjunction):联结两个命题P和Q构成一个新命题PQ,表达“P并且Q”. 读作:P与Q, P、Q的合取. 的定义可用真值关系精确给出: PQ为真 iff P和Q都为真,Lu Chaojun, SJTU,14,14,的真值表,的真值表描述了PQ的真值如何依赖于P和Q的真值.,Lu Chaojun, SJTU,15,15,的例子,1.令P:教室里有10名女同学. Q:教室里有15名男同学. 则P Q:教室里有10名女同学并且有15名男同学.
7、 2.令A:今天下雨了. B:教室里有100张桌子. 则A B:今天下雨了并且教室里有100张桌子.,Lu Chaojun, SJTU,16,16,与日常用语的差异,日常用语里的“和”、“与”、“并且”一般表示同类事物的并列;而形式逻辑中的只关心命题与命题之间的真值关系,并不考虑两命题是否有意义上的联系. 例如:“张三18岁并且今天天气晴朗” 日常用语中的某些意义用表达不出来 例如:“这台机器质量很好,但是很贵”用表达时并无“ 转折”的语气.,Lu Chaojun, SJTU,17,17,析取词“”,析取(disjunction):联结两个命题P、Q构成新命题P Q,表达“P或者Q”. 读作:
8、 P或Q, P、Q的析取. 的定义可用真值关系精确给出: PQ为假 iff P和Q都为假,Lu Chaojun, SJTU,18,18,的真值表,的真值表描述了PQ的真值如何依赖于P和Q的真值.,Lu Chaojun, SJTU,19,的例子,1.令P:今天刮风 Q:今天下雨 则PQ:今天刮风或者下雨. 2.令A:2小于3 B:雪是黑的 则AB: 2小于3或者雪是黑的 由于2小于3是真的,所以AB必为真,尽管“雪是黑的”为假.,19,Lu Chaojun, SJTU,20,与日常用语的差异,日常用语中的“或”往往具有“不可兼”的涵义,即二选一. 例如:你去或者我去. 也可定义“不可兼或”,也叫
9、“异或”.,20,Lu Chaojun, SJTU,21,蕴涵词“”,蕴涵(implication):将两个命题P、Q联结起来,构成一个新的命题PQ,表达“如果P成立那么Q成立”. 读作:P蕴涵Q P称前件(antecedent),Q称后件(consequent). 的定义可用真值关系精确给出: PQ为假 iff P真而Q假,21,Lu Chaojun, SJTU,22,22,的真值表,的真值表描述了PQ的真值如何依赖于P和Q的真值.,Lu Chaojun, SJTU,23,与推理,的最重要用途是进行命题间的推理. 如果已知PQ为真,那么只要P为真,必能推知Q为真. 绝不可能P真而Q假. 此即
10、传统逻辑所称modus ponens推理规则. 肯定前件式,或称分离规则 PQ 若P则Q P P Q Q,23,Lu Chaojun, SJTU,24,与日常用语的差异,称为实质蕴涵(material implication),与日常用语“如果那么”有不同. 因果联系? 日常用语的“如果P那么Q”仅用于P和Q有内容上的因果联系. 只反映P和Q的真值间的关系:不能P真而Q假,与命题内容无关. P为假时,不论Q的真假,PQ都为真. 存在不同的蕴涵定义.,24,Lu Chaojun, SJTU,25,的例子,令P:224; P :225. Q:雪是白的; Q :雪是黑的. 则 P Q为真 P Q为真
11、 P Q 为真 P Q 为假,25,Lu Chaojun, SJTU,26,双条件词“”,双条件/等价(biconditional /equivalence):将两个命题P、Q联结起来,构成一个新的命题PQ,表达“等价于” “当且仅当”等. 读作: P等价Q, P当且仅当Q 的定义可用真值关系精确给/出: PQ为真 iff P和Q真值相同,26,Lu Chaojun, SJTU,27,27,的真值表,的真值表描述了PQ的真值如何依赖于P和Q的真值. 验证: PQ和(PQ)(QP)真值表相同,Lu Chaojun, SJTU,28,的例子,令P: ABC是等腰三角形. Q: ABC中有两个角相等
12、. 则PQ表达了“ABC是等腰三角形当且仅当ABC中有两个角相等”. 就此例而言: PQ为真. 若把“等腰”换成“直角”,则PQ为假.,28,Lu Chaojun, SJTU,29,关于联结词,联结词是由命题定义新命题的基本方法. ,是最常用的. 其他符号: , , +, , 还可定义其他联结词,但既不常用,又都可由这五个联结词表示出来. 事实上,只需两个基本联结词:,或者, 联结词,对应着数字电路的与门,或门和非门电路.可见命题逻辑(布尔逻辑)是数字电路分析和设计的理论基础和工具.,29,小结,数理逻辑的简明历史 命题 命题连接词 , , , , 真值表 每个命题可以看作取值为0,1的变量
13、命题连接词可以看作定义在命题上的函数 真值表的各项就是函数值0,1,30,Lu Chaojun, SJTU,31,命题公式,在由命题变项通过联结词构成复杂命题时,如何才是有意义的命题? 例如: PQR.(意义明确吗?) 定义(命题公式): (1)命题变元(原子命题)是命题公式. (2)如果、是公式,那么(), ( ), ( ), ( )和( )是命题公式. (3)命题公式仅限于此. 上面这种定义方式是形式系统常用的合式定义,所定义的公式称为合式公式(well-formed formula,简记为wff).,31,1+2;2+4/5; 3*3+1 1+2-; 1-/3,Lu Chaojun, S
14、JTU,32,判断符号串是否wff,根据公式的合式定义,层层归约,直到原子命题即可判断. 例子 (PQ) (P(PQ) (PQ)(QR)(PR) (P) 这个公式是wff ? (PQ)(Q) (PQ,32,Lu Chaojun, SJTU,33,简写约定,为了减少括号的数量,可以引入优先级的约定. 例如按,的次序安排优先级. 相同联结词按从左到右的优先次序. 例: (P(QR)可写成P(QR),进而写成PQR. (P(PR)可写成P(PR),但不能写成PPR.,33,Lu Chaojun, SJTU,34,无括号表示法,前面的wff定义采用联结词中缀表示法,需要用括号区分运算次序. 波兰表示法
15、(前缀): A B 表示为 AB 逆波兰表示法(后缀): A B 表示为 AB (逆)波兰式无需括号,便于计算机处理. 例: (P(QR) 波兰式: PQR 逆波兰式: PQR,34,Lu Chaojun, SJTU,35,命题公式的真值(语义),命题公式的真值由其成员命题的真值决定.常用真值表方法计算. 设公式由成分命题P1, , Pn联结而成. 对P1, , Pn的真值指派(assignment)决定了 的真值,称为 的解释(interpretation),可表示为真值表的一行: P1 Pn T F T 总共有2n个解释,构成的真值表(2n行).,35,Lu Chaojun, SJTU,3
16、6,重言式,若公式在任一解释I 下值都为T,就称为重言式(或永真式,tautology). 例如: PP是重言式. 重言式由,联结所得公式仍是重言式. 重言式反映了逻辑规律. 若公式在某个解释I0下值为T,则称是可满足的(satisfiable). 例如:PQ在I0 = (T, F)下值为T,所以是可满足的. 若公式在任一解释I 下值都为F,就称为矛盾式(永假式或不可满足式,contradiction). 例如:P P,36,Lu Chaojun, SJTU,37,三类公式间关系,定理: (练习) 1. 永真 iff 永假. 2. 可满足 iff 非永真. 3. 非永假 iff 可满足.,37
17、,Lu Chaojun, SJTU,38,代入保持重言式,代入规则:将公式 中的命题变元P的所有出现都替换成公式. 记为 P/ . 针对命题变项代入. 处处代入. 定理:若是重言式,则 P/ 也是重言式.,38,Lu Chaojun, SJTU,39,例:代入,代入时被替换的是命题变元(原子命题),而不能是复合命题. 例如:可用(RS)来替换(PP)中的P,结果仍是重言式;但若用Q替换(PP),则不能保持重言式. 代入时必须对同一命题变项处处替换以同一公式. 例如:上例中用Q只替换一处P得到的QP不是重言式.,39,为什么?,Lu Chaojun, SJTU,40,利用代入规则证明重言式,例1
18、: 证明(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,自然语句的形式化表示,为了进行逻辑演算,需要首先对自然语句用形式化的逻辑语言进行表示. 方法: 1.根据自然语句的含义,确定若干简单命题,并用命题符号P、Q表示之; 2.根据自然语句的含义,确定简单命题之间的关系,并用命题联结词将它们联结起来. 可能需要仔细考察自然语句
19、的含义,才能抽取出隐含的简单命题和联结词.,41,Lu Chaojun, SJTU,42,例子,(1)张三不是学生. 令P:张三是学生.则(1): P. 令P:张三不是学生. 如何? (2)张三既聪明又用功. 令P:张三聪明. Q:张三用功.则(2):PQ. 令P:张三既聪明又用功. 如何? 思考:张三虽然聪明但不用功. (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,Lu Chaojun, SJTU,44,逻辑趣题,某岛上只有骑士(knight)和无赖(knave)两种居民.骑士总说真话,无赖总说假话. 假如你去该岛后遇到甲乙两人, 甲说:“乙是骑士.” 乙说:“我们两人是不同类型的人.” 问甲和乙分别是什么人?,44,解答,P:甲是骑士 Q:乙是骑士 P Q=T; Q P=T;,Lu Chaojun, SJTU,45,作业题,习题1：1-6 3月16号交,46,End,