SAT, CNF, Kodierung

• Geben Sie eine konjunktive Normalform für a↔(b→c) mathend000# an und begründen Sie die Äquivalenz.
• Spezifizieren Sie die Tseitin-Transformation:

  was ist Eingabe E mathend000#, was ist Ausgabe A mathend000#,
  welche Beziehungen bestehen zwischen E mathend000# und A mathend000#.

• Beschreiben Sie eine effiziente SAT-Kodierung für „von den Variablen x₁,…, x_n mathend000# ist eine ungerade Anzahl wahr``.

  Verwenden Sie Hilfsvariablen,
  spezifizieren Sie deren Bedeutung.