离散数学讲义(第1章).ppt

天津财经大学天津财经大学 信息科学与技术系信息科学与技术系 王宁王宁 Discrete MathematicsDiscrete Mathematics 离散数学讲义离散数学讲义（电子版）（电子版） 1 离散数学是以研究离散量的结构和 相互间的关系为主要目标的现代数学的一 个重要分支。 引言：什么是离散数学？ 它与计算机科学中的数据结构、操 作系统、编译原理、算法分析、逻辑设计 、系统结构、容错诊断、机器定理证明等 课程联系紧密。 离散数学的内容较广，主要包括数 理逻辑、集合论、图论、代数结构等四个 基本部分。 2 离散数学将日常的概念、判断 、推理用数学符号来表示，用数学方 法进行思维。其目标是掌握严密的思 维方法、严格证明的推理能力和演算 能力，掌握处理各种具有离散结构的 事物的描述工具与方法，适应学习其 他专业课程的各种需要，为学习其他 计算机课程提供必要的数学工具。 引言：什么是离散数学？ 3 趣味逻辑数学题巧猜围棋子趣味逻辑数学题巧猜围棋子 甲手里有一个围棋子，要乙来猜棋 子的颜色是白的还是黑的。条件是 ：只允许乙问一个只能回答“是”或“ 否”的问题，但甲可以说真话，也可 以说假话。问：乙可以向甲提出一 个什么问题，然后从甲回答“是”或“ 否”中就能判断出甲手中围棋子的颜 色？ 4 趣味逻辑数学题巧猜围棋子趣味逻辑数学题巧猜围棋子 答案 乙问：“棋子是白的且你说了真话， 或者棋子是黑的且你说了假话，对 吗？” 分析：棋子白：甲说真话： 是 甲说假话： 是 棋子黑：甲说真话： 否 甲说假话： 否 5 趣味逻辑数学题巧猜围棋子趣味逻辑数学题巧猜围棋子 用数理逻辑学方法解题 P表示：“棋子为白色” Q表示：“甲说的是真话” 数理逻辑运算符： （非），（与），（或） 问题答案：S=(PQ)(PQ) 6 第一篇第一篇 数理逻辑数理逻辑 7 数理逻辑数理逻辑 数理逻辑是用数学方法来研究推理 过程的科学。主要是指引进一套符 号体系的方法，因此数理逻辑一般 又叫符号逻辑。 基本内容是：命题逻辑（演算）和 谓词逻辑（演算）。 8 第一章第一章 命题逻辑命题逻辑 9 第一章第一章 命题逻辑命题逻辑 命题演算是数理逻辑的基本组成部分， 是谓词演算的基础。 本章包括以下内容： 1-1 命题及其表示法 1-2 联结词 1-3 命题公式与翻译 1-4 真值表与等价公式 10 第一章第一章 命题逻辑命题逻辑 本章包括以下内容： 1-5 重言式与蕴含式 1-6 其他联结词 1-7 对偶与范式 1-8 推理理论 11 命题：能够表达判断（分辩其真假）的 陈述语句。 1-1 命题及其表示法 原子命题（简单命题）：不能分解成更简单的 陈述语句的命题。 复合命题：由连结词、标点符号和原子命题复合 构成的命题。 8例：中国是一个国家。 8 9为素数。 一个命题总是具有一个“值”，称为真值 一般用字母“T” (True)表示“真”，“F” (False)表示“假”。 只有具有确定真值的陈述句才是命题 12 判断下列句子哪些是命题？ 中国人民是伟大的。 雪是黑的。 1+101=110 别的星球上有生物。 全体立正！ 是命题，真值为T 是命题，真值为F 是命题，真值需根据上下文确定 是命题，它的真值是唯一确定的 ，只是目前人们不知道 不是命题，祈使句不是命题 1-1 命题及其表示法（续） 13 明天是否开大会？ 天气多好啊！ 我正在说谎。 我学英语，或者我学日语。 如果天气好，那么我去散步。 不是命题，疑问句不是命题 不是命题，感叹句不是命题 是悖论 复合命题 复合命题 1-1 命题及其表示法（续） 再次注意：命题是具有唯一真值的陈述句。 14 8习惯上，命题用大写字母A，B，P，Q， 或用带下标的大写字母Ai或数字12等表示。称为 命题标识符。 1-1 命题及其表示法（续） 命题常量：命题标识符表示确定的命题。 命题变元：命题标识符只表示任意命题的位置 标志。 （命题变元不是命题） 例如： P：今天下雨。 或 12：今天下雨。 15 （1）否定 设P为一命题，则新命题“P是不对的”称为P的 否定。记作： P 如：P：2是常数。 P：2不是常数。 Q：今天是星期四。 Q：今天不是星期四。 1-2 联结词 16 例：P：上海是一个大城市。 P：上海并不是一个大城市。 或 P：上海是一个不大的城市。 这两个命题具有相同的含义，因此用 同一个符号表示。 1-2 联结词（续） 17 P与 P的真值关系： T F P F T P 否定是一个一元运算。 1-2 联结词（续） 18 设P，Q是两个命题，新命题“P并且Q”是 一个复合命题，称为命题P，Q的合取。记作 ：PQ 如：P：北京是中国的首都。 Q：北京是一个故都。 PQ：北京是中国的首都并且是一个 故都。 （2）合取 1-2 联结词（续） 规定：PQ的真值为T当且仅当P，Q同时为T。 19 PQ：今天下雨且明天下雨。 例：P：今天下雨。 Q：明天下雨。 PQ：今天与明天都下雨。 则 PQ：这两天都下雨。 1-2 联结词（续） 合取是一个二元运算。 20 F F F F F T F T P Q T F T T P Q P Q的真值关系： 1-2 联结词（续） 21 设P，Q为两个命题，则复合命题“P或者Q” 称为命题P，Q的析取。记作：PQ 如：P：北京是中国的首都。 Q：北京是一个故都。 PQ：北京是中国的首都或者是一个故都。 规定：PQ的真值为T当且仅当P，Q中至少有 一个真值为T。 1-2 联结词（续） （3）析取 或：PQ的真值为F当且仅当P，Q同时为F。 22 PQ的真值关系： F F F T F T T T P Q T F T T P Q 1-2 联结词（续） 析取是一个二元运算。 23 注意：析取联结词与汉语中的“或”的意义不完 全相同。汉语中的“或”既可以表示“排斥或”，也 可以表示“可兼或”。 例如： P：今天晚上我在家看电视或去剧场看戏。 Q：他可能是100米或400米赛跑的冠军。 “排斥或” “可兼或” （析取） 1-2 联结词（续） R：他昨天做了二十或三十道习题。 这里“或”不是 命题联结词 命题R是一个原子命题。 24 设P，Q是两命题，其条件命题是一个复合命 题，记做PQ，读做“如果P，则Q”。命题 联结词“”亦可记作“”。 例1：如果某动物为哺乳动物，则它必胎生。 1-2 联结词（续） （4）条件（蕴含） 例2：如果我得到这本小说，那么我今夜就读完它。 例3：如果雪是黑的，那么太阳从西方出。 规定：当且仅当P的真值为T，Q的真值为 F时，PQ的真值为F。 25 PQ 的真值关系： T F F T F T F T P Q T F T T P Q 1-2 联结词（续） “善意的推定” 条件联结词是一个二元运算。 26 设P，Q是两命题，其双条件命题是一个复合 命题，记做PQ，读做“P当且仅当Q”。双 条件联结词也记作“ ”或“iff”。 1-2 联结词（续） （5）双条件 例1：两个三角形全等，当且仅当他们的三组对应 边相等。 例2：燕子飞回南方，春天来了。 例3：2+2=4当且仅当雪是白的。 规定：当P和Q的真值相同时， PQ 的真 值为T，否则为F。 27 PQ的真值关系： T F F F F T F T PQ T F T T P Q 1-2 联结词（续） 双条件联结词是一个二元运算。 28 在命题演算中，五个联结词的含义由真值表唯一确定。 1-2 联结词（续） T F P F T P F F F F F T F T P Q T F T T P Q F T T T P Q F F F T T F T T P Q T T F T P Q F F F T T F T T P Q T F F T P Q F F F T T F T T P Q 29 几个概念 命题常元（常项） 命题变元（变项） 命题公式：由命题变元、命题常元经逻 辑联结词再加上圆括号后组 成的符号串。 1-3 命题公式与翻译 30 概念： 命题公式没有真值，仅当在一个公式中 命题变元用确定的命题代入时，才得到 一个命题，其真值依赖于代换变元的那 些命题的真值。 1-3 命题公式与翻译（续） 并不是由命题变元，联结词和一些括号 组成的字符串都能成为命题公式。 31 合式公式（wff） （1）单个命题变元本身是一个合式公式。 （2）如果A是合式公式，那么A是合式公式。 （3）如果A、B是合式公式，那么（AB）、 （AB）、（AB）、（AB）都是合式公 式。 （4）当且仅当能够有限次地应用上面（1）、 （2）、（3）所得到的包含命题变元、联结词 和括号的符号串是合式公式。 递归定义 基础 归纳 界限 1-3 命题公式与翻译（续） 32 例如： 合式公式： (PQ) (PQ) (P(PQ) (PQ)(QR) (ST) 1-3 命题公式与翻译（续） 括号不匹配 括号不匹配 应是二元运算符 运算优先级： 非合式公式： (PQ)(Q) (PQ (PQ)Q) 33 例题1 我们要做到身体好、学习好、工作好，为祖 国的四化建设而奋斗。 试以符号形式写出命题： 1-3 命题公式与翻译（续） 解 找出原子命题： A：我们要做到身体好。 B：我们要做到学习好。 C：我们要做到工作好。 P：我们要为祖国的四化建设而奋斗。 命题的形式化描述： (A B C) P。 34 例题2 上海到北京的14次列车是下午五点半或六点开。 解 找出原子命题： P：上海到北京的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。 PQ原命题题P QPQ(PQ) TTFTTF TFTTFT FTTTFT FFFFTF 命题的形式化描述：(PQ)。 1-3 命题公式与翻译（续） “排斥或” 35 例题3 他既聪明又用功。 例题4 他虽聪明但不用功。 1-3 命题公式与翻译（续） 解 P：他聪明。 Q：他用功。 命题的形式化描述：P Q 解 P：他聪明。 Q：他用功。 命题的形式化描述：P Q 36 例题5 除非你努力，否则你将失败。 例题6 张三或李四都可以做这件事。 1-3 命题公式与翻译（续） 解 P：你努力。 Q：你失败。 命题的形式化描述： P Q 解 P：张三可以做这件事。 Q：李四可以做这件事。 命题的形式化描述： P Q 37 定义：在命题公式中，对于分量指派真值的各种可能组 合，就确定了这个命题公式的各种真值情况，把它们汇列 成表，就是命题公式的真值表。 含n个命题变元的命题公式，共有2n组赋值。 例题1 PQ的真值表。 PQPPQ TTFT TFFF FTTT FFTT 1-4 真值表与等价公式 38 例题2 (PQ) P的真值表。 PQPQP(PQ) P TTTFF TFFFF FTFTF FFFTF 例题3 (PQ) v (PQ)的真值表。 PQPQPQPQ(PQ) (PQ) TTFFTFT TFFTFFF FTTFFFF FFTTFTT 永假公式 （矛盾式 ） 1-4 真值表与等价公式（续） 39 例题4 (PQ)(PQ)的真值表。 PQPQ (PQ)PQPQ(PQ)(PQ) TTTFFFFT TFFTFTTT FTFTTFTT FFFTTTTT 永真公式 （重言式 ） 有一类公式不论命题变元做何种指派，其真值 永为真（假），我们把这类公式记为T（F） 1-4 真值表与等价公式（续） 40 定义：给定两个命题公式A和B，设P1， P2， Pn，为 所有出现在A和B中的原子变元。若给P1， P2， Pn任 意一组真值指派，A和B的真值都相同，则称A和B是等价 （或逻辑相等），记做AB。 例题5 证明PQ (PQ)(QP) 。 PQPQPQQP(PQ)(QP) TTTTTT TFFFTF FTFTFF FFTTTT 1-4 真值表与等价公式（续） 41 两个公式: （1） P Q PQ PQ P P QPQ TTFTT TFFFF FTTTT FFTTT （2） (P Q) (P Q) PQ PQ P QP QP Q(P Q) (P Q)PQ TTFFTFTT TFFTFFFF FTTFFFFF FFTTFTTT 1-4 真值表与等价公式（续） 42 10个命题定律： 序号定律表达式 1对合律P P 2幂等律PP P PP P 3结合律(P Q) R P (Q R) (P Q) R P (Q R) 4交换律P Q Q P P Q Q P 5分配律P (Q R) (P Q) (P R) P (Q R) (P Q) (P R) 1-4 真值表与等价公式（续） 43 10个命题定律： 序号定律表达式 6吸收律 P (P Q) P P (P Q) P 7德.摩根律 (P Q) P Q (P Q) P Q 8同一律 P F P P T P 9零律 P T T P F F 10否定律 P P T P P F 1-4 真值表与等价公式（续） 44 证明 列出真值表 PQ(P Q)P (P Q)(P Q)P (P Q) TTTTTT TFFTTT FTFFTF FFFFFF 1-4 真值表与等价公式（续） 例题6 验证吸收律 P (P Q) P P (P Q) P 可知吸收律成立。 45 定义：如果X是合式公式A的一部分，且X本身也是一个 合式公式，则称X为公式A的一个子公式。 定理：设X是合式公式A的子公式，若X Y，如果将 A中的X用Y来置换，则所得到的公式B与公式A等价， 即A B。 1-4 真值表与等价公式（续） 满足上述定理条件的置换称为等价置换（等价代换） 。 46 例题7 验证Q (P(PQ) Q P 1-4 真值表与等价公式（续） 证明 由吸收律，P(PQ) P，因此，根据上面的定 理，有Q (P(PQ) Q P，证毕。 PQ(PQ)P (PQ)QP(PQ)QP TTTTTT TFFTTT FTFFFF FFFFTT 或者利用真值表证明 47 1-4 真值表与等价公式（续） 例题8 证明：(PQ)(P Q)P 证明： (PQ)(P Q) 证明： P(QR) 例题9 证明：P(QR)Q(PR)R(QP) P(Q Q) 分配律 PT 否定律 P 同一律 P(QR) 前面公式 Q(PR) 结合律 Q(PR) 前面公式 （第二个等价公式类似可证。） 48 1-4 真值表与等价公式（续） 例题10 证明： (PQ)(P(QR)(PQ)(PR) T 证明： 原始左端 (PQ)(P(QR)(PQ)(PR) (PQ)(P(QR)(PQ)(PR) (PQ)(PQ)(PR)(PQ)(PR) (PQ)(PR)(PQ)(PR) T 49 1-5 重言式与蕴含式 定义：给定一命题公式，若无论对分量作怎样的指派，其 对应的真值永为T，则称该命题公式为重言式或永 真公式。 定义：给定一命题公式，若无论对分量作怎样的指派，其 对应的真值永为F，则称该命题公式为矛盾式或永 假公式。 定理：任何两个重言式（矛盾式）的合取或析取仍然是 一个重言式（矛盾式）。 50 例题1 证明 (PS)R)(PS)R)为重言式。 1-5 重言式与蕴含式（续） 定理：一个重言式（矛盾式），对同一分量都用任何公 式置换，其结果仍为一个重言式（矛盾式）。 证明 因为 PP T，若以(PS)R)置换P即得(P S)R)(PS)R) T 51 1-5 重言式与蕴含式（续） 定理：设A，B为两个命题公式，A B当且仅当A B 为一个重言式。 例题2 证明 (PQ) (PQ) 证明 PQPQ(PQ)PQPQ(PQ)(PQ) TTTFFFFT TFFTFTTT FTFTTFTT FFFTTTTT 再由上述定理得证。 52 1-5 重言式与蕴含式（续） 定义：当且仅当PQ是一个重言式时，我们称P蕴含Q，并 记作P Q。 对于PQ， 关系 P Q Q P Q P P Q 逆换式： Q P 反换式： P Q 逆反式： Q P 53 PQP QP QQ PQ PP Q TTFFTTTT TFFTFFTT FTTFTTFF FFTTTTTT 1-5 重言式与蕴含式（续） 要证PQ，只要证PQ是一个重言式，根据PQ 的定义，即证 （1）若指定P为T，则Q也为T； （2）若指定Q为F时，则P也为F。 或者 54 1-5 重言式与蕴含式（续） 证明1：假定Q(PQ)为T， 例题3 证明 Q(PQ) P。 证明2：假定P为F，则 则 Q为T 且 (PQ)为T 由 Q为F，(PQ)为T 则必须 P为F， 故 P为T (a) 若Q为F，则PQ为F，Q(PQ)为F (b) 若Q为T，则Q为F，Q(PQ)为F 因此原式成立。 55 1-5 重言式与蕴含式（续） 定理：设P，Q为两个命题公式， P Q的充要条件为P Q且Q P。 （1） 若AB，且A为重言式，则B也为重言式。 蕴含式常用性质： 设A，B，C为合式公式， （2） 若AB，BC，则AC（传递性） （3） 若AB，AC，则A(BC) （4） 若AB，CB，则(AC) B 56 （6）不可兼析取（异或） 1-6 其他联结词 设P，Q是两个命题公式，复合命题“P Q”表 示：P、Q中只有一个成立。 P QP QP Q T TTF T FTT F T TT F FFF 规定：P Q的真值为T当且仅当P与Q的真值不 相同。 P Q (P Q) 57 (1) P Q Q P （交换律） 1-6 其他联结词（续） 联结词 的性质 定理：设P，Q，R为命题公式，如果P Q R，则P R Q， Q R P，且P Q R为一矛盾式。 (2) (P Q) R P (Q R) （结合律） (3) P (Q R) (P Q) (P R) (4) (P Q) (PQ)(PQ) (5) (P Q) (PQ) (6) P P F， F P P， T P P 58 （7）条件否定 1-6 其他联结词（续） 设P，Q是两个命题公式，复合命题 P Q 称 作命题P和Q的条件否定。 P QP Q T TF T FT F T F F FF 规定：P Q的真值为T当且仅当P的真值为T ，Q的真值为F。 P Q (PQ) 59 1-6 其他联结词（续） （8）与非 设P，Q是两个命题公式，复合命题 P Q 称 作命题P和Q的与非。 P QP QP Q T T T F T F F T F T F T F F F T 规定：当且仅当P和Q的真值都为T时， P Q 为F。 PQ (PQ) 60 n(1) P P (P P) P 1-6 其他联结词（续） 联结词的性质 n(2) (P Q) (P Q) (P Q) P Q n(3) (P P) (Q Q) P Q ( P Q) P Q 61 1-6 其他联结词（续） （9）或非 设P，Q是两个命题公式，复合命题 P Q 称 作命题P和Q的或非。 规定：当且仅当P和Q的真值都为F时， P Q 为T。 P Q (P Q) P QP QP Q T T T F T F T F F T T F F F F T 62 n(1) P P (P P) P 1-6 其他联结词（续） 联结词的性质 n(2) (P Q) (P Q) (P Q) P Q n(3) (P P) (Q Q) P Q ( P Q) P Q 小结 nP Q (P Q) (P Q) (P P) (Q Q) nP Q (P P) (Q Q) (P Q) (P Q) n P P P P P 63 命题联结词之间有如下等价关系： 1. PQ (PQ)(QP) 2. P Q PQ 3. PQ (PQ) PQ (PQ) 4. P Q (PQ) (PQ)(PQ) 5. P Q (P Q) 6. PQ (PQ) 7. PQ (PQ) 1-6 其他联结词（续） 64 1-6 其他联结词（续） 九个命题联结词： 最小联结词组为： ， 或 ， 或 或 65 1-6 其他联结词（续） 联结词联结词真值表小结真值表小结 12345678 PQTFPQPQPQ P Q TTTFTTFFTF TFTFTFFTFT FTTFFTTFFT FFTFFFTTFT 910111213141516 PQPQ P Q PQP QPQP QQPQ P TTTFTFTFTF TFTFFTFTTF FTTFTFFTFT FFFTTFTFTF 66 序号定律表达式 1对对合律P P 2幂幂等律PP P PP P 3结结合律(P Q) R P (Q R) (P Q) R P (Q R) 4交换换律P Q Q P P Q Q P 5分配律P (Q R) (P Q) (P R) P (Q R) (P Q) (P R) 1-7 对偶与范式 10个命题定律： 67 序号定律表达式 6吸收律P (P Q) P P (P Q) P 7德.摩根律(P Q) P Q (P Q) P Q 8同一律P F P P T P 9零律P T T P F F 10否定律P P T P P F 1-7 对偶与范式（续） 10个命题定律： 68 定义：在给定的命题中，将联结词换成 ，将 换成 ，若有特殊变元F和T也相互替代， 所得公式A*称为A的对偶式。 1-7 对偶与范式（续） 显然，A*与A互为对偶式。 69 1-7 对偶与范式（续） (a) (P Q) R (b) (P Q) T (c) (P Q) (P (Q S) 例题1 写出下列表达式的对偶式。 例题2 求P Q，P Q的对偶式。 解：因为P Q (P Q)，故P Q的对偶式为 (P Q)，即P Q 同理P Q的对偶式为P Q 解： (a) (P Q) R (b) (P Q) F (c) (P Q) (P (Q S) 70 1-7 对偶与范式（续） 例题3 设A*(S，W，R)是 S ( W R)，证明 A*( S， W， R) A(S，W，R) 证明：由于A*(S，W，R)是S (WR)， 定理：设A*为A的对偶式，P1,P2,Pn是出现在A和A*中的 原子变元，则 A(P1,P2, Pn) A*(P1,P2, Pn) A(P1,P2, Pn) A*(P1,P2, Pn) 则 A*(S，W，R)是S (WR)。 但 A(S，W，R)是S (WR)， 故 A(S，W，R)是(S (WR) S (WR) ，得证。 71 1-7 对偶与范式（续） 定理：设A*为A的对偶式，P1,P2,Pn是出现在公式A和B 中的原子变元，如果A B，则A* B*。 例题4 如果A(P, Q, R)是P (Q (R P)，求它的 对偶式A*(P, Q, R)。并求与A及A*等价，但仅包含联 结词 ，及的公式。 解：因为 A(P, Q, R)是P (Q (R P)， 故 A*(P, Q, R)是P (Q (R P)， 又 P (Q (R P) (P (Q (R P) 因此 P (Q (R P) (P (Q (R P) 证明：A B，则A B，又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* B*。 72 定义：一个命题称为合取范式，当且仅当它具有如下的形 式： A1 A2 An，(n1) 其中A1,A2,An都是由命题变元或其否定所组成的析取式。 注意：一个命题的合取范式或析取范式不是唯一的。 1-7 对偶与范式（续） 定义：一个命题称为析取范式，当且仅当它具有如下的形 式： A1 A2 An，(n1) 其中A1,A2,An都是由命题变元或其否定所组成的合取式。 例如：(PSQ) (SR)， (P) (PSR) 例如：(PQPQ) (QP) (PQ)， Q (PQ) 73 求一个命题的合取范式或析取范式的步骤： 1-7 对偶与范式（续） (1) 将公式中的联结词化归成 ， 及 。 (2) 利用德.摩根定律将否定联结词直接移到各 命题变元之前。 (3) 利用分配律、结合律将公式归约为合取范式 或析取范式。 74 1-7 对偶与范式（续） 例题5 求(P (Q R) S的合取范式。 解： (P(QR)S (P(QR)S (P(QR)S P(QR)S (PS)(QR) (PSQ) (PSR) (P(QR)S 75 1-7 对偶与范式（续） 例题6 求 (P Q) (P Q) 的析取范式。 解：由公式(A B) (A B) ( A B) (PQ)(PQ) ( (PQ)(PQ) ) ( (PQ)(PQ) ) (PQPQ) (PQ)(PQ) (PQPQ) (PQ)P) (PQ) Q) (PQPQ) (PP)(QP) (PQ)(QQ) (PQPQ) (F(QP) (PQ)F) (PQPQ) (QP) (PQ) 76 定义：n个命题变元的合取式称为布尔合取（或小项），其 中每个变元与它的否定不能同时存在，但两者必须出 现且仅出现一次。 一般说来，n个命题变元共有2n个小项。 1-7 对偶与范式（续） 例如： 两个变元P和Q，其小项为： PQ，PQ， PQ， P Q。 三个变元P，Q，R的小项为： P Q R，P Q R，P Q R， P Q R， P Q R ， P Q R ， P Q R ， P Q R。 77 两个变元P和Q的小项的真值表： PQPQPQPQPQ 001000 010100 100010 110001 1-7 对偶与范式（续） 78 小项的二进制编码： n=2:m00 P Q， m01 P Q m10 P Q， m11 P Q 1-7 对偶与范式（续） m00m01m10m11 PQPQPQPQPQ 001000 010100 100010 110001 脚码为0表示对应原子变元的否定，脚码为1表示对应原子变元本身 。 79 三个变元P，Q，R的小项的真值表： P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 0 0 010000000 0 0 101000000 0 1 000100000 0 1 100010000 1 0 000001000 1 0 100000100 1 1 000000010 1 1 100000001 1-7 对偶与范式（续） 80 三个变元P，Q，R的小项的编码表: m000 P Q R m001 P Q R m010 P Q R m011 P Q R m100 P Q R m101 P Q R m110 P Q R m111 P Q R 1-7 对偶与范式（续） 81 小项的性质: 1-7 对偶与范式（续） （1）每一个小项当其真值指派与编码相同时，其真值为T ，在其余2n-1中指派情况下均为F。 （2）任意两个不同小项的合取式为永假。 （3）全体小项的析取式为永真，记为： 82 定义：对于给定的命题公式，如果有一个等价公式，它仅 由小项的析取所组成，则该等式称为原式的主析取 范式。 定理：在真值表中，一个公式的真值为T的指派所对应的 小项的析取，即为此公式的主析取范式。 1-7 对偶与范式（续） 对于给定命题公式的主析取范式，如果将其 命题变元的个数和出现次序固定后，则此公式的 主析取范式就是唯一的。 例如：( P Q) ( P Q) (P Q)是主析取范式 而 P ( P Q)， ( P Q) ( P Q R)不是主析取范式 83 求一个命题的主析取范式的方法： 1-7 对偶与范式（续） （2）由基本等价公式推演，步骤如下： (a) 化归为析取范式 (b) 除去析取范式中所有永假的析取项 (c) 将析取式中重复出现的合取项和相同的变元合并 (d) 对合取项补入没有出现的命题变元，即添加 (P P)式，然后应用分配律展开公式 （1）真值表法 84 1-7 对偶与范式（续） 例题6 求公式PQ，P Q及 (P Q)的主析取范式。 解：由真值表， PQPQP Q(P Q) T(1)T(1)TTF T(1)F(0)FTT F(0)T(1)TTT F(0)F(0)TFT PQ m11m01m00 PQ m11m10m01 (PQ) m10m01m00 (P Q) (P Q) (P Q) (P Q) (P Q) (P Q) (P Q) (P Q) (P Q) 85 1-7 对偶与范式（续） 例题7 求设一公式A的真值表如下，求其主析取范式。 PQRA T(1)T(1)T(1)T TTFF TFTF T(1)F(0)F(0)T FTTF FTFF FFTF F(0)F(0)F(0)T 解：公式A的主析取范式为 A m111m100m000 (P Q R) (P Q R) (P Q R) 86 1-7 对偶与范式（续） 例题8 求 (P Q) (P R) (Q R)的主析取范式。 解：原式 (P Q (RR) (P R (QQ) (Q R (P P) (PQR) (PQR) (PQR) (P QR) 87 1-7 对偶与范式（续） 例题9 求P (P Q) (Q P)的主析取范式。 解：原式 P ( ( P Q) (Q P) ) P ( P Q P) (Q Q P) P ( P Q P) (Q P) P (Q P) (P (Q Q) (Q P) (P Q) (P Q) (P Q) P (F Q) (Q P) P (F (Q P) 88 定义：n个命题变元的析取式称为布尔析取或大项。其中 每个变元与它的否定不能同时存在，但两者必须且 仅出现一次。 1-7 对偶与范式（续） 例如：P Q，P Q，P Q，P Q，及P Q R，P Q R等。 89 两个变元P和Q的大项的真值表： PQP QPQPQPQ 000111 011011 101101 111110 1-7 对偶与范式（续） 90 大项的二进制编码： n=2:M00 P Q M01 P Q M10 P QM11 P Q 1-7 对偶与范式（续） M00M01M10M11 PQP QPQPQPQ 000111 011011 101101 111110 脚码为0表示对应原子变元本身，脚码为1表示对应原子变元的否定 。 91 大项的二进制编码： n=3: M000 P Q R M001 P Q R M010 P Q R M011 P Q R M100 P Q R M101 P Q R M110 P Q R M111 P Q R 1-7 对偶与范式（续） 92 三个变元P，Q，R的大项的真值表： P Q RP Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 0 00 01111111 0 01 10111111 0 10 11011111 0 11 11101111 1 00 11110111 1 01 11111011 1 10 11111101 1 11 11111110 1-7 对偶与范式（续） 93 大项的性质: （1）每一个大项当其真值指派与编码相同时，其真值为F ，在其余2n-1中指派情况下均为T。 （2）任意两个不同大项的析取式为永真。 （3）全体大项的合取式为永假，记为： 1-7 对偶与范式（续） 94 定义：对于给定的命题公式，如果有一个等价公式，它仅 由大项的合取所组成，则该等式称为原式的主合取 范式。 定理：在真值表中，一个公式的真值为F的指派所对应的 大项的合取，即为此公式的主合取范式。 1-7 对偶与范式（续） 例如：( P Q) ( P Q) (P Q)是主析取范式 而 P ( P Q)， ( P Q) ( P Q R)不是主析取范式 95 例题10：利用真值表技术求(PQ)(PR)的主析取范式和 主合取范式。 1-7 对偶与范式（续） 解：公式(PQ)(PR)的真值表如下所示。 PQRPP QP R(PQ) (PR) 1 1 1FTFT 1 1 0FTFT 1 0 1FFFF 1 0 0FFFF 0 1 1TFTT 0 1 0TFFF 0 0 1TFTT 0 0 0TFFF 96 1-7 对偶与范式（续） 主析取范式为： m111 m110 m011 m001 (PQR) (PQR) (PQR) (PQR) 主合取范式为： M101 M100 M010 M000 (PQR) (PQR) (PQR) (PQR) 97 求一个命题的主合取范式的方法： 1-7 对偶与范式（续） （1）真值表法 （2）由基本等价公式推演，步骤如下： (a) 化归为合取范式 (b) 除去合取范式中所有永真的合取项 (c) 合并相同的合取项和相同的变元 (d) 对析取项补入没有出现的命题变元，即添加 (P P)式，然后应用分配律展开公式 98 例题11：化(P Q) ( P R)为主合取范式。 1-7 对偶与范式（续） 解： (PQ)(PR) ( (PQ)P ) ( (PQ)R ) (QP (RR) ) (PR (QQ) ) (QR (PP) ) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) ( (PP) (QP) ) ( (PR) (QR) ) ( T (QP) ) ( (PR) (QR) ) (QP) (PR) (QR) (PQR) (PQR) (PQR) (PQR) M100 M101 M111 M010 m000 m001 m011 m110 99 1-8 推理理论 定义：设A和C是两个命题公式，当且仅当AC为一重言 式，即AC时，称C为A的有效结论，或C可由A逻 辑推出。 n个前提的有效结论为：H1 H2 Hn C (*) 判别有效结论的过程就是论证过程，包括 (1) 真值表法 (2) 直接证法 (3) 间接证法 100 1-8 推理理论（续） (1) 真值表法（适用于计算机处理） 设P1，P2，Pn 为出现于前提H1 ，H2 ，Hm 和 结论C中的全部命题变元，对P1，P2，Pn 作全部 的真值指派，则能对应的确定H1 ，H2 ，Hm 和结 论C的所有真值，列真值表检验(*)式是否成立，法则 如下： (i) 找出H1 ，H2 ，Hm 均为T的行，若相应的C也为 T，则(*)式成立。 (ii) 找出每一个C为F的行，若H1 ，H2 ，Hm 中至少 有一个为F，则(*)式成立。 101 1-8 推理理论（续） 例题1：一份统计表格的错误或是由于材料不可靠，或是 由于计算有误；这份统计表格的错误不是由于材 料不可靠，所以这份统计表格的错误是由于计算 有错误。 解： 设命题变元为： P：统计表格的错误是由于材料不可靠。 Q：统计表格的错误是由于计算有错误。 则本题即为：Q是前提PQ， P的有效结论，即 (PQ)P Q 102 1-8 推理理论（续） PQP Q P(PQ)P TTTFF TFTFF FTTTT FFFTF 列出真值表： 方法1