Search terms you apply to the same search (usually the same field) are combined with OR.

Example: Enter large, apply to Attributes.  Enter red, apply to Attributes.

Search terms you apply to different searches (usually different fields) are combined with AND.

Example: Enter large, apply to Attributes.  Enter stock, apply to Location.

To force Odoo to "OR" your different search terms together:

Use ADD A CONDITION under the Filters Menu beneath the search bar:

This results in two search terms on different fields being applied with OR:

To force Odoo to "AND" your same search terms together

Create two Custom Filters under Filters Menu beneath the search bar.  (Product Attributes is the field to search in your case);

This results in two search terms on the same field being applied with AND:

Note: Although the screenshots are from the Enterprise edition of version 9, this is how it works on the Community edition of version 8 and 9.