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

1、命题逻辑推理理论离散数学1第1页，共26页，2022年，5月20日，8点45分，星期二2.4.1 推理的形式结构一、什么是推理定义2.19 设A1，A2 ， ，Ak ，B都是命题公式，若对于每组赋值, A1A2 Ak为假, 或者当A1 A2 Ak为真时，B也为真, 则称由前提A1，A2，, Ak推B的推理有效或推理正确, 并称B是有效的结论。2第2页，共26页，2022年，5月20日，8点45分，星期二定理2.8 由前提A1, A2, , Ak 推出B 的推理正确当且仅当 A1 A2 Ak B为重言式.如果把（A1 A2 Ak ） B为永真式记为：上式的含义？3第3页，共26页，2022年，5

2、月20日，8点45分，星期二二、推理的形式结构定义2.20 称（A1 A2 Ak ） B为由前提 A1, A2, , Ak推结论 B 的推理的形式结构。推理的形式结构一般有以下三种： 形式(1) A1 A2 Ak B 形式(2) 前提: A1, A2, , Ak 结论: B 形式(3) A1， A2 ， ， Ak B4第4页，共26页，2022年，5月20日，8点45分，星期二真值表法等值演算法主析取范式法构造证明法判断推理是否正确的方法:真值表的方法参见P.67例2.23。5第5页，共26页，2022年，5月20日，8点45分，星期二例1 判断下面推理是否正确:(1) 若今天是1号, 则明天

3、是5号. 今天是1号. 所以, 明天是5号. 解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为证明 用等值演算法 所以，原推理正确。6第6页，共26页，2022年，5月20日，8点45分，星期二例1 (2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号。解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为证明 用主析取范式法 这不是一个永真式，01是该公式成假的赋值，所以推理不正确。7第7页，共26页，2022年，5月20日，8点45分，星期二三、推理定律重言蕴涵式 A (AB) 附加律 (AB) A 化简律(AB)A B 假言推理(AB)B A 拒

4、取式(AB)B A 析取三段论(AB)(BC) (AC) 假言三段论(AB)(BC) (AC) 等价三段论(AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式)(AB)(CD)( BD) (AC) 破坏性二难8第8页，共26页，2022年，5月20日，8点45分，星期二注意：（1）推理规则中出现的A、B、C 等是元语言符号；（2）直接引用而不需证明，只要说明所引用规则的名称；（3）24个永真公式每个都可以等效为2个推理规则。9第9页，共26页，2022年，5月20日，8点45分，星期二2.4.2 自然推理系统P自然推理系统P由下述3部分组成:1. 字母表(

5、1) 命题变项符号: p,q,r, pi,qi,ri,(2) 联结词: , , , , (3) 括号与逗号: ( ), ,2. 合式公式3. 推理规则(1) 前提引入规则(2) 结论引入规则(3) 置换规则10第10页，共26页，2022年，5月20日，8点45分，星期二自然推理系统P(续)(7) 拒取式规则 AB B A(8) 假言三段论规则 AB BC AC (4) 假言推理规则 AB A B(5) 附加规则 A AB(6) 化简规则 AB A 11第11页，共26页，2022年，5月20日，8点45分，星期二自然推理系统P(续)(11) 破坏性二难推理规则 AB CD BD AC(12)

6、 合取引入规则 A B AB (9) 析取三段论规则 AB B A(10)构造性二难推理规则 AB CD AC BD12第12页，共26页，2022年，5月20日，8点45分，星期二直接证明法例2 在自然推理系统P中构造下面推理的证明:前提: pq, qr, ps, s结论: r(pq)证明 ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq) 合取推理正确, r(pq)是有效结论13第13页，共26页，2022年，5月20日，8点45分，星期二实例例3 构造推理的证明: 若明天是星期一或星期三, 我就有课. 若有课, 今天必需备课

7、. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课前提: (pq)r, rs, s结论: pq 14第14页，共26页，2022年，5月20日，8点45分，星期二实例(续)前提: (pq)r, rs, s结论: pq 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换结论有效, 即明天不是星期一和星期三15第15页，共26页，2022年，5月20日，8点45分，星期二附加前提证明法欲证明 等价地证明前提: A1, A2, , Ak 前提: A1, A2, , Ak,

8、C结论: CB 结论: B理由: (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B16第16页，共26页，2022年，5月20日，8点45分，星期二实例例4 构造下面推理的证明:前提: pq, qr, rs结论: ps证明 p 附加前提引入 pq 前提引入 q 析取三段论 qr 前提引入 r 析取三段论 rs 前提引入 s 假言推理推理正确, ps是有效结论17第17页，共26页，2022年，5月20日，8点45分，星期二归谬法(反证法)欲证明前提：A1, A2, , Ak 结论：B将B加入前提, 若推出矛盾, 则得证推理正确. 理由: A1A

9、2AkB (A1A2Ak)B (A1A2AkB)括号内部为矛盾式当且仅当 (A1A2AkB)为重言式18第18页，共26页，2022年，5月20日，8点45分，星期二实例例5 构造下面推理的证明前提: (pq)r, rs, s, p结论: q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式19第19页，共26页，2022年，5月20日，8点45分，星期二实例(续) (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取推理正确, q是有效结论20第20页，共26页，2022年，5月20日，8点45分，星期二课堂练习11、 证明

10、2、 证明21第21页，共26页，2022年，5月20日，8点45分，星期二证证明前提附加前提、，假言推理前提、，拒取式、，析取三段论前提、，拒取式、，CP22第22页，共26页，2022年，5月20日，8点45分，星期二证 证明假设前提，E1前提、，假言推理前提、，析取三段论前提，化简、，合取引入 是一个永假式，因此，原推理正确。23第23页，共26页，2022年，5月20日，8点45分，星期二应用实例1 分析下列事实“如果我有很高的收入，那么我就能资助许多贫困学生；如果我能资助许多贫困学生，那么我很高兴；但我不高兴，所以我没有很高的收入。”试指明前提和结论，并给予证明。课堂练习224第24页，共26页，2022年，5月20日，8点45分，星期二应用实例2 将下列条件作为前提，验证所得结