Ausgabedatum: 11. November 2025

Abgabefrist: 25. November 2025

Boolesche Funktionen als GF(2)-Polynome

Alternativ zu DNF und CNF können wir eine Boolesche Funktion $f: \{0,1\}^\rightarrow \{0,1\}$ als großes XOR von Termen darstellen, also zum Beispiel \begin{align*} (x \wedge y) \oplus (x \wedge z) \oplus (x) \end{align*} Da das $\wedge$ der Multiplikation auf $\{0,1\}$ entspricht und $\oplus$ der Addition modulo 2, können wir obiges als Polynom modulo 2 auffassen, also über dem Körper ${\rm GF}(2)$: \begin{align*} xy + xz + x \end{align*}

Sogar noch mehr: jede Variable tritt nur mit Potenz $0$ or $1$ auf; es ist also ein multilineares Polynom.

Aufgabe Stellen Sie die Funktionen $\maj_3(x,y,z)$ und $x_1 \vee x_2 \vee \dots \vee x_n$ als ein multilineares Polynom modulo 2 dar! (Das sind und aus dem Vorlesungsskript).

Aufgabe Sei $p$ ein multilineares GF(2)-Polynom, das mindestens einen Term enthält (also nicht das Nullpolynom $0$ ist). Zeigen Sie, dass es eine Eingabe $b \in \{0,1\}^n$ gibt mit $p(b) \ne 0$. ( aus dem Vorlesungsskript).

SAT als Modellierungssprache

Sei $G = (V,E)$ ein gerichteter Graph. Eine Menge $X \subset V$ von Knoten heißt unabhängig wenn keine zwei Knoten mit einer Kante verbunden sind: \begin{align} \forall u, v \in X: (u,v) \not \in E \ . \end{align} Eine Menge $X$ heißt dominierend, wenn jedes $v \in V$ entweder selbst in $X$ ist oder von einem $x \in X$ "überwacht" wird, also $(x,v) \in V$. Formal: \begin{align} \forall v \in V: v \in X \vee \exists x \in X: (x,v) \in E \ . \end{align}

Unabhängig, aber nicht dominierend: der Knoten $d$ ist nicht überwacht.

Dominierend, aber nicht unabhängig: die Kante $(d,e)$ ist verletzt.

Dominierend und unabhängig.

Wir wollen für einen gegebenen gerichteten Graphen eine unabhängige dominierende Menge finden. Das geht leider nicht immer, wie bereits dieses Beispiel zeigt:

Eine unabhängige Menge kann nur einen Knoten enthalten. Das ist aber nicht genug, um alle Knoten zu dominieren.

Independent Dominating Set ist das Problem, für einen gegebenen gerichteten Graphen zu entscheiden, ob er eine unabhängige dominierende Menge hat.

Aufgabe Modellieren Sie Independent Dominating Set mit SAT! Beschreiben Sie

die Variablen;
die Klauseln; gerne mit der Schreibweise $\bigwedge_{u \in V}$ und so weiter.

Aufgabe Implementieren Sie Ihre Idee in einer Programmiersprache Ihrer Wahl. Wenn dies z.B. Python ist, schreiben Sie zwei Programme

inddomset-to-cnf.py, welches aus einem gerichteten Graphen im ICPC-Format eine CNF im DIMACS-Format erstellt.
assignment-to-vertex-set, welches aus einer erfüllenden Belegung die entsprechende dominierende unabhängige Menge $X$ erstellt.

Hilfsmittel und Vorlagen:

Graph-Editor. Da können Sie gerichtete Graphen zeichnen und mit export icpc ins ICPC-Format exporiteren.
Meine Implementierung von matching-to-cnf.py, welches aus einem ungerichteten Graphen eine CNF erstellt, die Perfect Matching modelliert. Da können Sie sehen, wie man einen Graphen im ICPC-Format einliest.
Meine Implementierung von assignment-to-matching.py, welches aus der erfüllenden Belegung das Matching erstellt. Das Matching ist dann im JSON-Format gegeben und kann im Graph-Editor mit dem Knopf highlight edge set angezeigt werden (wenn der korrekte Graph geladen ist). In Ihrem Falle ist die Lösung ja eine Knotenmenge $X$. Da empfehle ich Ihnen, eine Färbung in dem Format wie dodecahedron-coloring.txt zu erstellen, in Ihrem Falle halt mit zwei Farben (z.B. Schwarz und Rot), wobei dann die roten Knoten die in der unabhängigen dominierenden Menge $X$ sind und die schwarzen die restlichen. Mit dem Knopf import coloring können Sie sich dann diese "Färbung" (in Ihrem Falle eher Knotenmenge anzeigen lassen.)

Hier nochmal mein ganzes Matching-Verzeichnis gezippt: matching.zip.