Information for category learning may be provided as positive or negative equivalence constraints (PEC/NEC)-indicating that some exemplars belong to the same or different categories. To investigate categorization strategies, we studied category learning from each type of constraint separately, using a simple rule-based task. We found that participants use PECs differently than NECs, even when these provide the same amount of information. With informative PECs, categorization was rapid, reasonably accurate and uniform across participants. With informative NECs, performance was rapid and highly accurate for only some participants. When given directions, all participants reached high-performance levels with NECs, but the use of PECs remained unchanged. These results suggest that people may use PECs intuitively, but not perfectly. In contrast, using informative NECs enables a potentially more accurate categorization strategy, but a less natural, one which many participants initially fail to implement-even in this simplified setting.