离散数学第6讲

《离散数学第6讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学第6讲回顾上节课重要知识点：24个重要等值式析取范式与合取范式及相关定理极大项和极小项的概念主合取范式、主析取范式，二者的关系（必考题，一般运算较繁，应力求熟练）联结词的完备集1第三章命题逻辑的推理理论本章基本内容：3.1推理的形式结构基本概念推理方法：真值表法；等价（值）演算法；主析取范式九条重要的推理定律3.2自然推理系统定义推理证明中常用的推理规则2第三章命题逻辑的推理理论本讲基本知识点：3.1推理的形式结构基本概念推理方法：真值表法；等价（值）演算法；主析取范式九条重要的推理定律3在数学和其他自然学科（如人工智

2、能）中，经常要考虑从某些前提A1,A2,…,An能够推导出什么结论－推理。数理逻辑的主要任务就是用数学的方法来研究推理问题。基本概念：推理：从前提推出结论的思维过程。前提：已知的或假定的命题公式（可有多个前提）结论：从前提出发应用推理规则推出的命题公式。推理的一般形式：前提

3、-结论第三章命题逻辑的推理理论4第三章命题逻辑的推理理论3.1推理的形式结构定义3.1——推理的有效性设A1，A2，…Ak，B都是命题公式，若对于A1，A2，…Ak，B中出现的命题变项的任意一组赋值，或者A1∧A2∧…∧Ak为假，或者当A1∧A2∧…∧Ak

4、为真时，B也为真，则称由前提A1，A2，…Ak推出B的推理是有效的或正确的，并称B是有效的结论。5第三章命题逻辑的推理理论说明：（1）由前提A1，A2，…Ak推B的推理记作{A1，A2，…Ak}

5、-B,这称为推理的形式结构。如果推理是正确的，记作{A1，A2，…Ak}

6、=B，否则记作{A1，A2，…Ak}

7、≠B。（2）对于任一组赋值，前提和结论的取值有以下四种情况：①A1∧A2∧…∧Ak为0，B为0。√②A1∧A2∧…∧Ak为0，B为1。√③A1∧A2∧…∧Ak为1，B为0。×④A1∧A2∧…∧Ak为1，B为1。√6第三章命题

8、逻辑的推理理论例3.1:(1){p,pq}

9、-q(2){p,qp}

10、-q解：利用真值表，判断会不会出现定义中存在的情况③。pqp∧(pq)qp∧(qp)q0001101100010011000110117第三章命题逻辑的推理理论对于以上简单的推理，不用真值表也可以判断推理是否正确，在(1)中，前提为p∧(pq)，当q为假时，无论p取真取假，均为假。在(2)中，前提为p∧(qp)，当q为假时，如果p为真，则p∧(qp)为真，出现了前提为真，结论为假的情况，故推理是不正确的。8第三章命题逻辑的推理理论推理的另一种形式

11、：定理3.1命题公式A1，A2，…Ak推B的推理正确当且仅当(A1∧A2∧…∧Ak)B为重言式。（证明参见课本）于是推理的一般形式可转化为蕴含式：(A1∧A2∧…∧Ak)B推理正确转化为：A1∧A2∧…∧Ak=>B9第三章命题逻辑的推理理论于是，以后推理的形式就写作：前提：p,pq结论：q推理的形式结构：(p∧(pq))q判断推理是否正确的方法就是判断重言蕴涵式的方法：1、真值表法；2、等值演算法；3、主析取范式法。10第三章命题逻辑的推理理论由以下三种方法1、真值表法；2、等值演算法；3、主析取范式法。解决推理问题

12、的步骤：（a）将命题符号化；（b）写出前提、结论和推理的形式结构；（c）进行判断11第三章命题逻辑的推理理论例：判断下列推理是否正确。1、今天小李或去网吧或去教室。他没去教室，所以他去网吧了。设p：小李去网吧。q：小李去教室。则，前提：p∨q,רq结论：p推理的形式结构：((p∨q)∧רq)p12第三章命题逻辑的推理理论pqp∨qרq(p∨q)∧רq((p∨q)∧רq)p000101011001101111111001方法1：真值表法由真值表可知，((p∨q)∧רq)p为重言式，推理正确。13第三章命题逻辑的推理理论方法

13、2：等值演算法：((p∨q)∧רq)p((p∧רq)∨(q∧רq))p(p∧רq)pר(p∧רq)∨pרp∨q∨p1所以，推理正确，即（(p∨q)∧רq)=>p14第三章命题逻辑的推理理论方法3：主析取范式法：((p∨q)∧רq)pר((p∨q)∧רq)∨pר(p∨q)∨q∨p(רp∧רq)∨q∨p(רp∧רq)∨q∧(p∨רp)∨p∧(q∨רq)(רp∧רq)∨(q∧p)∨(q∧רp)∨(p∧q)∨(p∧רq)m0∨m1∨m2∨m3所以，推理正确，即（(p∨q)∧רq)=>p15第三章命题逻辑的

14、推理理论例：判断下列推理是否正确。2、若a能被4整除，则天下雨。现天下雨。所以a能被4整除。设p：a能被4整除。q：天下雨。则，前提：pq,q结论：p推理的形式结构：((pq)∧q)p答案：分析假设中的真值和联结词，当p为假时，结论为假，前提为真。故此推理不正确。16第