随着Web服务技术的发展，服务的数量不断增加，然而网络上注册的大部分Web服务都是功能单一、结构简单的服务，当面对用户提出复杂的服务需求时，这些简单的服务便显得无能为力。因此如何将网络中独立存在的Web服务在尽可能节省成本的前提下以最高的效率组合在一起具有重要意义。本文以Petri网理论为基础，针对Web服务自动组合以及组合服务的形式化验证进行了深入的研究，本文的主要工作如下：第一，在OWL-S语义Web服务描述的基础上进行了动态QoS扩展的研究，利用事例推理(CBR)方法对动态QoS预测，使得服务描述具有动态性，为服务查找、服务匹配和服务组合奠定了良好的基础。第二，利用模糊推理Petri网(FRPN)方法对OWL-S描述的语义Web服务的原子进程与复合进程进行形式化建模，然后借助服务匹配思想，分析了服务组合中可能出现的所有依赖关系，建立了服务发布图，采用基于模糊推理Petri网的推理方法，通过反向、正向推理算法从服务发布图中提取出满足用户需求的Web服务组合序列。第三，采用Petri网的分析技术对推理得到的组合服务进行形式化验证，首先利用转移矩阵分析方法对组合模型进行了可达性分析并检测是否存在死锁，然后采用可达树分析方法验证Web服务组合的可靠性。通过以上理论研究，本文对服务依赖关系图生成算法和服务组合推理算法进行仿真，验证了本文所设计的算法能够很好的实现Web服务组合应用，从而证明了本文模型的设计是合理的、算法的设计是有效的。