第十章 命题逻辑

数理逻辑数理逻辑•数理逻辑是用数学方法研究形式逻辑中推理规律的一种理论.•数理逻辑的研究对象：–从宏观上讲,数理逻辑是数学的基础,它的研究分证明论、模型论、递归论和集合论等四大理论–从狭义上讲,它是研究形式逻辑推理规则的一门数学.逻辑归纳性辩证逻辑演绎性数理逻辑研究对象形式逻辑数理逻辑•数理逻辑的研究方法–采用数学的方法研究演绎性推理形式逻辑的规律.–引进一套符号体系的方法,因此数理逻辑又称符号逻辑.•本篇内容：–命题逻辑–谓词逻辑–命题逻辑和谓词逻辑的公理化证明第十章命题逻辑•命题逻辑是数理逻辑的基础,它以命题为研究对象,研究基于命题的符号逻辑体系及推理规律,它也可称命题演算.10.1.1命题•命题：能判断真假的陈述句•真值：命题的值称真值，真值有T,F两种•例：1)雪是黑的2)1+101=1103)别的星球有生物4)我正在说谎5)天气多好啊！6)我学英语,或者我学日语7)明天是否开大会？命题命题命题悖论，不是命题不是陈述句命题不是陈述句10.1.1命题•原子命题：最简单的不可再分的命题•复合命题：由联结词,标点符号和原子命题复合构成的命题•一般用P,Q,R…等大写拉丁字母表示命题•命题常量：命题标识符如表示确定的命题•命题变元：命题标识符只表示任意命题的位置标志–命题变元可以表示任意命题,所以它不能确定真值,故不是命题10.1.2命题联结词•常用的5个命题联结词•1)“并且”(合取)P∧Q：“P并且Q”,P与Q的合取式,而P、Q分别叫做此合取式的合取项.真值表PQP∧QTTTTFFFTFFFF10.1.2命题联结词•例：王华的成绩很好并且打得一手好球解：P:王华的成绩很好Q:王华打得一手好球王华的成绩很好并且打得一手好球:P∧Q•对“并且”可以有多种不同表达方式：“同时”、“和”、“与”、“同”、“以及”、“而且”、“不但…而且…”、“既…又…”、“又”、“尽管…仍然…”、“虽然…依旧…”……•例：尽管他生病但他仍坚持工作10.1.2命题联结词•2)“或者”(析取)P∨Q：”P或者Q”,P与Q的析取式,而P、Q分别叫做此析取式的析取项.真值表PQP∨QTTTTFTFTTFFF10.1.2命题联结词•例：今天晚上我写字或看书解：P:今天晚上我写字Q:今天晚上我看书今天晚上我写字或看书:P∨Q•对“或者”可以有多种不同表达方式：“或”、“或许”、“可能”……•例：明天我可能看电影也可能逛公园10.1.2命题联结词•3)“否定”¬P：“非P”真值表P¬PTFFT10.1.2命题联结词•例：赵玲不是个好学生解：P:赵玲是个好学生赵玲不是个好学生:¬P•对“否定”可以有多种不同表达方式：“非”、“不”、“没有”、“无”、“并非”、“并不”……•例：他并不喜欢打球10.1.2命题联结词•4)“蕴含”(条件)P→Q：”P蕴含Q”,“如果P则Q”.P称为P→Q的前件,Q称为P→Q的后件.真值表PQP→QTTTTFFFTTFFT10.1.2命题联结词•例：如果明天天气晴朗,则举行运动会解：P:明天天气晴朗Q:举行运动会如果明天天气晴朗,则举行运动会:P→Q•对“蕴含”可以有多种不同表达方式：“当…则…”、“若…那么…”、“假如…那么…”……•例：倘若他生病了他就不参加这次会议10.1.2命题联结词•5)“等价”(双条件)P↔Q：P与Q的等价式,“P等价Q”,P、Q分别叫此等价式的两端.真值表PQP↔QTTTTFFFTFFFT10.1.2命题联结词•例：23当且仅当3-20解：P:23Q:3-2023当且仅当3-20:P↔Q•对“等价”可以有多种不同表达方式：“充分必要”、“只有…才能…”、“相同”、“相等”、“一样”、“等同”……•例：只有睡觉才能消除疲劳10.1.2命题联结词•在命题联结词中有些地方与一般习惯用语是不同的：1)两个逻辑上完全没有联系的命题可加以命题联结词而形成新的复合命题.2)有的联结词在日常用语中可有多种逻辑含义,但在命题逻辑中有确定含义,如命题逻辑中的“或”是“可兼或”的或.3)对于“蕴含”,在命题逻辑中,当其前件为假时,则不论其后件是真还是假其整个蕴含式一定为真.4)命题联结词是命题间的联结词而不是名词或形容词间的联结词.10.1.3复合命题•由原子命题经命题联结词可构成各种形式的复合命题,在复合命题中，为减少括号的使用，作出以下规定：1)5个联结词的结合能力强弱顺序为：“否定¬”＞“合取∧”＞“析取∨”＞“蕴含→”＞“等价↔”2)规定具有相同结合能力的联结词,按其出现的先后次序,先出现者先运算3)最外层括号可省去•例:(¬((P∧(¬Q))∨R)→((R∨P)∨Q)•可写成：¬(P∧¬Q∨R)→R∨P∨Q10.1.3复合命题•例10.13设命题P为“明天上午七点下雨”,Q为“明天上午七点下雪”,R为“我去学校”1)如果明天上午七点不是雨夹雪则我去学校¬(P∧Q)→R2)如果明天上午七点不下雨并且不下雪则我去学校¬P∧¬Q→R3)如果明天上午七点下雨或下雪则我不去学校P∨Q→¬R4)明天上午七点我将雨雪无阻一定去学校P∧Q∧R∨¬P∧Q∧R∨P∧¬Q∧R∨P∧¬Q∧R10.1.3复合命题5)只有当明天上午七点不下雪并且不下雨时我才去学校¬P∧¬Q↔R•例10.14：命题“说数理逻辑枯燥无味或毫无价值,那是不对的”,翻译成命题公式.•解；P:数理逻辑有味Q:数理逻辑有价值¬(¬P∨¬Q)10.1.3复合命题•例10.15“除非你陪伴我或代我叫辆车子,否则我不出去”,翻译成命题公式.•解：P:你陪伴我Q:你代我叫辆车R:我出去¬P∨¬Q↔¬R或P∨Q↔R•例10.16“天黑了,我得回家了”•解：P:天黑了Q:我得回家了P↔Q10.1.3复合命题•例10.17计算机机房规则:“凡进入机房者,必须换拖鞋,穿工作服;否则罚款人民币10元”,翻译成命题公式.•解：P:某人进入机房Q:某人换拖鞋R:某人穿工作服S:某人需罚款人民币10元凡进入机房者,必须换拖鞋,穿工作服P→Q∧R否则罚款人民币10元：¬(P→Q∧R)↔S10.1.3复合命题•例:“除非你年满18岁，否则只要你身高不足1.6米就不能乘坐过山车”,翻译成命题公式.•解：找出原子命题：P:你年满18岁Q:你身高不足1.6米R:你乘坐过山车A：只要你身高不足1.6米就不能乘坐过山车:=只要Q就非R：Q→¬R除非你年满18岁，否则A:=如果非P则A:¬P→(Q↔¬R)10.1.3复合命题•关于物质有以下两种定义：1)占据空间、有质量并且不断变化的客体称为物质.2)占据空间、有质量的客体称为物质,而物质是不断变化的.请问关于物质的这两种定义有什么区别?试用命题逻辑进行分析.10.1.3复合命题•解：设命题P:它占据空间Q:它有质量R:它不断变化S:它是物质定义(1):P∧Q∧R↔S定义(2):(P∧Q↔S)∧(S→R)不同点在于：定义(2)含有“如若P∧Q为真,则必有R为真”的意思,即“占据空间并且有质量的客体一定是不断变化的客体”,而定义(1)没有这个含义.10.2命题变元与命题公式•常值命题是一个特定的命题,它只有“T”与“F”两种•命题变元是一个任意的没有赋予具体内容的命题.•定义10.1•以“真”“假”为其变域的变元称为命题变元,用P,Q,R…表示,它也可以称为命题.10.2命题变元与命题公式•由命题经命题联结词可构成命题逻辑公式,亦可叫命题公式或公式•定义10.2命题逻辑公式(简称公式)可按如下法则生成:1)命题是公式2)如果P是公式,则(¬P)是公式3)如果P,Q是公式,则(P∧Q),(P∨Q),(P→Q),(P↔Q)是公式4)公式由且仅由有限次使用(1)(2)(3)而得.即，命题公式是一个按上述法则由命题变元、命题联结词及圆括号组成的字符串.10.2命题变元与命题公式•一个命题公式的真假由组成它的命题的真假唯一确定,故命题公式可看成是一个以真、假为定义域,以真、假为值域的函数.•可以用真值表方法来确定一个命题公式的真假,此真值表称为命题公式真值表.•设有一个由n个命题变元P1,P2,…,Pn个所组成的公式,则此公式的真假由此n个命题变元所唯一确定.给n个命题变元P1,P2,…,Pn一组确定的值后,则公式亦可以得到一个确定的值.命题变元的一组确定的值叫做公式的一个指派.所有指派构成的公式的值即组成了此公式真值表.10.2命题变元与命题公式•例：¬(P∧Q)→(¬(P∧¬Q))的真值表PTTFFQTFTFP∧QTFFF¬(P∧Q)FTTT¬QFTFTP∧¬QFTFF¬(P∧¬Q)TFTT¬(P∧Q)→(¬(P∧¬Q))TFTT10.3重言式•定义10.3一个公式如果对其所有指派均取值为真,则称此类公式为永真公式或叫重言式(tautology).反之,一个公式如果对其所有指派均取值为假,则称此类公式为永假公式或叫矛盾.•定义10.4一个公式如果至少存在一个指派使其取值为真,则称此公式为可满足公式.10.3重言式•重言式的性质:1)两个重言式的否定是矛盾,矛盾的否定式重言式.2)两个重言式的合取、析取、蕴含、等价均为重言式.3)若两个公式的等价是重言式,则这两公式对任何指派必同真假.•如果等价式P↔Q为永真,则称为等价重言式,并记为•它们也可称为P与Q相等,记为P=Q•如果等价式P→Q为永真,则称为蕴含重言式,并记为PQPQ10.4命题逻辑的基本等式•交换律：(1)P∧Q=Q∧P(2)P∨Q=Q∨P(3)P↔Q=Q↔P•结合律：(4)(P∧Q)∧R=P∧(Q∧R)(5)(P∨Q)∨R=P∨(Q∨R)(6)(P↔Q)↔R=P↔(Q↔R)10.4命题逻辑的基本等式•分配律：(7)P∧(Q∨R)=(P∧Q)∨(Q∧R)(8)P∨(Q∧R)=(P∨Q)∧(Q∨R)(9)P→(Q→R)=(P→Q)→(Q→R)•否定深入：(10)¬¬P=P双否定律(11)¬(P∧Q)=¬P∨¬Q德•摩根定律(12)¬(P∨Q)=¬P∧¬Q德•摩根定律(13)¬(P→Q)=P∧¬Q(14)¬(P↔Q)=¬P↔Q=P↔¬Q10.4命题逻辑的基本等式•变元等同：(15)P∧P=P(16)P∨P=P(17)P∧¬P=F(18)P∨¬P=T(19)P→P=T(20)P→¬P=¬P(21)¬P→P=P(22)P↔P=T(23)P↔¬P=¬P↔P=FPQP→QTTTTFFFTTFFTPQP↔QTTTTFFFTFFFT10.4命题逻辑的基本等式•常值与变元的联结：(24)T∧P=P(25)F∧P=F(26)T∨P=T(27)F∨P=P(28)T→P=P(29)F→P=T(30)P→T=T(31)P→F=¬P(32)T↔P=P(33)F↔P=¬PPQP→QTTTTFFFTTFFTPQP↔QTTTTFFFTFFFT10.4命题逻辑的基本等式•联结词化归：(34)P∧Q=(¬P∨¬Q)(35)P∨Q=(¬P∧¬Q)(36)P→Q=¬P∨Q(37)P↔Q=(P→Q)∧(Q→P)=(¬P∨Q)∧(¬Q∨P)=(P∧Q)∨(¬P∧¬Q)10.4命题逻辑的基本等式(38)P→Q=¬Q→¬P证明：P→Q=¬P∨Q=¬P∨¬¬Q=¬¬Q∨¬P=¬Q→¬P(39)(P→Q)∧(P→R)=P→Q∧R证明：(P→Q)∧(P→R)=(¬P∨Q)∧(¬P∨R)=¬P∨Q∧R=P→Q∧R10.4命题逻辑的基本等式(40)P∨P∧Q=P证明：P∨P∧Q=P∧(Q∨¬Q)∨P∧Q=(P∧Q)∨(P∧¬Q)∨P∧Q=(P∧Q)∨(P∧¬Q)=P∧(Q∨¬Q)=P(41)P→(Q→R)=P∧Q→R证明：P→(Q→R)=P→¬Q∨R=¬P∨(¬Q∨R)=(¬P∨¬Q)∨R=¬(P∧Q)∨R=P∧Q→R10.4命题逻辑的基本等式•例10.23化简语句“情况并非如此:如果他不来那么我也不去”•解：P:他来Q:我去这句话即¬(¬P→¬Q)化简¬(¬P→¬Q)=¬(P∨¬Q)=¬P∧Q即化简为:他没来但是我去10.4命题逻辑的基本等式•例10.24试证语句“不会休息的人也不会工作,没有丰富知识的人也不会工作”