This is an addendum to my reply above, and fixes an error therein ((?R) vice (?-1)). It also avoids an  s///e executable substitution.

Try this for better results (still needs 5.10+):

use 5.010;

use warnings;
use strict;

use Test::More
  # tests => ?? + 1  # Test::NoWarnings adds 1 test
    'no_plan'
    ;
use Test::NoWarnings;

use constant TEST_SET => (
    [ q{()},   q{()} ],
    [ q{()'},  q{!()} ],
    [ q{(()')'},  q{!(!())} ],
    [ q{((()')')'},  q{!(!(!()))} ],
    [ q{(()' (()')')'},  q{!(!() !(!()))} ],
    [ q{(A & B)},   q{(A & B)} ],
    [ q{(A & B)'},  q{!(A & B)} ],
    [ q{(A & B | (C & D)')'},  q{!(A & B | !(C & D))} ],
    [ q{((A & B)' | (A & C & (A & B & D)'))},
      q{(!(A & B) | (A & C & !(A & B & D)))}
      ],
    [ q{((A | B)' & (C | (D & (E & F)))')'},
      q{!(!(A | B) & !(C | (D & (E & F))))}
      ],
    [ q{((A & B)' | (A & C & (A & Boff' & D | (A & (B' & D)')'))},
      q{(!(A & B) | (A & C & (A & !Boff & D | !(A & !(!B & D))))}
      ],
    );

FUNT:
for my $func_name (qw(xform_4)) {

    note "\n----- testing $func_name() ----- \n\n";
    *xform = do { no strict 'refs';  *$func_name; };

    VECTOR:
    for my $ar_vector (TEST_SET) {

        if (not ref $ar_vector) {
            note $ar_vector;
            next VECTOR;
            }

        my ($string, $expected) = @$ar_vector;

        is xform($string), $expected, qq{$string}

        }  # end for VECTOR

    }  # end for FUNT

done_testing;

# functions under test #############################################

sub xform_4 {  # needs 5.10+ for (?PARNO) and (?|...)

    my ($str,
        ) = @_;

    my $parenthetic = qr{ ( [(] (?: [^()]*+ | (?-1))* [)] ) }xmso;
    my $term        = qr{ ( [[:alpha:]] \w*               ) }xmso;

    1 while $str =~ s{ (?| $parenthetic | $term) ' }
                     {!$1}xmsgo;

    return $str;

    }
[download]

c:\@Work\Perl\monks\Learning_Perl_2017>perl xform_nested_terms_1.pl
#
# ----- testing xform_4() -----
#
ok 1 - ()
ok 2 - ()'
ok 3 - (()')'
ok 4 - ((()')')'
ok 5 - (()' (()')')'
ok 6 - (A & B)
ok 7 - (A & B)'
ok 8 - (A & B | (C & D)')'
ok 9 - ((A & B)' | (A & C & (A & B & D)'))
ok 10 - ((A | B)' & (C | (D & (E & F)))')'
ok 11 - ((A & B)' | (A & C & (A & Boff' & D | (A & (B' & D)')'))
1..11
ok 12 - no warnings
1..12
[download]

Also note that your new expression is invalid: the number of left and right parentheses isn't the same. I added one more ) to the end.

Walking the string manually:

#!/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)))')'",
                "((A & B)' | (A & C & (A & B & D | (A & (B' & D)')'))"
              ) {
    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();

            if (')' eq substr $calc, $pos - 1, 1) { # Negated parenthe
+ses.
                substr $calc, $last, 0, '!';

            } else {                                # Negated literal.
                substr $calc, $pos - 1, 0, '!';
            }
        }
    }
    print "Given: $given\n";
    print "Calculated: $calc\n";
}
[download]

Writing a parser (no change required, I just changed the whitespace behaviour to make it even easier):

#!/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 operator Expression

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

__DSL__

my $i = 0;
sub concat { $i++; join ' ', @_[ 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)))')'",
                "((A & B)' | (A & C & (A & B & D | (A & (B' & D)')')))
+"
              ) {
    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]

Update: The approach discussed in this reply has a problem. Don't use it. For a fix, see my reply below.

This needs the Perl version 5.10 regex extensions and defined-or operator, the latter not critical. This approach needs extensive testing to be trusted. (Update: Some more testing done with the test cases used by choroba in his reply in your other thread gives me a bit more confidence in this approach, but you must still thoroughly test!)

c:\@Work\Perl\monks>perl -wMstrict -le
"use 5.010;
 ;;
 my $x = q{((A & B)' | (A & C & (A & B & D | (A & (B' & D)')'))};
 print qq{:$x:};
 ;;
 my $parenthetic = qr{ ( [(] (?: [^()]*+ | (?R))* [)] ) }xms;
 my $term        = qr{ ( [[:alpha:]] \w* ) }xms;
 ;;
 1 while $x =~ s{ (?: $parenthetic | $term) \x27 }{ '!' . ($1 // $2) }
+xmsge;
 print qq{:$x:};
"
:((A & B)' | (A & C & (A & B & D | (A & (B' & D)')')):
:(!(A & B) | (A & C & (A & B & D | !(A & !(!B & D)))):
[download]

Update 1:

From the original value of $x printed above, we have to create the following slightly modified expression, like below:

(!(A & B)' | (A & C & (A & B & D | !(A & !(!B & D))))

Update 2:

my $x ='((A & B)\' | (A & C & (A & B & D | (A & (B\' & D)\')\'))';

This thread is a continuation of the discussion in Regex matching and substitution.