离散数学.ppt

1、第一章 命题逻辑,这章是以“命题”为中心主要讨论：命题的表示、命题的演算命题演算中的公式，及其应用命题逻辑推理,1-1. 命题与命题的真值,本节主要讨论三个问题：命题的概念命题的真值原子命题与复合命题,一. 命题的概念 Statement,命题 是一个能确定是真的或是假的判断。 （判断都是用陈述句表示）例1-1.1 判定下面这些句子哪些是命题。 2是个素数。 雪是黑色的。 2010年人类将到达火星。 如果 ab且bc，则ac 。(a、b、c是确定实数) x+yb、bc、ac) 构成的复合命题。,1-2 联结词 Connectives,复合命题的构成：是用“联结词”将原子命题联结起来构成的。 归

2、纳自然语言中的联结词，定义了六个逻辑联结词，分别是： (1) 否定“” (2) 合取“”,(5) 蕴涵“” (6) 等价“”,(3) 析取“” (4) 异或“ ”,一. 否定“” Negation,表示：“不成立”，“不”。用于：对一个命题P的否定，写成P，并读成“非P”。P的真值：与P真值相反。 例1-2.1 P：2是素数。 P：2不是素数。,P P,T F,F T,二. 合取“”Conjunction,表示：“并且”、“不但而且.”、“既又 .”、“尽管还 ”例1-2.2 P：小王能唱歌。 Q：小王能跳舞。PQ：小王能歌善舞。 PQ读成P合取Q。PQ的真值为真，当且 仅当P和Q的真值均为真

3、。,P Q PQ,F F F,F T F,T F F,T T T,三. 析取“”、异或“ ”,表示“或者” “或者”有二义性，看下面两个例子： 例1-2.3. 灯泡或者线路有故障。 例1-2.4. 第一节课上数学或者上英语。例3中的或者是可兼取的或。即析取“”例4中的或者是不可兼取的或，也称之为异,或、排斥或。即“ ”。,1. 析取“” Disjunction,P：灯泡有故障。 Q：线路有故障。例3中的复合命题可 表示为：PQ，读 成P析取Q。PQ的真值为F，当 且仅当P与Q均为F。,P Q PQ,F F F,F T T,T F T,T T T,2. 异或“ ” Exclusive OR,P：

4、第一节上数学。Q：第一节上英语。例4中的复合命题,F F F,F T T,T F T,T T F,P Q P Q,当且仅当P与Q的真值相同。,P Q的真值为F，,可写成P Q，读成P异或Q。,3.“异或”的另一种表示,异或是表示两个命题不可能同时都成立。命题“第一节课上数学或者上英语。”可以解释为： “第一节课上数学而没有上英语或者第一节课上英语而没有上数学。” 于是有,实际应用中必须注意“或者”的二义性。,P Q 与 (PQ)(QP ) 是一样的。,四.条件(蕴涵)“” Conditional (Implication),表示“如果 ，则 ”，“只要 ，就 ”, “只有 , 才” , “ .

5、 , 仅当 ” 例1-2.5： P表示：缺少水分。 Q表示：植物会死亡。PQ：如果缺少水分，植物就会死亡。PQ：也称之为蕴涵式，读成“P蕴涵 Q”，“如果P则Q”。也说成P是PQ 的 前件，Q是PQ的后件。还可以说P是Q的 充分条件，Q是P的必要条件。,关于充分条件和必要条件的说明：,充分条件：就是只要条件成立，结论就成立，则该条件就是充分条件。 上例中，“缺少水分”就是“植物会死亡”的充分条件。在自然语言中表示充分条件的词有 ： 如果 则 ，只要 就，若则 必要条件：就是如果该条件不成立，那么结论就不成立, 则该条件就是必要条件。 上例中，“植物死亡”就是“缺少水分”的必要条件(植物未死亡，

6、一定不缺少水分)。 在自然语言中表示必要条件的词有 ： 只有 才 ； 仅当， ; , 仅当。,PQ的真值：,PQ的真值为假，当且仅当P为真，Q为假。注意：当前件P为假时， PQ为T。,P Q PQ小王借钱不还 我替他还 （我给小王担保）,F F T,F T T,T F F,T T T,举例：令：P：天气好。 Q：我去公园。1.如果天气好，我就去公园。2.只要天气好，我就去公园。3.天气好，我就去公园。4.仅当天气好，我才去公园。5.只有天气好，我才去公园。6.我去公园，仅当天气好。,PQ,QP,可见“”既表示充分条件（即前件是后件的充分条件）；也表示必要条件（即后件是前件的必要条件）。这一点要

7、特别注意!它决定了哪个作为前件，哪个作为后件。,五.双条件 (等价）“” “ ” Biconditional (Equivalence),表示“当且仅当”、“充分且必要”例1-2.6： P：ABC是等边三角形。 Q：ABC是等角三角形。 PQ ：ABC是等边三角形当且仅当 它是等角三角形。,P Q PQ,F F T,F T F,T F F,T T T,PQ的真值：,PQ的真值为真，当且仅当P与Q的真值相同。,本节小结：,要熟练掌握这六个联结词在自然语言中所表示的含义以及它们的真值表的定义。,特别要注意“或者”的二义性，即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”。特别要注意“”的用

8、法，它既表示“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件。下面做练习,练习：填空已知PQ为T，则P为( )，Q为( )。已知PQ为F，则P为( )，Q为( )。已知P为F，则PQ为( )。已知P为T，则PQ为( )。已知PQ为T，且P为F ，则Q为( )。已知PQ为F，则P为( )，Q为( )。已知P为F，则PQ为( )。已知Q为T，则PQ为( )。已知 PQ为F，则P为( )， Q为( )。,已知P为T， PQ为T，则Q为( )。已知Q为T, PQ为T，则P为( )。已知PQ为T，P为T , 则Q为( )。已知PQ为F，P为T , 则Q为( )。PP 的真值为( )。P

9、P 的真值为( )。,1-3 命题公式及命题符号化,一.常值命题与命题变元常值命题：即是我们前面所说的命题。它是有具体含义 (真值)的。例如：“3是素数。”就是常值命题。命题变元：用大写的英字母如P、Q等表示任何命题。称这些字母为命题变元。对命题变元作指派(给命题变元一个解释)：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值“T”或“F”的过程。注意：命题变元本身不是命题，只有给它一个解释，才变成命题。,二.合式公式 ( wff ) (well formed formulas)1.定义： 单个命题变元是个合式公式。 若A是合式公式，则A是合式公式。 若A和B是合式公式，则(AB)

10、， (AB)， (AB)和(AB)都是合式公式。 当且仅当有限次地应用，所得到的 含有命题变元、联结词和括号的符号串是合 式公式。 注意这个定义是递归的。(1)是递归的基础，由(1)开始，使用规则(2)(3) ，可以得到任意的合式公式。,这里所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式，有时也简称公式。下面的式子不是合式公式： PQ， PR， PQR下面的式子才是合式公式： (PQ)，(PR)，(PQ)R)按照合式公式定义最外层括号必须写。约定：为方便，最外层括号可以不写。 上面的合式公式可以写成： PQ，PR，(PQ)R,2. 命题公式的真值表 (Truth Table) 一

11、个命题公式不是复合命题，所以它没有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反应它的真值情况，例如命题 公式 (PQ)Q 的真值表如下所示：,P Q P PQ (PQ)Q,F F T F F,F T T T T,T F F T T,T T F T T,由于对每个命题变元可以有两个真值(T,F)被指派，所以有n个命题变元的命题公式 A(P1,P2,Pn) 的真值表有2n行。为有序地列出A(P1,P2,Pn)的真值表，可将F看成0、T看成1，按二进制数次序列表。,如A(P,Q)的真值表可按照如下次序指派： 00(FF)，01(FT)，10(TF)，11(TT),如A(P,

12、Q,R)的真值表可按照如下次序指派：,A(P1,P2,Pn)的真值表，按照二进制数000 0001 00010 1 10 111 0 1 2 2n -2 2n -1 即按照十进制的0，1，2，. ，2n -1的次序进行指派列真值表。,例如列出P(QR)的真值表,P Q R QR P(QR),000 F F F,001 F F T,010 F T F,011 F T T,100 T F F,101 T F T,110 T T F,111 T T T,T,T,T,T,F,T,T,T,T,T,T,T,F,F,T,T,三.命题符号化 所谓命题符号化，就是用命题公式的符号串来表示给定的命题。命题符号化的

13、方法 1.首先要明确给定命题的含义。 2.对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。 3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。,例1.说离散数学无用且枯燥无味是不对的。 P：离散数学是有用的。 Q：离散数学是枯燥无味的。 该命题可写成： (PQ)例2.如果小张与小王都不去，则小李去。 P：小张去。 Q：小王去。 R：小李去。 该命题可写成： (PQ)R 如果小张与小王不都去，则小李去。 该命题可写成： (PQ)R 也可以写成： (PQ)R,例3. 仅当天不下雨且我有时间，才上街。 P：天下雨。Q：我有时间。R：我上街。 分析：由于“仅当”

14、是表示“必要条件”的，既“天不下雨且我有时间”，是“我上街”的必要条件。所以 该命题可写成： R(PQ) 例4.人不犯我，我不犯人；人若犯我，我必犯人。 P：人犯我。Q：我犯人。 该命题可写成：(PQ)(PQ),P是Q的充分条件,P是Q的必要条件,P是Q的充分且必要条件,或写成： PQ,例5 .若天不下雨，我就上街；否则在家。 P：天下雨。Q ：我上街。R：我在家。 该命题可写成： (PQ)(P R). 注意：中间的联结词一定是“”，而不是,因为原命题表示：“天不下雨时我做什么，天下雨我又做什么”的两种作法，其中有一种作法是假的，则我说的就是假话，所以中间的联结词一定是“ ”。 如果写成 (P

15、Q)(P R)，就表明两种作法都是假的时候，我说的才是假话。这显然不对。,“”，也不是“ ”。,实际上, 公式(PQ)(P R) 的真值总是真的。 因为当P为T时， (PQ)为T， 当P为F时， (PR)为T，所以(PQ)(P R) 的真值总是真的。而例5中命题的真值不是总是真的。,此时此话是假话，虽然(PQ) 是F，而(P R)的真值是“T”。于是,若写成(PQ) (P R)：则表示两种作法一个是,表达式 (PQ) (P R) 的真值却是“T”。,所以这个表达式也不对。,真 , 另一个是假时，才是真的。,例如当P为F，Q为F时，即天没下雨而我没上街。,本节重点掌握： 列命题公式的真值表 将给

16、定命题符号化作业题： 第8页：（3） 第12页：（5）、（7） 第17页：（1）a)、d),1-4 重言式与重言蕴涵式 Tautology, Tautological Implications,一.重言式(永真式)与矛盾式(永假式)1.例子 P PP PP F T F T T F 可见不论P取什么真值PP 的真值总是为真，PP的真值总是为假。故称 PP为重言式(永真式)，称PP为矛盾式(永假式)。,2 .重言式(矛盾式)定义 A(P1,P2,Pn) 是含有命题变元P1,P2, Pn的命题公式，如不论对P1, P2 , , Pn作任何指派,都使得A(P1,P2, Pn) 为真(假)，则称之为重言

17、式(矛盾式), 也称之为永真式 (永假式)。3.重言式的证明方法 方法1：列真值表。 方法2：公式的等价变换，化简成“T”。 方法3：用公式的主析取范式。其中方法2 和方法3 我们在以后讨论。,方法1. 列真值表。 例如，证明 (P(PQ)Q 为重言式。 P Q PQ P(PQ) (P(PQ)Q F F T F T F T T F T T F F F T T T T T T 永真式的真值表的最后一列全是“T”。,4. 永真式的性质 1) 如果A是永真式，则A是永假式。 2) 如果A，B是永真式，则(AB)、(AB)、(AB)和(AB)也都是永真式。 3) 如果A是永真式，则A的置换例式也是永真

18、式。 置换例式： A(P1,P2,Pn) 是含有命题变元P1,P2, Pn的命题公式，如果用合式公式X替换某个Pi(如果Pi在A(P1,P2,Pn) 中多处出现，则各处均用X替换 )，其余变元不变，替换后得到新的公式B，则称B是A(P1,P2,Pn) 的置换例式。,例如： 公式A：P(P(PQ)R) 用(DE)替换A中P得到A的置换例式 B： (DE)(DE)(DE)Q)R)如果A是永真式，例如A为PP，用 (DE)替换A中P，得到A的置换例式 B： (DE)(DE) ， 显然B也是永真式。如果可以断定给定公式是某个永真式的置换例式的话，则这个公式也是永真式。,二.重言(永真)蕴涵式 有些重言

19、(永真)式，如(P(PQ)Q，公式中间是“”联结词，是很重要的，称之为重言蕴涵式。1.定义：如果公式AB是重言式，则称A重言(永真)蕴涵 B，记作AB。 上式可以写成 (P(PQ)Q注意符号“”不是联结词，它是表示公式间的“永真蕴涵”关系，也可以看成是“推导”关系。即AB可以理解成由A可推出B，即由A为真，可以推出B也为真。,2.重言(永真)蕴涵式证明方法 方法1.列真值表。(即列永真式的真值表)这里就不再举例了。 下面讨论另外两种方法。,先看一看AB的真值表，如果AB为永真式，则真值表的第三组指派不会出现。于是有下面两种证明方法。,方法2.假设前件为真，推出后件也为真。例如求证： (AB)C

20、)D(CD) AB证明:设前件(AB)C)D(CD) 为 真。则(AB)C)、D、(CD)均真， D为T，则D为F,得C为F,得AB为F,如果A为F，则A为T，所以AB为T。 如果B为F，则B为T，所以AB 为T。 (AB)C)D(CD) AB,(AB)C为T,CD为T,方法3.假设后件为假，推出前件也为假。例如求证： (AB)C)D(CD) AB证明:假设后件AB为F,则A与B均为T。1.如C为F，则(AB)C为F，所以前件 (AB)C)D(CD) 为F2.如C为T，则若D为T，则D为F，所以 前件(AB)C)D(CD) 为假 若D为F，则CD为F，所以 前件(AB)C)D(CD) 为假。(

21、AB)C)D(CD) AB,3.重要的重言蕴涵式(如教材第43页所示) I1.PQP I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q I12. Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC),上述公式的证明都比较简单，可以用假设前件为T，推出后件也为T的方法证明。4. 性质 1) 有自反性：对任何命题公式A，有AA 2) 有传递性：若AB且BC，则AC

22、 3) 有反对称性：若AB且BA，则AB 符号“”表示“等价”。本节重点掌握：永真式及永真蕴涵式的定义、证明方法、以及常用的公式。作业：第23页: (2) b) 、(6)、(8) e),1-5 等价公式 Equivalent Formulas,1. 例子 看下面三个公式的真值表 P Q PQ PQ QP F F T T T F T T T T T F F F F T T T T T 从真值表可以看出，不论对P、Q作何指派，都使得PQ、PQ和QP的真值相同，表明它们之间彼此等价。,2. 定义：A、B是含有命题变元P1,P2, Pn的命题公式，如不论对P1, P2 , , Pn作任何指派，都使得A

23、和B的真值相同，则称之为A与B等价，记作AB。 显然 PQPQQP3. 重要的等价公式 对合律 PP 幂等律 PPP PPP 结合律 P(QR)(PQ)R P(QR)(PQ)R 交换律 PQQP PQQP,分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P底-摩根定律 (PQ)PQ (PQ)PQ 同一律 PFP PTP 零律 PTT PFF 互补律 PPT PPF PQPQ PQQP PQ (PQ)(QP) PQ (PQ)(PQ) PQ (PQ)(PQ ),为便于记忆，将等价公式(前10个)与集合论的公式比较，请看集合公式： 对合律 AA A表示

24、A的绝对补集 幂等律 AAA AAA 结合律 A(BC)(AB)C A(BC)(AB)C 交换律 ABBA ABBA 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 吸收律 A(AB)A A(AB)A 底-摩根定律 (AB)AB (AB)AB 同一律 AA AEA E表示全集 零律 AEE A 互补律 AAE AA,4. 等价公式的证明方法 方法1：用列真值表。（不再举例） 方法2：用公式的等价变换.(用置换定律)置换定律:A是一个命题公式，X是A中的一部分且也是合式公式(A的子公式)，如果XY，用Y代替A中的X得到公式B，则AB。 应用置换定律以及前面列出的等价公式可以对给定

25、公式进行等价变换。,例题1. 求证吸收律 P(PQ)P证明 P(PQ) (PF)(PQ) (同一律) P(FQ) (分配律) PF (零律) P (同一律),例题2. 求证 (PQ)(PQ) P证明 (PQ)(PQ) (PQ)(PQ) (公式E16),公式E16 ： PQPQ, (PQ)(PQ) (摩根定律) (PQ)(PQ) (对合律)P(QQ) (分配律) PT (互补律) P (同一律),例题3.化简(PQ)(P(PQ)解： 原公式(PQ)(PP)Q) (E16,结合)(PQ)(PQ) (对合律，幂等律)(PQ)(QP) (交换律)(PQ)Q)P (结合律)QP (吸收律) 吸收律 P(

26、PQ)P P(PQ)P,5. 性质 1) 有自反性：任何命题公式A，有AA。 2) 有对称性：若AB，则BA 3) 有传递性：若AB且BC，则AC 4) 如果A(P1,P2,Pn)B(P1,P2,Pn)，则 A(P1,P2,Pn)B(P1,P2,Pn) 例 A(P,Q)PQ B(P,Q)PQ于是有 A(P,Q)B(P,Q) A(P,Q)PQ B(P, Q)PQ可见 A(P,Q)B(P, Q),6.等价公式的对偶性 (Duality) 从前面列出的等价公式看出，有很多是成对出现的。这就是等价公式的对偶性。 对偶式：在一个只含有联结词 、的公式A中，将换成，换成，T换成F，F换成T，其余部分不变，

27、得到另一个公式A*，称A与A*互为对偶式。 例如: A A* P P QR QR (PT)Q (PF)Q, 用对偶式求公式的否定 定理1-5.1 令A(P1,P2,Pn)是一个只含有联结词 、的命题公式，则 A(P1,P2,Pn)A*(P1,P2,Pn) 此定理可以反复地使用底-摩根定律得以证明。 下面我们验证一下。 令 A(P,Q)PQ A*(P,Q)PQ A(P,Q)(PQ) A*(P, Q)PQ 可见 A(P,Q)A*(P,Q) 推论:A(P1,P2,Pn)A*(P1,P2,Pn),例如，利用上述求公式的否定公式求(PQ)(PQ)R) (PQ)(PQ)R,对偶原理(定理1-5.2)： 令

28、A(P1,P2,Pn) 、B(P1,P2,Pn)是只含有联结词、的命题公式，则如果 A(P1,P2,Pn)B(P1,P2,Pn) 则 A*(P1,P2,Pn)B*(P1,P2, Pn) 证明：因为 A(P1,P2,Pn)B(P1,P2,Pn) 故 A(P1,P2,Pn)B(P1,P2,Pn) 而 A(P1,P2,Pn)A*(P1,P2,Pn) B(P1,P2,Pn)B*(P1,P2,Pn)故 A*(P1,P2,Pn) B*(P1,P2,Pn)所以 A*(P1,P2,Pn)B*(P1, P2, Pn),下面我们验证一下对偶原理： P(QR)(PQ)(PR) A B P(QR)(PQ)(PR) A

29、* B* PT T A B PF F A* B*本节要求掌握等价公式的证明方法及记忆公式。作业：第19页 (7) f) g) , (8) c),1-6.范式 Normal Form,范式就是命题公式形式的规范形式。这里约定在范式中 只含有联结词、和。一.析取范式与合取范式1.合取式与析取式 合取式：是用“”联结命题变元或变元的否定构成的式子。 如 P 、P 、PQ、PQR 析取式：是用“” 联结命题变元或变元的否定构成的式子。 如 P 、P 、PQ、PQR注: PPP PPP P是合(析)取式.,2.析取范式 公式A如果写成如下形式： A1A2.An (n1) 其中每个Ai (i=1,2,n)

30、是合取式，称之为A的析取范式。 3.合取范式 公式A如果写成如下形式： A1A2.An (n1) 其中每个Ai (i=1,2,n)是析取式，称之为A的合取范式。 例如，PQ 的析取范式与合取范式： PQ (PQ)(PQ)-析取范式 PQ (PQ)(PQ)-合取范式,4.析取范式与合取范式的写法 先用相应的公式去掉和。 公式E16 PQPQ 公式E21 PQ (PQ)(PQ) 公式E20 PQ (PQ)(QP) 再用E16 PQ (PQ)(PQ) 用公式的否定公式或摩根定律将后移到命题变元之前。 A(P1,P2,Pn)A*(P1,P2,Pn) 底-摩根定律 (PQ)PQ (PQ)PQ 用分配律、

31、幂等律等公式进行整理，使之成为所要求的形式。,例如求(PQ)R的析取范式与合取范式 (PQ)R (PQ)(PQ)R 去 (PQ)(PQ)R 后移 -析取范式 (PQ)R(PQ)(PQ)R 去 (PQ)(PQ)R 后移(PQR)(PQR) 分配律 -合取范式,二.主析取范式与主合取范式 一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。主析取范式 1.小项 Minterms 定义：在一个有n个命题变元的合取式中，每个变元必出现且仅出现一次，称这个合取式是个小项。 例如，有两个变元的小项： PQ、PQ、 PQ、 PQ,小项的性质 m3 m2 m1 m0 P Q PQ PQ PQ PQ 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F a).有n个变元，则有2n个小项。 b).每一组指派有且只有一个小项为T。为了记忆方便，可将各组指派对应的为T的小项分别记作m0,m1,m2,m2n-1 上例中 m0PQ m1PQ m2PQ m3PQ,