In this paper, a new method is proposed to remove the logical redundancy for the gate-level circuit optimization. In this method, only the fanout-branch signals in the circuits, not all the signals, are examined for redundancy. When a signal is determined to be nonredundant, other nonredundant signals are found out by the efficient procedure, using only the informations which are generated in the course of the redundancy-check. In order to avoid the re-examination of a signal for redudancy, a heuristic method is proposed to determine the redundancy-checking order of signals. The proposed method is heuristic, based on the VLSI test theory. It is much faster than other methods, since it does not reexamine a signal for redundancy.