Advanced search using and
I believe the AND OR operators you're referring to only control the relationship between different criteria (i.e. contained in X group AND had an activity of a certain type) not more than one option in the same criteria.

A workaround for sure but perhaps you could add all contacts from one of the groups to a tag and try searching all the belong to group A AND the newly created tag.