math-chap1-1.离散数学-命题逻辑

庄伯金bjzhuang@1第一章命题逻辑课件下载地址：/Lecture.php庄伯金bjzhuang@2主要内容命题的基本概念等值演算范式推理理论庄伯金bjzhuang@3命题的基本概念命题的定义能判断真假的陈述句命题的两个关键要素必须是陈述句能明确地判断真假命题的真值判断为正确的命题，其真值为真（1）；判断为错误的命题，其真值为假（0）。庄伯金bjzhuang@4命题的例4是素数。x大于y。充分大的偶数等于两个素数之和。(歌德巴赫猜想)2020年5月1日北京的天气是雨天。请不要吸烟！这朵花真美丽啊！我正在说假话。你现在好吗？庄伯金bjzhuang@5命题符号化命题常用小写字母表示，如p：4是素数命题的真值表示：1表示真0表示假简单命题不能被分解为更简单的陈述句的命题也称为原子命题命题常项与命题变项命题常项：真值可以确定；命题变项：真值可以变化。本质不是命题。庄伯金bjzhuang@6复合命题及联结复合命题：由简单命题通过联结词联结而成的命题。常见联结词否定联结词合取联结词析取联结词蕴涵联结词等价联结词庄伯金bjzhuang@7例P：今天是星期二。¬p：今天不是星期二。q：所有人都来上课了。¬q：不是所有人来上课了。有人没来上课。否定式定义：复合命题“非p”称为p的否定式，记作¬p。¬为否定联结词。¬p为真当且仅当p为假。即¬p表示对p的真值取反。p¬p1001庄伯金bjzhuang@8例小李既勤奋又聪明。小李不仅勤奋而且聪明。小李虽然聪明，但是不勤奋。小李和小王都很勤奋。小李和小王是同学。注：并不是所有的“和”、“与”都表示合取关系。合取式定义：复合命题“p并且q”称为p与q的合取式，记作p∧q。∧为合取联结词。p∧q为真当前仅当p与q同时为真。其他情况时p∧q为假。pqp∧q111100010000庄伯金bjzhuang@9例小李爱唱歌或者爱打篮球。小李在打篮球或者在踢足球。小李可以坐火车或者乘飞机回家。析取式定义：复合命题“p或者q”称为p与q的析取式，记作p∨q。∨为析取联结词。p∨q为假当且仅当p与q同时为假。其他情况p∨q为真。pqp∨q111101011000庄伯金bjzhuang@10析取式自然语言中的“或”具有二义性，与析取式中的“或”含义不完全相同。析取式可表示“相容或”和“不同时为真排斥或”；“能同时为真的排斥或”可用“异或”关系表示。庄伯金bjzhuang@11蕴涵式定义：复合命题“如果p，则q”称为p与q的蕴涵式，记作p→q。p→q为假当前仅当p为真且q为假。其他情况时，p→q为真。pqp→q111100011001自然语言中p与q具有联系，而数理逻辑中p与q可以没有联系。例如果3＋3＝6，则雪是黑的。如果3+36，则雪是黑的。庄伯金bjzhuang@12蕴涵式p→q在逻辑上表明p为q的充分条件，q为p的必要条件。例只要a能被4整除，则a一定能被2整除。a能被4整除，仅当a能被2整除。除非a能被2整除，a才能被4整除。只有a能被2整除，a才能被4整除。只有a能被4整除，a才能被2整除。庄伯金bjzhuang@13等价式定义：复合命题“p当且仅当q”称为p与q的等价式，记作p↔q。↔称作等价联结词。p↔q为真当且仅当p与q真值相同。其他情况时，p↔q为假。pqp↔q111100010001p↔q在逻辑上表明p与q互为充要条件。例：若今天为1号，则明天是2号，反之亦然。今天是雨天当且仅当雪是黑的。庄伯金bjzhuang@14基本复合命题真值表pq¬pp∧qp∨qp→qp↔q0010011011011010001001101111庄伯金bjzhuang@15联结词的优先顺序()¬∧∨→↔庄伯金bjzhuang@16练习判断下列命题的真值若2＋2＝4，则3＋3＝6若2＋2＝4，则3＋3≠6若2＋2≠4，则3＋3＝6若2＋2≠4，则3＋3≠62＋2＝4当且仅当3＋3＝62＋2＝4当且仅当3＋3≠62＋2≠4当且仅当3＋3＝62＋2≠4当且仅当3＋3≠6庄伯金bjzhuang@17练习将下列命题符号化2是偶数又是素数他一边吃饭一边看电视如果天下雨，他就乘公共汽车上班只有天下雨，他才乘公共汽车上班不经一事，不长一智庄伯金bjzhuang@18练习设p、q的真值为0，r、s的真值为1，求下列命题公式的真值p∨(q∧r)(p↔r)∧(¬q∨s)庄伯金bjzhuang@19命题公式命题常项（命题常元）：简单命题，真值唯一确定。命题变项（命题变元）：真值可以变化的陈述句。命题常项和命题变元都用小写字母表示。合式公式（命题公式）：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。庄伯金bjzhuang@20合式公式的定义递归定义1.单个命题变项是合式公式，并称为原子命题公式；2.若A是合式公式，则(¬A)也是合式公式；3.若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A↔B)也是合式公式；4.只有有限次地应用1－3形式的符号串才是合式公式。子公式定义若A为合式公式，B为A的一部分，且B也是合式公式，则称B为A的子公式。庄伯金bjzhuang@21公式的赋值定义设A为一命题公式，p1,p2,…,pn,为所有在A中出现的命题变项。给p1,p2,…,pn指定一组真值，称其为A的一个赋值或解释。若指定的一组赋值使A的真值为真，则称这组值为A的成真赋值。若指定的一组赋值使A的真值为假，则称这组值为A的成假赋值。将一个命题公式在所有赋值下的情况列成表，称为这个公式的真值表。n个命题变项共有2n组赋值。庄伯金bjzhuang@22例p∨(q∧r)的真值表pqrq∧rp∨(q∧r)0000000100010000111110001101011100111111庄伯金bjzhuang@23例p∨(¬p∨q)的真值表pq¬p¬p∨qp∨(¬p∨q)00111011111000111011庄伯金bjzhuang@24例p∧(¬p∧q)的真值表pq¬p¬p∧qp∧(¬p∧q)00100011101000011000庄伯金bjzhuang@25重言式（永真式）：所有的赋值都是A的成真赋值。矛盾式（永假式）：所有的赋值都是A的成假赋值。可满足式：至少存在一组赋值使A为真。庄伯金bjzhuang@26等值演算等值式（等价式）设A，B为两命题公式，若A↔B为重言式，则称A与B为等值式，记为AB。不是逻辑联结词，表示对任意的赋值，A与B的值相同。↔是等价联结词，它与不能混为一谈。等值式的性质（等价关系的通性）自反性：AA；对称性：若AB，则BA；传递性：若AB和BC，则AC。庄伯金bjzhuang@27例p→q与¬p∨q是否等值？庄伯金bjzhuang@28基本等值规律(1)双重否定律A¬¬A等幂律AA∨AAA∧A交换律A∨BB∨AA∧BB∧A结合律A∨(B∨C)(A∨B)∨CA∧(B∧C)(A∧B)∧C庄伯金bjzhuang@29基本等值规律(2)分配律A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)德.摩根律¬(A∨B)¬A∧¬B¬(A∧B)¬A∨¬B吸收律A∨(A∧B)AA∧(A∨B)A庄伯金bjzhuang@30基本等值规律(3)零律A∨11A∧00同一律A∨0AA∧1A排中律A∨¬A1矛盾律A∧¬A0庄伯金bjzhuang@31基本等值规律(4)蕴涵等值式A→B¬A∨B等价等值式A↔B(A→B)∧(B→A)(¬A∨B)∧(¬B∨A)假言易位A→B¬B→¬A等价否定等值式A↔B¬A↔¬B归谬论(A→B)∧(A→¬B)¬A庄伯金bjzhuang@32置换规则设Φ(A)为含公式A的命题公式，Φ(B)为用公式B置换了A的命题公式，若AB，则Φ(A)Φ(B)。利用等值规律及置换规则可以进行等值演算。例(p→q)→(¬q→¬p)¬(q→p)∧p(¬p→q)→(q→¬p)(p∨q)→r¬(p→(p∨q))∧r庄伯金bjzhuang@33联结词的完备集问题：含n个命题变项的命题公式其真值表的可能性有多少种？n元真值函数：F：{0,1}n→{0,1}为n元真值函数。联结词完备集：设S是一个联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。{¬,∧,∨}{¬,∧}{¬,∨}{¬,→}庄伯金bjzhuang@34对偶对偶的定义：在仅含有¬,∧,∨的命题公式A中，将∧换成∨，∨换成∧，若A中含0或1，将0换成1，1换成0，所得的命题公式称为A的对偶式，记为A*。定理：设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，若将A和A*写成n元函数形式，则：(1)¬A(p1,p2,…,pn)A*(¬p1,¬p2,…,¬pn)(2)A(¬p1,¬p2,…,¬pn)¬A*(p1,p2,…,pn)对偶原理：设A、B为两命题公式，若AB，则A*B*。庄伯金bjzhuang@35范式的概念命题公式的规范表示方法析取范式合取范式文字：命题变项及其否定式统称文字简单析取式仅有有限个文字构成的析取式简单合取式仅有有限个文字构成的合取式定理：一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式庄伯金bjzhuang@36析取范式定义由有限个简单合取式构成的析取式例p∨q(¬p∧q)∨r析取范式性质析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式庄伯金bjzhuang@37合取范式定义:由有限个简单析取式构成的合取式例p∧q(p∨¬q)∧r合取范式性质合取范式是重言式，当且仅当它的每个简单析取式是重言式庄伯金bjzhuang@38范式存在定理定理：任一命题公式都存在与之等值的析取范式（合取范式）。求范式的步骤利用蕴涵等值式和等价等值式消去联结词→、↔。用双重否定律消去否定联结词，利用德.摩根律将否定联结词内移。利用分配律求析取范式或合取范式。例：(p→q)↔r范式的求解例：(p→q)↔r庄伯金bjzhuang@39庄伯金bjzhuang@40极小项与极大项极小项的定义在含n个命题变项的简单合取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。极大项的定义在含n个命题变项的简单析取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。n个命题变项共可形成2n个极小项和2n个极大项。庄伯金bjzhuang@41极小项的成真赋值每个极小项仅有一个成真赋值每个极小项的成真赋值均不相同可以利用不同的成真赋值区别每个极小项，给予标记二元极小项取值成真赋值简记名称¬p∧¬q100m0¬p∧q101m1p∧¬q110m2p∧q111m3庄伯金bjzhuang@42极大项的成假赋值每个极大项仅有一个成假赋值每个极大项的成假赋值均不相同可以利用不同的成假赋值区别每个极大项，给予标记二元极大项取值成假赋值简记名称p∨q000M0p∨¬q001M1¬p∨q010M2¬p∨¬q011M3庄伯金bjzhuang@43主析取范式与主合取范式主析取范式的定义若A的命题公式由若干个极小项进行析取构成，则称该析取范式为A的主析取范式从主析取范式中很容易得到成真赋值主合取范式的定义若A的命题公式由若干个极大项进行合取构成，则称该合取范式为A的主合取范式从主合取范式中很容易得到成假赋值定理：任何命题公式都存在与之等值的主析取（合取）范式，且唯一。庄伯金bjzhuang@44主析取范式的求解方法(1)用等值演算求得析取范式依次扫描析取范式中的每个简单合取式B若B为极小项，则继续扫描下一个若B不为极小项，将不含的命题变项p及其否定式¬p用等值变换添入BB∧(p∨¬p)(B∧p)∨(B∧¬p)

消去重复出现的命题变项、极小项和矛盾式。庄伯金bjzhuang@45主析取范式的求解方法(2)根据公式构造真值表写出每个公式成真赋值对应的极小项将极小项进行析取，即得主析取范式庄伯金bjzhuang@46主析取范式例：求(p→(q∧r))∧(¬p→(¬q∧¬r))庄伯金bjzhuang@47主合取范式的求解方法(1)用等值演算求得合取范式依次扫描合取范式中的每个简单析取式B若B为极大项，则继续扫描下一个若B不为极大项，将不含的命题变项p及其否定式¬p用等值变换添入BB∨(p∧¬p)(B∨p)∧(B∨¬p)

消去重复出现的命题变项、极大项和重言式。庄伯金bjzhuang@48主合取范式的求解方法(2)根据公式构造真值表写出每个公式成假赋值对应的极大项将极大项进行合取，即得主合取范式庄伯金bjzhuang@49主合取范式例：求(p→(q∧r))∧(¬p→(¬q∧¬r))庄伯金bjzhuang@50主析取范式与主合取范式主析取范式与主合取范式之间的关系？庄伯金bjzhuang@51推理的形式结构设两命题公式A、B，若A→B为重言式，则称A蕴涵B，记为AB。设A1、A2、...、An、B为命题公式，若A1∧A2∧...∧AnB，则称B为A1、A2、...、An的逻辑结论或有效结论，也称B可由一组前提A1、A2、...、An逻辑推出。记为A1，A2，...，AnB。正确推理的本质是A1∧A2∧...∧An→B为重言式。当A1∧A2∧...∧An为假时，不论B是真是假，A1∧A2∧...∧An→B均为真。所以B为有效结论并不意味B为真。庄伯金bjzhuang@52推理的基本方法简单证明法：证明A1∧A2∧...∧An→B是重言式，即A1∧A2∧...∧An→B1。真值表法等值演算法主析取范式法例：若a能被4整除，则a能被2整除。因为a能被2整除，所以a能被4整除。庄伯金bjzhuang@53推理的基本方法(2)直接构造证明法由给定的一组前提出发，利用推理规则逐步演算得到结论。常用推理规则前提引入规则：在证明过程的任何步骤都可以将前提引入使用结论引入规则：在推理中，若已证出结论B，则B可以引入到以后的推理中作为前提使用置换规则：命题公式中任何