Your question is still not clear. You've stated your needs, you have laid your cards on the table... so what do you need? a solution? a suggestion? or perhaps an opinion?
Assuming its a "way" I make my post & reply.
Set Operation? Think Venn Diagrams
They best represent all possible operations in a way anyone could digest. How? Look at the illustration below:
Using color merge I represent a set of people who like red shirts and were born in January. Similarly you can use color inverse to represent the other scenario.

In a HTML-table or in a Search result panel - I can do a similar color (on rows and columns) based representation to distinguish between results optimal to the selected operation. Check out this example for more ideas and formula.
Cool story so far, How do I construct such a search bar / widget?
If you want to torment your end-users, feel free to use [+] [-] icons and complex filter mechanism in the search text area. OR If you prefer a smooth easy solution try natural language forms as seen here, and here is the code
and here is another illustration:

Replace the fixed AND with OR, or even leave that as an interactive field for the end-user to play with.