离散数学－逻辑和证明ppt课件

1、离散数学逻辑离散数学逻辑黄晓宇黄晓宇HuangSirchinaHuangSirchina能力要求n三大能力三大能力n逻辑推理能力逻辑推理能力n算法分析与设计能力算法分析与设计能力n表达与编程能力表达与编程能力内容要求n逻辑与证明逻辑与证明n算法算法n计数方法计数方法n递归递归n树树n网络模型网络模型本讲内容n命题命题n命题逻辑命题逻辑n逻辑联接词逻辑联接词n真值表真值表命题逻辑电路化简rqp命题逻辑电路化简二）XYZ000010100111与电路与电路或电路或电路XYZXYZXYZ000011101111命题逻辑电路化简三）rqprqpPQRO0000001001000110100010111

2、1011111命题逻辑推理知：（知：（1 1如果今天是星期一，则要进行英语或离散数学考如果今天是星期一，则要进行英语或离散数学考试；（试；（2 2如果英语老师有会，则不考英语；（如果英语老师有会，则不考英语；（3 3今天是今天是星期一，英语老师有会。星期一，英语老师有会。（1 1）考英语或离散数学考英语或离散数学今天是星期一今天是星期一英语老师有会英语老师有会（2 2）不考英语不考英语考离散数学考离散数学小结n使用自然语言表述的存在问题使用自然语言表述的存在问题n能否有一种语言，具有：能否有一种语言，具有：n高度的抽象性高度的抽象性n强大的表达能力强大的表达能力n完善的公理集合完善的公理集合命

3、题逻辑n命题逻辑也称命题演算或语句演算，命题逻辑也称命题演算或语句演算，它研究由命题为基本单位构成的前它研究由命题为基本单位构成的前提和结论之间的可推导关系提和结论之间的可推导关系n组成：命题组成：命题n研究对象：推导关系研究对象：推导关系命题n命题命题(Proposition)(Proposition)，是指具有真假意义的，是指具有真假意义的单句或复句，命题通常都是陈述句单句或复句，命题通常都是陈述句n命题是能够确定或能够分辨其真假的陈命题是能够确定或能够分辨其真假的陈述句，且真或假二者必居其一，也只居述句，且真或假二者必居其一，也只居其一。简言之，命题非真必假。其一。简言之，命题非真必假。

4、n例例1 1：P1 (a)P1 (a)(e)(e)n例例2 2：在引例：在引例2 2中，有哪些命题？中，有哪些命题？命题二）n一个命题的真或假称为命题的真值，一个命题的真或假称为命题的真值，简称值，真用简称值，真用T(True)T(True)或或1 1表示；假用表示；假用F(False)F(False)或或0 0表示表示n由于命题只有真、假二个真值，所以由于命题只有真、假二个真值，所以命题逻辑也称二值逻辑命题逻辑也称二值逻辑命题三）n应该注意，一个陈述句能否分辨真假，应该注意，一个陈述句能否分辨真假，与是否知道它的真假，是两件事与是否知道它的真假，是两件事: :n大学城共有大学城共有30013

5、30013人人n我所说的是假的我所说的是假的n在数理逻辑中，不能去纠缠各种具体命在数理逻辑中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句。念，把命题定义成非真必假的陈述句。命题的表示n一个原子命题，一般用大写字母或带下一个原子命题，一般用大写字母或带下标的大写字母，如标的大写字母，如P, Q, R,P, Q, R,或或Pi, Qi, Pi, Qi, Ri ,Ri ,等表示，把表示原子命题的符号，等表示，把表示原子命题的符号，称为命题标识符，简称命题符

6、称为命题标识符，简称命题符nP:P:今天是星期一今天是星期一nQ:Q:英语老师有会英语老师有会n逻辑联接词n逻辑联结词或命题联结词的简称，它逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象是自然语言中连词的逻辑抽象. . 有了联有了联结词，便可以用它和原子命题构成复结词，便可以用它和原子命题构成复合命题合命题n逻辑联接词种类：否认、合取、析取、逻辑联接词种类：否认、合取、析取、条件、等价条件、等价否认(Negation)， PPTFFT合取(Conjunction)，PQP QT T TTFFFTFFFF析取(Disjunction)，PQP QT T TTFTFTTFFF判断真假P

7、Q命题真假命题真假今天是星期一今天是星期一考英语考英语今天是星期一今天是星期一不考试不考试今天星期二今天星期二考离散数学考离散数学今天星期二今天星期二学生放假学生放假如果今天是星期一，则要进行英语或离散数学考试如果今天是星期一，则要进行英语或离散数学考试P：今天是星期一：今天是星期一Q：今天考了英语或离散数学：今天考了英语或离散数学TTTF判断真假二）n句型解读：如果P则QPQ）n若P成立，则仅当Q成立时为Tn若P不成立，则为T缘由？）逻辑蕴含(Implication)，命题PQ,读作“P条件Q或“如果P,则Q”。PQP QT T TTFFFTTFFTPQ P Q逻辑等价(logically

8、equivalent)，PQ命题真假命题真假今天是星期五今天是星期五今天离数提问今天离数提问今天是星期五今天是星期五今天没离数今天没离数今天星期二今天星期二今天离数提问今天离数提问今天星期二今天星期二今天没离数今天没离数每星期只在周五上离散数学，每次离散数学都提问。每星期只在周五上离散数学，每次离散数学都提问。P：今天是星期五：今天是星期五Q：今天离散数学提了问题：今天离散数学提了问题TFTF逻辑等价二）n定义：定义：P12 P12 定义定义.10nDe MorganDe Morgan逻辑定律逻辑定律n (P1 P2 Pn) (P1 P2 Pn) P1 P2 P1 P2 Pn

9、 Pnn (P1 P2 Pn) (P1 P2 Pn) P1 P2 P1 P2 Pn Pnn例例1 1：今天没有人逃课。：今天没有人逃课。n例例2 2：今天有人逃课。：今天有人逃课。逻辑等价三）PQP QT T TTFFFTFFFT逻辑等价四）P Q？(PQ) (Q P) (PQ) (Q P) (P Q) ( Q P) 真值表n对于命题公式对于命题公式 A A中每个命题变元，任给一中每个命题变元，任给一个指派个指派S(P)S(P)得到一种真值的组合得到一种真值的组合S(P1)S(P1)，S(P2)S(P2)，S(Pn)S(Pn)，称为，称为A A的一个真值指派，的一个真值指派，记为记为S(A)S(A)。若。若S(A)S(A)为为T T，称，称S(A)S(A)为为A A的真指派。的真指派。n设设A A为一命题公式，对其中出现