离散数学1-3-2 命题逻辑

1、请交作业一复习思考题2n由p、q构成的重言式的主析取范式为_.n矛盾式的主析取范式为_。n已知由三个变量构成的公式A的主析取范式为：A (1,2,4,7)，则 公式公式A的类型是的类型是_； 公式公式A的主合取范式是的主合取范式是_。复习思考题2n 有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱由，一为死亡，你可任意开启一门。为协助你脱逃，今派两名战士负责解答你所提出的任何问题。逃，今派两名战士负责解答你所提出的任何问题。惟可虑者，此两战士中一名天性诚实，一名说慌惟可虑者，此两战士中一名天性诚实，一

2、名说慌成性，今后生死由你自己选择。成性，今后生死由你自己选择。”逻辑学家深思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？n 逻辑学家手指一门问身旁一名战士，说：逻辑学家手指一门问身旁一名战士，说：“这扇门是死亡门，他这扇门是死亡门，他（指另一名战士）（指另一名战士）将将回答回答是是，对吗？，对吗？”第1章 命题逻辑 1.1 命题符号化及联结词1.2 命题公式及分类1.3 等值演算1.4 范式1.5 联结词全功能集1.7 推理理论1.5 联结词全功能集 复合联结词与非式与非式: p q(p q)或非式或非式: p q(p q)pqp q p q0011011010101100如

3、如:p:他在家里他在家里. q:他在做作业他在做作业. p q: 并非并非他在家里或在做作业他在家里或在做作业.联结词“”的性质 n定义定义： pq (pq) n性质性质 p (pp) pp pq (pq) (pq) (pq)(pq) pq (pq) (p)(q) (pp)(qq)联结词“”的性质 n定义：定义： p q(pq) n性质性质 p (pp) pp pq (pq) (pq) (pq)(pq) pq (pq) (p) (q) (pp)(qq)联结词全功能集n 联结词全功能集 设设S是一个是一个联结词集合联结词集合，若任何，若任何真值函数真值函数都可以由仅含都可以由仅含S中的联结词构成

4、的公式表示，则称中的联结词构成的公式表示，则称S是是联结词全功能集联结词全功能集.n 说明 n在在S中，若一个联结词可由集合中的其他联结词定义，中，若一个联结词可由集合中的其他联结词定义，则称此联结词为则称此联结词为冗余的联结词冗余的联结词，否则称为，否则称为独立的联结词独立的联结词。 p q p q， p q (p q) ( p q )n 在在 ， ， ，中中，是冗余的。是冗余的。n 而在 ， ， 中， p q （ p q ）n 在在 ， 中无冗余的联结词。中无冗余的联结词。n 同理，同理，在在 ， 中无冗余的联结词。中无冗余的联结词。所以所以” ”是是冗余的。冗余的。联结词极小全功能集n定

5、义 n若一个若一个联结词全功能集联结词全功能集中不含冗余的联结词，中不含冗余的联结词，则称它是则称它是联结词极小全功能集联结词极小全功能集。n如：联结词全功能集有n ， ， ，, ， ， ，, , n ， ， , , , ， n如：联结词极小全功能集有n ， ， ， , , 联结词全功能集举例n 例例: 将公式将公式 p q 化成只含下列各联结词集中的化成只含下列各联结词集中的联结词的等值的公式联结词的等值的公式. (1) ，；(2) ，；(3) ；(4) .解解： (1) p q ( pq). (2) p q ( pq) (pq). (3) p q p(qq) ( (p(qq) (p(qq)

6、 (p(qq)(p(qq). (4) p q ( pq) ( p)q(pp)q.1.7 命题逻辑的推理理论n 引例: (1) 正项级数收敛当且仅当部分和有上界正项级数收敛当且仅当部分和有上界. (2) 若若A C B D，则，则A B且且C D.n 推理 从从前提前提出发推出出发推出结论结论的思维过程。的思维过程。n上面上面(1)是正确的推理，而是正确的推理，而(2)是错误的推理是错误的推理. n 推理的组成n前提前提是推理所根据的是推理所根据的已知命题已知命题n结论结论是从前提出发通过推理而得到的是从前提出发通过推理而得到的新命题新命题n 证明 描述推理正确或错误的过程描述推理正确或错误的过

7、程. . n 要研究推理，首先应该明确什么样的推理是有效的或正确的。推理的形式结构n 定义定义n 若若 (A1 A2 Ak ) B为为重言式重言式， 则称则称由由 A1, A2, , Ak推出结论推出结论B的的推理正确（有推理正确（有效结论）效结论） , 否则否则推理不正确（错误）推理不正确（错误）.n “A1, A2, , Ak 推出结论B” 的推理正确 当且仅当 A1 A2 AkB为重言式.n 推理的形式结构推理的形式结构: A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 结论：结论： B n 若推理正确，则记作：若推理正确，则记作：A1 A2 Ak B判断推理是否正确的

8、方法n真值表法n等值演算法n主析取范式法n构造证明法 n说明：说明：n当命题变项比较少时，用前当命题变项比较少时，用前3 3个方法比较方便个方法比较方便, , 此时采用此时采用形式结构形式结构“ A1 A2 AkB” . n而在构造证明时，而在构造证明时，采用采用 前提前提: A1, A2, , Ak 结论结论: B例：判断下面推理是否正确?（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。解题方法将命题符号化将命题符号化写出前提、结论和推理的形式结构写出前提、结论和推理的形式结构进行判断进行判断解： 设 p：天气凉快，q：小王去游泳. 前提： p q，p 结论： q 推理的形式结

9、构为： (pq) p) q 判断上式是否为重言式 例：判断下面推理是否正确?（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断 (pq) p) q 是否为重言式 方法1：真值表法pqpq(pq) p(pq) p) q00101011011011111001例：判断下面推理是否正确?（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断 (pq) p) q 是否为重言式 方法2：等值演算法 (pq) p) q ( pq) p)q (p q) p q (p q) (p q) 1例：判断下面推理是否正确?（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断

10、(pq) p) q 是否为重言式 方法3：主析取范式法 (pq) p) q ( pq) p)q (p q) p q m11 m0 x mx0 m11 m00 m01 m00 m10 (0,1,2,3) 1例：判断下面推理是否正确?（2）若我上街，我一定去书店。我没上街，所以我没去书店。解： 设 p：我上街，q：我去书店. 前提： p q， p 结论： q 推理的形式结构为： (p q)p) q 判断上式是否为重言式 (p q)p) q ( p q) p )q (p q) p q m10 m1x mx0 m10 m10 m11 m00 m10 (0,2,3)不是重言式！不是重言式！所以推理不正确

11、所以推理不正确构造证明法及推理定律n 构造证明法n一个描述推理过程的命题公式序列。一个描述推理过程的命题公式序列。n其中的每个命题公式可以是其中的每个命题公式可以是n已知的前提，已知的前提，n由某些前提依据由某些前提依据等价关系式等价关系式或或蕴涵关系式蕴涵关系式、应用、应用推推理规则理规则得到的结论得到的结论n 重要的推理定律 A (A B) 附加律附加律 (A B) A 化简律化简律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式构造证明法及推理定律n 重要的推理定律 (A B)B A 析取三段论析取三段论 (AB) (BC) (AC) 假言三段论假言三段论 (AB) (

12、BC) (AC) 等价三段论等价三段论 (AB) (CD) (A C) B D 构造性二难构造性二难 (AB) ( AB) (AA) B 构造性二难构造性二难 （特殊形式）（特殊形式）(AB) (CD) ( BD) AC 破坏性二难破坏性二难说明：说明： (1)A, B, C, D为元语言符号为元语言符号 (2)(2)A AB B产生两条推理定律产生两条推理定律: : A A B, B B, B A A常用的推理规则 (1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则(4) 假言推理规则假言推理规则 AB A B(5) 附加规则附加规则 A A B (6)

13、 化简规则化简规则 A B A (7) 拒取式规则拒取式规则 AB B A(8) 假言三段论规则假言三段论规则 AB BC AC 推理规则(续) (11) 破坏性二难推理破坏性二难推理规则规则 AB CD BD AC(12) 合取引入规则合取引入规则 A B A B (9) 析取三段论规则析取三段论规则 A B B A (10)构造性二难推理构造性二难推理规则规则 AB CD A C B D构造证明直接证明法构造下列推理的证明：前提：前提：p r, q s, p q 结论：结论：r s证明证明1： p q 前提前提 p q 置换规则置换规则 q s 前提前提 p s 假言三段论规则假言三段论规

14、则 s p 置换规则置换规则 p r 前提前提 s r 假言三段论规则假言三段论规则 r s 置换规则置换规则证明2： p r 前提 q s 前提 p q 前提 r s 构造性二难构造性二难构造证明直接证明法构造下列推理的证明：前提：前提： p q，p r, s t, s r, t 结论：结论：q证明：证明： s t 前提前提 t 前提前提 s 拒取式拒取式 s r 前提前提 r 假言推理假言推理 p r 前提前提 p 拒取式拒取式 p q 前提前提 q 析取三段论析取三段论如果如果今天是星期二今天是星期二，则要，则要进行英语进行英语或或离散数学离散数学考试考试，如果，如果英语老师有会英语老师

15、有会，则不考英语。今天是星期，则不考英语。今天是星期二，英语老师有会，所以进行离散数学考试。二，英语老师有会，所以进行离散数学考试。 解：设 p：今天是星期二。：今天是星期二。 q：进行英语考试。：进行英语考试。 r：进行离散数学考试。：进行离散数学考试。 s：英语老师有会。：英语老师有会。 前提：前提： p(q r)，sq，p，s 结论：结论：r写出对应下面推理的证明 p (q r) 前提前提 p 前提前提 q r 假言推理假言推理 s q 前提前提 s 前提前提 q 假言推理假言推理 r 析取三段论析取三段论构造证明附加前提证明法 欲证明欲证明 前提：前提：A1, A2, , Ak 结论：

16、结论：CB等价地证明等价地证明 前提：前提：A1, A2, , Ak, C 结论：结论：B 理由：理由： (A1 A2 Ak) (C B) (A1 A2 Ak) ( C B) ( (A1 A2 Ak ) C) B) (A1 A2 Ak C) B (A1 A2 Ak C) B 例如：证明下列推理。 前提： p (q r)， s p ， q ， 结论： s r证明证明： s p 前提前提 s p 置换置换 p (q r) 前提前提 s (q r) 假言推理假言推理 s q r 置换置换 q 前提前提 s r 析取析取三段论三段论 s r 置换置换直接证明法举例例如：证明下列推理。 前提： p (q r)， s p ， q ， 结论： s r证明证明： s p 前提前提 s 附加前提引入附加前提引入 p 析取析取三段论三段论 p (q r) 前提前提 q r 假言推理假言推理 q 前提前提 r 假言推理假言推理附加前提证明法 举例构造证明归谬法（反证法） 欲证明欲证明 前提：前提：A1, A2, , Ak 结论：结论：B将将 B 加入前提，若推出矛盾，则得证推理正确加入前提，若推出矛盾，则得证推理正确.理由