离散数学(命题逻辑)课后总结.doc

离散数学（课件上习题）第一章例1-1.1 判定下面这些句子哪些是命题。 2是个素数。 雪是黑色的。 2013年人类将到达火星。 如果 ab且bc，则ac 。（其中a,b,c都是 确定的实数） x+y5 请打开书！ 您去吗？ 是命题例1-2.1 P：2是素数。 P：2不是素数 。例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 PQ：小王能歌善舞。 例1-2.3. 灯泡或者 线路有故障。（析取“”） 例1-2.4. 第一节课上数学或者上英语。（异或 、排斥或 。即“”） 注意：P Q 与 (PQ)(QP ) 是一样的。 归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定 “ ” (2) 合取 “ ” (3) 析取 “ ” (4) 异或 “ ” (5) 蕴涵 “ ” (6) 等价 “ ” 例1-2.5： P表示：缺少水分。 Q表示：植物会死亡。 PQ：如果缺少水分，植物就会死亡。 PQ：也称之为蕴涵式，读成 “P蕴涵Q”， “如果P则Q”。 也说成P是PQ 的前件，Q是PQ的后件。 还可以说P是Q的充分条件，Q是P的必要条件。 以下是关于蕴含式的一个例子 P：天气好。 Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。命题1.、2.、3.写成： PQ 命题4.、5.、6.写成： QP例1-2.6： P：ABC 是等边三角形。 Q ：ABC是等角三角形。 PQ ：ABC 是等边三角形 当且仅当它是等角三角形。课后练习：填空已知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 的真值为( ).PP 的真值为( )。13节例1.说离散数学无用且枯燥无味是不对的。 P：离散数学是有用的。 Q：离散数学是枯燥无味的。 该命题可写成： (PQ)例2. 如果小张与小王都不去，则小李去。 P ： 小张去。 Q ： 小王去。 R ： 小李去。 该命题可写成： (PQ)R 如果小张与小王不都去，则小李去。 该命题可写成： (PQ)R 也可以写成： (PQ)R例3. 仅当天不下雨且我有时间，才上街。 P：天下雨。Q：我有时间。R：我上街。 分析：由于 “仅当 ”是表示 “必要条件 ”的，既 “天不下雨且我有时间 ”，是 “我上街 ”的必要条件。所以 该命题可写成： R(PQ) 例4. 人不犯我，我不犯人；人若犯我，我必犯人。 P ： 人犯我。Q ： 我犯人。 该命题可写成：(PQ)(PQ)或写成： PQ例5 .若天不下雨，我就上街；否则在家。 P：天下雨。Q ：我上街。R：我在家。 该命题可写成： (PQ)(PR). 注意：中间的联结词一定是“”，而不是“”，也不是“ ”。14节重言(永真)蕴涵式证明方法方法1.列真值表。方法2.假设前件为真，推出后件也为真。例如求证： (AB)C)D(CD) AB证明:设前件(AB)C)D(CD) 为真则(AB)C)、D、(CD)均真， D为T，则D为F CD为T 得C为F (AB)C )为T 得AB为F 如果A为F，则A为T，所以AB为T。 如果B为F，则B为T，所以AB 为T。 (AB)C)D(CD) AB方法3.假设后件为假，推出前件也为假 。例如求证： (AB)C)D(CD) AB 证明: 假设后件AB 为F, 则A 与B 均为T 。 1. 如C 为F ，则(AB)C为F，所以 前件(AB)C)D(CD) 为F 。 2. 如C 为T ，则 若D 为T ，则D 为F ， 所以前件(AB)C)D(CD) 为假； 若D为F，则CD 为F ， 所以 前件(AB)C)D(CD) 为假。(AB)C)D(CD) AB重要的重言蕴涵式( 如教材第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)15节重要的等价公式（课件中出现多次，可不用记忆） 对合律 P P 幂等律 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 PQ PQ PQ QP PQ (PQ)(QP) PQ (PQ)(PQ) PQ (PQ)(PQ )例题1. 求证吸收律 P(PQ)P证明 ： P(PQ) (PF)(PQ) (同一律) P(FQ) (分配律) PF (零律) P (同一律)例题2. 求证 (PQ)(PQ) P 证明 (PQ)(PQ) (PQ)(PQ) ( 公式E16) (PQ)(PQ) ( 摩根定律) (PQ)(PQ) ( 对合律) P(QQ) ( 分配律) PT ( 互补律) P ( 同一律) 公式E16 ： PQPQ 例题3.化简(PQ)(P(PQ)解 原公式(PQ)(PP)Q) (E16,结合) (PQ)(PQ) (对合律，幂等律) (PQ)(QP) (交换律) (PQ)Q)P (结合律) QP (吸收律)公式E16 ： PQPQ 1-6.范式(Paradigm) 例1. 求 PQ 和PQ的 主析取范式TTTTFFFTFTTFTTFFPQPQQP方法一：真值表 PQ m0m1m3 (PQ)(PQ)(PQ) PQm0m3 (PQ)(PQ)方法 ：用公式的等价变换 先写出给定公式的析取范式 A1A2.An 。 为使每个Ai 都变成小项，对缺少变元的Ai 补全变元，比如缺变元R ， 就用 联结永真式(RR) 形式补R 。 用分配律等公式加以整理。 PQPQ(P(QQ)(P P) Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)思考题: 永真式的主析取范式是什么样 ？（包含所有小项） 例2.求 PQ 和PQ的 主合取范式TTTTFFFTFTTFTTFFPQPQQP PQ M2 PQ PQ M1M2 (PQ )(PQ)方法：用公式的等价变换 先写出给定公式的合取范式 A1A2.An 。 为使每个Ai 变成大项，对缺少变元的析取式Ai 补全变元，比如缺变元R ， 就用联 结永假式(RR) 形式补R 。 用分配律等公式加以整理。 例如，求(PQ)R 的主合取范式 (PQ)R (PQ)R (PQ)R (PR)(QR) (P(QQ)R)(PP)QR) (PQR) (PQR) (PQR)(PQR) (PQR)(PQR) (PQR) 例3. 安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。令L1 、L2 、L3 分别表示语言课排在第一、第二、第三节。 M1 、M2 、M3 分别表示数学课排在第一、第二、第三节。 P1 、P2 、P3 分别表示原理课排在第一、 第二、第三节。 三位教师都满意的条件是：(L1L3)(M2M3)(P1P2 ) 为真。 将上式写成析取范式( 用分配律) 得：(L1M2)(L1M3)(L3M2)(L3M3)(P1P2)(L1M2P1)(L1M3P1) (L3M2P1)(L3M3P1) (L1M2P2)(L1M3P2) (L3M2P2)(L3M3P2) 可以取(L3 M2P1)、(L1M3P2) 为T ， 得到两种排法。TTTTTFTTFTFTTFFTTTTFFFTFFTFFTFFFA(P,Q,R)RQP课堂练习：1.已知A(P,Q,R)的真值表如图： 求它的主析取和主合取范式。2. 已知A(P,Q,R)的主析取范式中 含有下面小项m1, m3, m5, m7 求它的主合取范式.3. 已知A(P1,P2,Pn)的主合取范式中 含有k个大项，问它的主析取范式 中有多少个小项？课堂练习答案1.A(P,Q,R)的主析取范式: A(P,Q,R) m0m3m4m6m7 (PQR)(PQR) (PQR)(PQR)(PQ R) A(P,Q,R)的主合取范式： A(P,Q,R) M1M2M5 (PQR)(PQR)(PQR) 2. A(P,Q,R) M0M2M4 M6 (PQR)(PQR)(PQR) (PQR)3. A(P1,P2,Pn)的主析取范式中含有2n-k个小项.1-7. 命题逻辑推理例题求证 PQ，QR，P R证明 序号 前提或结论 所用规则 从哪几步得到 所用公式 (1) P P (2) PQ P (3) Q T (1)(2) I11 (4) QR P (5) R T (3)(4) I11例题求证(PQ)(QR)R P(1) QR P(2) R P(3) Q T (1)(2) I10(4) (PQ) P(5) PQ T (4) E8(6) P T (3)(5) I10注公式I10为： P,PQ Q 公式E8为： (PQ) PQ 例题 用命题逻辑推理方法证明下面推理的有效性： 如果我学习，那么我数学不会不及格。如果我不热衷于玩朴克，那么我将学习。但是我数学不及格。因此，我热衷于玩朴克。解:设 P：我学习。 Q：我数学及格。 R：我热衷于玩朴克。 于是符号化为： PQ，RP，Q RPQ，RP，Q R(1) PQ P(2) Q P (3) P T (1)(2) I12 (4) RP P(5) R T (3)(4) I12 (6) R T (5) E1注：公式I12为： Q，PQ P公式E1 为： RR 例题求证P(QS),RP,Q RS 证明(1) P(QS) P (2) P(QS) T (1) E16 (3) P(SQ) T (2) E3 (4) (PS)Q T (3) E5 (5) Q P (6) PS T (4)(5) I10 (7) PS T (6) E16 (8) RP P (9) RP T (8) E16 (10) RS T (7)(9) I13例题 用条件论证，证明例题 P(QS),RP,Q RS证明 (1) R P(附加前提) (2) RP P (3) P T (1)(2) I10 (4) P(QS) P (5) QS T (3)(4) I11 (6) Q P (7) S T (5)(6) I11 (8) RS CP例题 用命题逻辑推理方法证明下面推理的有效性： 如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。证明 先将命题符号化。 设 P：体育馆有球赛。 Q：青年大街交通拥挤。 R：小王提前出发。 S：小王迟到。 PQ，(QR)S (RS)P PQ，(QR)S (RS)P证明(1) RS P(附加前提)(2) R T (1) I1(3) S T (1) I2(4) (QR)S P(5) (Q) T (3)(4) I12(6) QR T (5) E8 (7) Q T (2)(6) I10(8) PQ P(9) P T (7)(8) I12(10)(RS)P CP例 PQ,(QR)R, (PS)S 证明 (1) S P(假设前提)(2) S T (1) E1(3) (PS) P(4) PS T (3) E8(5) P T (2)(4) I10(6) PQ P(7) Q T (5)(6) I11(8) (QR)R P(9) QR T (8) I1 (10) R T (8) I2(11) R T (7)(9) I10(12) RR T (10)(11) I9第一章 习题课1.有工具箱A、B、C、D，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。工具箱 改锥扳 手钳 子锤 子A有有B有有有C有有D有有解：设A、B、C、D分别表示带A、B、C、D箱。则总的条件为： (AC)(ABD)(BC)(BD) 为真。 改锥 扳手 钳子 锤子将(AC)(ABD)(BC)(BD)写成析取范式，上式(AC)(BC)(A(BD)(BD) (交换 ) (AB)C)(BD) (分配(提取C)、吸收) (ABB )(CB )(ABD)(CD) (分配) (AB)(CB )(ABD)(CD)分别可以取(AB)、(CB )、(CD)为真。于是可以得到三种携带方法：