foo.clj

(defn explode-conjuncts [conjuncts]
  "create sequence of [conjunct term] for all terms in all conjuncts"
  (for [conjunct conjuncts
        term (remove #{'not 'and} (flatten conjunct))]
    [conjunct term]))

(defn make-conjunct-terms-map [conjuncts]
  "build map of <conjunct> -> #{terms}"
  (->> conjuncts
       (explode-conjuncts)
       (group-by first) ; group by conjunct
       (map second)
       (map (fn [ct-seq] [(ffirst ct-seq) (set (map second ct-seq))]))
       (into {})))

(def conjuncts
  ['[and f1 f2 f3]
   '[and f1 f2]  
   '[not f4]])

(def conjunct->terms (make-conjunct-terms-map conjuncts))

;; > conjunct->terms
;; {[and f1 f2 f3] #{f1 f3 f2}, [and f1 f2] #{f1 f2}, [not f4] #{f4}}