Do a google or groups.google search for DeMorgan's Laws. It is a set of simple rules for reducing logic equations to their simplest form. They are used by logic circuit designers all the time to convert all their logic to nor or nand gates,to facilitate circuit design. It would seem that some Perl Coder would have incorporated them into a module by now, but maybe there is a roadblock.

Maybe Math::Logic would help you?