$str =~ s/(\w+)'/!$1/g;
$str =~ s/\(([^\)]+)\)'/!($1)/g;
[download]

It you're going to allow (a+b)' — the OP might be happy with only supporting /\w+'/ — you must allow (a*(b+c))' too.

Other than that, there are a few other problems. You don't handle xor, you assume the same precedence and associativity as Perl, and you don't generate a truth table. I presume that's intentional and that you're leaving those as an exercise to the reader, so I'm just documenting what's left to do.

For your viewing pleasure.....

while(<DATA>){
    my ($re, $term, @vars, %vars, $loops);
    s/\*/ && /g;
    s/\+/ || /g;
    s/(\w+)\s*'/!$1/g;
    $re = qr{\((?:(?>[^()]+)|(??{$re}))*\)};  # :-)
    s/($re)\s*'/!$1/g;
    $term = $_;
    @vars = $_ =~ m/(\w+)/g;
    $vars{$_}++ for @vars;
    @vars = sort keys %vars;
    s/(\w+)/\$$1/g;
    printf "\n@vars = $term";
    @vars = map {"\$$_"}@vars;
    $loops .= "for $_ (0..1) {\n" for @vars;
    $loops .= qq{printf "@vars = %d\n", eval;\n};
    $loops .= "}" for @vars;
    do{ no strict 'vars'; eval $loops };
    die "Can't process $term$_\n$@\n" if $@;
}
__DATA__
a*b*!(c)
a'+b'+c'
!(a*b)
b^a
(a^b)'
(a+(a+b))'*c
[download]