import Control.Applicative -- this is needed for <$> as the ideone Haskell version ist not up-to date
 
main = putStr(show test)
 
t=1<3
e%((t,f):r)=or((e<$>t)++map(not.e)f)&&e%r
e%_=t
u v b e s|s==v=b|t=e s
s e[]c=1<0
s e(v:w)c=e%c||s(u v t e)w c||s(u v(1<0)e)w c
g v[]=v
g v((t,f):r)=g(v++[x|x<-t++f,notElem x v])r
 
isSat = g[]>>=s(\x->t)
 
test = (isSat[(["A","B"],[])] == True) 
 && (isSat[([],["B"]),(["A","B"],[])] == True) 
 && (isSat[([],["B"]),(["B"],[])] == False)
 && (isSat[(["P"],["Q","R"]),(["Q","R"],["P"]),(["Q"],["P","R"])] == True) 
 && (isSat[([],["P"]),(["S"],[]),(["R"],["P"]),(["U"],["Q"]),(["X"],["R"]),(["Q"],["S"]),([],["P","U"]),(["W"],["Q","U"])] == True) 
 && (isSat[([],["P","Q"]),(["Q","P"],[]),(["P"],["Q"]),(["Q"],["P"])] == False) 
 && (isSat[(["P"],[]),([],["P","S"]),(["P","T"],[]),(["Q"],["R"]),([],["R","S"]),([],["P","Q","R"]),([],["P"])] == False)

aW1wb3J0IENvbnRyb2wuQXBwbGljYXRpdmUgLS0gdGhpcyBpcyBuZWVkZWQgZm9yIDwkPiBhcyB0aGUgaWRlb25lIEhhc2tlbGwgdmVyc2lvbiBpc3Qgbm90IHVwLXRvIGRhdGUKCm1haW4gPSBwdXRTdHIoc2hvdyB0ZXN0KQoKdD0xPDMKZSUoKHQsZik6cik9b3IoKGU8JD50KSsrbWFwKG5vdC5lKWYpJiZlJXIKZSVfPXQKdSB2IGIgZSBzfHM9PXY9Ynx0PWUgcwpzIGVbXWM9MTwwCnMgZSh2OncpYz1lJWN8fHModSB2IHQgZSl3IGN8fHModSB2KDE8MCllKXcgYwpnIHZbXT12CmcgdigodCxmKTpyKT1nKHYrK1t4fHg8LXQrK2Ysbm90RWxlbSB4IHZdKXIKCmlzU2F0ID0gZ1tdPj49cyhceC0+dCkKCnRlc3QgPSAoaXNTYXRbKFsiQSIsIkIiXSxbXSldID09IFRydWUpIAogJiYgKGlzU2F0WyhbXSxbIkIiXSksKFsiQSIsIkIiXSxbXSldID09IFRydWUpIAogJiYgKGlzU2F0WyhbXSxbIkIiXSksKFsiQiJdLFtdKV0gPT0gRmFsc2UpCiAmJiAoaXNTYXRbKFsiUCJdLFsiUSIsIlIiXSksKFsiUSIsIlIiXSxbIlAiXSksKFsiUSJdLFsiUCIsIlIiXSldID09IFRydWUpIAogJiYgKGlzU2F0WyhbXSxbIlAiXSksKFsiUyJdLFtdKSwoWyJSIl0sWyJQIl0pLChbIlUiXSxbIlEiXSksKFsiWCJdLFsiUiJdKSwoWyJRIl0sWyJTIl0pLChbXSxbIlAiLCJVIl0pLChbIlciXSxbIlEiLCJVIl0pXSA9PSBUcnVlKSAKICYmIChpc1NhdFsoW10sWyJQIiwiUSJdKSwoWyJRIiwiUCJdLFtdKSwoWyJQIl0sWyJRIl0pLChbIlEiXSxbIlAiXSldID09IEZhbHNlKSAKICYmIChpc1NhdFsoWyJQIl0sW10pLChbXSxbIlAiLCJTIl0pLChbIlAiLCJUIl0sW10pLChbIlEiXSxbIlIiXSksKFtdLFsiUiIsIlMiXSksKFtdLFsiUCIsIlEiLCJSIl0pLChbXSxbIlAiXSldID09IEZhbHNlKQ==