Hornformeln Schnitt 2er Modelle

Question

Aufgabe:

Zeige, dass wenn F eine Hornformel ist und A1 und A2 Modelle für F sind, der Schnitt der Modelle wieder ein Modell für F ist.

Der Schnitt ist definiert als: A1 ∩ A2 =Wenn A1(Ai)=A2(Ai)=1 dann 1, sonst 0.


Ansatz/Problem:

Ich weiß was Hornformeln sind, das sind Disjunktionen von Konjunktionen. Wobei in den Klauseln (Konjunktionen) maximal eine positive atomare Formel vorkommen darf. Nur hab ich keine Ahnung wie ich weiter vorgehen soll.

Answer 1

Antwort mit KI erzeugt

Hornformeln und Modellschnitt

Um den Beweis zu führen, dass der Schnitt zweier Modelle $A_1$ und $A_2$ einer Hornformel $F$ wiederum ein Modell für $F$ ist, müssen wir uns zunächst klar machen, was Hornformeln, Modelle und deren Schnitt bedeuten.

Hornformeln

Hornformeln sind eine spezielle Klasse von booleschen Formeln, die in der konjunktiven Normalform (KNF) sind, wobei jede Klausel höchstens eine positive Literal enthält. Eine Klausel ist eine Disjunktion von Literalen (atomare Aussagen oder deren Negation). In der Praxis bedeutet dies, dass eine Hornklausel entweder eine reine Negationsklausel (nur negative Literale), eine Implikationsklausel (genau eine positive Literal, möglicherweise mit mehreren negativen Literalen) oder eine Faktenklausel (genau eine positive Literal, ohne negative Literale) ist.

Beispiele für Hornklauseln:
- $(\neg x \vee \neg y \vee z)$ ist eine Hornklausel ($z$ ist das einzige positive Literal).
- $(\neg x)$ ist auch eine Hornklausel (nur ein negatives Literal, keine positiven).
- $z$ ist ebenfalls eine Hornklausel (genau ein positives Literal, keine negativen).

Modelle und ihr Schnitt

Ein Modell einer booleschen Formel ist eine Belegung ihrer Variablen mit Wahrheitswerten ($0$ für falsch und $1$ für wahr), so dass die gesamte Formel wahr ($1$) wird.

Der Schnitt zweier Modelle $A_1$ und $A_2$ für eine Formel $F$ ist definiert durch die Belegung, bei der alle Variablen, die in beiden Modellen den Wert $1$ haben, auch im Schnittmodell den Wert $1$ erhalten. Variablen, die nicht in beiden Modellen den Wert $1$ haben, erhalten im Schnittmodell den Wert $0$.

Beweisansatz

Zu zeigen ist, dass wenn $A_1$ und $A_2$ Modelle für eine Hornformel $F$ sind, dann ist auch $A_1 \cap A_2$ ein Modell für $F$.

1. Betrachte eine beliebige Hornklausel $K$ von $F$:
- Wenn $K$ eine reine Negationsklausel ist ($K = \neg x_1 \vee \neg x_2 \vee \ldots \vee \neg x_n$), dann ist $K$ in jedem Modell wahr, da mindestens eine Variable negiert (falsch) sein muss. Der Schnitt $A_1 \cap A_2$ ändert dies nicht, da er höchstens weitere Variablen auf $0$ setzen kann, aber keine auf $1$.

- Wenn $K$ eine Fakten- oder Implikationsklausel ist ($K = x_1 \vee \ldots \vee x_{n-1} \vee y$), mit $y$ als einzigem positivem Literal, dann muss $y$ in mindestens einem der Modelle $A_1$ oder $A_2$ den Wert $1$ haben, damit $K$ erfüllt ist. Wenn $y$ in beiden Modellen $1$ ist, dann ist $y=1$ im Schnittmodell, also $K$ wahr in $A_1 \cap A_2$. Wenn $y$ nur in einem Modell $1$ ist, aber die negativen Literale ($x_1, \ldots, x_{n-1}$) in mindestens einem der Modelle $0$ sind, dann ist $K$ auch ohne $y=1$ erfüllt. Im Schnittmodell können diese negativen Literale nicht von $0$ auf $1$ wechseln, was bedeutet, dass $K$ weiterhin wahr bleibt.

2. Anwendung auf alle Hornklauseln: Da wir festgestellt haben, dass eine beliebige Klausel $K$ von $F$ im Schnittmodell wahr bleibt, und da $F$ eine Konjunktion dieser Klauseln ist, bleibt $F$ insgesamt wahr im Schnittmodell $A_1 \cap A_2$.

Somit haben wir gezeigt, dass wenn $A_1$ und $A_2$ Modelle einer Hornformel $F$ sind, der Schnitt $A_1 \cap A_2$ ebenfalls ein Modell für $F$ ist.