离散数学24命题逻辑推理理论.ppt

2.4 命题逻辑推理理论命题逻辑推理理论•2.4.1 推理的形式结构推理的形式结构–推理的前提与结论推理的前提与结论, ,正确推理正确推理–推理定律推理定律•2.4.2 自然推理系统自然推理系统P–推理规则推理规则–直接证明法直接证明法, , 附加前提证明法附加前提证明法, , 归谬法归谬法( (反证法反证法), ), 归结证明法归结证明法1课件有效推理有效推理定义定义2.20 若对于每组赋值若对于每组赋值, A1 A2 …  Ak 为假为假, 或者或者当当A1 A2 … Ak为真时为真时, B也为真也为真, 则称由前提则称由前提A1,A2,…, Ak推推B的的推理有效推理有效或或推理正确推理正确, 并称并称B是是有效的结论有效的结论定理定理2.8 由前提由前提A1, A2, …, Ak 推出推出B 的推理正确当且仅当的推理正确当且仅当 A1 A2 … AkB为重言式为重言式.2课件推理的形式结构推理的形式结构形式形式(1) A1 A2 … AkB形式形式(2) 前提前提: A1, A2, … , Ak 结论结论: B 推理正确记作推理正确记作 A1 A2 … AkÞÞB判断推理是否正确的方法判断推理是否正确的方法:•真值表法真值表法•等值演算法等值演算法•主析取范式法主析取范式法•构造证明法构造证明法3课件实例实例例例1 判断下面推理是否正确判断下面推理是否正确:(1) 若若今今天天是是1号号, 则则明明天天是是5号号. 今今天天是是1号号. 所所以以, 明明天天是是5号号. 解解 设设 p: 今天是今天是1号号, q: 明天是明天是5号号 推理的形式结构为推理的形式结构为 (pq) pq证明证明 用等值演算法用等值演算法 (pq) pq ÛÛ  (( p q) p) q Û Û ((pq)p) q ÛÛ  pq q ÛÛ 1得证推理正确得证推理正确4课件实例实例(续续)(2) 若若今今天天是是1号号, 则则明明天天是是5号号. 明明天天是是5号号. 所所以以, 今今天天是是1号号. 解解 设设p: 今天是今天是1号号, q: 明天是明天是5号号. 推理的形式结构为推理的形式结构为 (pq) qp证明证明 用主析取范式法用主析取范式法 (pq) qp ÛÛ ( p q) qp ÛÛ   (( p q) q) p ÛÛ  q p ÛÛ ( pq) (pq)  (pq) (p q) ÛÛ m0 m2 m3 01是成假赋值是成假赋值, 所以推理不正确所以推理不正确.5课件推理定律推理定律——重言蕴涵式重言蕴涵式 A ÞÞ (A B) 附加律附加律 (A B) ÞÞ A 化简律化简律(AB) A ÞÞ B 假言推理假言推理(AB)B ÞÞ  A 拒取式拒取式(A B)B ÞÞ A 析取三段论析取三段论(AB) (BC) ÞÞ (AC) 假言三段论假言三段论(AB) (BC) ÞÞ (AC) 等价三段论等价三段论(AB) (CD) (A C) ÞÞ (B D) 构造性二难构造性二难 (AB) ( AB) ÞÞ B 构造性二难构造性二难(特殊形式特殊形式)(AB) (CD) (  BD) ÞÞ ( AC) 破坏性二难破坏性二难6课件自然推理系统自然推理系统P自然推理系统自然推理系统P由下述由下述3部分组成部分组成:1. 字母表字母表(1) 命题变项符号命题变项符号: p,q,r,…, pi,qi,ri,…(2) 联结词联结词:   ,   ,   ,  , (3) 括号与逗号括号与逗号: ( ), ,2. 合式公式合式公式3. 推理规则推理规则(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则7课件自然推理系统自然推理系统P(续续)(7) 拒取式规则拒取式规则 AB  B \\A(8) 假言三段论规则假言三段论规则 AB BC \\AC (4) 假言推理规则假言推理规则 AB A \\ B(5) 附加规则附加规则 A \\A B(6) 化简规则化简规则 A B \\A 8课件自然推理系统自然推理系统P(续续)(11) 破坏性二难推理规则破坏性二难推理规则 AB CD  BD \\AC(12) 合取引入规则合取引入规则 A B \\A B (9) 析取三段论规则析取三段论规则 A B  B \\A(10)构造性二难推理规则构造性二难推理规则 AB CD A C \\B D9课件直接证明法直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提: p q, qr, ps,  s结论结论: r((p q) )证明证明 ①① ps 前提引入前提引入②②   s 前提引入前提引入③③   p ①②①②拒取式拒取式④④ p q 前提引入前提引入⑤⑤ q ③④③④析取三段论析取三段论 ⑥⑥ qr 前提引入前提引入⑦⑦ r ⑤⑥⑤⑥假言推理假言推理⑧⑧ r((p q) ) ⑦④⑦④合取合取推理正确推理正确, , r((p q) )是有效结论是有效结论10课件实例实例例例3 构造推理的证明构造推理的证明: 若明天是星期一或星期三若明天是星期一或星期三, 我就有我就有课课. 若若有有课课, 今今天天必必需需备备课课. 我我今今天天下下午午没没备备课课. 所所以以, 明明天天不是星期一和星期三不是星期一和星期三. 解解 设设 p:明天是星期一明天是星期一, q:明天是星期三，明天是星期三， r:我有课，我有课， s:我备课我备课前提前提: (p q)r, rs,  s结论结论:  pq 11课件实例实例(续续)前提前提: (p q)r, rs,  s结论结论:  pq 证明证明①① rs 前提引入前提引入 ②②  s 前提引入前提引入③③  r ①②①②拒取式拒取式④④ (p q)r 前提引入前提引入⑤⑤  (p q) ③④③④拒取式拒取式⑥⑥  pq ⑤⑤置换置换结论有效结论有效, 即明天不是星期一和星期三即明天不是星期一和星期三12课件附加前提证明法附加前提证明法欲证明欲证明 等价地证明等价地证明前提前提: A1, A2, …, Ak 前提前提: A1, A2, …, Ak, C结论结论: CB 结论结论: B理由理由: (A1 A2 … Ak)(CB) ÛÛ  ( A1 A2 … Ak) ( C B) ÛÛ  ( A1 A2 … Ak C) B ÛÛ (A1 A2 … Ak C)B13课件实例实例例例4 构造下面推理的证明构造下面推理的证明:前提前提:  p q,  q r, rs结论结论: ps证明证明 ①① p 附加前提引入附加前提引入②②  p q 前提引入前提引入③③ q ①②①②析取三段论析取三段论④④  q r 前提引入前提引入⑤⑤ r ③④③④析取三段论析取三段论 ⑥⑥ rs 前提引入前提引入⑦⑦ s ⑤⑥⑤⑥假言推理假言推理推理正确推理正确, , ps是有效结论是有效结论14课件归谬法归谬法(反证法反证法)欲证明欲证明前提：前提：A1, A2, … , Ak 结论：结论：B将将 B加入前提加入前提, 若推出矛盾若推出矛盾, 则得证推理正确则得证推理正确. 理由理由: A1 A2 … AkB ÛÛ  (A1 A2 … Ak) B ÛÛ  (A1 A2 … AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当 (A1 A2 … AkB)为重言式为重言式15课件实例实例例例5 构造下面推理的证明构造下面推理的证明前提前提:  (p q) r, rs,  s, p结论结论:  q证明证明 用归缪法用归缪法①① q 结论否定引入结论否定引入②② rs 前提引入前提引入③③  s 前提引入前提引入④④  r ②③②③拒取式拒取式16课件实例实例(续续)⑤⑤  (p q) r 前提引入前提引入 ⑥⑥  (p q) ④⑤④⑤析取三段论析取三段论⑦⑦  pq ⑥⑥置换置换⑧⑧  p ①⑦①⑦析取三段论析取三段论⑨⑨ p 前提引入前提引入⑩⑩  p p ⑧⑨⑧⑨合取合取推理正确推理正确, ,  q是有效结论是有效结论17课件归结证明法归结证明法理由理由 (p q)((p r)(q r) Û Û  ( ((p q)((p r)) (q r) Û Û ( pq)((pr) q r Û (Û (( pq) q)((((pr) r) Û Û ( p q)((p r) Û 1Û 1归结规则归结规则 A   B   A   C \\ B   C18课件归结证明法归结证明法(续续)在自然推理系统在自然推理系统P中只需下述推理规则中只需下述推理规则:(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则(4) 化简规则化简规则(5) 合取引入规则合取引入规则(6) 归结规则归结规则19课件归结证明法的基本步骤归结证明法的基本步骤1. 将每一个前提化成等值的合取范式将每一个前提化成等值的合取范式, 设所有合取范式的设所有合取范式的全部简单析取式为全部简单析取式为A1, A2,…, At2. 将结论化成等值的合取范式将结论化成等值的合取范式B1 B2 … Bs, 其中每个其中每个Bj是简单析取式是简单析取式3. 以以A1,A2,…,At为前提为前提, 使用归结规则推出每一个使用归结规则推出每一个Bj, 1 j s4. 由合取引入规则得到结论由合取引入规则得到结论B1 B2 … Bs20课件实例实例例例6 用归结证明法构造下面推理的证明用归结证明法构造下面推理的证明:前提前提: ( (pq))r, rs,  s结论结论: ( (pq)()(p s) )解解 ( (pq))r Û Û ((p q))r Û (Û (pq))r Û Û ( (p r)((q r) ) rs Û Û  r s ( (pq)()(p s) Û ) Û ((p q)()(p s) Û () Û (pq)((p s) ) Û Û p((q s)推理可表成推理可表成前提前提: : p r, ,  q r, ,  r s, ,  s结论结论: p((q s)21课件实例实例(续续)前提前提: : p r, , q r, , r s, , s结论结论: p((q s)证明证明 ①①  q r 前提引入前提引入②②  r s 前提引入前提引入③③  q s ①②①②归结归结④④  s 前提引入前提引入⑤⑤  s0 0 ④④置换置换 ⑥⑥  r00 ②⑤②⑤归结归结⑦⑦ p r 前提引入前提引入⑧⑧ p00 ⑥⑦⑥⑦归结归结⑨⑨ p ⑧⑧置换置换 ⑩⑩ p((q s) ③⑨③⑨合取引入合取引入22课件实例：公安破案实例：公安破案•一个公安人员审查一件盗窃案，已知的事实如下：A或B盗窃了钻石；若A盗窃了钻石，则作案时间不能发生在午夜前；若B证词正确，则在午夜时屋里灯光未灭；若B证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。

谁盗窃了钻石呢？23课件。