Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Horn-Formel

Horn-Formel

Universität / Fachhochschule

Tags: Horn-Formel

pac89 aktiv_icon

20:06 Uhr, 21.06.2013

hallo, ich muss folgende Aufgabe(s. kleines Bild unten) widerlegen oder zeigen:

meine Lösung:

Diese Aussage hierzu habe ich mit einem Gegenbeispiel widerlegt.
meine Idee hierzu war, dass Horn-Formeln unter Schnitt abgeschlossen sind.

D . h

. Wenn ich zwei Modelle I und I1 habe, die mein

ψ

erfüllen, dann muss auch der Schnitt I1

\cap

I2 mein

ψ

erfüllen.
Also habe ich

ψ

und

φ

wie folgt gewählt:

sei

φ = \bar{Z} \lor \bar{X} \lor Y

(meine Horn-Formel)
sei

ψ = \bar{Z} \lor \bar{X} \lor Y

Wähle Interpretation I1

: Y \mapsto 1, Z \to 1, X \to 0

I1 würde mein beiden Formeln erfüllen.
Also: I1

\mapsto φ

und I1

\mapsto ψ

Somit hätte ich die semantische Folgerungsbeziehung

φ ⊨ ψ

sichergestellt.

nun zeige ich, dass

ψ

nicht äquivalent zu einer horn-formel ist. dazu gebe ich eineweitere Interpretation an:

I2:

X \mapsto 1, Z \mapsto 1, Y \mapsto 0

Es gilt auch I2

⊨ ψ

Aber wenn ich den Schnitt von I1 und I2 bilde erhalte ich:

I1

\cap

: Z \mapsto 1, X \mapsto 0, Y \mapsto 0

Wenn

ψ

zu einer Horn-Formel äquivalent wäre so müsste der Schnitt auch

ψ

erfüllen
Aber der Schnitt erfüllt

ψ

nicht.

\Rightarrow ψ

nicht äqivalent zu einer Horn-Formel. Aussage widerlegt.

Stimmt das so?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1102536

	Status: nicht eingeloggt	Noch nicht registriert?