数理逻辑最难章节 第四章纲要精华.pptVIP

说明;可靠性完备性;可满足性和有效性;定理 若A(u1，u2，…，un)是可满足的 iff ?x1?x2…?xnA(x1，x2，…，xn) 是可满足的。 证明： A(u)可满足 iff 存在赋值v，使得A(u)v=1 iff 存在赋值v，使得A(u)v(u/uv)=1 iff 存在赋值v，使得(?xA(x))v=1 iff ?xA(x)可满足 使用归纳证明即可。;定理 若A(u1，u2，…，un)是有效的 iff ?x1?x2…?xnA(x1，x2，…，xn) 是有效的。 证明： A(u)有效 iff ?A(u)不可满足 iff ?x(?A(x))不可满足 iff ??xA(x)不可满足 iff ?xA(x)有效的 使用归纳证明即可。 ;定理： A可满足 iff A的前束范式是可满足的 A有效 iff A的前束范式是有效的 定义： ∑在论域D中可满足 iff 存在以D为论域的赋值v，使得∑v=1。 A在论域D中有效 iff 对于任何以D为论域的赋值v，Av=1。;可靠性定理（一）;协调性;定理： ∑?Form(L )是协调的，当且仅当存在A∈Form(L )，使得∑├A。 证明： 必要性：假设对于任何A∈Form(L )，∑├A。这与∑是协调的相矛盾。 充分性：假设∑是不协调的，即存在B∈Form(L )，使得∑├B且∑├?B。则对于任何A∈Form(L ) ， ∑，?A├B且∑，?A ├?B，可得到∑├A。矛盾。;可靠性定理（二）;极大协调性;定理： 设∑?Form(L )是极大协调的。对于任何A ∈Form(L )，∑├A iff A∈∑。 证明： 必要性：假设A ? ∑。 由∑是极大协调的，则∑∪{A}是不协调的，即存在存在B∈Form(L )，使得∑├B且∑├?B。可得∑， A ├B且∑，A ├?B。因此， ∑├ ?A。这与∑协调矛盾。 充分性：易证。;定理： 设∑?Form(L )是极大协调的。对于任何A ∈Form(L )，?A∈∑ iff A ? ∑。 证明： 必要性：假设A∈∑。可得， ∑├A。 又因为?A∈∑，且∑├?A 。这与∑协调矛盾。 充分性：因为A ? ∑且∑是极大协调的， ∑∪{A}是不协调的，即存在B∈Form(L )，使得∑，A├B且∑，A├?B，可得∑├?A 。所以?A∈∑。;定理： 设∑?Form(L )是极大协调的。对于任何A，B∈Form(L )，A∧B∈∑ iff A∈∑并且B∈∑。 证明： 必要性：因为A∧B∈∑。可得， ∑├A ∧B。 进一步得到， ∑├A 且∑├ B 。所以A∈∑且B∈∑。 充分性：因为A∈∑且B∈∑。可得，∑├A 且∑├ B。 进一步得到， ∑├A ∧B 。所???A∧B∈∑。;定理： 设∑?Form(L )是极大协调的。对于任何A，B∈Form(L )，A∨B∈∑ iff A∈∑或B∈∑。 证明： 必要性：假设A ? ∑且B ? ∑。 可得， ?A∈∑且?B∈∑。 进一步可得，?A ∧ ?B∈∑， ?(A ∨ B)∈ ∑， ∑├ ?(A ∨ B) 。 又因为A∨B∈∑， ∑├ A ∨ B。这与∑协调矛盾。 充分性：因为A∈∑或B∈∑。可得，∑├A ∨B 或∑├ B ∨ A。 进一步得到， A ∨ B∈∑。;定理： 设∑?Form(L )是极大协调的。对于任何A，B∈Form(L )， A→B∈∑ iff A∈∑蕴含B∈∑。 A?B∈∑ iff A∈∑等值于B∈∑。 定理： 设∑?Form(L )是极大协调的。对于任何A ∈Form(L )，∑├A iff ?A∈∑。 定理： 任何协调集都可扩充为极大协调集。;引理： 设A ∈Form(L p)含不同的原子公式p1，p2，…，pn，v是真假赋值。对于i=1，2，…，n，令 若piv=1，则Ai=pi；否则，Ai=?pi。则 若Av=1，则A1，A2 ，…，An├A。 若Av=0，则A1，A2 ，…，An├?A。;定理：设∑?Form(L p)，A∈Form(L p)，且∑为有限集。 若Ф╞ A，则Ф├A 。 若∑╞A ，则∑├A 。 证明： 设A含不同的原子公式p1，p2，…，pn。令v1，v2是真假赋值，且p1v1=1， p1v2=0， p2v1= p2v2=1，piv1= piv2，i=3，…，n。由引理，由于Av1=1，所以p1，p2 ，…，An├A。由于Av2=1，所以?p1，p2 ，…，An├A。可得， p1 ∨ ?p1 ，p2 ，…，An├A， p2 ，…，An├ (p1 ∨ ?p1 ) →A 又因为Ф├ p1 ∨ ?p1 ，所以 p2 ，…，An├ p1 ∨ ?p1 。 可得， p2 ，…，An├ A。 再令u1，u2是真假赋值，且p1u1=1，