I agree the mix and match scenario you refer to would be a bit more challenging. But at the risk of repeating myself, my interpretation based on the original post was not to mix and match but to supply one or the other possibility. To that end I said use option buttons with labels that define what the selection means: One for records where all criteria must be present, one for records where any are present. If you want to do what you said, I guess I'd put combos in between textboxes for operators and read it right to left.
Foo AND bar OR Dis And Dat
I don't recall ever doing that, but I don't see why I couldn't replace the actual operators with the combobox values (e.g. AND or OR). I just might take a whack at it for fun. If anyone has any 'heads up' things to consider, they could be useful comments.
The more we hear silence, the more we begin to think about our value in this universe.
Paraphrase of Professor Brian Cox.