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

《math-chap1-1.离散数学_命题逻辑.ppt》由会员分享，可在线阅读，更多相关《math-chap1-1.离散数学_命题逻辑.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、math-chap1-1.离散数学_命题逻辑 Four short words sum up what has lifted most successful Four short words sum up what has lifted most successful individuals above the crowd: a little bit more. individuals above the crowd: a little bit more. -author -author -date-date主要内容n命题的基本概念命题的基本概念n等值演算等值演算n范式范式n推理理论推理理论命

2、题的基本概念n命题的定义命题的定义n能判断真假的陈述句能判断真假的陈述句n命题的两个关键要素命题的两个关键要素n必须是必须是陈述句陈述句n能明确地能明确地判断真假判断真假n命题的真值命题的真值n判断为判断为正确正确的命题，其真值为的命题，其真值为真（真（1）；n判断为判断为错误错误的命题，其真值为的命题，其真值为假（假（0）。命题的例n4是素数。是素数。nx大于大于y。n充分大的偶数等于两个素数之和。充分大的偶数等于两个素数之和。(歌德巴赫猜想歌德巴赫猜想)n2020年年5月月1日北京的天气是雨天。日北京的天气是雨天。n请不要吸烟！请不要吸烟！n这朵花真美丽啊！这朵花真美丽啊！n我正在说假话。

3、我正在说假话。n你现在好吗？你现在好吗？命题符号化n命题常用小写字母表示，如命题常用小写字母表示，如p：4是素数是素数n命题的真值表示：命题的真值表示：n1表示真表示真n0表示假表示假n简单命题简单命题n不能被分解为更简单的陈述句的命题不能被分解为更简单的陈述句的命题n也称为原子命题也称为原子命题n命题常项与命题变项命题常项与命题变项n命题常项：真值可以确定；命题常项：真值可以确定；n命题变项：真值可以变化。命题变项：真值可以变化。本质不是命题本质不是命题。复合命题及联结n复合命题：由简单命题通过联结词联结而成的命题。复合命题：由简单命题通过联结词联结而成的命题。n常见联结词常见联结词n否定联

4、结词否定联结词n合取联结词合取联结词n析取联结词析取联结词n蕴涵联结词蕴涵联结词n等价联结词等价联结词n例例nP：今天是星期二。今天是星期二。np：今天不是星期二。今天不是星期二。nq：所有人都来上课了。所有人都来上课了。nq：不是所有人来上课了。不是所有人来上课了。有人没来上课。有人没来上课。否定式n定义：复合命题定义：复合命题“非非p”称为称为p的否定式，记的否定式，记作作p。为否定联结词。为否定联结词。np为真当且仅当为真当且仅当p为假。即为假。即p表示对表示对p的真值取的真值取反。反。pp1001n例例n小李小李既既勤奋勤奋又又聪明。聪明。n小李小李不仅不仅勤奋勤奋而且而且聪明。聪明。

5、n小李小李虽然虽然聪明，聪明，但是但是不勤奋。不勤奋。n小李小李和和小王都很勤奋。小王都很勤奋。n小李小李和和小王是同学。小王是同学。n注注：并不是所有的：并不是所有的“和和”、“与与”都表示合取关系。都表示合取关系。合取式n定义：复合命题定义：复合命题“p并且并且q”称为称为p与与q的合取式，记作的合取式，记作pq。 为合取联结词。为合取联结词。npq为真当前仅当为真当前仅当p与与q同时为真。其他情况时同时为真。其他情况时pq为假。为假。pqpq111100010000n例例n小李爱唱歌小李爱唱歌或者或者爱打篮球。爱打篮球。n小李在打篮球小李在打篮球或者或者在踢足球。在踢足球。n小李可以坐火

6、车小李可以坐火车或者或者乘飞机回家。乘飞机回家。析取式n定义：复合命题定义：复合命题“p或者或者q”称为称为p与与q的析取式，记作的析取式，记作pq。为析取联结词。为析取联结词。npq为假当且仅当为假当且仅当p与与q同时为假。其他情况同时为假。其他情况pq为真。为真。pqpq111101011000析取式n自然语言中的自然语言中的“或或”具有具有二义性二义性，与析取式中的，与析取式中的“或或”含义不含义不完全相同。完全相同。n析取式可表示析取式可表示“相容或相容或”和和“不同时为真排斥或不同时为真排斥或”；n“能同时为真的排斥或能同时为真的排斥或”可用可用“异或异或”关系表示。关系表示。蕴涵式

7、n定义：复合命题定义：复合命题“如果如果p，则则q”称为称为p与与q的蕴涵式，的蕴涵式，记作记作pq。 npq为假当前仅当为假当前仅当p为真且为真且q为假。其他情况时，为假。其他情况时， pq为真。为真。pqpq111100011001n自然语言中自然语言中p与与q具有联系，而具有联系，而数理逻辑中数理逻辑中p与与q可以没有联系。可以没有联系。n例例n如果如果336，则雪是黑的。，则雪是黑的。n如果如果3+3 6，则雪是黑的。，则雪是黑的。蕴涵式npq在逻辑上表明在逻辑上表明p为为q的充分条件，的充分条件，q为为p的必要条的必要条件。件。n例例n只要只要a能被能被4整除，整除，则则a一定能被一

8、定能被2整除。整除。na能被能被4整除，整除，仅当仅当a能被能被2整除。整除。n除非除非a能被能被2整除，整除，a才能才能被被4整除。整除。n只有只有a能被能被2整除，整除，a才能才能被被4整除。整除。n只有只有a能被能被4整除，整除，a才能才能被被2整除。整除。等价式n定义：复合命题定义：复合命题“p当且仅当当且仅当q”称为称为p与与q的等价式，的等价式，记作记作pq。称作等价联结词。称作等价联结词。npq为真当且仅当为真当且仅当p与与q真值相同。其他情况时，真值相同。其他情况时，pq为为假。假。pqpq111100010001npq在逻辑上表明在逻辑上表明p与与q互为充要互为充要条件。条件

9、。n例：例：n若今天为若今天为1号，则明天是号，则明天是2号，反之号，反之亦然。亦然。n今天是雨天当且仅当雪是黑的。今天是雨天当且仅当雪是黑的。基本复合命题真值表pqppqpqpqpq0010011011011010001001101111联结词的优先顺序n()nnnnn练习n判断下列命题的真值判断下列命题的真值n若若224，则，则336n若若224，则，则336n若若224，则，则336n若若224，则，则336n224当且仅当当且仅当336n224当且仅当当且仅当336n224当且仅当当且仅当336n224当且仅当当且仅当336练习n将下列命题符号化将下列命题符号化n2是偶数又是素数是偶数

10、又是素数n他一边吃饭一边看电视他一边吃饭一边看电视n如果天下雨，他就乘公共汽车上班如果天下雨，他就乘公共汽车上班n只有天下雨，他才乘公共汽车上班只有天下雨，他才乘公共汽车上班n不经一事，不长一智不经一事，不长一智练习n设设p、q的真值为的真值为0，r、s的真值为的真值为1，求下列命题公，求下列命题公式的真值式的真值np(qr)n(pr)(qs)命题公式n命题常项（命题常元）：简单命题，真值唯一确定。命题常项（命题常元）：简单命题，真值唯一确定。n命题变项（命题变元）：真值可以变化的陈述句。命题变项（命题变元）：真值可以变化的陈述句。n命题常项和命题变元都用小写字母表示。命题常项和命题变元都用小

11、写字母表示。n合式公式（命题公式）合式公式（命题公式）：将命题变项用联结词和圆括：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。号按一定的逻辑关系联结起来的符号串。合式公式的定义n递归定义递归定义n1. 单个命题变项是合式公式，并称为原子命题公式；单个命题变项是合式公式，并称为原子命题公式；n2. 若若A是合式公式，则是合式公式，则(A)也是合式公式；也是合式公式；n3. 若若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式；也是合式公式；n4. 只有只有有限次有限次地应用地应用13形式的符号串才是合式公式。形式的符号串才是合式公式。n子公式定

12、义子公式定义n若若A为合式公式，为合式公式，B为为A的一部分，且的一部分，且B也是合式公式，则称也是合式公式，则称B为为A的子公式。的子公式。公式的赋值n定义定义n设设A为一命题公式，为一命题公式，p1, p2, , pn, 为所有在为所有在A中出现的命中出现的命题变项。给题变项。给p1, p2, , pn指定一组真值，称其为指定一组真值，称其为A的一个的一个赋赋值值或或解释解释。n若指定的一组赋值使若指定的一组赋值使A的真值为的真值为真真，则称这组值为，则称这组值为A的的成真成真赋值赋值。n若指定的一组赋值使若指定的一组赋值使A的真值为的真值为假假，则称这组值为，则称这组值为A的的成假成假赋

13、值赋值。n将一个命题公式在所有赋值下的情况列成表，称为这个公将一个命题公式在所有赋值下的情况列成表，称为这个公式的式的真值表真值表。nn个命题变项共有个命题变项共有2n组赋值。组赋值。例np(qr)的真值表的真值表pqrqrp(qr)0000000100010000111110001101011100111111例np(pq)的真值表的真值表pqppqp(pq)00111011111000111011例np(pq)的真值表的真值表pqppqp(pq)00100011101000011000n重言式（永真式）重言式（永真式）：n所有的赋值都是所有的赋值都是A的成真赋值。的成真赋值。n矛盾式（永假

14、式）矛盾式（永假式）：n所有的赋值都是所有的赋值都是A的成假赋值。的成假赋值。n可满足式可满足式：n至少存在一组赋值使至少存在一组赋值使A为真。为真。等值演算n等值式（等价式）等值式（等价式）n设设A，B为两命题公式，若为两命题公式，若AB为为重言式重言式，则称，则称A与与B为为等等值式值式，记为，记为AB。n不是逻辑联结词，表示对任意的赋值，不是逻辑联结词，表示对任意的赋值，A与与B的值相同。的值相同。n是等价联结词，它与是等价联结词，它与不能混为一谈。不能混为一谈。n等值式的性质（等价关系的通性）等值式的性质（等价关系的通性）n自反性：自反性：AA；n对称性：若对称性：若AB，则则BA；n

15、传递性：若传递性：若AB和和BC，则则AC。例npq与与pq是否等值？是否等值？基本等值规律(1)n双重否定律双重否定律nAAn等幂律等幂律nAAAnAAAn交换律交换律nABBAnABBAn结合律结合律nA(BC)(AB)CnA(BC)(AB)C基本等值规律(2)n分配律分配律nA(BC)(AB)(AC)nA(BC)(AB)(AC)n德德.摩根律摩根律n(AB)ABn(AB)ABn吸收律吸收律nA(AB)AnA(AB)A基本等值规律(3)n零律零律nA11nA00n同一律同一律nA0AnA1An排中律排中律nAA1n矛盾律矛盾律nAA0基本等值规律(4)n蕴涵等值式蕴涵等值式nABABn等价

16、等值式等价等值式nAB(AB)(BA) (AB)(BA)n假言易位假言易位nABBAn等价否定等值式等价否定等值式nABABn归谬论归谬论n(AB)(AB)A置换规则n设设(A)为含公式为含公式A的命题公式，的命题公式，(B)为用公式为用公式B置置换了换了A的命题公式，若的命题公式，若AB，则则(A)(B)。n利用等值规律及置换规则可以进行利用等值规律及置换规则可以进行等值演算等值演算。n例例n(pq)(qp)n(qp)pn(pq)(qp)n(pq) rn(p(pq)r联结词的完备集n问题：含问题：含n个命题变项的命题公式其真值表的可能性个命题变项的命题公式其真值表的可能性有多少种？有多少种？

17、nn元真值函数元真值函数：F：0,1n0,1为为n元真值函数。元真值函数。n联结词完备集：设联结词完备集：设S是一个联结词集合，如果任何是一个联结词集合，如果任何n元真值函数都可以由仅含元真值函数都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是联结词完备集。是联结词完备集。n, , n, n, n, 对偶n对偶的定义：在仅含有对偶的定义：在仅含有, , 的命题公式的命题公式A中，将中，将换成换成， 换成换成，若若A中含中含0或或1，将，将0换成换成1，1换成换成0，所得的命题公式称为，所得的命题公式称为A的对偶式，记为的对偶式，记为A*。n定理：设定理：设A和和A

18、*互为对偶式，互为对偶式， 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)n对偶原理：设对偶原理：设A、B为两命题公式，若为两命题公式，若AB，则则A*B*。范式的概念n命题公式的规范表示方法命题公式的规范表示方法n析取范式析取范式n合取范式合取范式n文字：命题变项及其否定式统称文字文字：命题变项及其否定式统称文字n简单析取式简单析取式n仅有有限个文字构成的析取式仅有

19、有限个文字构成的析取式n简单合取式简单合取式n仅有有限个文字构成的合取式仅有有限个文字构成的合取式n定理：定理：n一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式n一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式析取范式n定义定义n由有限个由有限个简单合取式简单合取式构成的构成的析取式析取式n例例npqn(pq)rn析取范式性质析取范式性质n析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式合取范式n定

20、义定义:n由有限个简单析取式构成的合取式由有限个简单析取式构成的合取式n例例npqn(pq)rn合取范式性质合取范式性质n合取范式是重言式，当且仅当它的每个简单析取式是重言合取范式是重言式，当且仅当它的每个简单析取式是重言式式范式存在定理n定理：定理：任一命题公式都存在与之等值的析取范式（合任一命题公式都存在与之等值的析取范式（合取范式）。取范式）。n求范式的步骤求范式的步骤n利用蕴涵等值式和等价等值式消去联结词利用蕴涵等值式和等价等值式消去联结词 、。n用双重否定律消去否定联结词，利用德用双重否定律消去否定联结词，利用德.摩根律将否定联结摩根律将否定联结词内移。词内移。n利用分配律求析取范式

21、或合取范式。利用分配律求析取范式或合取范式。n例：例：n(pq)r范式的求解n例：例：n(pq)r极小项与极大项n极小项的定义极小项的定义n在含在含n个命题变项的简单合取式中，如果每个变项与其否定个命题变项的简单合取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现式不同时存在，但两者之一恰出现1次，且第次，且第i个命题变项个命题变项或否定式出现在从左起的第或否定式出现在从左起的第i位上。位上。n极大项的定义极大项的定义n在含在含n个命题变项的简单析取式中，如果每个变项与其否定个命题变项的简单析取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现式不同时存在，但两者之一恰出现1次，

22、且第次，且第i个命题变项个命题变项或否定式出现在从左起的第或否定式出现在从左起的第i位上。位上。nn个命题变项共可形成个命题变项共可形成2n个极小项和个极小项和2n个极大项。个极大项。极小项的成真赋值n每个极小项仅有一个成真赋值每个极小项仅有一个成真赋值n每个极小项的成真赋值均不相同每个极小项的成真赋值均不相同n可以利用不同的成真赋值区别每个极小项，给予标记可以利用不同的成真赋值区别每个极小项，给予标记二元极小项二元极小项取值取值成真赋值成真赋值简记名称简记名称pq100m0pq101m1pq110m2pq111m3极大项的成假赋值n每个极大项仅有一个成假赋值每个极大项仅有一个成假赋值n每个极

23、大项的成假赋值均不相同每个极大项的成假赋值均不相同n可以利用不同的成假赋值区别每个极大项，给予标记可以利用不同的成假赋值区别每个极大项，给予标记二元极大项二元极大项取值取值成假赋值成假赋值简记名称简记名称pq000M0pq001M1pq010M2pq011M3主析取范式与主合取范式n主析取范式的定义主析取范式的定义n若若A的命题公式由若干个极小项进行析取构成，则称该析取的命题公式由若干个极小项进行析取构成，则称该析取范式为范式为A的主析取范式的主析取范式n从主析取范式中很容易得到成真赋值从主析取范式中很容易得到成真赋值n主合取范式的定义主合取范式的定义n若若A的命题公式由若干个极大项进行合取构

24、成，则称该合取的命题公式由若干个极大项进行合取构成，则称该合取范式为范式为A的主合取范式的主合取范式n从主合取范式中很容易得到成假赋值从主合取范式中很容易得到成假赋值n定理：任何命题公式都存在与之等值的定理：任何命题公式都存在与之等值的主析取（合取）主析取（合取）范式范式，且，且唯一唯一。主析取范式的求解方法(1)n用等值演算求得析取范式用等值演算求得析取范式n依次扫描析取范式中的每个简单合取式依次扫描析取范式中的每个简单合取式Bn若若B为极小项，则继续扫描下一个为极小项，则继续扫描下一个n若若B不为极小项，将不含的命题变项不为极小项，将不含的命题变项p及其否定式及其否定式p用等值用等值变换添

25、入变换添入BB(pp) (Bp)(Bp) n消去重复出现的命题变项、极小项和矛盾式。消去重复出现的命题变项、极小项和矛盾式。主析取范式的求解方法(2)n根据公式构造真值表根据公式构造真值表n写出每个公式成真赋值对应的极小项写出每个公式成真赋值对应的极小项n将极小项进行析取，即得主析取范式将极小项进行析取，即得主析取范式主析取范式n例：求例：求(p(qr)(p(qr)主合取范式的求解方法(1)n用等值演算求得合取范式用等值演算求得合取范式n依次扫描合取范式中的每个简单析取式依次扫描合取范式中的每个简单析取式Bn若若B为极大项，则继续扫描下一个为极大项，则继续扫描下一个n若若B不为极大项，将不含的

26、命题变项不为极大项，将不含的命题变项p及其否定式及其否定式p用等值用等值变换添入变换添入BB (pp) (Bp)(Bp) n消去重复出现的命题变项、极大项和重言式。消去重复出现的命题变项、极大项和重言式。主合取范式的求解方法(2)n根据公式构造真值表根据公式构造真值表n写出每个公式成假赋值对应的极大项写出每个公式成假赋值对应的极大项n将极大项进行合取，即得主合取范式将极大项进行合取，即得主合取范式主合取范式n例：求例：求(p(qr)(p(qr)主析取范式与主合取范式n主析取范式与主合取范式之间的关系？主析取范式与主合取范式之间的关系？推理的形式结构n设两命题公式设两命题公式A、B，若若AB为为

27、重言式，重言式，则称则称A蕴涵蕴涵B，记为记为AB。n设设A1、A2、.、An、B为命题公式，若为命题公式，若A1A2. An B，则称则称B为为A1、A2、.、An的的逻辑结论逻辑结论或或有有效结论效结论，也称，也称B可由一组前提可由一组前提A1、A2、.、An逻辑推逻辑推出。记为出。记为A1，A2，.，AnB。n正确推理的本质是正确推理的本质是A1A2. AnB为重言式。为重言式。n当当A1A2. An为假时，不论为假时，不论B是真是假，是真是假， A1A2. AnB均为真。所以均为真。所以B为有效结论并不为有效结论并不意味意味B为真。为真。推理的基本方法n简单证明法：简单证明法： 证明证

28、明A1A2. AnB是重言式，是重言式，即即A1A2. AnB1。n真值表法真值表法n等值演算法等值演算法n主析取范式法主析取范式法n例：若例：若a能被能被4整除，则整除，则a能被能被2整除。因为整除。因为a能被能被2整整除，所以除，所以a能被能被4整除。整除。推理的基本方法(2)n直接构造证明法直接构造证明法n由给定的一组前提出发，利用推理规则逐步演算得到结论。由给定的一组前提出发，利用推理规则逐步演算得到结论。n常用推理规则常用推理规则n前提引入规则：在证明过程的任何步骤都可以将前提引入前提引入规则：在证明过程的任何步骤都可以将前提引入使用使用n结论引入规则：在推理中，若已证出结论结论引入

29、规则：在推理中，若已证出结论B，则则B可以引入可以引入到以后的推理中作为前提使用到以后的推理中作为前提使用n置换规则：命题公式中任何子公式都可以用等值公式置换置换规则：命题公式中任何子公式都可以用等值公式置换n化简规则：化简规则： AB A， AB Bn附加规则：附加规则： AAB常用推理规则n假言推理规则：假言推理规则：AB，ABn拒取式规则：拒取式规则：AB，BAn析取三段论：析取三段论：AB，ABn假言三段推理：假言三段推理：AB，BCACn等价三段论：等价三段论：AB，BCACn构造性二难规则：构造性二难规则：AB，CD，ACBDn破坏性二难规则：破坏性二难规则： AB，CD，BDAC

30、n合取引入规则：合取引入规则：A，BAB常用推理规则n证明：若证明：若a是实数，则它不是有理数就是无理数。若是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。不能表示成分数，则它不是有理数。a是实数且它是实数且它不能表示成分数，所以不能表示成分数，所以a是无理数。是无理数。推理的基本方法(3)n间接构造证明法间接构造证明法n附加前提证明法附加前提证明法nA1A2. AnBCnA1A2. AnB Cn归谬法归谬法nA1A2. AnBnA1A2. AnB 0推理的基本方法(3)n例：证明例：证明p(qr)，sp，qsrn例：如果小张守第一垒并且小李向例：如果小张守第一垒并且小李向B队投球，则队投球，则A队将获胜。队将获胜。A队未取胜或者队未取胜或者A队成为联赛第一名。队成为联赛第一名。A队没有成为联赛的第队没有成为联赛的第一名。小张守第一垒。因此小李没向一名。小张守第一垒。因此小李没向B队投球。队投球。作业(1)nP33 1.5 (3)(4)(7)nP33 1.6 (3)(4) 作业(2)nP34 1.7 (4)(9)(10)nP34 1.8 (2)nP34 1.9 (3)nP34 1.10 (2)(3)nP34 1.11 (1) (2)(3)