I have yet to see a GUI that could replace the expressive power of a text representation for any query.
Bugzilla has a somewhat clumsy Custom Search interface that allows you to "Show Advanced Features" to be able to put parentheses around groups of criteria like (a OR b) AND (c OR d NOT e)
- almost impossible to change your mind if you make a 1 wrong click, but the search in bugzilla is a GET request, so it is possible to manipulate the text of the query in the URL.
If individual criteria are too complex (i.e. not simple keywords), you can try to experiment and separate the Boolean logic from individual criteria, e.g.:
Criteria:
1. ddd ddd ddd
2. ddd ddd ddd
3. ...
□ Match ALL Criteria
□ Match ANY Criterium
■ Create Custom Query [?](help box):
+---------------------------------+
|1 AND 2 AND 3 |
+---------------------------------+
Unless manually edited, the text box should be pre-populated by ANDs when matching ALL criteria vs. ORs if matching ANY, it should not automatically change after manually edited, any omitted criteria should be highlighted red with appropriate warning message..
You could provide buttons AND OR NOT ( ) - when pressed to insert that command into text box, also possible to drag&drop into arbitrary position, same for dragging criteria into the text box..
But as always, ask your users and test your solutions.