#!/usr/bin/perl
use warnings;
use strict;

for my $given ( "(A & B)'",
                "((A & B)' | (A & C & (A & B & D)'))",
                "((A | B)' & (C | (D & (E & F)))')'",
              ) {
    my @left;
    my $calc = $given;
    my $last;
    for my $pos (0 .. length($given) - 1) {
        my $current = substr $given, $pos, 1;
        push @left, $pos if '(' eq $current;
        $last = pop @left if ')' eq $current;
        if ("'" eq $current) {
            substr $calc, $pos, 1, q();
            substr $calc, $last, 0, '!';
        }
    }
    print "Given: $given\n";
    print "Calculated: $calc\n";
}
[download]

Update: Or, if you really need to use a regex, use a recursive subpattern (see perlre):

#!/usr/bin/perl
use warnings;
use strict;

my $re = qr/(\(((?:(?>[^()]+)|(?1))*)\))'/;

for my $given ( "(A & B)'",
                "((A & B)' | (A & C & (A & B & D)'))",
                "((A | B)' & (C | (D & (E & F)))')'",
              ) {
    my $calc = $given;
    $calc =~ s/$re/!($2)/g while $calc =~ /'/;
    print "Given: $given\n";
    print "Calculated: $calc\n";
}
[download]

Update 2: You can also write a full parser for the expressions:

#!/usr/bin/perl
use warnings;
use strict;

use Marpa::R2;

my $dsl = << '__DSL__';

:default ::= action => concat
lexeme default = latm => 1

Expression ::= '(' Expression ')'             assoc  => group
             | literal
             | Expression quote               action => negation
            || Expression sp operator sp Expression

quote    ~ [']                                                   # '
operator ~ [&|]
literal  ~ [A-Z]
sp       ~ [\s]+

__DSL__

my $i = 0;
sub concat { $i++; join q(), @_[ 1 .. $#_ ] }
sub negation { $i++; "!$_[1]" }

my $grammar = 'Marpa::R2::Scanless::G'->new({ source => \$dsl });

for my $given ( "(A & B)'",
                "((A & B)' | (A & C & (A & B & D)'))",
                "((A | B)' & (C | (D & (E & F)))')'",
              ) {
    my $calc = $grammar->parse(\$given, { semantics_package => 'main' 
+});
    print "Given: $given\n";
    print "Calculated: $$calc\n";
}
[download]

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]