Übungsblatt 3 (Mathematische Logik) (Grädel)

Aus Infostudium Wiki

Inhaltsverzeichnis 1 Aufgabe 1 2 Aufgabe 2 2.1 a) 3 Aufgabe 3 4 Aufgabe 4 5 Aufgabe 5 5.1 (i) 5.2 (ii)

Aufgabe 1

Das n-Damen Problem besteht darin, auf einem -Schachbrett n Damen so aufzustellen, dass sie sich gegenseitig nicht bedrohen. Überlegen Sie sich eine geeignete Modellierung für Aufstellungen und formalisieren Sie dann das Problem in der Aussagenlogik.

Siehe: http://de.wikipedia.org/wiki/Damenproblem

Die Dame kann sich beim Schach vorwärts, rückwärts, seitlich und diagonal bewegen.

Folgende Bedingungen müssen daher erfüllt sein:

• in jeder Spalte darf nur eine Dame stehen
• in jeder Zeile darf nur eine Dame stehen
• in jeder Diagonale darf nur eine Dame stehen.

Aufgabe 2

a)

Weisen Sie mit der Resolutionsmethode nach, dass die folgende Formel unerfüllbar ist:

Aufgabe 3

Aufgabe 4

Aufgabe 5

Das Schubfachprinzip von Dirichlet (1805-1859) ist ein unschätzbares Werkzeug der Kombinatorik. In seiner einfachsten Variante lautet es: Werden n + 1 Perlen auf n Schubfächer verteilt, so gibt es wenigstens ein Schubfach mit mehr als einer Perle.

(i)

Formulieren Sie dieses Prinzip in der Aussagenlogik für einen gegebenen Wert .

Tipp (grob umgangssprachlich):

Jede Perle liegt in mindestens einer Schublade

und

Es gibt keine Schublade, in der mehr als eine Perle liegt

Die obige KNF-Formel ist unerfüllbar, wenn das Schubfachprinzip korrekt ist. (Was natürlich zutrifft...)

(ii)

Zeigen Sie durch Resolution, dass das Prinzip für n = 2 gilt.