北大离散数学ppt课件

1、第二章 一阶逻辑,第一节 一阶逻辑基本概念,内容,个体词，谓词，量词，命题符号化,重点,1、掌握个体词，谓词，量词的有关概念,2、掌握在一阶逻辑中的命题符号化,一、一阶逻辑(谓词逻辑)研究的内容,例如：判断以下推理是否正确,凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的,二、个体词，谓词，量词,1、个体词，谓词,例如：李华是大学生,是无理数,小王比小明高,个体域(或称论域)个体变项取值的范围,小王,小明,小王比小明高,一元谓词,个体常项,个体常项,李华,小明,分别表示李华，小明是大学生,它们是0元谓词,2、量词表示数量的词,使用量词时，应注意以下6点,2、量词表示数量的词,使用量词时，应注

2、意以下6点,全称量词,2、量词表示数量的词,全称量词,使用量词时，应注意以下6点,2、量词表示数量的词,全称量词,使用量词时，应注意以下6点,三、命题符号化,例1、在一阶逻辑中将下面命题符号化,1) 所有的有理数均可表成分数,解,因无指定个体域，则以全总个体域为个体域,三、命题符号化,例1、在一阶逻辑中将下面命题符号化,2) 有的有理数是整数,解,例2、在一阶逻辑中将下列命题符号化,1) 凡偶数均能被2整除,2) 存在着偶素数,例2、在一阶逻辑中将下列命题符号化,3) 没有不犯错误的人,原命题即：“每个人都犯错误,又可符号化为,例2、在一阶逻辑中将下列命题符号化,4) 在北京工作的人未必是北京

3、人,5) 尽管有些人聪明，但未必一切人都聪明,例2、在一阶逻辑中将下列命题符号化,第一句为,或,例2、在一阶逻辑中将下列命题符号化,第二句为,或,第二节 一阶逻辑合式公式及解释,内容,重点,1) 掌握合式公式的概念,一般,1) 换名规则，代替规则,2) 解释的概念,3) 代换实例,了解,1) 闭式的概念,2) 判断合式公式的类型,一、一阶逻辑中的合式公式,1、字母表,1) 个体常项,2) 个体变项,3) 函数符号,4) 谓词符号,一、一阶逻辑中的合式公式,1、字母表,5) 量词符号,6) 联结词符,7) 括号和逗号：( ，)， ，,2、项的递归定义,1) 个体常项和变项是项,3) 只有有限次地

4、使用(1)、(2)生成的符号串才是项,例如,等都是项,3、原子公式,4、合式公式的递归定义,1) 原子公式是合式公式,3、原子公式,4、合式公式的递归定义,5、约束出现，自由出现,约束出现，自由出现,1,2,3,换名规则指导变项，约束变项换名,例如,换成,代替规则自由变项代替,例如,换成,二、合式公式的解释,二、合式公式的解释,1) 个体域为自然数集合,1,真值为0,真值为1,2,1) 个体域为自然数集合,真值为1,3,1) 个体域为自然数集合,真值为0,4,真值为不确定(不是命题,5,有一些公式，可以利用命题公式的结论,例如,1,由以上，原公式是逻辑有效的,2,所以原公式是逻辑有效的,所以原

5、公式是逻辑有效的,3,4,所以原公式是矛盾式,第三节 一阶逻辑等值式,内容,一阶逻辑等值式，前束范式,重点,一般,使用基本等值式进行等值演算,了解,前束范式的定义和求法,一、一阶逻辑等值式,1、量词否定等值式,1,2,2、量词辖域收缩与扩张等值式,1,2,4,3,1、量词否定等值式,1,2,2、量词辖域收缩与扩张等值式,5,6,8,7,3、量词分配等值式,1,2,例1,3、量词分配等值式,1,2,例1,注意,4、多个量词间的次序排列等值式,1,2,二、前束范式,前束范式：形式,例如,4、多个量词间的次序排列等值式,1,2,二、前束范式,前束范式：形式,例如,例2、求下列公式的前束范式,1,解,

6、量词否定等值式,例2、求下列公式的前束范式,2,解,量词否定等值式,换名规则,量词辖域的扩张,第四节 一阶逻辑推理理论,一、一阶逻辑推理的概念,1、概念,2、量词分配定律,1,2,3,4,二、推理规则,1、全称量词消去规则,二、推理规则,2、全称量词引入规则,二、推理规则,3、存在量词引入规则,二、推理规则,4、存在量词消去规则,苏格拉底,例1、证明：苏格拉底三段论,前提,结论,证明,前提引入,前提引入,假言推理,例2、构造下面定理的证明,前提,结论,证明,前提引入,置换,置换,例2、构造下面定理的证明,前提,结论,证明,前提引入,假言三段论,第二章 小结与例题,一、一阶逻辑的基本概念,1、基本概念,2、应用,在一阶逻辑中将命题符号化,二、一阶逻辑合式公式及解释,1、基本概念,2、应用,1) 求某些公式在给定解释下的真值,2) 判断某些简单公式的类型,三、一阶逻辑等值式,基本概念,等值式，常用等值式；前束范式,四、一阶逻辑推理理论,三、一阶逻辑等值式,基本概念,等值式，常用等值式；前束范式,四、一阶逻辑推理理论,2、应用,用构造法证明某些简单的推理,例1、在一阶逻辑中将下列命题符号化,1) 每一个有理数都是实数,2) 并非每一个实数都是有理数,例1、在一阶逻