A clausal logic allowing to handle term-graphs is defined. Term-graphs are a generalization of terms (in the usual sense) possibly containing shared subterms and cycles. The satisfiability problem for this logic is shown to be undecidable (not even semi-decidable), but some fragments are identified for which it is semi-decidable. A complete (w.r.t validity) calculus for these fragments is proposed. Some simple examples give a taste of this calculus at work.