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

定理21,9(可满足性定理)设A是P(Y的协 调子集,则存在P(Y)的解释域U和项解释 使得赋值函数vA)≤{1}。 不失一般性,假设X,A是满足引理21.5的 i)(i)和(i)。现构造解释域如下 YU=I, (c)=c, 2(ifm i, (3(R,)=R,i 定义fu(t1…,t)=(fn,t1…,t,并规定:当 Rn(t1…,t)∈A时,(t1,tn)∈Rn",否则, (t1…,t)gRn"。又定义变元指派p(x)=x 由此扩张为项解释这就构成了P(Y)的解 释域和项解释

❖ 定理21.9(可满足性定理)设A是P(Y)的协 调子集，则存在P(Y)的解释域U和项解释 ，使得赋值函数v(A){1}。 ❖ 不失一般性，假设X,A是满足引理21.5的 (i),(ii)和(iii)。现构造解释域如下： ❖ 令U=I，1 (c)=c， 2 (fn i )=fn ' i ，3 (Rn i )=Rn ' i ， 定义fn ' i (t1 ,…,tn )=(fn i , t1 ,…,tn ),并规定：当 ❖ Rn i (t1 ,…,tn )A时，(t1 ,…,tn )Rn ' i ，否则， (t1 ,…,tn )Rn ' i 。又定义变元指派0 (x)=x, 由此扩张为项解释,这就构成了P(Y)的解 释域和项解释

冷在此U和φ下定义函数v:P(Y9)→Z2如下: 当p∈A时,v(p)=1,否则v(p)=0。下面证 明v是满足赋值函数的定义(a)(b)(c) 定理21.10(完备性定理):设AP(Y),p∈P(Y), 若Ap,则AHp (紧致性定理):如果Ap,则存在A的某个有 限子集A,使得APp。 命题逻辑Prop(X的有效性和可证明性是可 判定的, 冷谓词逻辑Pred(Y的有效性和可证明性则是 不具有可判定性的

❖ 在此U和下,定义函数v: P(YU,)→Z2如下： 当p A时，v(p)=1，否则v(p)=0。下面证 明v是满足赋值函数的定义(a)(b)(ck) ❖ 定理21.10(完备性定理):设AP(Y),pP(Y), 若A╞p，则A┣p。 ❖ (紧致性定理):如果A╞p，则存在A的某个有 限子集A0，使得A0╞p。 ❖ 命题逻辑 Prop(X)的有效性和可证明性是可 判定的， ❖ 谓词逻辑Pred(Y)的有效性和可证明性则是 不具有可判定性的

P42412.(4)(5),13 [21.13]下述结论是否正确,并说明理由 (6)xp(x)→p(t) (4)F(p→xq(x)→x(p→q),这里x 不在p中自由出现。 (5)(p→3xq(x))→丑x(p→q),这里x不 在p中自由出现。 [21.14]设项t对于谓词合式公式p(x)中 的x是自由的,则当卜p(x)时,必有 p(t)

❖P424 12.(4)(5),13 ❖ [21.13]下述结论是否正确，并说明理由 ❖ (6)╞xp(x)→p(t) ❖ (4)╞(p→xq(x))→x(p→q) ， 这 里 x 不在p中自由出现。 ❖ (5)╞(p→xq(x))→x(p→q)，这里x不 在p中自由出现。 ❖ [21.14]设项t对于谓词合式公式p(x)中 的x是自由的,则当╞p(x)时,必有╞ p(t)

23(1)设AcP(Y),如果AU{p(x)Fq,这里x 不在A和q中自由出现,则AU{3 xp(x)) Fq (2)设AcP(Y,如果Ap(y),则A上xp(x) 其中的p(x)是在p(y)中将y的某些(不一定所有) 出现替换为x而得 20

❖ 23.(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而得。 ❖ 20