Um die Landkarte mit drei Farben R,G,B einzufärben, verwenden wir Variablen R_i,G_i und B_i für i=0,1,2,3. Aufgrund der Nachbarschaften der Länder muss dabei Folgendes gelten, damit benachbarte Länder unterschiedliche Farben erhalten:
(R0->!R1) & (G0->!G1) & (B0->!B1) &
(R0->!R2) & (G0->!G2) & (B0->!B2) &
(R1->!R2) & (G1->!G2) & (B1->!B2) &
(R1->!R3) & (G1->!G3) & (B1->!B3) &
(R2->!R3) & (G2->!G3) & (B2->!B3)
Ferner muss jedes Land eine Farbe bekommen:
(R0 | G0 | B0)
(R1 | G1 | B1) &
(R2 | G2 | B2) &
(R3 | G3 | B3)
und jedes Land soll nicht mehr als eine Farbe bekommen:
(R0 -> !G0 & !B0) & (G0 -> !R0 & !B0) & (B0 -> !R0 & !G0) &
(R1 -> !G1 & !B1) & (G1 -> !R1 & !B1) & (B1 -> !R1 & !G1) &
(R2 -> !G2 & !B2) & (G2 -> !R2 & !B2) & (B2 -> !R2 & !G2) &
(R3 -> !G3 & !B3) & (G3 -> !R3 & !B3) & (B3 -> !R3 & !G3)
Wenn man alle diese Formeln zu einer Konjunktion zusammenfasst, dann entsprechen alle erfüllenden Belegungen den Färbungen der Landkarte. Zum Beispiel kann man einen BDD für diese Formeln bestimmen und daraus alle Färbungen ablesen. Man kann dafür auch andere Formulierungen finden, die zu den obigen Formeln äquivalent sind.
Da die obigen Formeln viele Wiederholungen für alle Länder enthalten, wurde in der Aufgabe nur nach den Einschränkungen für ein Land gefragt, um die Schreibarbeit für alle Länder zu sparen.
