this is an age-old question. I first saw satisfactory implementation in NeXTSTEP in 1990, and in some Windows applications including Windows 95 file manager file property-sheets around 1997. Still often not done properly.
this comes up in your context, search criteria entry.
this also comes up in any context where Properties of many objects-- a multiple selection-- can be reported (shown) for all objects at once, and can be manipulated (set on all objects to a particular value, in one action).
the problem is that a checkbox can only express two values: True or False. This is the PRESENTATION of data TO the user, not the INPUT FROM the user.
many misleading and error-prone UIs conflate a boolean False value of a checkbox widget with an "indeterminate" or "does not apply" (your case), or "varies among the selection" (my example above), leading to wrong answers being provided by the computer to the user (because "False" cannot be specified as search criteria), or data corruption (because the user appears to be setting all objects to False for that attribute).
NeXTSTEP and Windows implemented this using a tri-state checkbox; that is, a checkbox that displays three possible visualizations, false: empty [ ], true: checked [x], and indeterminate: [~]. And allows the user to rotate from among them: in a Search Criteria context, from among all three choices; in a Multi-Objects Properties contexts, from among True or False as positive-to-be-done actions*.
sometimes instead of [ ][x][~] the visualizations were [N][Y][gray box] etc
When I designed UIs using this principle for plain HTML where built-in checkbox widgets cannot be modified, I generally used a drop-down menu (SELECT tag) with the three values instead of a checkbox.
*if these widgets are on a dialog or pane whose action only takes place at a later time when OK or Search or Apply is clicked, then it's ok to rotate back to the third choice, effecting a "nevermind" gesture. However, if widgets are instant-acting and modify the page or data immediately, then upon refresh the third choice would no longer apply. Be careful of "instant actions" on multiple selections, it's a great way to put a gun in users' hands by making it trivial to corrupt data widely with a single click! (such situations should not be 'instant acting', it's too dangerous).