Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Äquivalenz zu Horn-Formeln

Äquivalenz zu Horn-Formeln

Schüler Gymnasium, 13. Klassenstufe

Tags: Äquivalenz, Horn-Formel

8mileproof aktiv_icon

21:46 Uhr, 16.04.2012

hallo,

ich muss zeigen, ob die formel

φ = ((X \lor Z) \to (\bar{X} \land \bar{Z})) \land (1 \to X))

wir haben gelernt, dass man das ganz auf 2 wegen machen kann:

1 .)

durch Umformungen zu einer Horn-formeln bringen

2 .)

zwei interpretationen finden, die ein modell darstellen, deren schnitt aber kein modell ist.

also:

ich hab das ganze mal versucht umzuformen. das kam dabei raus:

((X \lor Z) \to (\bar{Y} \land \bar{Z})) \land (1 \to X)) \equiv (\bar{X \lor Z} \lor (\bar{Y} \land \bar{Z}) \land (1 \to X)) \equiv ((\bar{X} \land \bar{Z}) \lor (\bar{Y} \land \bar{Z})) \land (1 \to X)

an dieser stelle, weiß ich nicht mehr wie ich weitermachen kann...kann mir da jmd. weiterhelfen?

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

heitho aktiv_icon

04:26 Uhr, 18.04.2012

Du hast deine Aufgabenstellung halb geschluckt, ist schwer was dazu zu sagen ;-)

Die hintere Implikation kannst du auf jeden Fall noch auflösen, und dann schau nochmal genau auf die Formel drauf und überlege dir, was erfüllt sein muss damit die Formel erfüllt ist.

8mileproof aktiv_icon

17:19 Uhr, 21.03.2013

also nach langer zeit habe ich die aufgabe wieder aufgegriffen und folgendes geschrieben:

((X \lor Z) \to (\bar{Y} \land \bar{Z})) \land (1 \to X)

\equiv ((\bar{X \lor Z}) \lor (\bar{Y} \land \bar{Z})) \land (1 \to X)

\equiv (\bar{Z} \land (\bar{X} \land \bar{Y})) \land (1 \to X)

laut definition ausm Skript ist eine Horn-Formel eine Formel

ψ = \underset{i}{⋀} \underset{i}{⋁} Y_{i, j}

in KNF, wobei

\underset{i}{⋁} Y_{i, j}

HÖCHSTENS ein positives Literal

Y_{i, j}

enthält.

und dass wir oben eben an der stelle

(\bar{X} \land \bar{Y})

kein postives Literal haben, ist doch kein problem, denn man kann auch keins haben. ist ja nur "höchstens" gemeint.

\Rightarrow

ist diese Formel äquivalent zu einer hornformel.

nun habe ich aber weitere solcher formeln gefunden, die ich auch gerne zeigen würde, um zu erfahren, ob ich sie richtig gelöst habe:

X \to (Y \lor Z) \equiv \bar{X} \lor (Y \lor Z) \equiv \bar{\bar{\bar{X} \lor (Y \lor Z)}} \equiv \bar{X \land \bar{X \lor Z}} \equiv \bar{X \land (\bar{Y} \land \bar{Z})} \equiv \bar{X} \lor \bar{\bar{Y} \land \bar{Z}} \equiv \bar{X} \lor (Y \lor Z)

wie zu sehen ist, habe ich mit einer doppelten negation begonnen, ein paar mal DeMorgan angewendet, aber am ende bin ich wieder bei

\bar{X} \lor (Y \lor Z)

gelandet.
und hier haben wir mehr als ein positives Literal und somit ist diese formel nicht äquivalent zu einer horn-formel.
Richtig so?

ii)

(\bar{Z} \to (X \lor Y)) \land (Z \to Y) \equiv (Z \lor (X \lor Y)) \land (\bar{Z} \lor Y)

hier habe ich daselbe problem wie oben. mehr als ein posivites literal und somit auch keine horn-formel.
ist das so korrekt? oder gibt es da einen anderen umwandlungs-trick, was ich anwenden kann.

würde mich über hilfen freuen....xD

heitho aktiv_icon

17:36 Uhr, 21.03.2013

zum ersten Punkt) Du musst immernoch die letzte Implikation auflösen, sonst kannst du das so pauschal nicht sagen! Es dürfen als Operanden, wie in deinem Skript ja nun auch steht, nur Konjunktionen und Disjunktionen vorkommen.

Allgemein:
Zudem ist es für dein ganzes Vorhaben hilfreich zu überlegen, wann man Klammern weglassen kann. Weil entweder man kann sie weglassen oder man kann "ausmultiplizieren".

für i) da ist dir die Negation vom X beim Auflösen der Impliktion verloren gegangen. Lass dann einfach die Klammern weg, und du siehst, dass es nicht äquivalent zu einer Horn-Formel sein kann

8mileproof aktiv_icon

18:54 Uhr, 28.03.2013

ah, ok...

also wenn ich ganz oben die letzte implikation auflöse, so habe ich:

((X \lor Z) \to (\bar{Y} \lor \bar{Z})) \land (1 \to X) \equiv ...

\equiv (\bar{Z} \land (\bar{X} \land \bar{Y})) \land (\bar{1} \lor X) \equiv (\bar{Z} \land (\bar{X} \land \bar{Y})) \land (0 \lor X)

die letzte klammer hat nur ein pos. literal. also horn formel.

zu

i)

da habe ich die klammern aufgelöst und erhalte im letzten schritt:

\bar{X} \lor Y \lor X

somit habe ich mehr als ein positives Literal. also keine horn-formel.

zu ii)

hier habe ich die innere klammer der 1. klammer weggelassen und dann kam zum schluss folgendes raus:

(Z \lor X \lor Y) \land (\bar{Z} \lor Y)

somit habe ich mehr als ein positives Literal. also wieder keine horn-formel.

ist das so korrekt?

heitho aktiv_icon

19:06 Uhr, 28.03.2013

i) stimmt noch nicht, du kannst

X \lor \neg X

noch zusammenfassen.

8mileproof aktiv_icon

15:38 Uhr, 29.03.2013

kann ich das

X \lor \bar{X}

zu einer 1 zusammenfassen? denn egal wie ich das

X

belege, kommt am ende immer wahr raus, also 1.

geht das so?

heitho aktiv_icon

15:42 Uhr, 29.03.2013

japp

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

1084596

993290

	Status: nicht eingeloggt	Noch nicht registriert?