资源描述：
《作为描述工具数理逻辑》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、离散数学中形式化方法在后续课程中的应用一阶语言可以描述的:给定一个图,假设2元关系E(x,y)成立表示顶点x,y之间存在一条边.以下给出图论一些概念的形式描述.ò简单无向图(即无自环及无平行弧):]xy(E(x,y)>E(y,x))]xE(x,x)ò无向完全图:]xy(E(x,y)[E(y,x))ò无向正则图(所有顶点的次数都是k):]xy(^ululvlu(1k1k(Z(u=u/[v=v/))[i=j/ijij([(x=u/[y=v/))[iii([(E(x,u)[E(y,v)))iii))ò若假设四个1元关系R,G,B,Y将
2、用于标识四种颜色,则一个图可以被四着色能够被表示为:]x(R(x)ZG(x)ZB(x)ZY(x))[]x(R(x)>(G(x)ZB(x)ZY(x)))[l[]x]y(R(x)[R(y)[E(x,y))[l[ò假设1V元关系,V分别表示顶点及路径,2元关系12P(x,y)表示x,y之间存在一路径,2元关系I(x,p)表示顶点xp在路径上.以下公理描述简单连通图:]xy(V(x)[V(y)>(E(x,y)>E(y,x)))11]x(V(x)>E(x,x))1]xp(I(x,p)>V(x)[V(p))12^x(V(x)[V(x)
3、)12]xy(P(x,y)>^p(I(x,p)[I(y,p)))]xyz(P(x,y)[P(y,z)>P(x,z))]xy^p((I(x,p)[I(y,p))[]q(I(x,q)[I(y,q)>]z(I(z,p)>I(z,q))))一阶语言不能描述的:不存在仅包含两个变元符号x,y及一个2元关系符号E的公式9(x,y),使得9(x,y)对于一个图成立当且仅当该图包含一条从顶点xy到的一条路径.证明:假设存在满足上述条件的公式9(x,y).定义以下公式4、112n-1nn[x=x)i=j/ij它表示不存在xy到的长度是n+1的路径.考虑语句集合{9(c,c)}P{<(c,c)
5、n=1,2,l}12n12其中c1,c2表示一个图的两个顶点.上述语句集合的任意有限子集有模型但它本身没模型,这与谓词逻辑的紧致性是相矛盾的.一阶模型可以表示的:可以使用逻辑概念统一定义图论一些概念,这些与代数系统的相应概念是一致的:ò图同构:上述理论的两个模型的是同构的.ò子图:上述理论的两个模型有子模型关系.代数系统的一些概念:òm-元代数运算:S#S#l#S到S的一个映射.可以看成是12m集合SPSP
6、lPSPSm上的一个+1元关系.12mò代数系统:mS个非空集合,S,l,S与它们上面的n个12mmf-元代数运算,f,l,f组成一个代数系统:12n.12m12n可以假设S,S,l,S,S是m+1个一元关系符号,12mf,f,l,f是nm个+1元关系符号.则上述代数系统可以12n看成是以下语句的一个模型:[^x(S(x)[S(x)),j=k/jk^x(S(x)[S(x),i]x(S(x)ZS(x)ZlZS(x)),1n]xlxy(f(x,l,x,y)>S(y)[[S(x)),1mi1njjj
7、]xlxyz(f(x,l,x,y)[f(x,l,x,z)>y=z),1mi1ni1n其中i=1,l,m.一阶语言形式化证明:
