离散数学课程教学的理性思考

1、离散数学教学的理性思考离散数学教学的理性思考计算机学院2计算机学院2主要内容主要内容 基本问题基本问题 数理逻辑数理逻辑 数理逻辑是基础数理逻辑是基础 离散数学是基础离散数学是基础计算机学院3计算机学院3基本问题基本问题 离散数学离散数学 数理逻辑数理逻辑 集合论集合论 图论图论 代数系统代数系统 常识常识 问：学习离散数学有什么有？问：学习离散数学有什么有？ 答：离散数学是计算机专业基础答：离散数学是计算机专业基础 基本问题基本问题 “离散数学是计算机专业基础离散数学是计算机专业基础”是什么意思？是什么意思？ “离散数学如何是计算机专业基础离散数学如何是计算机专业基础”是什么意思？是什么意思

2、？计算机学院4计算机学院4离散数学与计算机专业课程关系问题离散数学与计算机专业课程关系问题核心课程核心课程先修课程先修课程计算机导论计算机导论程序设计基础程序设计基础计算机导论计算机导论离散结构离散结构数学分析或高等数学数学分析或高等数学算法与数据结构算法与数据结构高级语言程序设计、离散结构高级语言程序设计、离散结构计算机组成基础计算机组成基础计算机导论、数字逻辑计算机导论、数字逻辑计算机体系结构计算机体系结构计算机组成基础计算机组成基础操作系统操作系统算法与数据结构算法与数据结构数据库系统原理数据库系统原理算法与数据结构、离散数学算法与数据结构、离散数学编译原理编译原理程序设计、离散结构、算

3、法与数据结构程序设计、离散结构、算法与数据结构软件工程软件工程程序设计、算法与数据结构程序设计、算法与数据结构计算机图形学计算机图形学程序设计、离散数学程序设计、离散数学计算机网络计算机网络计算机导论、计算机组成、操作系统、计算机导论、计算机组成、操作系统、算法与数据结构算法与数据结构人工智能人工智能高级语言程序设计、离散结构高级语言程序设计、离散结构数字逻辑数字逻辑计算机导论计算机导论高等学校计算机科学与技术专业发展战略报告暨专业规范高等学校计算机科学与技术专业发展战略报告暨专业规范为什么离散数学的为什么离散数学的前导课程是数学？前导课程是数学？为什么数字逻辑课为什么数字逻辑课程前导课程是计

4、算程前导课程是计算机导论？机导论？如何体现离散数学如何体现离散数学课程的基础性？课程的基础性？计算机学院5计算机学院5计算机专业的基础问题计算机专业的基础问题 逻辑是所有数学推理及其所有自逻辑是所有数学推理及其所有自动推理的基础。动推理的基础。 对于计算机的设计、系统规范说对于计算机的设计、系统规范说明、人工智能、计算机程序设计明、人工智能、计算机程序设计、程序设计语言以及计算机科学、程序设计语言以及计算机科学的其它许多领域，逻辑都有实际的其它许多领域，逻辑都有实际的应用。的应用。 Kenneth H. RosenKenneth H. Rosen计算机学院6计算机学院6ACM Computer

5、 Science Curricula 2013ACM Computer Science Curricula 2013DS.DS.离散结构（离散结构（3737个核心一级学时，个核心一级学时，4 4个核心二级学时）个核心二级学时）核心一级学时核心一级学时核心二级学时核心二级学时比例比例DS/DS/集合、关系与函数集合、关系与函数4 49%9%DS/DS/基础逻辑基础逻辑9 922%22%DS/DS/证明方法证明方法10101 127%27%DS/DS/计数基础计数基础5 512%12%DS/DS/树和图树和图3 31 110%10%DS/DS/离散概率离散概率6 62 220%20%计算机学院7计

6、算机学院7集合、基本逻辑和证明方法的知识点集合、基本逻辑和证明方法的知识点 集合集合 维恩图维恩图 并集、交集、补集并集、交集、补集 笛卡尔积、幂集、笛卡尔积、幂集、有限集合的基数有限集合的基数 关系关系 自反性、对称性、自反性、对称性、传递性传递性 等价关系、偏序关等价关系、偏序关系系 函数函数 满射、单射、双射满射、单射、双射 反函数反函数 函数的复合函数的复合命题逻辑（参考：命题命题逻辑（参考：命题逻辑同时出现在智能系逻辑同时出现在智能系统统/ /知识推理）知识推理）逻辑联结词逻辑联结词真值表真值表范式（合取范式、析取范式（合取范式、析取范式）范式）合式公式的有效性合式公式的有效性命题推

7、理定律（肯定前命题推理定律（肯定前件式和否定后件式的概件式和否定后件式的概念）念）谓词逻辑谓词逻辑全称量词与存在量词全称量词与存在量词命题逻辑和谓词逻辑的命题逻辑和谓词逻辑的局限局限蕴含、等价、逆命题蕴含、等价、逆命题、否命题、逆否命题、否命题、逆否命题、否定和矛盾等概念、否定和矛盾等概念数学证明架构数学证明架构直接证明直接证明反例证伪反例证伪反证法反证法数学归纳法数学归纳法结构归纳法结构归纳法弱归纳法与强归纳法弱归纳法与强归纳法（即，第一类数学归（即，第一类数学归纳法和第二类数学归纳法和第二类数学归纳法）纳法）数学上的递归定义数学上的递归定义计算机学院8计算机学院8主要内容主要内容 基本问题

8、基本问题 数理逻辑数理逻辑 数理逻辑是基础数理逻辑是基础 离散数学是基础离散数学是基础计算机学院9计算机学院9最简单的论域最简单的论域逻辑域逻辑域 逻辑对象：逻辑对象：0,10,1 逻辑运算：逻辑运算： , , , , , , , , , , 逻辑关系：逻辑关系： =, , 真值表真值表 一组逻辑自变量与一个逻辑因变量的对应表一组逻辑自变量与一个逻辑因变量的对应表 真值表定义逻辑运算和关系真值表定义逻辑运算和关系0110pp100110111110111001010000qpqpqpqpqp计算机学院10计算机学院10命题逻辑公式与语言命题逻辑公式与语言 定义：定义： (1).(1).常量常量

9、0 0和和1 1是逻辑公式；是逻辑公式； (2).(2).命题变量是逻辑公式；命题变量是逻辑公式； (3).(3).若若Q,RQ,R是逻辑公式，则是逻辑公式，则( ( Q)Q)、(Q(Q R) R) 、(Q(Q R) R) 、(Q(QR) R) 、(Q(QR) R) 、(Q(Q R)R)是逻辑是逻辑公式；公式； (4).(4).只有有限次应用只有有限次应用(1)(1)(3)(3)构成的公式是逻构成的公式是逻辑公式。辑公式。计算机学院11计算机学院11真值表验证运算性质真值表验证运算性质 结合律结合律 (PQ)R=P(QR)(PQ)R=P(QR) (PQ)R=P(QR)(PQ)R=P(QR) (

10、P(PQ)Q)R=PR=P(Q(QR) R) 分配律分配律 P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) P(QR)=(PQ)(PR)P(QR)=(PQ)(PR) P(QP(QR)=(PQ)R)=(PQ)(PR) (PR) 交换律交换律 QR=RQQR=RQ QR=RQQR=RQ Q QR=RR=RQ Q 德德 摩根律摩根律 (QR)=(QR)= QQ R R (QR)=(QR)= QQ R R 计算机学院12计算机学院12逻辑表达式一般方法逻辑表达式一般方法 若若x xi,j i,j =1=1，则，则x xi,j i,j=x=xk k，若，若x xi,j i,j =0=0，则，

11、则x xi,j i,j= = x xi,j i,j 若若y yk k=1=1，k=0,nk=0,n，则，则y yk k=x=xm-1,km-1,k x x0,k0,k y= yy= y0 0 y yn n 功能可以用真值表表达功能可以用真值表表达 所有逻辑运算都可以所有逻辑运算都可以表达为表达为 , , , , , ,的运算。的运算。x0 xkxm-1y000000k1001012m-11111计算机学院13计算机学院13逻辑哲学逻辑哲学 世界是由事实构成的世界是由事实构成的 逻辑哲学论逻辑哲学论 事实是事物的性质，以及事物之事实是事物的性质，以及事物之间的关系间的关系 我们关于外间世界的知识

12、我们关于外间世界的知识- -哲学哲学上科学方法应用的一个领域上科学方法应用的一个领域维特根斯坦维特根斯坦罗素罗素 根据维特根斯坦和罗素的哲学思想，事实是表达事物的性质根据维特根斯坦和罗素的哲学思想，事实是表达事物的性质或表达一些事物之间的关系。或表达一些事物之间的关系。 世界由事实构成，而命题与事实对应，事实使一个命题为真世界由事实构成，而命题与事实对应，事实使一个命题为真或为假。最简单的事实称为原子事实，与原子事实对应的是或为假。最简单的事实称为原子事实，与原子事实对应的是原子命题。原子命题。 原子命题的真或假取决于它与相应的原子事实是否符合。原子命题的真或假取决于它与相应的原子事实是否符合

13、。计算机学院14计算机学院14谓词谓词 定义：研究对象统称为客体。定义：研究对象统称为客体。 定义：事物的性质词和事物的关系词统称为谓词。定义：事物的性质词和事物的关系词统称为谓词。谓词可以表示为谓词可以表示为Q(xQ(x1 1,.,x,.,xn n) )，其中，其中，Q Q是谓词，是谓词，x x1 1,.,x,.,xn n是客体是客体Q(x)Q(x)是一元谓词，是一元谓词，Q(x,y)Q(x,y)二元谓词，二元谓词，Q(xQ(x1 1,.,x,.,xn n) )是是n n元谓词。元谓词。谓词对于任意客体都有真值。谓词对于任意客体都有真值。 谓词形式谓词形式 如果谓词形式是如果谓词形式是Q(x

14、)Q(x)表示客体表示客体x x有有Q Q性质；性质； 如果谓词形式是如果谓词形式是Q(xQ(x1 1,.,x,.,xn n) )表示客体表示客体x x1 1,.,x,.,xn n之间有之间有Q Q关系。关系。 量词量词 表示所有客体具有某性质或关系的词称为全称量词，记为表示所有客体具有某性质或关系的词称为全称量词，记为 x(Q(x)x(Q(x)R(x)R(x) 表示至少有一个客体具有某性质或关系的词称为存在量词，记表示至少有一个客体具有某性质或关系的词称为存在量词，记为为 x(Q(x)x(Q(x) R(x)R(x)计算机学院15计算机学院15合式公式与一阶谓词语言合式公式与一阶谓词语言 定义

15、：合式公式是按如下规则构成的有穷长符号串。定义：合式公式是按如下规则构成的有穷长符号串。 (1).(1).若是若是x x1 1, ,x ,xn n是变元，是变元，Q Qi in n是是n n元谓词，则元谓词，则Q Qi in n(x (x1 1, ,x ,xn n) )是是合式公式。合式公式。 (2).(2).若若Q Q是合式公式，则是合式公式，则( ( Q)Q)是合式公式；是合式公式； (3).(3).若若Q Q和和R R是合式公式，则是合式公式，则(Q(Q R)R)、(Q(Q R)R)、(Q(QR) R) 、(Q(QR)R)及及(Q(Q R)R)是合式公式；是合式公式； (4).(4).若

16、若Q Q是合式公式，是合式公式，x x是变元，则是变元，则( ( xQ)xQ)及及( ( xQ)xQ)是合式是合式公式。公式。 (5).(5).只有有限次应用只有有限次应用(1)(1)(4)(4)构成的公式是合式公式。构成的公式是合式公式。计算机学院16计算机学院16思想理论与逻辑语言思想理论与逻辑语言 弗雷格思想理论弗雷格思想理论 思想是陈述句的含义思想是陈述句的含义 思想有真假思想有真假 思想有结构思想有结构 思想通过语言来表达和传递思想通过语言来表达和传递 存在判定思想同一性的标准存在判定思想同一性的标准 思想影响人的意志思想影响人的意志 自然语言符合逻辑语言自然语言符合逻辑语言 在保持

17、思想的情况下，自然语言在保持思想的情况下，自然语言变换为逻辑语言变换为逻辑语言Gottlob Frege 1848-1925计算机学院17计算机学院17自然（科学）语言命题符合逻辑语言自然（科学）语言命题符合逻辑语言 定义：具有确定真或假含义的陈述句称为定义：具有确定真或假含义的陈述句称为原子命题原子命题，或，或简单简单命题命题。 在自然语言中，在自然语言中，并且并且、或或、并非并非、如果如果. .，则，则. .。、当且当且仅当仅当等词也称为联接词。等词也称为联接词。 复合语句复合语句是一些陈述句用是一些陈述句用并且并且、或或、并非并非、如果如果. .，则，则. .。、当且仅当当且仅当等联接为

18、一条语句。等联接为一条语句。 量化语句量化语句是用是用所有所有、存在存在等量词约束陈述句或复合语句。等量词约束陈述句或复合语句。 定义：原子命题用定义：原子命题用并且并且、或或、并非并非、如果如果. .，则，则. .。、当当且仅当且仅当等联接词联接的语句称为等联接词联接的语句称为复合命题复合命题。 定义：用定义：用所有所有和和存在存在量词约束的原子命题或复合命题称为量词约束的原子命题或复合命题称为量化命题量化命题。 定义：原子命题、复合命题和量化命题统称为定义：原子命题、复合命题和量化命题统称为命题命题。计算机学院18计算机学院18符号化机械过程符号化机械过程 自然语言的命题符号化方法是机械式

19、过程，无需理解具自然语言的命题符号化方法是机械式过程，无需理解具体概念的含义，仅仅将相同的客体、函数、性质或关系体概念的含义，仅仅将相同的客体、函数、性质或关系分别用相同符号表示。分别用相同符号表示。 复合语句由简单语句、联接词及量词构成。复合语句由简单语句、联接词及量词构成。 首先，识别出简单语句，而后，简单语句符号化。首先，识别出简单语句，而后，简单语句符号化。 复合语句由符号化的简单命题形式和联接词及量词构成。复合语句由符号化的简单命题形式和联接词及量词构成。 复合语句就可以根据联接词及量词的含义，形成符号化的复合语句就可以根据联接词及量词的含义，形成符号化的命题。命题。计算机学院19计

20、算机学院19符号化机械过程（续）符号化机械过程（续） 自然知识可以表示为命题，所有的自然律也可以表达为自然知识可以表示为命题，所有的自然律也可以表达为命题。命题。 自然语言的命题符号化方法：自然语言的命题符号化方法： (1).(1).在复合语句中识别出陈述句，并用下划线标出在复合语句中识别出陈述句，并用下划线标出 (2).(2).陈述语句符号化陈述语句符号化相同相同（不同）（不同）的客体用相同的客体用相同( (不同不同) )符号表示符号表示相同相同（不同）（不同）函数用相同函数用相同（不同）（不同）符号表示符号表示相同相同（不同）（不同）性质或关系用相同性质或关系用相同（不同）（不同）符号表示

21、符号表示 (3).(3).联接词及量词符号化联接词及量词符号化并且并且表示为表示为 ，或或表示为表示为 ，并非并非表示为表示为 ，如果如果. .，则，则. .。表示为表示为，当且仅当当且仅当表示为表示为所有所有表示为表示为 ，存在存在表示为表示为 ，形成符号化的命题。，形成符号化的命题。计算机学院20计算机学院20数学分析概念数学分析概念 在研究过程中，首先用定义的方式给出概念，而后研究在研究过程中，首先用定义的方式给出概念，而后研究概念的性质以及概念之间的关系，形成定理。概念的性质以及概念之间的关系，形成定理。 概念的定义是复合语句，也能够用机械方式符号化。概念的定义是复合语句，也能够用机械

22、方式符号化。 自然语言表达序列极限、函数极限、连续、一致连续、自然语言表达序列极限、函数极限、连续、一致连续、导数等概念，人们可能有二义性理解，即人们对这些概导数等概念，人们可能有二义性理解，即人们对这些概念含义会有不同的理解。念含义会有不同的理解。 如果这些概念符号化，那么，人们对这些概念的理解就如果这些概念符号化，那么，人们对这些概念的理解就会相同。会相同。计算机学院21计算机学院21定义（极限）是命题定义（极限）是命题 定义：设定义：设xxn n 是序列，对于任意是序列，对于任意 00，存在，存在N0N0，对于任，对于任何何n n，当，当nNnN时，都有时，都有|x|xn n-b|-b|

23、00，存在，存在N N，N0N0，对于任何，对于任何n n，当，当nNnN时，都有时，都有|x|xn n-b|-b|00，存在，存在N N，N0N0，对于所有，对于所有n n，当，当nNnN时时，都有，都有|x|xn n-b|-b|00N(N0N(N0n(nNn(nN|x|xn n-b|-b|0(0N N1 1(N(N1 100n(nNn(nN1 1|x|xn n-a|), -a|0(0N N2 2(N(N2 200n(nNn(nN2 2|x|xn n-b|) a=b-b|0(0N(N0N(N0n(nNn(nN|x|xn n-a|) -a|0M(M0n(n0n(n0|x|xn n |M) |M

24、)计算机学院23计算机学院23欧几里德几何学欧几里德几何学 欧几里德欧几里德（325 BC -265 BC ），），古希腊数学家；古希腊数学家； 几何原本几何原本是一个实质公理系统是一个实质公理系统把点、线、面、角等分为原始定义概念（把点、线、面、角等分为原始定义概念（2323）和可定）和可定义概念；义概念；命题分为公理（命题分为公理（5 5）、公设（）、公设（5 5）；）；由公理公设出发加以证明的定理（由公理公设出发加以证明的定理（467467） 从简单到复杂，证明相当严格。从而建立了欧几里从简单到复杂，证明相当严格。从而建立了欧几里得几何学的第一个公理化数学体系。得几何学的第一个公理化数学

25、体系。 公设公设1. 1.由任意一点到另外任意一点可以画直线。由任意一点到另外任意一点可以画直线。2. 2.一条有限直线可以继续延长。一条有限直线可以继续延长。3. 3.以任意点为心及任意的距离可以画圆。以任意点为心及任意的距离可以画圆。4. 4.凡直角都彼此相等。凡直角都彼此相等。5 5( (平行公设平行公设) )若一直线与两直线相交，且若若一直线与两直线相交，且若同侧所交两内角之和小于两直角，则两直线同侧所交两内角之和小于两直角，则两直线无限延长后必相交于该侧的一点。无限延长后必相交于该侧的一点。 公理公理1 1等于同量的量彼此相等。等于同量的量彼此相等。2 2等最加等量，其和仍相等。等最

26、加等量，其和仍相等。3 3，等量减等量，其差仍相等。，等量减等量，其差仍相等。4 4彼此能重合的物体是全等的。彼此能重合的物体是全等的。5 5整体大于部分。整体大于部分。计算机学院24计算机学院24希尔伯特证明论希尔伯特证明论 通过形式化第一次使证明本身成为通过形式化第一次使证明本身成为数学研究对象。数学研究对象。 给出初始符号集合给出初始符号集合 构造合式公式规则构造合式公式规则 Q Q的证明，的证明，构造出构造出1m1m个合式个合式公式序列，其中，第公式序列，其中，第m m个合式公式个合式公式是是Q Q，并且，并且1m1m合式公式合式公式 或者是前提或者是前提 或者是公理或者是公理 或者是

27、推导规则或者是推导规则 形式证明正确性的验证。形式证明正确性的验证。David Hilbert 1826-1943计算机学院25计算机学院25逻辑证明有何不同？逻辑证明有何不同？ 领域知识是提出概念，形成定理，对定理进行证明。领域知识是提出概念，形成定理，对定理进行证明。 通过思想概念的涵义以及关系，形成一个个推理步骤，最通过思想概念的涵义以及关系，形成一个个推理步骤，最后完成证明。领域知识不同，证明方法也不同。后完成证明。领域知识不同，证明方法也不同。 在逻辑公理系统中，已知语言、公理、在逻辑公理系统中，已知语言、公理、推理规则推理规则 是前提集是前提集, Q, Q是结论是结论 是是语句集合

28、，语句集合，Q Q是语句是语句 在逻辑公理系统中，各个领域知识都抽象为形式语言。在逻辑公理系统中，各个领域知识都抽象为形式语言。从形式语言表示的公理和前提集开始，一步步推理到结从形式语言表示的公理和前提集开始，一步步推理到结论。论。 因为推理过程没有领域概念及其涵义，仅有抽象的符号，因为推理过程没有领域概念及其涵义，仅有抽象的符号，按照推理规则一步一步进行推理，所以，推理具有统一方按照推理规则一步一步进行推理，所以，推理具有统一方法。法。计算机学院26计算机学院26逻辑公理系统逻辑公理系统 公理系统公理系统 从一些从一些公理公理出发，根据出发，根据演绎法演绎法，推导出一系列，推导出一系列定理定

29、理，形成的演绎体系叫作，形成的演绎体系叫作公理系统公理系统。 公理系统的组成：公理系统的组成： 语言集语言集 公理集公理集公理是用于表达推理由之出发的初始肯定命题；公理是用于表达推理由之出发的初始肯定命题； 推理规则集推理规则集推理规则是由公理及已证定理得出新定理的规则；推理规则是由公理及已证定理得出新定理的规则； 定理集定理集表达了肯定的所有命题。表达了肯定的所有命题。计算机学院27计算机学院27谓词逻辑公理系统谓词逻辑公理系统 (1)(1)谓词逻辑语言：谓词逻辑语言：L=L=,P,F,C ( (2 2). ).公理集合：公理集合： 1).1).公理模式公理模式A A 1 1：Q Q (R

30、(RQ)Q) 2).2).公理模式公理模式A A 2 2：(P(P (Q (QR) R) (P (PQ) Q) (P (PR)R) 3).3).公理模式公理模式A A 3 3：( ( Q QR) R) (R (RQ) Q) 4).4).公理模式公理模式A A 4 4： xQ(x)xQ(x)Q(x)Q(x)x/t x/t 其中，项其中，项t t对于对于Q Q中的中的x x是可代入的。是可代入的。 5).5).公理模式公理模式A A 5 5： x x( (Q QR(x)R(x) ) ( (Q QxR(x)xR(x) ) 其中其中x x不是不是Q Q中自由变元中自由变元。 ( (3 3). ).推理

31、规则推理规则 1).1).分离规则（简称分离规则（简称MPMP规则）：从规则）：从Q Q和和Q QR R推出推出R R。 2).2).全称全称概括（简称概括（简称UGUG规则）：从规则）：从Q(x)Q(x)推出推出( ( xQ)xQ)。计算机学院28计算机学院28演绎与证明演绎与证明 Q Q的的证明，就是要构造一个合式公式的变换序列，其证明，就是要构造一个合式公式的变换序列，其中每一步产生的合式公式中每一步产生的合式公式，并且，并且 或者是公理模式或者是公理模式 或者是前提模式或者是前提模式 或者是由分离规或者是由分离规 或者是或者是全称全称概括概括（谓词逻辑）（谓词逻辑）计算机学院29计算机

32、学院29 xQ(x)yQ(y) (y不在不在Q中出现中出现) 证明：证明： 证据：证据： A A1 1= = xQ(x) xQ(x) Q(y) Q(y) A4 4 A A2 2= = y y( ( xQ(x) xQ(x) Q(y) UG Q(y) UG A A3 3= = y y( ( xQ(x) xQ(x) Q(y)Q(y)( ( xQ(x) xQ(x) y Q(y) y Q(y) A5 5 A A4 4= = xQ(x) xQ(x) y Q(y) Ay Q(y) A3 3=A=A2 2 A A4 4 证毕证毕计算机学院30计算机学院30定理定理( (传递律传递律) )：P PQ,QQ,QR

33、PRPR R 证明：证明： 证据：证据：A A1 1=(Q=(QR) R) (P(P (Q (QR) R) A1 1A A2 2=Q=QR R A A2 2 A A3 3=P=P (Q (QR) R) A A1 1= =A A2 2 A A3 3 A A4 4=(P=(P (Q (QR) R) (P(PQ) Q) (P(PR) R) A2 2A A5 5=(P=(PQ) Q) (P(PR) R) A A4 4= =A A3 3 A A5 5 A A6 6=(P=(PQ) Q) A A6 6 A A7 7=(P=(PR) R) A A5 5= =A A6 6A A7 7 证毕证毕计算机学院31计

34、算机学院31定律与规则定律与规则 思维直觉思维直觉、思维定律与定理。思维定律与定理。 充分理由律（三段论）：充分理由律（三段论）：Q, QQ, QR RR R 传递律：传递律：P PQ,QQ,QRPRPR R 反证律：如果反证律：如果 , , Q R, Q R, , , QQ R,R,则则 Q Q 归谬律：如果归谬律：如果 , Q R, , Q R, , Q , Q R R，则，则 Q Q 排中律：排中律：(Q(QQ Q) ) 矛盾律：矛盾律： (Q(QQ)Q) 引入规则：引入规则： P(c) P(c) xP(x) xP(x) 选择规则：选择规则： xP(x)xP(x)P(c) P(c) 计算

35、机学院32计算机学院32命题逻辑定理命题逻辑定理 (P (P(Q(QR) R) (Q(Q(P(PR)R)(Q(QR)R)(P(PQ)Q)(P(PR)R)(P(P Q) Q)(Q(QR)R)(P(PR)R)(P(P Q) Q)(P(PR)R)(P(P(Q (Q R)R)QQQ QQ QQ Q Q QQ QQ Q(Q(QR)R) R)R) Q Q (Q(QR)R)R R Q Q Q Q Q Q Q Q Q Q Q Q(Q(QR) R) (R (RQ)Q)(Q(Q R) R) (Q (Q R) R) ( (Q QR)R)(Q(QR)R) (Q(QR)R)( (Q QR)R)(Q(QR)R)( ( R

36、 RQ)Q)( Q QR)R)( ( R RQ)Q)(Q(QR )R )(R(RQ)Q) Q Q(Q(Q R) R)( ( Q QQ)Q)(R(RQ)Q)( ( Q QQ)Q)Q Q ( Q QR RR)R)Q Q( ( Q QR) R) ( ( Q QR) R) Q)Q)(Q(QR) R) (Q(QR)R)Q)Q) 计算机学院33计算机学院33一阶谓词逻辑定理一阶谓词逻辑定理 xR(x) xR(x) y R(y)y R(y) xR(x) xR(x) y R(y)y R(y) Q(c) Q(c) xQ(x)xQ(x) Q(c) Q(c) xQ(x)xQ(x) xR(x) xR(x) xR(x)

37、 xR(x) x x y R(x,y) y R(x,y) y y xR(x,y) xR(x,y) x x y R(x,y) y R(x,y) y y xR(x,y) xR(x,y) x x yR(x,y) yR(x,y) y y x R(x,y)x R(x,y) x x yR(x,y) yR(x,y) xR(x,x)xR(x,x) xR(x,x) xR(x,x) x x yR(x,y) yR(x,y) x(P(x)x(P(x)Q(x) Q(x) ( ( xP(x) xP(x) x Q(x)x Q(x) x(P(x) x(P(x) Q(x) Q(x) ( ( xP(x) xP(x) x Q(x)

38、x Q(x) x(P(x)x(P(x) Q(x)Q(x)( ( xP(x)xP(x)xQ(x) xQ(x) xP(x) xP(x) xQ(x)xQ(x)x(P(x) x(P(x) Q(x) Q(x) x(P(x)x(P(x) Q(x) Q(x) ( ( xP(x) xP(x) xQ(x)xQ(x) x(P(x)x(P(x) Q(x) Q(x) ( ( xP(x) xP(x) xQ(x) xQ(x) xP(x) xP(x) x x P(x) P(x) xP(x) xP(x) x x P(x) P(x) x x P(x) P(x) xP(x) xP(x) x x P(x) P(x) xP(x)xP

39、(x)计算机学院34计算机学院34论域、解释、赋值与模型论域、解释、赋值与模型 在指定论域上，对于一阶逻辑语言在指定论域上，对于一阶逻辑语言L L 解释解释将常元指称为论域中某客体；将常元指称为论域中某客体；将谓词指称为论域上的关系；将谓词指称为论域上的关系；将函词指称为论域上的函数。将函词指称为论域上的函数。 赋值赋值将客体变元指称为论域中的客体。将客体变元指称为论域中的客体。 一阶逻辑语言的解释，是确定该种语言里的符号表达式同某一阶逻辑语言的解释，是确定该种语言里的符号表达式同某个论域之间的联系。个论域之间的联系。 论域和解释构成了结构。论域和解释构成了结构。 结构和赋值构成了模型。结构和

40、赋值构成了模型。 一阶逻辑语言的语义就是在模型上的逻辑真值。一阶逻辑语言的语义就是在模型上的逻辑真值。计算机学院35计算机学院35合式公式、合式公式集合与模型合式公式、合式公式集合与模型 研究合式公式或合式公式集合研究合式公式或合式公式集合 Q Q = Q= Q1 1,.,Q,.,Qn n 在一个模型上具有的性质；在一个模型上具有的性质； 在所有模型上具有的性质在所有模型上具有的性质真值性真值性永真性永真性相等性相等性推论性推论性存在模型存在模型可满足性可满足性模型模型永真永真模型等值模型等值模型推论模型推论所有模型所有模型有效性有效性逻辑逻辑永真永真逻辑等逻辑等值值逻辑推论逻辑推论计算机学院

41、36计算机学院36等式关系和推论关系等式关系和推论关系 定义：给定一阶语言定义：给定一阶语言L L及它的两个公式及它的两个公式Q,RQ,R，如果存在模型，如果存在模型M=D, M=，使得，使得(Q) = (R), (Q) = (R), 则称则称Q Q与与R R是在是在模型模型MM等值等值，记，记为为Q QMMR R。 定义：给定一个语言定义：给定一个语言L , L , 是一个公式集合是一个公式集合, Q , Q 是一个公式。是一个公式。 若存在模型若存在模型M=M=，使得当，使得当( ( )=1)=1时时，有有(Q)=1(Q)=1，则称，则称Q Q 是是 关于模型逻辑推论关于模型逻辑推论，记为

42、，记为 MMQ Q。 定义：如果对于定义：如果对于任意模型任意模型M=D, M=，都有，都有 (Q) = (Q) = (R), (R), 则称则称Q Q与与R R是是逻辑等价逻辑等价，记为，记为Q QR R。 定义：给定一个语言定义：给定一个语言L , L , 是一个公式集合是一个公式集合, Q , Q 是一个公式。是一个公式。 若对于若对于任意模型任意模型M=M=，使得当，使得当( ( )=1)=1时有时有(Q)=1(Q)=1，则称，则称Q Q 是是 逻辑推论逻辑推论，或称，或称 语义推出语义推出Q Q，记为，记为 QQ。计算机学院37计算机学院37前束范式前束范式 定义：设定义：设 k k

43、为为 , , 量词，量词，x x1 1xxn n为不同变元，为不同变元，Q Q为开公式为开公式，形式为，形式为 1 1x x1 1n n x xn nQ Q的公式称为前束范式，的公式称为前束范式， 称称 1 1x x1 1n n x xn n为前束词，称为前束词，称Q Q为母式。为母式。 定理：设定理：设 k k为为 , , 量词，量词，x x1 1xxn n为不同变元，对于任意合为不同变元，对于任意合式公式式公式Q Q，存在前束范式，存在前束范式 1 1x x1 1n n x xn nR R， 使得使得Q Q 1 1x x1 1n n x xn nR R。 定义：若定义：若 1 1x x1

44、1n n x xn nQ Q的是前束范式，并且的是前束范式，并且Q Q是合取范式是合取范式，则称，则称 1 1x x1 1n n x xn nQ Q是前束合取范式。是前束合取范式。计算机学院38计算机学院38前束范式步骤前束范式步骤(1).(1).依次用等值公式依次用等值公式Q Q R R (Q (QR)R)Q QR R (Q (QR)R) (R(RQ)Q)Q QR R Q Q R R进行等值变换，产生的公式仅有联结词进行等值变换，产生的公式仅有联结词 、 、 以及量词以及量词 、 。(2). (2). 用等值公式用等值公式Q QQ Q进行变换化简公式。进行变换化简公式。(3).(3).根据以

45、上等值公式，以及如下量词变换等值公式根据以上等值公式，以及如下量词变换等值公式Q(x) Q(x) x x Q(x)Q(x)Q(x) Q(x) x x Q(x)Q(x)(4).(4).用德用德 摩根律摩根律 (Q(Q R) R) Q QR R， (Q(Q R) R) Q QR R进行化简。进行化简。重复应用重复应用(2)(2)、(3)(3)、(4)(4)步骤，逐次将所有联结词步骤，逐次将所有联结词 置于原子谓词。置于原子谓词。计算机学院39计算机学院39前束范式步骤（续）前束范式步骤（续）(5).(5).用换名等值公式用换名等值公式 xQ(x)xQ(x)yQ(y)yQ(y)和和 xQ(x)xQ(

46、x)yQ(y)yQ(y)将所有不同量词辖将所有不同量词辖域的变元换名为互不同的变元。域的变元换名为互不同的变元。(6). (6). 若若x x不在不在Q Q中出现，则中出现，则Q QxR(x) xR(x) x(Qx(Q R(x)R(x)Q QxR(x) xR(x) x(Qx(Q R(x)R(x)Q QxR(x) xR(x) x(Qx(Q R(x)R(x)Q QxR(x) xR(x) x(Qx(Q R(x)R(x) 1 1x x1 1Q(xQ(x1 1) ) 2 2 R(x R(x2 2) ) 1 1x x1 1 2 2 x x2 2(Q(x(Q(x1 1) ) R(xR(x2 2) ) 1 1

47、x x1 1Q(xQ(x1 1) ) 2 2 R(x R(x2 2) ) 1 1x x1 1 2 2 x x2 2(Q(x(Q(x1 1) ) R(xR(x2 2) )重复应用重复应用(6)(6)步骤，逐次将量词前置，使得公式变换为前束范式。步骤，逐次将量词前置，使得公式变换为前束范式。(7).(7).用等值变换交换量词次序用等值变换交换量词次序 x x y Q(x,y) y Q(x,y) y y xQ(x,y)xQ(x,y) x x y Q(x,y) y Q(x,y) y y xQ(x,y)xQ(x,y)计算机学院40计算机学院40等式演算一般方法等式演算一般方法 命题公式命题公式:Q:Q的

48、范式是的范式是Q Q ，R R的范式是的范式是R R ， 因为因为 Q QQ Q ， Q Q R R ，R R R R 。 所以所以Q QR R 谓词公式谓词公式:Q:Q的前束合取范式是的前束合取范式是Q Q ，R R的前束合取范式是的前束合取范式是R R ， 因为因为 Q QQ Q ， Q Q R R ，R R R R 。 所以所以Q QR R计算机学院41计算机学院41主要内容主要内容 基本问题基本问题 数理逻辑数理逻辑 数理逻辑是基础数理逻辑是基础 离散数学是基础离散数学是基础计算机学院42计算机学院42结构主义结构主义 在在结构主义结构主义中，皮亚杰给出中，皮亚杰给出结构特征结构特征

49、结构由对象集合结构由对象集合S S以及关系集合以及关系集合R R、运算集合、运算集合F F和常元集合和常元集合C C组成，组成， 整体性、转换、自身调整性整体性、转换、自身调整性 结构主义是知识表征的重要方法结构主义是知识表征的重要方法计算机学院43计算机学院43从结构主义观点看从结构主义观点看 集合论集合论 性质定义概念性质定义概念 外延与内涵外延与内涵 图论图论 结构集合定义概念结构集合定义概念 代数系统代数系统 操作定义概念操作定义概念 定义运算定义运算 保持封闭性保持封闭性 定义关系定义关系 洞察性质，形成定理洞察性质，形成定理 逻辑表达概念、运算和关系逻辑表达概念、运算和关系 一般方

50、法证明等式一般方法证明等式 演绎形式证明演绎形式证明计算机学院44计算机学院44命题的逻辑构造命题的逻辑构造 基本概念与导出概念基本概念与导出概念 命题：命题： 概念定义是命题。概念定义是命题。 运算定义是命题。运算定义是命题。 关系定义是命题。关系定义是命题。 定理是命题。定理是命题。 逻辑命题能由自然语言描述机械式的变换为逻辑描述。逻辑命题能由自然语言描述机械式的变换为逻辑描述。 联接词联接词 , , , , , , , 量词量词 , , 谓词、函词和常元谓词、函词和常元 逻辑命题是形式的。逻辑命题是形式的。计算机学院45计算机学院45集合基本概念、概括性公理集合基本概念、概括性公理 集合

51、是一些能够明确区分的对象构成的整体。集合是一些能够明确区分的对象构成的整体。 集合一般用大写英文字母表示，构成集合的对象称为元素集合一般用大写英文字母表示，构成集合的对象称为元素，一般用小写英文字母表示。，一般用小写英文字母表示。 元素与集合有元素与集合有“属于属于”基本关系基本关系， 关系关系 如果对象如果对象 a a 在集合在集合 A A 中，则称中，则称 a a 是是A A 的元素，或者的元素，或者a a 属于属于A A，记为，记为 a a A A，否则记为，否则记为a a A A。 概括性公理概括性公理 谓词谓词(x)是给定的一个性质，则是给定的一个性质，则(x)确定唯一一个集合。确定

52、唯一一个集合。 设设A = x |(x)，满足性质，满足性质(x)的对象都在的对象都在A A中，不满足中，不满足该性质的对象都不在该性质的对象都不在A A中。即中。即 x (x) x A) 计算机学院46计算机学院46关系关系 定义定义 设设X X，Y Y是集合，若是集合，若R R X X Y Y ，则称，则称 R R 为从为从X X到到Y Y的关系，简称为关系的关系，简称为关系R R。R= |xR= |x X X y y Y Y 若若R R 是从是从X X到到Y Y的关系，就是集合的关系，就是集合X X中元素与集合中元素与集合Y Y中元中元素之间的对应素之间的对应。计算机学院47计算机学院4

53、7函数函数 定义：设定义：设 f f 是从集合是从集合 X X 到到 Y Y 的关系的关系 若对每个若对每个 x x X X 存在唯一存在唯一 y y Y Y 使得使得 f f，则称，则称 f f 为从为从 X X 到到 Y Y 的函数的函数( (映射映射) )，记为，记为 f : X f : X Y Y。 从从 X X 到到 Y Y 的函数指的是的函数指的是单值全函数单值全函数，满足，满足f f X X Y Y dom( f ) = Xdom( f ) = X ran( f ) ran( f ) Y Y f f f fy = zy = z计算机学院48计算机学院48满射、单射和双射满射、单射

54、和双射 定义：设函数定义：设函数f : X f : X Y Y， (1).(1).若对于每个若对于每个 y y Y Y ，都存在，都存在 x x X X使得使得 f (x) = yf (x) = y，则称，则称 f f 为满射，即为满射，即 y (yy (y Y Y x (xx (x X X f (x) = y) f (x) = y) (2).(2).若对于任意若对于任意 x x X, yX, y Y Y，只要，只要 f (x) = f (y)f (x) = f (y)，就有，就有 x = y x = y ，或只要，或只要 x x y y，就有，就有 f (x) f (x) f (y) f (

55、y) ，则称，则称 f f 为单射，即为单射，即 x x y(xy(x X X y y X X f (x) = f (y) f (x) = f (y) x = y) x = y) (3).(3).若函数若函数f f既是单射又是满射，则称既是单射又是满射，则称 f f为双射，也称为一为双射，也称为一一对应。一对应。计算机学院49计算机学院49单调性函数单调性函数 定义：设定义：设X X，Y Y为集合，为集合，是全序关系，是全序关系，f: f: X XY Y， (1).(1).如果对于任意如果对于任意x x1 1 x x2 2，则，则f(xf(x1 1) ) f(xf(x2 2) )，则称，则称f

56、 f是单调递增的是单调递增的 x x1 1 x x2 2(x (x1 1 x x2 2 f(x f(x1 1) ) f(xf(x2 2) ) (2).(2).如果对于任意如果对于任意x x1 1 x x2 2，则，则f(xf(x1 1) ) f(xf(x2 2) )，则称，则称f f是严格单调递增是严格单调递增的的 x x1 1 x x2 2(x (x1 1 x x2 2 f(x f(x1 1) ) f(xf(x2 2) ) (3).(3).如果对于任意如果对于任意x x1 1 x x2 2，则，则f(xf(x1 1) ) f(xf(x2 2) )，则称，则称f f是单调递减的是单调递减的 x

57、 x1 1 x x2 2(x (x1 1 x x2 2 f(x f(x1 1) ) f(xf(x2 2) ) (4).(4).如果对于任意如果对于任意x x1 1 x f(xf(x2 2) )，则称，则称f f是严格单调递减是严格单调递减的的 x x1 1 x x2 2(x (x1 1 x f(xf(x2 2) )计算机学院50计算机学院50集合运算集合运算 定义：设定义：设A,BA,B为二集合，称由为二集合，称由A A和和B B的所有元素组成的集合为的所有元素组成的集合为A A与与B B的并集，记作的并集，记作A A B B，称，称 为并运算符。为并运算符。A A B = x | x B =

58、 x | x A A x x BB A A B = x | xB = x | x A A x x B B 交运算交运算 A-B = x | xA-B = x | x A A x x B B 差运算差运算 A+B = x | xA+B = x | x A A x x B B 对称差运算对称差运算 A = x | xA = x | x A A 补运算补运算 集合运算也是由集合及集合运算也是由集合及“ ”这两个基本概念的导出概念。这两个基本概念的导出概念。计算机学院51计算机学院51关系运算关系运算 定义：设关系定义：设关系R R和和S S是从是从X X到到Y Y的两个关系，则的两个关系，则R R

59、S, R S, R S, R S, R S, R + S, S, R + S, R R为为 R R S=| S=| R R S S R R S=| S=| R R S S R R S=| S=| R R S S R + S=|R + S=| R R S S R=| R=| RR 复合运算、指数运算及逆运算复合运算、指数运算及逆运算 R R S = | S = | y(y( R R SS R Rn+1 n+1 = R= Rn n R R（ R R0 0 = I= IX X ） R R 1 1 = | = | RR计算机学院52计算机学院52集合相等关系集合相等关系 定义定义( (外延性公理）：外

60、延性公理）： 如果集合如果集合A A 和和B B 含有相同的元素，含有相同的元素，则称则称A A 和和B B相等，记为相等，记为A = BA = B。 A = B A = B x (xx (x A A x x B)B)x (xx (x A A x x B)B)x (xx (x B B x x A)A) 其中其中表示当且仅当关系。在数理逻辑证明中，用表示当且仅当关系。在数理逻辑证明中，用“符符号号”代替集合符号代替集合符号“”。 集合的集合的“= =”是集合之间的一种关系，即相等关系；是集合之间的一种关系，即相等关系； 这个等关系也可以是表示相等谓词。这个等关系也可以是表示相等谓词。 谓词谓词“