Abstract: Aiming at the problem of equivalent conversion from conjunctive normal form to disjunctive normal form, an effective algorithm was proposed to construct reduction tree based on discernibility matrix. The discernibility set was acquired by improving discernibility matrix, and then reduction tree was designed to describe concrete process of getting reductions, finally each path from root to leaf was set to a reduction. This method decreases overhead in forming and storing discernibility matrix, and simplifies the process of acquiring all reductions of decision system.

Key words: rough set, discernibility matrix, reduction tree

摘要： 针对差别矩阵求约简过程中合取范式向析取范式等价转换的难题，提出一种基于差别矩阵构造约简树的有效方法。首先优化改进差别矩阵得到差别集，然后设计约简树描述约简获取的具体过程，最终所得约简树根节点到叶节点的每条路径即对应一个约简。该方法减少了生成和存储差别矩阵的时空开销，简化了获取决策系统全部约简的过程。

关键词: 粗糙集, 差别矩阵, 约简树