无限集合初步z写出集合论公理的一阶描述. 解答外延公理:空集公理:偶对公理:并集公理:子集公理:幂集公理:无穷公理:替换公理:正规公理:选择公理：□z证明:可数符号表上有限长字符串集合是可数的.证明假设给定的可数符号表是集合 , 则 {长度是 的字符串的集合 . {长度是 的字符串的集合 .{每个 都是可数集合, 这可数个可数集合的并集是可数的.高等数理逻辑作业全部]xy(]z(z J x ?z J y)> x =y )^x ]y(y J x)./]xy ^u ]z(z J u ?z=x Z z=y).]x ^u ]y(y J u ?(^z(z J x [y J z))).]x 1,l ,x n ]x ^y ]z(z J y ?z J x [9).]x ^y(]z(z J y ?z N x )).^x(IJ x [(]y(y J x >y +J x ))).]x 1,l ,x n ]x(<> ^y ]z(z J y ?^u J x 9[u,z])).]x(x=I> ^y(y J x [y Q x=I ))./]x(x=I> ^y(91[92))./A 1S 1=A 2S 2={ab|a,b J A}l S n□z证明: .证明可以仅考虑开区间 内的实数, 证明可以按照以下方式构造双射: □公理集合论初步z空集是函数. 证明是一个函数, 当且仅当以下性质成立:其中{ 是公式 {是公式是一个函数. 这是因为:在上述定义中, 两个蕴涵式的前提不成立.□z对于集合 及 , 则它们的交集是集合.证明这个集合是存在的, 是由子集公理保证的:相应的集合是 、一阶公式是 . □z对于集合 及 ,它们的卡氏积 是集合. 对于以下两个实数:对应于以下实数:R .R #R (0,1)(0,1)#(0,1).(0,1).u=0$a 0a 1a 2l v=0$b 0b 1b 2l w=0$a 0b 0a 1b 1a 2b 2l a 91[92.91]x(x J a > ^uv(x=< u ,v> )).92]uvw(< u ,v> J a [< u ,w> J a > v =w ).I x J a > ^uv(x=< u ,v> ),< u ,v> J a [< u ,w> J a > v =w x y a-b={x|x J a [x J b}./a-b={x J a|x J b}./a x Jb /x y x #y={<u ,v> |u J x,v J y}证明对于集合 及 , 乘积 的存在性可以由子集公理保证:其中:{ 是集合:{ 是公式: . □z假设 是两个集合, 存在 到 的满射. 证明: 存在 到 的单射.证明假设 是满射, 则可以定义 到 的映射 : 是单射, 这是因为当 时, , 所以□公理集合论及自然数理论初步z证明: 存在无限集合 证明定义以下公式 :其中{ 是公式: . {是公式: .对任意的 , 存在唯一一个函数 满足由此可知, 对任意的 , 存在唯一的 使得根据替换公理, 可知存在集合这时对每个 , 考虑集合因为 是满射, 所以 不是空集, 任取 作为 的象, 则可以定义 到 的映射 . a b a #b a #b={w|w J c [9(w)}.c 3(3(x)P 3(a P b)).9(w)^uv(u J a [v J b [w=<u ,v> )A,B A B B A f:A >B B A g y J B f -1({y})={x J A|f(x)=y},f f -1({y})x J f -1({y})y B A g g y 1=y 2J B /f -1({y 1})Q f -1({y 2})=I g(y 1)=g(y 2)./{0,{1},{{2}},{{{3}}},l }.)(x,y)(x=0> y =x )[(\x=0> ^f(91[92[y=f(x)))91func (f)[0J dom (f)[f(0)=x [dom (f)=x +92]u(u J dom (f)[u +J dom (f)> f (u +)={f(u)})n J =f 91[n][92.n J =a )[n,a]..={a|^n(n J =[)[n,a])}.0,{1},{{2}},{{{3}}},lJ ..□z证明: 证明假设 是两个自然数, 满足 , 这时, 根据定义可知:若 , 则 {从 可知 , 因而 .{从 可知 , 因而 .这时集合 不满足正规公理:这个矛盾表明 .□命题逻辑的可靠性证明命题逻辑具有可靠性. 证明如下定义公理系统:z公理:{ : . { : . {: .z规则:定义 为: 存在公式序列 使得z 或者 ;z 或者 是公理; z 或者存在 , 使得 是 . 且 是 .这时, 对任意的赋值 , 都有同时所以这是命题逻辑的可靠性质. 如下定义公理系统:当 且 ,时, . 若 , 则 .]mn(m J =[n J =[m +=n +> m =n).m,n m +=n +m P {m}=n P {n}.m=n/m J m P {m}m J n P {n}m J n n J n P {n}n J m P {m}n J m x={m,n}x=I> ^y(y J x [y Q x=I )./m=n 91A > (B > A )92(A > (B > C ))> ((A > B )> (A > C ))93(\A > B )> ((\A > \B)> A )A,A > B B.D U C < A 1,A 2,l ,A n > A iJ > A ij,k< i A k A j > A i A n C v v(91)=1,v(92)=1v(93)=1.v(A)=1v(A >B )=1v(B)=1D UCD X Cz公理:z规则:{ . 单调性{反证法{三段论{演绎定理 {,{{{, {,{可以类似地验证可靠性.□命题逻辑完备性对任意的极大协调集合 及公式 , 有以下性质:z当且仅当 . 证明若 则 . 若 , 则这时 , 与 的协调性相矛盾.所以 . 若 则 . 若 , 则根据极大协调集合的定义, 可知 是不协调的,所以 , 这与 相矛盾, 所以 .□A U A.D U A D ,D d U AD ,\A U B 且D ,\A U\B D U A.D U A 且D U A > B D U B.D ,A U B D U A > B .D U A [B D U AD U A [B D U B.D U A 且D U B D U A [B.D ,A U C 且D ,B U C D ,A Z B U C.D U A D U A Z BD U A D U B Z A.D U A ?B 且D U A D U BD U A ?B 且D U B D U A.D ,A U B 且D ,B U A D U A ?B.D A,B \A J D A J D /\A J D A JD /A J D A,\A J D D A JD /A JD /\A J D \A JD /D P {\A}D ,\A U 0,A J D A JD /\A J Dz当且仅当 并且 . 证明若 则 并且 . 因为所以当 时,因为极大协调集合对 是封闭的, 所以若 并且 则 . 若 并且 ,则因而根据极大协调集合对 是封闭的,可知 .□z 当且仅当 或者 .z 当且仅当 蕴涵 . z当且仅当 等价于 .命题逻辑公理独立性(1)z独立于 . 证明选择以下真值表验证: □z独立于 . 证明选择以下真值表验证:A [B J D A J D B J D A [B J D A J D B J D A [B U A 且A [B U B,A [B J D D U A 且D U B.U A J D 并且B J D .A J D B J D A [B J D A J D B J D D U A 且D U B,D U A [B,U A [B J D A Z B J D A J D B J D A > B J D A J D B J D A ?B J D A J D B J D 92{91,93}> 0123\00113310010020003030000093{91,92}> 01\0010□命题逻辑公理独立性(2)z单调性规则是独立的 证明在单调规则之外的规则, 前提都不增加, 若不使用此规则, 则以下推演关系是不可证的:由此可得独立性证明.□z反证法规则是独立的 证明对于任意的真值赋值 及公式 , 定义可以得到新的逻辑推出关系 . 除反证法规则之外, 其他规则都是可靠的. 使用反证法规则可得推演关系但由此可得独立性的证明.□z演绎定理规则是独立的证明对于任意的真值赋值 及公式 , 定义可以得到新的逻辑推出关系 . 对于与 无关的规则, 都是可靠的. 以下考虑三段论规则:需证明:对任意的赋值 , 若 , 则从1000A,B U A.v A v(\A)=1.X d \\p U p.\\p X d/p.v A,B v(A > B )=i aa a aa e a a a a j0,若v(A)=1,1,否则.X dd > D U A 且D U A > B D U B.D X dd A且D X dd A > BD X ddB.v v(D )=1可知这与定义相矛盾, 所以 .所以是成立的. 因此使用演绎定理规则, 可得推演关系但由此可得独立性的证明.□z... 证明同理可以证明其他规则是独立的.□直觉主义逻辑证明以下推导关系成立:z证明从 及 , 可知同理可知所以□z若 , , 且 , 则 . D X dd A 且D X dd A > B ,v(A)=1且v(A > B )=1,v(D )=0v(D )=1D X dd A D X dd A >B v(B)=1D X ddB.p U q > p ,p X dd/q > p .\(A Z B)U c \A [\B.C >D U c \D > \C U c A > A Z B U c \(A Z B)> \A.U c \(A Z B)> \B.\(A Z B)U c \A [\B.\A [\B U c \(A Z B).证明. .所以 . 所以集合不是 协调的.由 可知□z证明 集合不是 协调的.所以□z证明 集合不是 协调的.所以□证明以下推导关系不成立:z证明假设 分别是命题变元 , 构造模型 使得其中{ 使得 及 ,{ 使得 及 .这时 , , 所以但是 , 所以\A,\B,A U c 0\A,\B,B U c 0\A,\B,A Z B U c 0{\A [\B,A Z B}U c -(\+)\A [\B U c \(A Z B).A Z B U c \(\A [\B).{\A [\B,A Z B}U c -A Z B U c \(\A [\B).\A Z\B U c \(A [B).{A [B,\A Z\B}U c -\A Z\B U c \(A [B).\A >B U c \B > A A,B p,q K =<V ,R> ,V={v,w},R={(v,v),(v,w),(w,w)}.v v(p)=0v(q)=0w w(p)=1v(q)=0q K ,v =0q K ,w =0(\q)K ,v=1.p K ,v =0另一方面,所以即在模型 的第一层, 左边取 而右边取 . 因而上述公式是不永真的, 因而是不可证的.□z证明假设 是命题变元 . 构造模型 , 使得其中{ 使得 ,{ 使得 .这时 , 但 , 所以□z证明假设 分别是命题变元 , 构造模型 , 使得其中{ , , { , , {, .□假设 是命题逻辑公式集合,是命题逻辑公式,则 其中证明以下证明:z .(\q > p )K ,v =0.(\p)K ,v=0,(\p)K ,w=0,(\p > q )K ,v=1.K 10U c A Z\A A p K =< V ,R> V={v,w},R={(v,v),(v,w),(w,w)}.v v(p)=0w w(p)=1p K ,v =0(\p)K ,v =0(p Z\p)K ,v=0.\(A > \B)U c A [B A,B p,q K =< V ,R> V={v 1,v 2,v 3},R={(v 1,v 1),(v 2,v 2),(v 3,v 3),(v 1,v 2),(v 1,v 3)}.v 1(p)=0v 1(q)=0v 2(p)=1v 2(q)=0v 3(p)=0v 3(q)=1D A \D U\A \D U c \A \D ={\B|B J D }.\\\A U c\Az若 , 则 .则可知以下条件是等价的:z .z . z .. 因为 , 所以是不相容的, 因而 .若 , 则 . 因为 , 所以存在一个 推演, 将出现的所有公式 都换为 , 以下证明这样得到一个 推演. 以应用 为例. 这时有被转换为将前提推演序列中的 换为 , 则可以由 得到□模态命题逻辑z证明以下推演关系:证明假设 是 . 从 及 , 根据 推演规则, 可知 . 所以 . 同理可知 . 由此可知 □证明: {D U A \\D U c \\A \D U\A \\\D U c\\\A \D U c\A \\\A U c \A A U c \\A {\\\A,A}\\\A U c \A D U A \\D U c \\A D U A U -C \\C U c -(\-)> ,\E U F 且> ,\E U\F >U E ,\\> ,\\\E U \\F 且\\> ,\\\E U \\\F \\>U \\E ,\\\E \E (\+)\\> U \\E.U T (`(A > B )[`(B > A ))> (`A ?`B).D {`(A >B ),`A}D U T `(A >B )D U T `A T-D U T `B `(A >B )U T `A > `B `(B >A )U T `B > `A U T (`(A >B )[`(B > A ))> (`A ?`B)U T `(A [B)?(`A [`B).`(A [B)U T (`A [`B)A [B U A{ (性质){ (同理){{{ (规则){ (性质){ (性质){{ (性质)□证明{ (已证){ (性质){ (性质){ (定义)□z证明 可靠性.证明只需证明对任意 及 , 若 , 则从 可知 :因而对任意的 , 都有根据定义, 当且仅当 当且仅当(1)对任意的 , 都有`(A[B)U`A`(A[B)U`B`(A[B)UT(`A[`B)`A[`B UT`(A[B)U A> (B> A[B)UT`(A> (B> A[B))UT`A> `(B> A[B)`A UT`(B> A[B)`A UT`B> `(A[B)`A,`B UT`(A[B)UTa(A Z B)?(a A Za B).UT`(\A[\B)?(`\A[`\B)UT\`(\A[\B)?\(`\A[`\B)UT\`\(A Z B)?(\`\A Z\`\B)UTa(A Z B)?(a A Za B)S4-D XS4`AD XS4``A.M=< V,R> J KS4v J V D M,v=1D XS4`A `A M,v=1,w:vRwA M,w=1.``A M,v=1v 1:vRv1`A M,v1=1.对任意的v1,v2:vRv1,v1Rv2,都有A M,v2=1但根据传递性可知 , 所以由 (1) 成立可知 (2) 成立. 所以 .□z证明 可靠性. 证明只需证明对任意 及 , 若 , 则从 可知 :因而存在 , 都有根据定义,当且仅当当且仅当这时 成立 所以由 (1) 成立可知 (2) 成立.所以 .□谓词逻辑推演规则 以下规则是可靠的:证明以下证明 (:左规则) 是可靠的, 其他规则的可靠性可以类似证明. 需要证明以下事实:对任意的模型 及一个赋值, 当 时, 从 可知, 对任意的, 都有(1)对任意的 , 都有(2)vRv 2D X S 4``A S 5-D X S 5a AD X S 5`a A.M =<V ,R> J K s 5v J V D M ,v =1D X S 5a A a AM ,v=1,w:vRw A M ,w =1.`a AM ,v=1v 1:vRv 1a AM ,v1=1.对任意的v 1:vRv 1,存在v 2:v 1Rv 2,使得AM ,v2=1wRv 2D X S 5`a A ]]^^]D ,A x tX B D ,]xA X B.M M X D ,]xA M X]xA a J |M |M X A[a].而每个项 在 中代表一个具体的值, 所以 , 因而□谓词逻辑完备性质已知 是公式集合,是公式, 常元 不在 中出现, 证明: 证明根据谓词逻辑的完备性质, 只需证明 即因为常元 不出现在 中, 所以任意改变 在 中的取值, 都不影响 的真值.假设 的取值是 , 从 及可靠性,可知因为 是任意的, 所以□已知 是协调公式集合,且证明这些公式集合的并集是协调的. 证明假设 是公式集合若 不协调, 则 . 因为每个推演仅涉及有限多个公式, 所以存在 , 使得根据 的定义, 可以假设 .假设 , 则 . 这与 的协调性相矛盾. 所以 是协调的.□实闭域的判定性质语言 的理论 具有量词消去性质, 当且仅当 若 , 则对于任意的模型 , 当 时,对 的任意 个原子公式或者原子公式的否定t M M X D ,A x t M X B.D A c D P {A}D U A x c D U]xA.D X]xA,M M X D M X]xA.c D P {A}c M D P {A}c a D U A x c M X A[a].a M X]xA.D n (n=0,1,2,l )D 0N D 1N D 1Nl > D 0P D 1P D 1Pl > >U 0A 1,A 2,l ,A m J > A 1,A 2,l ,A m U 0.> A i J D k il=max {k 1,k 2,l ,k m }A 1,A 2,l ,A m J D l D l > L T L k证明(结构归纳法)假设已证明以下结论 (*):对任意的开公式 因为而 是一个开公式, 所以存在开公式 使得这里的 是一个开公式.由此可知, 每个前束范式都等值于一个开公式. 对于结论 (*), 可以将开公式 写为其中每个 是一些原子公式或者原子公式的否定的合取式. 这时所以, 只需对上述 这一类公式考察量词消去性质.□(介值定理)证明在实闭域内, 每个多项式可以分解为 次及 次多项式的乘积, 可以假设这些多项式的最高项系数都是 .次多项式 可以写为z若 , 则 可以分解为 次多项式的乘积.z若 , 则 .所以, 当 的取值在一个区间 内改变符号时, 一定有一个 次因子, 它在这个区间内取值改变符号, 该 次因子在这个区间内有零点, 因而 在这个区间内有零点.□存在 的一个开公式 , 使得对任意的开公式 , 存在开公式 , 使得9i (x ,x 1,x 2,l ,x n ),i=1,2,l ,k,L <(x 1,x 2,l ,x n )T X]x 1,x 2,l ,x n (^x (91[92[l[9k )?< (x 1,x 2,l ,x n )).))d T X^x )?)d.3]x 3等值于\^x \3,\33d T X^x \3?3d,T X]x 3?\3d,\3d))1Z )2ZlZ )k ,)i X^x()1Z )2ZlZ )k )?(^x )1Z^x )2ZlZ^x )k ),)i RCF X]xy(x< y [f(x)f(y)< 0> ^z(x< z [z< y [f(z)=0)).1212x 2+ax+b (x+a 2)2+(b-a24),(b-a 24)50x 2+ax+b 1(b-a24)>0RCF X x 2+ax+b> 0f(x)[a,b]f(x)11f(Rolle 定理) 证明(由介值定理证明 Rolle 定理)每个多项式最多有有限个零点, 当 时, 可以假设在区间 内, 不再有其他零点.所以 在区间 内不可能是单调的, 因而存在 使得 . 对于多项式 , 根据介值定理可知: 存在 使得 .□一阶逻辑的不可判定性质写出以下 Turing 机对应的一阶语句:解答这些转换规则对应以下语句: ::::□RCF X]xy(x< y [f(x)=0[f(y)=0> ^z(x< z [z< y [f d (z)=0)).f(a)=f(b)=0[a,b]f f [a,b]u<v J [a,b]f d (u)f d (v)< 0f d c J [a,b]f d (c)=0{q 01Rq 0,q 00Rq 2,q 110q 2,q 10Rq 1}q 01Rq 0]xy(R 0(x,f 1(y))> R 0(f 1(x),y))q 00Rq 2]xy(R 0(x,f 0(y))> R 2(f 0(x),y))q 110q 2]xy(R 1(f 0(x),f 1(y))> R 2(x,f 0(f 0(y))))]xy(R 1(f 1(x),f 1(y))> R 2(x,f 1(f 0(y))))q 10Rq 1]xy(R 1(x,f 0(y))> R 1(f 0(x),y))。
