Aspects of a method and system for combinational equivalence checking for threshold logic circuits are provided. In this regard, one or more inputs may be received at a threshold logic gate. The threshold function of the threshold logic gate may be recursively decomposed into a first function and a second function using cofactors of the threshold function. A Boolean function representation of the threshold logic gate may be generated based on the recursive decomposition of the threshold function. The generated Boolean function representation of the threshold logic gate may be a maximally factored form representation of a minimal sum of products (SOP) for the threshold logic gate. A logical equivalence of the threshold logic gate may be verified with one or more other logic circuits based on the generated Boolean function representation of the threshold logic gate.