Widerlege mich!

22

Einführung

Ihre Mission im Leben ist einfach: Beweisen Sie, dass sich Menschen im Internet irren!
Dazu analysieren Sie normalerweise sorgfältig ihre Aussagen und weisen auf den Widerspruch in ihnen hin.
Es ist an der Zeit, dies zu automatisieren, aber da wir faul sind, möchten wir Menschen das Gegenteil mit dem geringstmöglichen Aufwand beweisen (lesen: kürzester Code).

Spezifikation

Eingang

Ihre Eingabe wird eine Formel in konjunktiver Normalform sein . Für das Format können Sie das folgende Format verwenden oder Ihr eigenes definieren, je nach den Anforderungen Ihrer Sprache (Sie dürfen jedoch nicht mehr im Format als im reinen CNF codieren). Die Testfälle (hier) werden jedoch im folgenden Format bereitgestellt (obwohl es nicht allzu schwierig sein wird, eigene zu generieren).

Ihre Eingabe ist eine Liste einer Liste von Variablen (Sie können sie auch als Zeichenfolgen lesen / Zeichenfolgen benötigen). Die Eingabe ist eine Formel in Conjunctive Normal Form (CNF), die als Satz von Klauseln geschrieben ist und jeweils eine Liste von zwei Listen enthält. Die erste Liste in der Klausel codiert die positiven Literale (Variablen), die zweite Liste die negativen (negierten) Literale (Variablen). Jede Variable in der Klausel wird zusammen ODER-verknüpft und alle Klauseln werden zusammen UND-verknüpft.

Um es klarer zu machen: [[[A,B],[C]],[[C,A],[B]],[[B],[A]]]kann gelesen werden als:
(A OR B OR (NOT C)) AND (C OR A OR (NOT B)) AND (B OR (NOT A))

Ausgabe

Die Ausgabe ist boolesch, z. B. entweder ein Wahrheitswert oder ein falscher Wert.

Was ist zu tun?

Es ist ganz einfach: Prüfen Sie, ob die angegebene Formel erfüllt werden kann, z. B. ob allen Variablen eine Zuordnung von wahr und falsch vorliegt, sodass die Gesamtformel "wahr" ergibt. Ihre Ausgabe ist "wahr", wenn die Formel erfüllt werden kann, und "falsch", wenn dies nicht der Fall ist.
Fun-Fact: Dies ist ein NP-vollständiges Problem im allgemeinen Fall.
Anmerkung: Das Generieren einer Wahrheitstabelle und das Überprüfen, ob ein resultierender Eintrag wahr ist, ist zulässig.

Eckkoffer

Wenn Sie eine leere Liste der 3. Ebene erhalten, enthält diese Klausel keine solche (positive / negative) Variable - eine gültige Eingabe.
Sie können andere Eckfälle undefiniert lassen, wenn Sie möchten.
Sie können auch true bei einer leeren Formel (Liste der ersten Ebene) und false bei einer leeren Klausel (Liste der zweiten Ebene) zurückgeben.

Wer gewinnt?

Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes!
Es gelten selbstverständlich Standardregeln.

Testfälle

[[[P],[Q,R]],[[Q,R],[P]],[[Q],[P,R]]] -> true
[[[],[P]],[[S],[]],[[R],[P]],[[U],[Q]],[[X],[R]],[[Q],[S]],[[],[P,U]],[[W],[Q,U]]] -> true
[[[],[P,Q]],[[Q,P],[]],[[P],[Q]],[[Q],[P]]] -> false
[[[P],[]],[[],[P,S]],[[P,T],[]],[[Q],[R]],[[],[R,S]],[[],[P,Q,R]],[[],[P]]] -> false
optional behavior (not mandatory, may be left undefined):
[] -> true (empty formula)
[[]] -> false (empty clause)
[[[],[]]] -> false (empty clause)
SEJPM
quelle
1
Dürfen wir Input als nehmen (A OR B OR (NOT C)) AND (C OR A OR (NOT B)) AND (B OR (NOT A))?
Adám
1
@ Adám, wie in der Aufforderung angegeben, liegt das Format ganz bei Ihnen, solange es nicht mehr Informationen als die auf einer Liste basierenden codiert. (ZB die Formulierung, wie Sie es gegeben haben, ist voll erlaubt)
SEJPM
@SEJPM Wenn ich die Notation richtig verstehe, sollten meiner Meinung nach der 3. und 4. Testfall true zurückgeben. Ich habe versucht, (P, Q) = (1,1) und (P, Q, R, S, T) = (0,0,0,0,0) zu ersetzen und habe beide als wahr befunden, also sollte es mindestens eine geben Fall, in dem der Ausdruck wahr ist.
Busukxuan
@busukxuan, ich bin mir zu 100% sicher, dass der dritte und vierte falsch sind. Zu 3): Dies ist {{P,Q},{P,!Q},{!P,Q},{!P,!Q}}(nicht in dieser Reihenfolge), was leicht gezeigt werden kann, ein Widerspruch. Zu 4): Dies ist ein trivialer Widerspruch, da dies P AND ... AND (NOT P)offensichtlich für keinen Wert von P.
SEJPM 30.06.16
2
Komisch, wie kürzerer Code tatsächlich mehr Aufwand erfordert, um geschrieben zu werden.
user6245072

Antworten:

41

Mathematica, 12 Bytes

SatisfiableQ

Nun, es gibt eine eingebaute ...

Eingabeformat ist And[Or[a, b, Not[c], Not[d]], Or[...], ...]. Dies funktioniert korrekt für leere Unterausdrücke, weil Or[]ist Falseund And[]ist True.

Für den Datensatz ist eine Lösung, die das listenbasierte Format von der Challenge erhält und die Konvertierung selbst durchführt, 44 Bytes, aber das OP hat in einem Kommentar klargestellt, dass jedes Format in Ordnung ist, solange es keine zusätzlichen Informationen codiert:

SatisfiableQ[Or@@Join[#,Not/@#2]&@@@And@@#]&
Martin Ender
quelle
18
Weil Mathematica ...
Undichte Nonne
11
Mathematica hat wirklich eine verrückte Anzahl von eingebauten ._.
TuxCrafting
3
@ TùxCräftîñg In der Tat .
jpmc26
15
Für den Bruchteil einer Sekunde dachte ich, diese Antwort wäre in einem obskuren, gestapelten Esolang geschrieben, in dem die Befehlssequenz S a t i s f i a b l e Qdas Problem zufällig lösen würde. Erst dann klopfte das Leseverständnis an die Tür ...
30.
3

Haskell, 203 200 Bytes

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
g[]>>=s(\x->t)

Diese Herausforderung verdient eine uneingeschränkte Antwort. Probiere es auf ideone aus . Der Algorithmus versucht einfach alle Variablenzuweisungen und prüft, ob eine davon die Formel erfüllt.

Die Eingabe erfolgt in Form von [([],["P","Q"]),(["Q","P"],[]),(["P"],["Q"]),(["Q"],["P"])], obwohl anstelle von Zeichenfolgen jeder Typ mit Gleichheit funktioniert.

Ungolfed-Code:

type Variable   = String
type CNF        = [([Variable], [Variable])]
type Evaluation = (Variable -> Bool)

satisfies :: Evaluation -> CNF -> Bool
satisfies eval [] = True
satisfies eval ((t,f):r) = or(map eval t ++ map (not.eval) f) && satisfies eval r

update :: Evaluation -> Variable -> Bool -> Evaluation
update eval s b var = if var == s then b else eval var

search :: Evaluation -> [Variable] -> CNF -> Bool
search eval [] cnf = False
search eval (v:vars) cnf = satisfies eval cnf || search (update eval v True) vars cnf || search (update eval v False) vars cnf 

getVars :: CNF -> [Variable] -> [Variable]
getVars [] vars = vars
getVars ((t,f):cnf) vars = getVars cnf (vars ++ [v |v<-(t++f), notElem v vars])

isSat :: CNF -> Bool
isSat cnf = search (\x->True) (getVars cnf []) cnf
Laikoni
quelle
1

JavaScript 6, 69B

x=>f=(v,e)=>(e=v.pop())?[0,1].some(t=>f([...v],eval(e+'=t'))):eval(x)

Verwendung:

f('a|b')(['a','b'])
true
l4m2
quelle