P425 21. 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)

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)，可作为待证，之后补证。

(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

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 这可以作为待证

补证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),可作为待证

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

19.下述结论是否正确： (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)

32.求下述各谓词公式的前束范式： (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)))。

设谓词合式公式p=x2(R21(x1,x2))x3R31(x1,x2, x3)) 1.将p写成自由{F, →, x|xX}-代数P(Y)中的元素形式。 2.按照自由{F, →, x|xX}-代数的构造方式，P(Y) ＝ ，则应该存在某个n，使得pGn，问此n应 该为何值？ 3.指出谓词合式公式p中的自由变元和约束变元。 4.项f21(x1,x2)对谓词合式公式p中的哪些自由变元是自由的，哪些是不自由的？分别说明理由。

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

在布尔代数上定义的环是有单位元的可交换环,即布尔环; 而有单位元满足幂等律的环,布尔环 二、泛代数 自由T-代数 引理19.1,定理19.1,证明方法, 唯一性 存在性:构造性证明过程实质上就是后面逻辑的模型构造方法 给定谓词逻辑公式，化为自由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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)|A╞p}。 形式证明，给定公理集，MP规则，演绎定理 命题符号化 分析，问题的化解。 掌握可靠性定理，可满足性定理，完备性定理的方法

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

解释域，项解释，赋值，语义蕴涵 习题21.12, 21.13, 21.14, 21.20, 21.21, 21.23 形式证明，要求同命题逻辑,注意有时可能规定只能用公理集和演绎定理 注意问题的化解 习题18,19 命题符号化 求前束范式 习题31.

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

答疑时间: 6月30日(周四) 下午1:30-4:30 7月1日(周五)上午9:30-11:30 地点：软件楼4楼密码与信息安全 实验室。

祝大家过个愉快的暑假

谢 谢！