The attribute reduction algorithms of decision table based on discernible matrix are required to construct discernible matrix, which reduces efficiency of algorithms. In this paper, the relationship between attribute discernible matrix and its discernibility is first established for general information systems. Based on the idea that the equivalent discernible matrix has a same attribute reduction, existing matrices are modified and a formula of attribute discernibility associated with algebraic reduction for decision table is proposed. A heuristic attribute reduction algorithm based on attribute discernibility is presented. Experimental results indicate that the algorithm can more easily explore an optimal or sub-optimal reduction, and is efficient.