复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）32/32

P42521.AFp表示:不存在一个使得 v(A{1}而vp)=0的解释域U 冷说明:所谓在解释域U下v(p)=1,表示解释域 U的任一项解释都使得v(p)=1;在解释域U下 v(p)=0则表示在解释域U中至少存在一个项解 释使得v(p)=0。 问下述结论是否正确, *(1)Ap(x)3F*Vx p(x) (2)Fp(x)→xpx)

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){yxp(xy)}xvyp(x,y)这里关 键是脱帽带帽的问题 今(2)x(p(x)→q(x)}xp(x)→3xq(x) 冷彐Xp(x)→xq(x)=VXp(x))-VX-q(x) 即要证x(p(x)→q(x)}→Yx-→p(x)Yx-qx) 考虑先证x(p(x)→q(x)FYx-qx)→Yx-p(x) 令由演绎定理知可先证 .(Vx(p(x)->q(x)), Vx-q(x3 Vx-p(x) 这里要用到Hp→q)→(q→p),可作为待证,之后补证

❖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)Yx(p(x)→Q(x)Yxp(x)→xg(x) 由演绎定理知可先证 *(Vx(p(x)q(x)),Vxp(x)3-vxq(x) 今(4)(p→xq(x)→x(p→q),这里x不在p中 自由出现。 由演绎定理知可先证 {(p→vxq(x)hvx(p→q) 今可先证{(p→xq(x)}hp→q 今由演绎定理知可先证(p→xq(x),p}hq

❖ (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

185)(p→3xq(x)→x(p→q)这里x不在p中自由 出现。 今即证(p→Vx-(x)→=Yx-(p→q) 由演绎定理知可先证 冷{p→Vx-q(x)Px-(p→q)=Vx(p→>q)一→F 由演绎定理知可先证 今{p→Yx-q(x),x-(p→q)F 冷由_(p→q)知道应该有 冷上-(p→q)→p 今-(p→q)→-q 这可以作为待证

❖ 18.(5)┣(p→xq(x))→x(p→q),这里x不在p中自由 出现。 ❖ 即证┣(p→xq(x))→x(p→q) ❖ 由演绎定理知可先证 ❖ {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:H(p→q)→(q→p) 由演绎定理知可先证 {(p→q)=q}F→p=p→F 由演绎定理知可先证 (p→q),=q,p}F 今补证T2:}-(p→q)→p 今可考虑先证→p→(p→q) 今由演绎定理知可先证{-p,p}q 今这里要用到Hp→q)→(-q→p),可作为待证

❖ 补证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}Fp, 证明时可以用前面补证T1 卜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)设AcP,如果AU{p(x)hq,这里x不 在A和q中自由出现,则AU日xp(x)}q (2)设AcP(NY,如果AFpy),则AHxp(x) 其中的p(x)是在p(y)中将y的某些(不一定所有) 出现替换为x而得。 (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)yxR1(x)→xR21(x,y) 令(2)(Vx三y(R31(u,x,y)→x(yR21(y,v)→R1( (3)彐x(三yR21(x,y)(ZR1(z)-R12(x)

❖ 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)x3R3(x1,x2,x3) 冷1将p写成自由{E,→,Vxx∈X}-代数P(Y)中的元素形 式。 2按照自由{F,→, VXXEX}-代数的构造方式,P(Y) =UGn,则应该存在某个n,使得peGn,问此n应 该为何值? 冷3指出谓词合式公式p中的自由变元和约束变元。 冷4项f2(x1,x2)对谓词合式公式p中的哪些自由变元是 自由的,哪些是不自由的?分别说明理由

❖ 设谓词合式公式p=x2 (R2 1 (x1 ,x2 ))x3R3 1 (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.项f2 1 (x1 ,x2 )对谓词合式公式p中的哪些自由变元是 自由的，哪些是不自由的？分别说明理由。   n=0 Gn

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

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