《L1命题逻辑1 离散数学》由会员分享，可在线阅读，更多相关《L1命题逻辑1 离散数学（44页珍藏版）》请在金锄头文库上搜索。
1、命题逻辑一Lu Chaojun, SJTU 2 2主要内容 命题与命题联结词 命题公式 等值演算 命题公式的范式 联结词的功能完全集 永真蕴涵式 命题逻辑推理Lu Chaojun, SJTU 3 3什么是命题? 命题(proposition):可判断真假而且非真即假的 陈述句的内容. 是陈述句的内容,而非陈述句本身. 命令句、疑问句或感叹句等的内容不构成命题. 可判定真假:是否符合事实. 不可:不真不假，又真又假. 命题的真值(truth value):命题的真假结果.即真 (TRUE)和假(FALSE). 常记作T和F,或者1和0. 二值逻辑Lu Chaojun, SJTU 4 4例:命题(
2、1) “雪是白的.” 是命题,真值为1. (2) “雪是黑的.” 是命题,真值为0. (3) “好大的雪啊!” 不是命题 (4) “大于2的偶数可表示成两个素数之和.”(Goldbach猜想) 是命题,目前不知其真假. (5) “1+10l110.” 此数学式相当于命题“1加101等于110”.在十进制中真值为0,在 二进制中真值为1. 并非说同一命题有两个真值!在不同数制中是不同的命题.Lu Chaojun, SJTU 5 5命题的符号化表示 为便于进行命题演算,将自然语言符号化. 用符号表示命题: 命题常量:有确定真值的具体命题. 符号化:如用a表示“雪是白的”. 命题变量:用符号来表示任
3、意命题. 命题变量的真值是不确定的.对其指派了具体命题之后,才 具有确定的真值. 我们采用的表示法 采用小写字母(可带下标)作为命题符号: a, b, c, 命题符号如果不加说明一般是命题变量Lu Chaojun, SJTU 6 6简单命题和复合命题 从自然语言的简单句和复合句可形成简单命题 与复合命题的概念. 简单命题(或原子命题):简单语句 不含“并且” “或者” “如果那么”之类的联结词. 例如“雪是白的.” 命题逻辑中不作进一步分析.但谓词逻辑不同. 复合命题:复合语句 可分析为:简单命题经联结词联结而成. 联结词:并且,或者,非,如果那么, 例如“张三是教师并且雪是白的.”Lu Ch
4、aojun, SJTU 7 7命题联结词 命题联结词(propositional connective):将 命题联结起来构成新命题. 常用命题联结词: , 将命题视为运算对象, 命题联结词视为运 算符,则构成运算表达式. 比较:初等代数中运算对象是a,b,c等,运算符 有 等Lu Chaojun, SJTU 8 8否定词“” 否定(negation):命题a加上否定词就形成 一个新命题a,表达的是对a的否定. 读作:非a 的严格定义可利用真值关系给出: a为真 iff a为假. 这种真值关系常常用真值表(truth table)来表 示.Lu Chaojun, SJTU 9 9的真值表 真值
5、表描述了a的真值如何依赖于a的真 值. 当命题变量不多时,真值表是研究真值关系的 重要工具.aa 10 01Lu Chaojun, SJTU 1010的例子1.令a: “张三去看球赛了.”则a: “张三没有去看球赛.” 2.令b: “今天是星期三.”则b: “今天不是星期三.”Lu Chaojun, SJTU 1111合取词“” 合取(conjunction):联结两个命题a和b构成 一个新命题ab,表达“a并且b”. 读作: a且b, a与b, a、b的合取. 的严格定义可用真值关系给出:ab为真 iff a和b都为真Lu Chaojun, SJTU 1212的真值表 的真值表描述了ab的真
6、值如何依赖于a 和b的真值.aba b 000 010 100 111Lu Chaojun, SJTU 1313的例子1.令a: “雪是白的.”b: “煤是黑的.”则a b: “雪是白的并且煤是黑的.” 2.令a: “雪是白的.”b: “教室里有人.”则a b: “雪是白的并且教室里有人.”Lu Chaojun, SJTU 1414与日常用语的差异 日常用语里的“和”“与”“并且”一般表示有 联系的事物;而只关心命题间的真值关 系,并不考虑两命题是否有意义上的联系. 例如“雪是白的并且教室里有人.” 日常用语中的某些意义用表达不出来 例如“苹果电脑质量很好,但是很贵.” 可符号化为用表达,但没
7、有转折语气. “张和李是同学”中的“和”不是联结词.Lu Chaojun, SJTU 1515析取词“” 析取(disjunction):联结两个命题a和b构成 新命题ab,表达“a或者b”. 读作: a或b, a、b的析取. 的严格定义可用真值关系给出:ab为假 iff a和b都为假Lu Chaojun, SJTU 1616的真值表 的真值表描述了ab的真值如何依赖于a 和b的真值.aba b 000 011 101 111Lu Chaojun, SJTU 17的例子1.令a:“雪是白的.”b:“雪是黑的.”则ab:“雪是白的或者雪是黑的.” 2.令a:“2小于3.”b:“雪是黑的.”则ab
8、:“2小于3或者雪是黑的.” 由于“2小于3”真,所以ab必真,尽管“雪是黑 的”为假.17Lu Chaojun, SJTU 18与日常用语的差异 日常用语中的“或”还可能具有“排他”涵义 例如“你去或者我去”有二选一的意思 可定义这种“排他的或(exclusive or)”,称为异 或. 而是“包容的或(inclusive or)”.18Lu Chaojun, SJTU 19蕴涵词“” 蕴涵(implication):将两个命题a和b联结起 来,构成一个新的命题ab,表达“如果a成 立那么b成立”. 读作:a蕴涵b a称前件(antecedent),b称后件(consequent). 的严格
9、定义可用真值关系给出:ab为假 iff a真而b假19Lu Chaojun, SJTU 2020的真值表 的真值表描述了ab的真值如何依赖 于a和b的真值.abab 001 011 100 111Lu Chaojun, SJTU 21与推理 的最重要用途是进行命题间的推理. 如果已知ab为真,那么只要a为真,必能 推知b为真. 绝不可能a真而b假. 此即传统逻辑所称modus ponens推理规则. 肯定前件式,或称分离规则ab 若a则ba ab b21Lu Chaojun, SJTU 22与日常用语的差异 称为实质蕴涵(material implication),与 日常用语“如果那么”有不
10、同. 因果联系? 日常用语的“如果a那么b”表明a和b有因果联系. 而只反映a和b的真值关系,与因果无关. a为假时,不论b的真假, ab都为真. “如果雪是黑的,那么1=2.”是个真命题! 若对此不满,可给出不同的蕴涵定义.22Lu Chaojun, SJTU 23的例子 1.令a:“224.” a1:“225.”b:“雪是白的.” b1:“雪是黑的.”则a b为真a1 b为真a1 b1为真a b1为假 2.令a:“陆老师讲课.”b:“他来听课.”则“只有陆老师讲课他才来听课”应译为ba.23Lu Chaojun, SJTU 24双条件词“” 双条件/等价(biconditional /eq
11、uivalence): 将两个命题a和b联结起来,构成一个新的 命题ab,表达“等价于” “当且仅当”等. 读作: a等价b, a当且仅当b 的严格定义可用真值关系给出:ab为真 iff a和b真值相同24Lu Chaojun, SJTU 2525的真值表 的真值表描述了ab的真值如何依赖 于a和b的真值. 验证: ab和(ab)(ba)真值表相同abab 001 010 100 111Lu Chaojun, SJTU 26与日常用语的差异 和蕴含一样,并不意味着有因果联系. 例如“225 太阳从西边出来”是真的.26Lu Chaojun, SJTU 27的例子令a:“ABC是等腰三角形.”b
12、:“ABC中有两个角相等.” 则ab表达了“ABC是等腰三角形当且仅 当ABC中有两个角相等”. 就此例而言: ab为真. 若把“等腰”换成“直角”,则ab为假.27Lu Chaojun, SJTU 28关于联结词 ,是最常用的. 也有用不同符号的: , , +, , 还可定义其他联结词 如异或但既不常用,又都可由上述五个联结词 表示出来.(稍后讨论) 联结词,对应着数字电路的门电路,可 见命题逻辑(布尔逻辑)是数字电路分析和 设计的理论基础和工具.28Lu Chaojun, SJTU 29关于自然语句的符号化 将自然语句翻译成符号化的命题 (1)根据自然语句的含义,确定若干简单命题,并 用命
13、题符号a, b, c, 表示之; (2)根据自然语句的含义,确定简单命题之间的 关系,并用命题联结词将它们联结起来. 可能需要仔细考察自然语句的含义,才能 抽取出隐含的简单命题和联结词.29Lu Chaojun, SJTU 30例子(1)张三不是学生. 令a:张三是学生.则(1): a. 令a:张三不是学生. 如何? (2)张三既聪明又用功. 令a:张三聪明. b:张三用功.则(2):ab. 令a:张三既聪明又用功. 如何? 思考:张三虽然聪明但不用功. (3)张三一感冒就发烧. 令a:张三感冒. b:张三发烧.则(3):ab.30Lu Chaojun, SJTU 31例子(续)(4)张三和李
14、四是学生. 令a:张三是学生. b:李四是学生.则(4):ab. 思考:张三和李四是表兄弟.也用? (5)张三或李四当班长. 令a:张三当班长. b:李四当班长.则(5):ab? 不可兼或!(5)应表示为:(ab)(ab). 思考:张三和李四至少一人是学生.ab合适. 思考:张三或李四都可当班长.也用?31Lu Chaojun, SJTU 3232主要内容命题与命题联结词 命题公式 等值演算 命题公式的范式 联结词的功能完全集 永真蕴涵式 命题逻辑推理Lu Chaojun, SJTU 33命题公式 问题:通过联结词构成复杂命题时,如何才 是有意义的命题? 例如: abc的意义明确吗? 定义(命
15、题公式):(1)命题常量和命题变量是命题公式. (2)如果A、B是命题公式,则(A), (AB), (AB), (AB)和(AB)也是命题公式. (3)所有命题公式都通过(1)(2)得到.33关于命题公式定义 符号表:这里隐含规定使用大小写字母(可带下 标),联结词,圆括号. 这种定义方式是形式系统常用的合式定义,所定 义的公式称为合式公式(wff). (1)(2)是归纳定义的奠基和归纳步骤,(3)并不是 多余的一句话.(Why?) 为简化括号的使用,可规定联结词的优先级(由 高到低): 同级:自左到右次序 最外层括号常省略Lu Chaojun, SJTU 34Lu Chaojun, SJTU 35判断符号串是否wff 根据合式定义,层层归约,直到原子命题即 可判断. 例 (ab) (a(ab) (ab)(b
