《作为描述工具数理逻辑》由会员分享，可在线阅读，更多相关《作为描述工具数理逻辑（4页珍藏版）》请在金锄头文库上搜索。
1、 一阶语言可以描述的: 给定一个图, 假设 元关系 成立表示顶点 之间存在 一条边. 以下给出图论一些概念的形式描述. ?简单无向图简单无向图 (即无自环及无平行弧): ?无向完全图无向完全图: ?无向正则图无向正则图(所有顶点的次数都是 ): ?若假设四个 元关系 将用于标识四种颜色, 则一 个图可以被四着色四着色能够被表示为: 离散数学中形式化方法在后续课程中的应用 2E(x,y)x,yxy(E(x,y) E(y,x)xE(x,x)xy(E(x,y)E(y,x)kxy (u1luklv1luk(Zi=j/(ui=ujvi=vj)/(i(x=uiy=vi)/(i(E(x,ui)E(y,vi)
2、1R,G,B,Yx(R(x)ZG(x)ZB(x)ZY(x)x(R(x) (G(x)ZB(x)ZY(x)l?假设 元关系 分别表示顶点及路径, 元关系 表示 之间存在一路径, 元关系 表示顶点 在路径 上. 以下公理描述简单连通简单连通图: 一阶语言不能描述的: 不存在仅包含两个变元符号 及一个 元关系符号 的公 式 , 使得 对于一个图成立当且仅当该图包含一 条从顶点 到 的一条路径. 证明证明: 假设存在满足上述条件的公式 . 定义以下公式 : 它表示不存在 到 的长度是 的路径. 考虑语句集合 xy(R(x)R(y)E(x,y)l1V1,V22P(x,y)x,y2I(x,p) xp xy(
3、V1(x)V1(y) (E(x,y) E(y,x)x(V1(x) E(x,x)xp(I(x,p) V1(x)V2(p)x(V1(x)V2(x)xy(P(x,y) p(I(x,p)I(y,p) xyz(P(x,y)P(y,z) P(x,z) xyp( (I(x,p)I(y,p)q(I(x,q)I(y,q) z(I(z,p) I(z,q)x,y2E 9(x,y)9(x,y) xy 9(x,y) .S1,S2,l,Sm,Sm+1f1,f2,l,fnnm+1j=k/x(Sj(x)Sk(x),x(S(x)Si(x),x(S(x)ZS1(x)ZlZSn(x),x1lxmy(fi(x1,l,xn,y) S(y)jSj(xj)x1lxmyz(fi(x1,l,xn,y)fi(x1,l,xn,z) y=z)i=1,l,m一阶语言形式化证明:
