命题逻辑的基本概念课件课件

命题逻辑的基本概念LuChaojun,SJTU**主要 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 命题命题联结词合式公式重言式LuChaojun,SJTU**什么是命题?命题(proposition):是一个非真即假的陈述句.是陈述句,而非命令句、疑问句或感叹句等. 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达的内容可判断真假,而且非真即假.真假的判定:与事实是否相符.不能不真又不假，也不能又真又假.真值(truthvalue):命题具有两种可能的取值,即真(true)和假(false).常写做T和F.称为二值逻辑.LuChaojun,SJTU**例子:命题(1)雪是白的.是命题,真值为T.(2)雪是黑的.是命题,真值为F.(3)好大的雪啊!不是命题(4)偶数可表示成两个素数之和.(Goldbach猜想)是命题,目前不知其真假.(5)1+10l＝110.相当于陈述句“1加101等于110”.在十进制范围中真值为F,在二进制范围中真值为T.并不意味着同一命题有两个真值!在不同数制中是不同的命题.LuChaojun,SJTU**简单命题和复合命题简单命题:简单句,不包含任何“并且”,“或者”之类的联结词.例如:雪是白的.又叫原子命题:不可分割.如果按主语谓语 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ,则是谓词逻辑的做法.复合命题:成分命题经联结词联结而成.例如:张三是教师并且雪是白的.又叫分子命题:可以分割.联结词例子:并且,或者,非,如果…那么…LuChaojun,SJTU**复合命题的真值复合命题的真值是成分命题的真值的函数.当成分命题被赋予任一真值组合时,联结词完全决定了复合命题的真值.例如:“张三学英语且李四学日语”由简单命题“张三学英语”,“李四学日语”经联结词“且”联结而成.当这两个简单命题真值均为T时,该复合命题真值才为T.LuChaojun,SJTU**命题联结词命题联结词(propositionalconnective):将命题联结起来构成新命题.将命题视为运算对象,命题联结词视为运算符,从而构成运算表达式.比较:初等代数中运算对象是a,b,c等,运算符有等常用命题联结词:,,,,LuChaojun,SJTU**否定词“”否定(negation):命题P加上否定词就形成一个新命题P,表达的是对P的否定.读作:非P的定义可用真值关系精确给出:P为真iffP为假.这种真值关系常常用真值表(truthtable)来表示.LuChaojun,SJTU**的真值表真值表描述了P的真值如何依赖于P的真值.当命题变项不多时,真值表是研究真值关系的重要工具.PPTFFTLuChaojun,SJTU**的例子1.令P:张三去看球赛了.则P:张三没有去看球赛.2.令Q:今天是星期三.则Q:今天不是星期三.LuChaojun,SJTU**合取词“”合取(conjunction):联结两个命题P和Q构成一个新命题PQ,表达“P并且Q”.读作:P与Q,P、Q的合取.的定义可用真值关系精确给出:PQ为真iffP和Q都为真LuChaojun,SJTU**的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.PQPQFFFFTFTFFTTTLuChaojun,SJTU**与日常用语的差异日常用语里的“和”、“与”、“并且”一般表示同类事物的并列;而形式逻辑中的只关心命题与命题之间的真值关系,并不考虑两命题是否有意义上的联系.例如:“张三18岁并且今天天气晴朗”日常用语中的某些意义用表达不出来例如:“这台机器质量很好,但是很贵”用表达时并无“转折”的语气.LuChaojun,SJTU**析取词“”析取(disjunction):联结两个命题P、Q构成新命题PQ,表达“P或者Q”.读作:P或Q,P、Q的析取.的定义可用真值关系精确给出:PQ为假iffP和Q都为假LuChaojun,SJTU*的例子1.令P:今天刮风Q:今天下雨则PQ:今天刮风或者下雨.2.令A:2小于3B:雪是黑的则AB:2小于3或者雪是黑的由于2小于3是真的,所以AB必为真,尽管“雪是黑的”为假.*LuChaojun,SJTU*与日常用语的差异日常用语中的“或”往往具有“不可兼”的涵义,即二选一.例如:你去或者我去.也可定义“不可兼或”,也叫“异或”.*LuChaojun,SJTU*蕴涵词“”蕴涵(implication):将两个命题P、Q联结起来,构成一个新的命题PQ,表达“如果P成立那么Q成立”.读作:P蕴涵QP称前件(antecedent),Q称后件(consequent).的定义可用真值关系精确给出:PQ为假iffP真而Q假*LuChaojun,SJTU**的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.PQPQFFTFTTTFFTTTLuChaojun,SJTU*与推理的最重要用途是进行命题间的推理.如果已知PQ为真,那么只要P为真,必能推知Q为真.绝不可能P真而Q假.此即传统逻辑所称modusponens推理规则.肯定前件式,或称分离规则PQ∵若P则QP∵PQ∴Q*LuChaojun,SJTU*与日常用语的差异称为实质蕴涵(materialimplication),与日常用语“如果…那么…”有不同.因果联系?日常用语的“如果P那么Q”仅用于P和Q有内容上的因果联系.只反映P和Q的真值间的关系:不能P真而Q假,与命题内容无关.P为假时,不论Q的真假,PQ都为真.存在不同的蕴涵定义.*LuChaojun,SJTU*双条件词“”双条件/等价(biconditional/equivalence):将两个命题P、Q联结起来,构成一个新的命题PQ,表达“等价于”“当且仅当”等.读作:P等价Q,P当且仅当Q的定义可用真值关系精确给/出:PQ为真iffP和Q真值相同*LuChaojun,SJTU**的真值表的真值表描述了PQ的真值如何依赖于P和Q的真值.验证:PQ和(PQ)(QP)真值表相同PQPQFFTFTFTFFTTTLuChaojun,SJTU*关于联结词联结词是由命题定义新命题的基本方法.,,,,是最常用的.其他符号:～,·,+,,还可定义其他联结词,但既不常用,又都可由这五个联结词表示出来.事实上,只需两个基本联结词:,或者,联结词,,对应着数字电路的与门,或门和非门电路.可见命题逻辑(布尔逻辑)是数字电路分析和 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的理论基础和工具.*小结数理逻辑的简明历史命题命题连接词,,,,真值表每个命题可以看作取值为{0,1}的变量命题连接词可以看作定义在命题上的函数真值表的各项就是函数值{0,1}*LuChaojun,SJTU*命题公式在由命题变项通过联结词构成复杂命题时,如何才是有意义的命题?例如:PQR.(意义明确吗?)定义(命题公式):(1)命题变元(原子命题)是命题公式.(2)如果、是公式,那么(),(),(),()和()是命题公式.(3)命题公式仅限于此.上面这种定义方式是形式系统常用的合式定义,所定义的公式称为合式公式(well-formedformula,简记为wff).*1+2;2+4/5;3*3+11+2-;1-/3LuChaojun,SJTU*判断符号串是否wff根据公式的合式定义,层层归约,直到原子命题即可判断.例子(PQ)(P(PQ))(((PQ)(QR))(PR))(P)这个公式是wff?((PQ)(Q))(PQ*LuChaojun,SJTU*简写约定为了减少括号的数量,可以引入优先级的约定.例如按,,,,的次序安排优先级.相同联结词按从左到右的优先次序.例:(P(QR))可写成P(QR),进而写成PQR.(P(PR))可写成P(PR),但不能写成PPR.*LuChaojun,SJTU*无括号表示法前面的wff定义采用联结词中缀表示法,需要用括号区分运算次序.波兰表示法(前缀):AB表示为AB逆波兰表示法(后缀):AB表示为AB(逆)波兰式无需括号,便于计算机处理.例:(P(QR))波兰式:PQR逆波兰式:PQR*LuChaojun,SJTU*命题公式的真值(语义)命题公式的真值由其成员命题的真值决定.常用真值表方法计算.设公式由成分命题P1,…,Pn联结而成.对P1,…,Pn的真值指派(assignment)决定了的真值,称为的解释(interpretation),可表示为真值表的一行:P1…PnT…FT总共有2n个解释,构成的真值表(2n行).*LuChaojun,SJTU*重言式若公式在任一解释I下值都为T,就称为重言式(或永真式,tautology).例如:PP是重言式.重言式由,,,联结所得公式仍是重言式.重言式反映了逻辑规律.若公式在某个解释I0下值为T,则称是可满足的(satisfiable).例如:PQ在I0=(T,F)下值为T,所以是可满足的.若公式在任一解释I下值都为F,就称为矛盾式(永假式或不可满足式,contradiction).例如:PP*LuChaojun,SJTU*三类公式间关系定理:(练习)1.永真iff永假.2.可满足iff非永真.3.非永假iff可满足.*LuChaojun,SJTU*代入保持重言式代入规则:将公式中的命题变元P的所有出现都替换成公式.记为[P/].针对命题变项代入.处处代入.定理:若是重言式,则[P/]也是重言式.*LuChaojun,SJTU*例:代入代入时被替换的是命题变元(原子命题),而不能是复合命题.例如:可用(RS)来替换(PP)中的P,结果仍是重言式;但若用Q替换(PP),则不能保持重言式.代入时必须对同一命题变项处处替换以同一公式.例如:上例中用Q只替换一处P得到的QP不是重言式.*为什么?LuChaojun,SJTU*利用代入规则证明重言式例1:证明(RS)(RS)为重言式。因PP是重言式,以(RS)代入P,得(RS)(RS).必是重言式.例2:证明((RS)((RS)(PQ)))(PQ)为重言式.易验证:(A(AB))B是重言式(此公式表达的正是modusponens推理规则),A以RS代入,B以PQ代入即可证明.*LuChaojun,SJTU*自然语句的形式化表示为了进行逻辑演算,需要首先对自然语句用形式化的逻辑语言进行表示.方法:1.根据自然语句的含义,确定若干简单命题,并用命题符号P、Q…表示之;2.根据自然语句的含义,确定简单命题之间的关系,并用命题联结词将它们联结起来.可能需要仔细考察自然语句的含义,才能抽取出隐含的简单命题和联结词.*LuChaojun,SJTU*例子(1)张三不是学生.令P:张三是学生.则(1):P.令P:张三不是学生.如何?(2)张三既聪明又用功.令P:张三聪明.Q:张三用功.则(2):PQ.令P:张三既聪明又用功.如何?思考:张三虽然聪明但不用功.(3)张三一感冒就发烧.令P:张三感冒.Q:张三发烧.则(3):PQ.*LuChaojun,SJTU*例子(续)(4)张三和李四是学生.令P:张三是学生.Q:李四是学生.则(4):PQ.思考:张三和李四是表兄弟.也用?(5)张三或李四当班长.令P:张三当班长.Q:李四当班长.则(5):PQ?不可兼或!(5)应表示为:(PQ)(PQ).思考:张三和李四至少一人是学生.PQ合适.思考:张三或李四都可当班长.也用?*LuChaojun,SJTU*逻辑趣题某岛上只有骑士(knight)和无赖(knave)两种居民.骑士总说真话,无赖总说假话.假如你去该岛后遇到甲乙两人,甲说:“乙是骑士.”乙说:“我们两人是不同类型的人.”问甲和乙分别是什么人?*解答P:甲是骑士Q:乙是骑士PQ=T;QP=T;LuChaojun,SJTU*作业题习题1：1-63月16号交*End