关键词: 有序决策图（OBDD）, 同一变量排序, 多有序决策图（OBDD）合并, Apply算法

Abstract: Ordered Binary Decision Diagrams（OBDD） is a Boolean function representation data structure, and has been applied in many fields. In dynamic or distribute environment, how to efficiently build OBDD of the target Boolean expression form the known Boolean expression’s OBDD is a frequent encountered problem. Under identical variable ordering, this paper puts forward a OBDD merging algorithm based on Shannon decomposition principle. In the algorithm, it firstly establishes a storage table for the target Boolean expression, and then under the reverse variable ordering it handles each variable in turn, and combines the rows with same values, until all the variables are handled.

Key words: Ordered Binary Decision Diagrams（OBDD）, identical variable ordering, multiple Ordered Binary Decision Diagrams（OBDD） merging, Apply algorithm