Network Transparent Boolean Logic Evaluator

ECMASCript 6 variation, 213 194 190 189 192 166 chars

try{P=_=>JSON.parse(prompt())
B=P()
f=(a,c)=>a[c?'some':'every'](v=>v.big?[B][+/\W|_/.test(s=v.slice(C=v[0]=='!'))-!s][s]^C:f(v,!c))
q=f(P())}catch(_){q=null}alert(q)

Note: takes Bob's input first, and then Alice's input. This saves us four bytes.

• Checks for syntactically valid JSON since JSON.parse throws if it isn't.
• Since we're already relying on the try-catch for the above, we (ab)use out-of-bounds access to trigger our "failed validation" path when validating the (possibly negated) literals
  • This is accomplished with the [B][...][s] part (thanks, @l4m2! used to use a slightly more verbose construction)
  • The -!s is to catch "" and "!" as invalid literals
  • The C variable holds the "should negate" state, which is accomplished with a "bitwise" XOR (and relies on implicit type coercion)

---

ES5 solution: https://codegolf.stackexchange.com/revisions/19863/8

Ruby, 335 (327?) characters

begin;a,b=*$<;require'json';b=JSON[b];q if a=~/{|}/||!a[?[]||b.any?{|v,x|v=~/[\W_]/||x!=!!x}
l=0;a.gsub!(/\[|\]/){"[{}]"[($&==?]?2:0)+l=1-l]};a.gsub!(/"(!)?([a-z\d]+)"/i){b[$2]^$1}
0 while [[/\[[#{f=!1},\s]*\]/,f],[/{[#{t=!f},\s]*?}/,t],[/\[[\w,\s]*\]/,t],[/{[\w,\s]*}/,f]].any?{|k,v|a.sub!(k){v}}
rescue a=??;end;puts a=~/\W/?"null":a

I've heard you can't parse HTML with Regex, but I've never been told you cannot parse JSON this way, so I tried.

Alice's input is separated from Bob's input by a newline; also, it's assumed that neither input contains newlines itself. This assumption is for I/O purposes only, and is not used later. If I can make an extra assumption that Alice's input contains no whitespace, we can drop 8 characters by removing all \s's on line #3. If we can only assume it contains no whitespace but spaces, we can still replace \s's with the space characters to save 4 characters.

Python 3 (429)

Longer than the other answers, but arguably the most readable so far... :)

import json,sys,re
r,p,m='^!?[a-zA-Z\d]+$',print,re.match
def g(a,b,s):
 if type(a)is str:
  if m(r,a):
   try:return('not '+str(b[a[1:]]))if a[0]=='!'else str(b[a])
   except:return'False'
  raise Exception
 return'('+((' and 'if s else' or ').join(g(x,b,not s)for x in a))+')'
s,j=sys.argv,json.loads
try:
 a,b = j(s[1]),j(s[2]or'{}');
 if all(m(r,x)and x[0]!='!'for x in b):p(str(eval(g(a,b,1))).lower())
except:
 p('null')