usability - How to convey set inclusion and exclusion?

We have an application where users perform an action on a large set of things. The user decides which things to perform the action on by selecting to either include or exclude things based on various attributes. First, the user selects from a list of attributes (shown on the left). The selected attributes then get added to a second list where the user needs to decide whether to include or exclude the attribute (shown on the right).

^{download bmml source – Wireframes created with Balsamiq Mockups}

The end result is a union of the things with the included attributes and a subtraction of the things with the excluded attributes. Based on feedback from customers, this procedure is very confusing and users constantly make mistakes.

For example, let's say the things are people. If a user wants to perform the action on all people with brown hair, they would simply include the brown hair attribute. If the user wanted only brown-haired males, they would have to include the brown hair attribute and exclude the female attribute (yuck!). A common mistake in this case is to include brown hair and include males. However, this selection would include all people who have brown hair OR who are male (e.g. the result would include brown-haired females). The problem seems to be that sometimes users want a union of attributes (brown-hair OR black-hair) and other times they want an intersection of attributes (brown-hair AND male), but there is no way to make this distinction in the UI.

How can we improve this interface so that it is clear what is actually being chosen? Is there a better approach that still allows both inclusion and exclusion?

_{I found a similar question: Searching for items that include/exclude an attribute, but the accepted answer which suggests to intelligently prioritize results wont work for us. User's aren't selecting attributes to filter search results and then make a choice...the selection of attributes is the choice in itself. The other answers will only work with a small set of attributes (which isn't our case). Also, it isn't feasible to list out all of the things for users to validate that their selection is correct (there could be millions).}

Answer

I think using words like "and" and "or" will be best to ensure your users understand what they are doing. In this example the user would set the first attribute and then they can choose "And" or "Or" for the second attribute to determine if it is a union or an intersection. This can be done for both included and excluded items. You could select "and/or" for each subsequent attribute.

Having this include the words "items which meet" or similar will produce a SQL-like sentence which should help understanding. The user can read "INCLUDE people with Brown Hair AND Male" or "INCLUDE people with Brown Hair OR Male." Even to people unfamiliar with SQL or the concept of data sets, this should make sense.