离散数学命题逻辑推理理论

1、离散数学命题逻辑推理理论1第1页，共23页，2022年，5月20日，11点10分，星期五有效推理定义2.20 若对于每组赋值, A1A2 Ak 为假, 或者当A1A2Ak为真时, B也为真, 则称由前提A1,A2, Ak推B的推理有效或推理正确, 并称B是有效的结论定理2.8 由前提A1, A2, , Ak 推出B 的推理正确当且仅当 A1A2AkB为重言式.2第2页，共23页，2022年，5月20日，11点10分，星期五推理的形式结构形式(1) A1A2AkB形式(2) 前提: A1, A2, , Ak 结论: B 推理正确记作 A1A2AkB判断推理是否正确的方法:真值表法等值演算法主析取

2、范式法构造证明法3第3页，共23页，2022年，5月20日，11点10分，星期五实例例1 判断下面推理是否正确:(1) 若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号. 解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为 (pq)pq证明 用等值演算法 (pq)pq (pq)p)q (pq)p)q pqq 1得证推理正确4第4页，共23页，2022年，5月20日，11点10分，星期五实例(续)(2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号. 解 设p: 今天是1号, q: 明天是5号. 推理的形式结构为 (pq)qp证明 用主析取范式法

3、(pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 01是成假赋值, 所以推理不正确.5第5页，共23页，2022年，5月20日，11点10分，星期五推理定律重言蕴涵式 A (AB) 附加律 (AB) A 化简律(AB)A B 假言推理(AB)B A 拒取式(AB)B A 析取三段论(AB)(BC) (AC) 假言三段论(AB)(BC) (AC) 等价三段论(AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式)(AB)(CD)( BD) (AC) 破坏性二难6第6页，共23页，2022年，5月20日，11点1

4、0分，星期五自然推理系统P自然推理系统P由下述3部分组成:1. 字母表(1) 命题变项符号: p,q,r, pi,qi,ri,(2) 联结词: , , , , (3) 括号与逗号: ( ), ,2. 合式公式3. 推理规则(1) 前提引入规则(2) 结论引入规则(3) 置换规则7第7页，共23页，2022年，5月20日，11点10分，星期五自然推理系统P(续)(7) 拒取式规则 AB B A(8) 假言三段论规则 AB BC AC (4) 假言推理规则 AB A B(5) 附加规则 A AB(6) 化简规则 AB A 8第8页，共23页，2022年，5月20日，11点10分，星期五自然推理系统

5、P(续)(11) 破坏性二难推理规则 AB CD BD AC(12) 合取引入规则 A B AB (9) 析取三段论规则 AB B A(10)构造性二难推理规则 AB CD AC BD9第9页，共23页，2022年，5月20日，11点10分，星期五直接证明法例2 在自然推理系统P中构造下面推理的证明:前提: pq, qr, ps, s结论: r(pq)证明 ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq) 合取推理正确, r(pq)是有效结论10第10页，共23页，2022年，5月20日，11点10分，星期五实例例3 构造推理的

6、证明: 若明天是星期一或星期三, 我就有课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课前提: (pq)r, rs, s结论: pq 11第11页，共23页，2022年，5月20日，11点10分，星期五实例(续)前提: (pq)r, rs, s结论: pq 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换结论有效, 即明天不是星期一和星期三12第12页，共23页，2022年，5月20日，11点10分，星期五附加前提证明法欲证明 等价地证

7、明前提: A1, A2, , Ak 前提: A1, A2, , Ak, C结论: CB 结论: B理由: (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B13第13页，共23页，2022年，5月20日，11点10分，星期五实例例4 构造下面推理的证明:前提: pq, qr, rs结论: ps证明 p 附加前提引入 pq 前提引入 q 析取三段论 qr 前提引入 r 析取三段论 rs 前提引入 s 假言推理推理正确, ps是有效结论14第14页，共23页，2022年，5月20日，11点10分，星期五归谬法(反证法)欲证明前提：A1, A2, ,

8、Ak 结论：B将B加入前提, 若推出矛盾, 则得证推理正确. 理由: A1A2AkB (A1A2Ak)B (A1A2AkB)括号内部为矛盾式当且仅当 (A1A2AkB)为重言式15第15页，共23页，2022年，5月20日，11点10分，星期五实例例5 构造下面推理的证明前提: (pq)r, rs, s, p结论: q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式16第16页，共23页，2022年，5月20日，11点10分，星期五实例(续) (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取推理正确, q是有效结论17第

9、17页，共23页，2022年，5月20日，11点10分，星期五归结证明法理由 (pq)(pr)(qr) (pq)(pr)(qr) (pq)(pr)qr (pq)q)(pr)r) (pq)(pr) 1归结规则 A B A C B C18第18页，共23页，2022年，5月20日，11点10分，星期五归结证明法(续)在自然推理系统P中只需下述推理规则:(1) 前提引入规则(2) 结论引入规则(3) 置换规则(4) 化简规则(5) 合取引入规则(6) 归结规则19第19页，共23页，2022年，5月20日，11点10分，星期五归结证明法的基本步骤1. 将每一个前提化成等值的合取范式, 设所有合取范式

10、的全部简单析取式为A1, A2, At2. 将结论化成等值的合取范式B1B2Bs, 其中每个Bj是简单析取式3. 以A1,A2,At为前提, 使用归结规则推出每一个Bj, 1js4. 由合取引入规则得到结论B1B2Bs20第20页，共23页，2022年，5月20日，11点10分，星期五实例例6 用归结证明法构造下面推理的证明:前提: (pq)r, rs, s结论: (pq)(ps)解 (pq)r (pq)r (pq)r (pr)(qr) rs rs (pq)(ps) (pq)(ps) (pq)(ps) p(qs)推理可表成前提: pr, qr, rs, s结论: p(qs)21第21页，共23页，2022年，5月20日，11点10分，星期五实例(续)前提: pr, qr, rs, s结论: p(qs)证明 qr 前提引入 rs 前提引入 qs 归结 s 前提引入 s0 置换 r0 归结 pr 前提引入 p0 归结 p 置换 p(qs) 合取引入22第22页，共23页，2022年，5月