离散数学第1章命题逻辑.ppt

1、第一章 命题逻辑 （Proposition Logic）,命题符号化及联结词,命题公式及分类,等值演算,联结词全功能集,对偶与范式,推理理论,1,2,3,4,5,6,2,简介,逻辑学： 研究推理的一门学科 数理逻辑： 用数学方法研究推理的一门数学学科, 一套符号体系 + 一组规则,3,简介,数理逻辑的内容： 古典数理逻辑： 命题逻辑、谓词逻辑 现代数理逻辑： 逻辑演算、公理化集合论、递归论、模型论、证明论,4,命题逻辑,命题(Proposition)： 一个有确定真或假意义的语句。,命题符号化及联结词,1,5,EXAMPLE 1,下列句子都是命题： 1. 华盛顿是美国的首都。 2. 多伦多是加

2、拿大的首都。 3. 1+1=2。 4. 2+2=3。,命题1和3是真命题，2和4是假命题。,命题符号化及联结词,6,命题符号化及联结词,EXAMPLE 2,考虑如下句子： 1. 现在几点了？ 2. 认真阅读一下。 3. x+1=2. 4. x+y=z.,句子1和2不是命题，因为它们都不是陈述句。 句子3和4不是命题，由于x，y和z的值不确定，使得它们的真值都不唯一。,7,命题的语句形式： 陈述句 非命题语句： 疑问句、命令句、感叹句、 非命题陈述句：悖论语句（真值不唯一）,命题符号化及联结词,8,命题的符号表示： 大小写英文字母：P、Q、R、 p 、q 、r 命题真值(Truth Values

3、)的表示： 真：T、1 假：F、0,命题符号化及联结词,9,命题语句真值确定的几点说明： 1、时间性 2、区域性 3、标准性 命题真值间的关系表示： 真值表(Truth Table),命题符号化及联结词,10,DEFINITION 1.,设p为任一命题，复合命题“非p”（或“p的否定”）称为p的否定式。记作 p 。 为否定联结词。真值表见Table 1。(Let p be a proposition. The statement “It is not the case that p.” is another proposition, called the negation of p. The

4、negation of p is denoted by p. The proposition p is read “not p.”),p的否定,命题符号化及联结词,11,Table 1,命题符号化及联结词,12,EXAMPLE 3,设p表示“今天是星期五”，则 p表示“今天不是星期五”。,显然，当p的真值为0时， p的真值为1。,命题符号化及联结词,13,命题符号化及联结词,设p，q为两命题，复合命题“p并且q”（或“p和q”）称作p与q的合取式。记作pq。 为合取联结词。真值表见Table 2。(Let p and q be propositions. The proposition p a

5、nd q, denoted by pq, is the proposition that is true when both p and q are true and is false otherwise. The proposition pq is called the conjunction of p and q. ),p和q的合取,DEFINITION 2.,14,命题符号化及联结词,Table 2,15,EXAMPLE 4,用p表示命题“今天是星期五”，q表示命题“今天下雨”， 则命题p与q的合取式是什么？,解答： p与q的合取式 pq是“今天是星期五，而且今天下雨。”如果是星期五，又

6、下雨，则该命题为真；如果是除星期五外的任意一天，或者虽是星期五但没下雨，则该命题为假。,命题符号化及联结词,16,命题符号化及联结词,设p，q为两命题，复合命题“p或q” 称作p与q的析取式。记作pq。为析取联结词。真值表见Table 3。 (Let p and q be propositions.The proposition p or q, denoted by pq,is the proposition that is false when p and q are both false and true otherwise. The proposition pq is called th

7、e disjunction of p and q.),p和q的析取,DEFINITION 3.,17,命题符号化及联结词,Table 3,18,还是以Example 4 为例，命题p与q的析取式是什么？,解答： p与q的析取式 pq是“今天是星期五或今天下雨。”只有今天既不是星期五，又没有下雨，则该命题为假；如果今天是星期五或者今天下雨了（包括下雨的星期五），则该命题就为真。,EXAMPLE 5,命题符号化及联结词,19,命题符号化及联结词,设p，q为两命题，复合命题“如果p，则q”称作p与q的蕴含式。 记作 pq。称p为蕴含式的前件(hypothesis)，q为蕴含式的后件(conclusi

8、on)。称作蕴含联结词。真值表见Table 4。(Let p and q be propositions.The implication pq is the proposition that is false when p is true and q is false and true otherwise. ),如果p，则q,单条件， 蕴涵 p：前提 q：结论,DEFINITION 4.,20,命题符号化及联结词,Table 4,21,命题符号化及联结词,用p表示命题“天下雨”，用q表示命题“我骑自行车上班”，将下列命题符号化： （1）只要不下雨，我就骑自行车上班。 （2）只有不下雨，我才骑自

9、行车上班。,解答： （1）中， p是q的充分条件，因而符号化为 pq；（2）中， p是q的必要条件，因而符号化为q p。,EXAMPLE 6,22,命题符号化及联结词,设p，q为两命题，复合命题“p当且仅当q”称作p与q的等价式。记作pq，称作等价联结词。真值表见Table 5。(Let p and q be propositions, The biconditional pq is the proposition that is true when p and q have the same truth values and is false otherwise.),p当且仅当q,双条件，等

10、价,DEFINITION 5.,23,命题符号化及联结词,Table 5,24,命题符号化及联结词,将下一命题符号化： “只有（仅当）你是计算机科学系的学生或者你不是新生，你才可以通过校园网上Internet。”,解答： a (cf ),EXAMPLE 7,c,f,a,25,将下一命题符号化： “如果你身高小于4英尺，你就不能乘坐过山车，除非你超过了16岁。”,解答： (1) (r s) q. (2) s(r q).,EXAMPLE 8,r,q,s,如果你身高小于4英尺，而且你不超过16岁，那么你就不能乘坐过山车。,如果你不超过16岁，那么当你身高小于4英尺时，你就不能乘坐过山车。,命题符号化

11、及联结词,26,命题符号化及联结词,“说离散数学是枯燥无味的或毫无价值的，那是不对的。” p：离散数学是有味道的； q：离散数学是有价值的；,EXAMPLE 9,符号化为：( p q),27,命题逻辑,命题公式及分类,2,P、Q、R 称为原子命题(Atomic Proposition)。 原子命题或加上逻辑联结词组成的表达式成为复合命题(Compositional Proposition)。 从命题常量 到 命题变量(Propositional Variable),命题公式： 1. 原子命题是命题公式； 2. 设P是命题公式，则 P也是命题公式； 3. 设P、Q是命题公式，则(PQ)、(PQ)

12、、(PQ)、(P Q)也是命题公式； 4. 有限次地使用1、2、3所得到的也是命题公式。 Proposition Formulas, Well-Formed Formulas(wff),28,命题公式及分类,命题公式的运算规则： 逻辑联接词的优先级： 、 、 、 、 命题公式的表达式的运算规律： 同代数表达式 命题公式的运算方法： 所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。 性质1：如果一个命题公式有n个互异的命题变量，则命题公式对应的真值有2n种可能分布。,29,命题公式及分类,EXAMPLE 10,求下列命题公式的真值表：（1）p (q r ) .,30

13、,命题公式及分类,EXAMPLE 10,求下列命题公式的真值表：（2）( p ( pq ) q .,31,命题公式及分类,EXAMPLE 10,求下列命题公式的真值表：（3） ( pq ) q .,32,命题公式及分类,永真式(Tautology)：公式中的命题变量无论怎样代入，公式对应的真值恒为1。 永假式(Contradiction)：公式中的命题变量无论怎样代入，公式对应的真值恒为0。 可满足式(Satisfaction)：公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为1。 一般命题公式(Contingency)：既不是永真公式也不是永假公式。,33,命题公式及分类,性质2：

14、 （1）设P是永真命题公式，则P的否定公式是永假命题公式； （2）设P是永假命题公式，则P的否定公式是永真命题公式； （3）设P、Q是永真命题公式，则 (PQ)、(PQ)、(PQ)、(P Q)也是永真命题公式 。,34,命题公式及分类,小 结 1. 命题的概念：定义、逻辑值、 符号化表示 2. 从简单命题到复合命题： 逻辑联接词：运算方法、运算优先级 3. 从命题常量到命题变量， 从复合命题到命题公式： 命题公式的真值描述：真值表 4. 命题公式的分类： 永真公式、永假公式、可满足公式 、一般公式,35,Propositional Equivalences,设A，B为两命题公式，若等价式AB是

15、重言式，则称A与B是等值的。记作AB。 (The propositions A and B are called logically equivalent if AB is a tautology. The notation AB denotes that A and B are logically equivalent.),逻辑等值，或逻辑等价,DEFINITION 6.,命题逻辑,等值演算,3,36,证明( pq )与pq 是等值的。 （这个等值关系是德摩根(De Morgan)定律之一。德摩根是十九世纪中叶的英国数学家。）,解答：真值表见Table 9。因为对于p和q 所有可能的组合，

16、(pq)和pq的真值都相同，所以这两个命题是等值的。,EXAMPLE 11,等值演算,37,Table 9,等值演算,38,证明pq 与p q 是等值的。,解答：真值表见Table 10。因为对于p和q 所有可能的组合， pq 和pq的真值都相同，所以这两个命题是等值的。,EXAMPLE 12,等值演算,39,Table 10,等值演算,40,证明p(qr)与 (pq)(pr) 是等值的。（分配律）,解答：真值表见Table 11。因为对于p、q和r所有可能的组合， p(qr) 和(pq)(pr) 的真值都相同，所以这两个命题是等值的。,EXAMPLE 13,等值演算,41,Table 11,

17、等值演算,42,下面给出24个重要的等值式（祥见P9）：双重否定律、等幂律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾式、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。,根据已知的等值式，推演出另外一些等值式的过程称为等值演算。在进行等值演算时，往往用到置换规则。,等值演算,43,证明(p(pq)与pq是等值的。,EXAMPLE 14,等值演算,44,证明(pq) (pq)是重言式。,EXAMPLE 15,等值演算,45,判断命题公式逻辑等价的方法： 1. 真值表 2. 命题公式的演算 基本等值定理； 公式的代入不变性（置换规则）； 等值关系的传递性。,等

18、值演算,46,命题公式逻辑等价关系的应用： 1、判定是否逻辑等价（等值）； 2、判断是否为永真公式或永假公式； 3、命题公式的化简。,等值演算,47,设p,q为两命题，复合命题“p,q之中恰有一个成立”称为p与q的排斥或或异或。记作p q， 称作排斥或或异或联结词。真值表见Table 12。(Let p and q be propositions.The exclusive or of p and q, denoted by p q,is the proposition that is true when exactly one of p and q is true and is false

19、otherwise.),p和q的异或,DEFINITION 7.,命题逻辑,联结词全功能集,4,48,Table 12,联结词全功能集,p q (p q)(pq),49,设p,q为两命题，复合命题“p与q的否定”称为p与q的与非式。记作pq， 称作与非联结词。真值表见Table 13。(Let p and q be propositions.The and not of p and q, denoted by pq, is the proposition that is false when p and q are both true and true otherwise. ),p和q的与非,

20、DEFINITION 8.,联结词全功能集,50,Table 13,pq ( pq ),联结词全功能集,51,设p,q为两命题，复合命题“p或q的否定”称为p与q的或非式。记作pq， 称作或非联结词。真值表见Table 14。(Let p and q be propositions.The or not of p and q, denoted by pq, is the proposition that is true when p and q are both false and false otherwise. ),p和q的或非,DEFINITION 9.,联结词全功能集,52,Table

21、 14,pq ( pq ),联结词全功能集,53,逻辑联结词集是功能完备集(Functionally Complete Set)： 任一个命题公式都能够等价于仅包含这些逻辑联结词联结起来的公式。 逻辑联结词集是极小功能完备集： 是功能完备集并且没有冗余联结词。,联结词全功能集,54,例1：、是功能完备的，但不是极小功能完备的。 例2：、 是极小功能完备的。 例3：、 、 是极小功能完备的。,联结词全功能集,55,DEFINITION 10.,命题公式P的对偶公式(Dual)：将P中的 析取联结词换成合取联结词， 合取联结词换成析取联结词， 1换成0，0换成1（如果存在的话）。 记为P*.,命题

22、逻辑,对偶与范式,5,56,对偶原理(Duality Principle)： 设P，Q是两命题公式，如果 P Q， 则 P* Q*。,例：A： (P Q) Q B： P Q,这里， A B，分析是否A* B*。,对偶与范式,57,命题公式的标准化范式,小项(small item)/合取式(conjunctive form): 若干个原子命题或其否定的合取。 大项(large item)/析取式(disjunctive form): 若干个原子命题或其否定的析取。 析取范式(disjunctive normal form)： 若干个小项的析取。 合取范式(conjunctive normal f

23、orm)： 若干个大项的合取。,对偶与范式,58,定理的证明思路： 1、消去对、来说冗余的联结词； 2、将否定联结词移到命题变量的前面； 3、消除多余的否定联结词； 4、利用分配律化成合取范式和析取范式。,定理1：任意一个命题公式都存在与之等价的 合取范式和析取范式。,范式存在定理,对偶与范式,59,令A(a1、a2、an)是包含有n个变量的公式， 极小项(extremal ):小项中恰包含n个变量或其否定。 极大项(extremal ):大项中恰包含n个变量或其否定。 主析取范式(Unique disjunctive normal form): 若干个极小项的析取。 主合取范式(Unique

24、 conjunctive normal form): 若干个极大项的合取。,对偶与范式,60,以三个命题变项p,q,r为例，可形成23=8个极小项，每个极小项对应一个二进制数，也对应一个十进制数，二进制数是该极小项的成真赋值，十进制数可做该极小项抽象表示法的角码。对应情况如下： pqr 0000，记作m0； pqr 0011，记作m1； pqr 0102，记作m2； pqr 0113，记作m3； pqr 1004，记作m4； pqr 1015，记作m5； pqr 1106，记作m6； pqr 1117，记作m7。 主析取范式：如m1m2m5可用( 1,2,5 )表示。,对偶与范式,61,以三个

25、命题变项p,q,r为例，可形成23=8个极大项，每个极大项对应一个二进制数，也对应一个十进制数，二进制数是该极大项的成假赋值，十进制数可做该极大项抽象表示法的角码。对应情况如下： pqr 0000，记作M0； pqr 0011，记作M1； pqr 0102，记作M2； pqr 0113，记作M3； pqr 1004，记作M4； pqr 1015，记作M5； pqr 1106，记作M6； pqr 1117，记作M7。 主合取范式：如M0 M3 M6可用( 0,3,6 )表示。,对偶与范式,62,EXAMPLE 16,求pqr的主析取范式和主合取范式：,解：( pq )r (p q) ( r r)

26、(r (p p) (p q r) (p q r)(p r) ( p r) (pqr)(pqr)(pr)(qq)(pr) (qq) (pqr)(pqr)(pqr)(pqr) ( pqr)( pqr) (pqr)(pqr)(pqr)( pqr)( pqr) m7 m6 m5 m3 m1 ( 1,3,5,6,7 )（主析取范式） M0 M2 M4 ( 0,2,4) （主合取范式）,对偶与范式,63,例6 张先生手中有代号为A、B、C、D、E的五种股票，根据当前股市情况及张先生本人的经济需求，需要有若干个股票抛出，但又必须满足如下复杂的要求： （1）若A抛出，则B也抛出； （2）B和C要留一种股票且只

27、能留一种； （3）C和D要么全抛，要么都不抛； （4）D和E两种股票中必然有一种或两种要抛出； （5）若E抛出，则A、B也抛出。 上述五种条件全部满足，问有几种合理的方案供张先生选择。,AB,C D,DE,EA B,解答：留ABE或CD（将题意置换成主析取范式）。,对偶与范式,B C,64,小 结 1、命题公式的等价演算 2、命题公式的标准化描述 表达、分类、判定、应用,对偶与范式,65,数理逻辑的主要任务是借助于数学的方法来研究推理的逻辑。 推理是从前题推出结论的思维过程，前提是已知的命题公式，结论是从前题出发应用推理规则推出的命题公式。,命题逻辑,推理理论,6,66,DEFINITION

28、11.,若A1A2AkB为重言式，则称从A1, A2, , Ak推出结论B的推理正确，记作A1A2AkB。B是A1, A2, , Ak的逻辑结论或有效结论。 称A1A2AkB为推理的形式结构。,推理理论,67,判断推理是否正确的方法有以下几种： （1）真值表法； （2）等值演算法； （3）主析取范式法。 （即判断A1A2AkB是否为重言式）,推理理论,68,EXAMPLE 17,判断下列推理是否正确：如果天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。,解这类推理问题，应先将命题符号化，然后写出前提、结论和推理的形式结构，最后进行判断。 在这里，设p：天气凉快；q：小王去游泳。 前提：p

29、q, p。结论：q。 推理的形式结构： (pq )p)q 。 下面分别用三种方法来判断该蕴含式是否为重言式。,推理理论,69,Table 15 （1）真值表法,真值表的最后一列全为1，因而（*）是重言式，所以推理正确。,推理理论,70,（2）等值演算法,(pq)p)q (pq)p)q (p q)p)q (p q)pq (pq)(pq) 1,该蕴含式是重言式，所以推理正确。,推理理论,71,(pq)p)q (pq)p)q (pq)p)q (pq)pq (pq)(p(qq)(q(pp) (pq)(pq)(pq)(qp) (qp) (pq)(pq)(pq)(pq) m3m1m0m2 ( 0,1,2,3 ),（3）主析取范式法,该蕴含式的主析取范式中含有4个极小项，因而是重言式。,推理理论,72,为了更好地判断推理的正确性，引入构造证明的方法。 在数理逻辑中，证明是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论。其中有些规则建立在推理定律（重言蕴含式）的基础之上。 重要的8条推理定律