normalize boolean expression for caching reasons. is there a more efficient way than truth tables?

My current project is an advanced tag database with boolean retrieval features. Records are being queried with boolean expressions like such (e.g. in a music database):

funky-music and not (live or cover)

which should yield all funky music in the music database but not live or cover versions of the songs.

When it comes to caching, the problem is that there exist queries which are equivalent but different in structure. For example, applying de Morgan's rule the above query could be written like this:

funky-music and not live and not cover

which would yield exactly the same records but of cause break caching when caching would be implemented by hashing the query string, for example.

Therefore, my first intention was to create a truth table of the query which could then be used as a caching key as equivalent expressions form the same truth table. Unfortunately, this is not practicable as the truth table grows exponentially with the number of inputs (tags) and I do not want to limit the number of tags used in one query.

Another approach could be traversing the syntax tree applying rules defined by the boolean algebra to form a (minimal) normalized representation which seems to be tricky too.

Thus the overall question is: Is there a practicable way to implement recognition of equivalent queries without the need of circuit minimization or truth tables (edit: or any other algorithm which is NP-hard)?

The ne plus ultra would be recognizing already cached subqueries but that is no primary target.