Logical Methods in Computer Science Vol. 9(3:25)2013, pp. 1–46 www.lmcs-online.orgSubmitted Jan. 16, 2013 Published Sep. 24, 2013UNARY NEGATIONBALDER TEN CATE a AND LUC SEGOUFIN ba UC Santa Cruz e-mail address: btencate@ucsc.edub INRIA and ENS Cachan, LSV e-mail address: luc.segoufin@inria.frAbstract. We study fragments of first-order logic and of least fixed point logic that allow only unary negation: negation of formulas with at most one free variable. These logics generalize many interesting