Welche booleschen Funktionen sind in 3SAT, aber nicht in SAT?

Ich weiss, dass phi in SAT gilt, denn die Belegung von x_1,...,x_5=00110 erfüllt die Funktion

Ich würde sagen, dass phi außerdem in 3SAT liegen, weil folgendes eine äquivalente Darstellung ist

Frage 1: Darf man einfach die gleichen Literale in den Klauseln haben, d.h. sind derartige Funktionen Element in 3SAT?

Frage 2: Sind alle Funktionen in 3SAT auch in SAT? Gilt das auch umgekehrt?

Answer 1

[Rammstein53]

n-KNF-Formeln haben Klauseln mit höchstens n Literalen, denn die alternative Definition "genau n Literale" stellt keine Verallgemeinerung dar. Das gilt somit auch für die Menge n-SAT.

Klauseln mit identischen Literalen zählen als ein Literal, was aufgrund der obigen Definition aber keine Rolle spielt. Eine Umformung von phi auf Klauseln mit genau 3 Literalen ist deshalb nicht nötig.

phi ist Element von 3-SAT.

3-SAT ist ein Spezialfall von SAT. Aber jedes SAT Problem ist in polynomieller Zeit auf das 3-SAT Problem reduzierbar.

Weiterführende Infos siehe hier:

https://userpages.uni-koblenz.de/~sofronie/logik-ss-2013/slides/aussagenlogik-04.pdf

Comments

[Daubeny]

Nice danke