Download presentation
Presentation is loading. Please wait.
1
定理21.9(可满足性定理)设A是P(Y)的协调子集，则存在P(Y)的解释域U和项解释，使得赋值函数v(A){1}。
不失一般性，假设X,A是满足引理21.5的(i),(ii)和(iii)。现构造解释域如下： 令U=I，1(c)=c， 2(fni)=fn'i，3(Rni)=Rn'i，定义fn'i(t1,…,tn)=(fni, t1,…,tn),并规定：当 Rni(t1,…,tn)A时，(t1,…,tn)Rn'i，否则，(t1,…,tn)Rn'i。又定义变元指派0(x)=x,由此扩张为项解释,这就构成了P(Y)的解释域和项解释。
2
在此U和下,定义函数v: P(YU,)→Z2如下：当p A时，v(p)=1，否则v(p)=0。下面证明v是满足赋值函数的定义(a)(b)(ck)
定理21.10(完备性定理):设AP(Y),pP(Y), 若A╞p，则A┣p。 (紧致性定理):如果A╞p，则存在A的某个有限子集A0，使得A0╞p。 命题逻辑 Prop(X)的有效性和可证明性是可判定的， 谓词逻辑Pred(Y)的有效性和可证明性则是不具有可判定性的
3
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)。
![P (4)(5),13 [21.13]下述结论是否正确，并说明理由 (6)╞xp(x)→p(t)](http://slidesplayer.com/slide/16651420/96/images/3/P+%284%29%285%29%2C13+%5B21.13%5D%E4%B8%8B%E8%BF%B0%E7%BB%93%E8%AE%BA%E6%98%AF%E5%90%A6%E6%AD%A3%E7%A1%AE%EF%BC%8C%E5%B9%B6%E8%AF%B4%E6%98%8E%E7%90%86%E7%94%B1+%286%29%E2%95%9E%EF%80%A2xp%28x%29%E2%86%92p%28t%29.jpg "(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)。")
4
23.(1)设AP(Y)，如果A∪{p(x)}╞q，这里x不在A和q中自由出现，则A∪{xp(x)}╞q。
(2)设AP(Y)，如果A╞p(y)，则A╞xp(x)，其中的p(x)是在p(y)中将y的某些(不一定所有)出现替换为x而得。 20.
Similar presentations
