Python 3, 487 bytes

Not very golfed right now, but I figure I'd get the ball rolling with an answer. Try it here, g() is the main function.

import re, itertools
def g(i):
 y=re.sub(r'\W','',''.join(set(i)).upper())
 l=i.split(' ')
 def e(s):
  d={'v':'+','^':'*','<->':'==','->':'<=','-':'not '}
  def f(a,b):
   for v,w in zip(a,b):
    exec(v+'='+w)
   return eval(re.compile('v|\\^|<->|->|-').sub(lambda x:d[x.group()],s))
  return [c for c in itertools.product("01",repeat=len(y)) if f(y,c)]
 for n in reversed(range(len(l)+1)):
  for q in itertools.combinations(l,n):
   if e('('+')^('.join(q)+')'):
    return ' '.join(q)