离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu29nnn.ppt

《离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu29nnn.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、格格的定义，最大元，最小元，有界格，有补格子格(是格不一定是子格),给定Hasse图，判断是否分配格，布尔格给定Hasse图，判断某个子集是否为子格给定格的子集，验证是否为子格。分配不等式证明,分配格等价定理证明利用性质和上下界的概念证明等式成立。格的同态映射，同构映射，保序映射布尔格，布尔代数注意分配格不一定是布尔格布尔环：a2=a,2a=0在布尔代数上定义的环是有单位元的可交换环,即布尔环;而有单位元满足幂等律的环,布尔环二、泛代数自由T-代数引理17.1,定理17.1,证明方法,唯一性存在

2、性:构造性证明过程实质上就是后面逻辑的模型构造方法给定谓词逻辑公式，化为自由T-代数元素中的形式,并且知道属于哪个Gn三、命题逻辑设X是可列集，X上的自由T-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。对P(X)如何解释设P(X)是X上关于命题演算的命题代数，称P(X)→Z2的同态映射v为P(X)的赋值。对于任意的p

3、P(X)，若v(p)=1则称p按赋值v为真，若v(p)=0则称p按赋值v为假。真值函数，真值表标准析取范式，标准合取范式设AP(X),qP(X)，若对所有使得v(p)=1(对一切pA)的赋值v，都有v(q)=1，则称q是假设集A的后件，或称A语义蕴含q，记为A╞q，用Con(A)表示A的后件全体，即Con(A)={pP(X)

4、A╞p}。形式证明，给定公理集，MP规则，演绎定理命题符号化分析，问题的化解。掌握可靠性定理，可满足性定理，完备性定理的方法四、谓词逻辑个体变元集X,个体常元集C项集

5、I是X∪C自由T(1)-代数Rni(t1,,tn)是In上的n元关系,为原子关系原子关系全体YY上的自由{F,,x

6、xX}-代数P(Y)给定谓词逻辑公式，化为自由T-代数元素中的形式,并且知道属于哪个Gn谓词合式公式，辖域，自由变元，约束变元，项t对自由变元x自由,能够判断习题19.6,19.7,19.8求l(p),d(p)解释域，项解释，赋值，语义蕴涵习题19.12,19.13,19.14,19.15,19.22,19.23形式证明，要求同命题逻辑,注意有时可能规定只能用公理集和演绎定理注

7、意问题的化解习题18,21命题符号化求前束析取范式习题27.Skolem范式集合是协调的概念，证明集合是协调的。掌握演绎定理,完备性定理,协调性定理，掌握可满足性定理(谓词逻辑系统)证明的基本思路,掌握演绎定理的证明方法。(7)

8、-(pq)→q证明:即证

9、-¬(¬¬p→¬q)→q由演绎定理即证{¬(¬¬p→¬q)}

10、-qp1=¬(¬¬p→¬q)=(¬¬p→(q→F))→F(A)p2=((¬¬p→(q→F))→F)→((q→F)→((¬¬p→(q→F))→F))(A1)p3=(q→F)→((¬¬p→

11、(q→F))→F)(p1,p2MP)P4=((q→F)→((¬¬p→(q→F))→F))→((((q→F)→(¬¬p→(q→F)))→((q→F)→F)))(A2)p5=((q→F)→(¬¬p→(q→F)))→((q→F)→F)(p3,p4MP)p6=(q→F)→(¬¬p→(q→F))(A1)p7=(q→F)→F=¬¬q(p6,p5MP)P8=¬¬q→q(A3)P9=q(p7,p8MP)可简单，利用¬q→(¬¬p→¬q)p1=¬q→(¬¬p→¬q)A1.P2=(¬q→(¬¬p→¬q))→(¬(¬¬p

12、→¬q)→¬¬q)已证P3=¬(¬¬p→¬q)→¬¬qp1,p2MPP4=¬(¬¬p→¬q)AP5=¬¬qp4,p3MPP6=¬¬q→q(A3)P7=qp5,p6MPP25712.(4)(5),13[13]下述结论是否正确，并说明理由(6)╞xp(x)→p(t)(4)╞(p→xq(x))→x(p→q)，这里x不在p中自由出现。(5)╞(p→xq(x))→x(p→q)，这里x不在p中自由出现。[14]设项t对于谓词合式公式p(x)中的x是自由的,则当╞p(x)时,必有╞p(t)。15.设A

13、P(Y)，且对所有的xX有p(x)A，问是否A╞xp(x)。23.设AP(Y)，如果A∪{p(x)}╞q，这里x不在A和q中自由出现，则A∪{xp(x)}╞q。P25722.A╞*p表示：不存在一个使得v(A){1}而v(p)=0的解释域U。说明：所谓在解释域U下v(p)=1，表示解释域U的任一项解释都使得v(p)=1；在解释域U下v(p)=0则表示在解释域U中至少存在一个项解释使得v(p)=0。问下述结论是否正确，(1){p(x)}╞*xp(x)(2)