Check if two items are equal after replacing
I found a solution to my problem. Let's look at the simpler but equivalent problem in which an item is recursively defined as an empty list or a list of items. I'll summarize the algorithm.
Variables:

Int counter starting at 0
Hash map: list of integers $\to$ integer.
The integers represent equivalence classes.

Function find(item) $\to$ int:
Finds the equivalence class of an item. Recursively call find on all the children of item. Now you have a list of ints. If this list of ints is contained in the hash map, return the corresponding value. If not, add the list to the hash map with the counter as value. Increase the counter and return the value.
Function merge(int a, int b):
Merges two equivalence classes a and b. In the hash map, replace all occurences (both in keys and in values) of a by b. Now it can happen that one key is mapped to multiple values. If that happens, again merge those values.  Repeat this until every key maps to a unique value.
Algorithm:
For every rule c = d, call merge(find(c), find(d)). Then to see if a = b, check if find(a) = find(b).