一、格 格的定义，最大元，最小元，有界格，有补格 子格(是格不一定是子格), 给定Hasse图，判断是否分配格，布尔格

Presentation on theme: "一、格 格的定义，最大元，最小元，有界格，有补格 子格(是格不一定是子格), 给定Hasse图，判断是否分配格，布尔格"— Presentation transcript:

1 一、格 格的定义，最大元，最小元，有界格，有补格 子格(是格不一定是子格), 给定Hasse图，判断是否分配格，布尔格 给定Hasse图，判断某个子集是否为子格 给定格的子集，验证是否为子格。 分配不等式证明,分配格等价定理证明 利用性质和上下界的概念证明等式成立。 格的同态映射，同构映射，保序映射 布尔格，布尔代数 注意分配格不一定是布尔格 布尔环：a2=a,2a=0

2 在布尔代数上定义的环是有单位元的可交换环,即布尔环;
而有单位元满足幂等律的环,布尔环 二、泛代数 自由T-代数 引理17.1,定理17.1,证明方法, 唯一性 存在性:构造性证明过程实质上就是后面逻辑的模型构造方法 给定谓词逻辑公式，化为自由T-代数元素中的形式,并且知道属于哪个Gn

3 三、命题逻辑 设X是可列集，X上的自由T-代数称为X 上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。

4 对P(X)如何解释 设P(X)是X上关于命题演算的命题代数，称P(X)→Z2的同态映射v为P(X)的赋值。对于任意的pP(X)，若v(p)=1则称p按赋值v为真，若v(p)=0则称p按赋值v为假。 真值函数，真值表 标准析取范式，标准合取范式

5 设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)|A╞p}。 形式证明，给定公理集，MP规则，演绎定理 命题符号化 分析，问题的化解。 掌握可靠性定理，可满足性定理，完备性定理的方法

6 四、谓词逻辑 个体变元集X,个体常元集C 项集I是X∪C自由T(1)-代数 Rni(t1,,tn)是In上的n元关系,为原子关系 原子关系全体Y Y上的自由{F,,x|xX}-代数P(Y) 给定谓词逻辑公式，化为自由T-代数元素中的形式,并且知道属于哪个Gn 谓词合式公式，辖域，自由变元，约束变元，项t对自由变元x自由,能够判断 习题19.6, 19.7, 19.8 求l(p),d(p)

7 解释域，项解释，赋值，语义蕴涵 习题19.12, 19.13, 19.14, 19.15, 19.22, 19.23 形式证明，要求同命题逻辑,注意有时可能规定只能用公理集和演绎定理 注意问题的化解 习题18,21 命题符号化 求前束析取范式 习题27. Skolem范式

8 集合是协调的概念，证明集合是协调的。 掌握演绎定理,完备性定理,协调性定理，掌握可满足性定理(谓词逻辑系统)证明的基本思路, 掌握演绎定理的证明方法。

9 (7) |-(pq) →q 证明:即证|-¬(¬¬p→¬q)→q 由演绎定理即证{¬(¬¬p→¬q)}|-q p1= ¬(¬ ¬ p → ¬q)=(¬ ¬ p →(q→F)) →F (A) p2= ((¬ ¬ p →(q→F)) →F) →((q→F) →((¬ ¬ p →(q→F)) →F)) (A1) p3= (q→F) →((¬ ¬ p →(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)

10 p1=¬q→(¬ ¬ p→¬q) A1. P2=(¬q→(¬ ¬ p→¬q))→(¬(¬ ¬p→¬q)→¬ ¬q) 已证 P3=¬(¬¬p→¬q)→¬ ¬q p1,p2MP P4=¬(¬ ¬ p→¬q) A P5=¬ ¬q p4,p3MP P6= ¬ ¬q →q (A3) P7=q p5,p6MP

11 P257 12.(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)。

12 15.设A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。

13 P257 22. 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)}╞*x p(x) (2)╞*p(x)→xp(x)

14 18(1){yxp(x,y)}┣xyp(x,y)这里关键是脱帽带帽的问题
(2){x(p(x)→q(x))}┣xp(x)→xq(x) xp(x)→xq(x)=xp(x)→xq(x) 即要证{x(p(x)→q(x))}┣ xp(x)→xq(x) 考虑先证{x(p(x)→q(x)}┣ xq(x)→xp(x) 由演绎定理知可先证 {x(p(x)→q(x)), xq(x)}┣ xp(x) 这里要用到┣(p→q)→(q→p)，可作为待证，之后补证。

15 (3){x(p(x)→q(x))}┣xp(x)→xq(x)
由演绎定理知可先证 {x(p(x)→q(x)),xp(x)}┣xq(x) (4)┣(p→xq(x))→x(p→q),这里x不在p中自由出现。 {(p→xq(x))}┣x(p→q) 可先证{(p→xq(x))}┣p→q 由演绎定理知可先证{(p→xq(x)),p}┣q

16 18.(5)┣(p→xq(x))→x(p→q),这里x不在p中自由出现。
由演绎定理知可先证 {p→xq(x)}┣x(p→q)=x(p→q) →F {p→xq(x), x(p→q)}┣F 由(p→q)知道应该有 ┣ (p→q)→p ┣ (p→q)→q 这可以作为待证

17 补证T1:┣(p→q)→(q→p)， 由演绎定理知可先证 {(p→q), q}┣ p=p→F {(p→q), q,p}┣F 补证T2:┣ (p→q)→p 可考虑先证┣ p→(p→q) 由演绎定理知可先证{p,p} ┣ q 这里要用到┣( p→q)→(q→p),可作为待证

18 补证T3:┣ (p→q)→q 可考虑由公理集A1,A3 补证T4:┣(p→q)→(q→p) 由演绎定理知可先证 {p→q,q}┣p, 证明时可以用前面补证T1 ┣(p→q)→(q→p)

19 21.下述结论是否正确： (1)设AP(Y)，如果A∪{p(x)}┣q，这里x不在A和q中自由出现，则A∪{xp(x)}┣q。 (2)设AP(Y)，如果A┣p(y)，则A┣xp(x)，其中的p(x)是在p(y)中将y的某些(不一定所有)出现替换为x而得。 ┣(p→q)→(q→p)

20 27.求下述各谓词公式的前束范式： (1)xR11(x)→xR21(x,y)； (2)(xy(R31(u,x,y)→x(yR21(y,v))→R11(x))) (3)x(yR21(x,y)→(zR11(z)→R12(x)))。

21 答疑时间: 6月28日(周五)上午8:30-11:00 地点：软件楼4楼密码与信息安全实验室。

22 祝大家过个愉快的暑假

23 谢 谢！