[MaLo] 2. Ãœbungsblatt

[fw]

würde zu der 5a) sagen: unabhängig, wenn die einzelne formel keine tautologie ist (also nicht aus der leeren menge folgt)

[lebowski]

würde zu der 5a) sagen: unabhängig, wenn die einzelne formel keine tautologie ist (also nicht aus der leeren menge folgt)

stimmt, die leere menge ist ja auch ne tautologie. haste recht.

[Thomas]

Kann mir jemand bei Aufgabe 3 helfen.
Erstmal meine Hinweise fuer a) und b)
a) Obermengen betrachten. (siehe Platzaufgaben 2 Aufgabe 3 c)
b) Stichwoerter sind Tautologie und leere Menge

bei c) und d) weiss ich gar nicht was gemeint ist.
z.B weiss ich gar nicht wie Klammern gesetzt werden sollten.
oder


irgendwelche Tipps waeren super!!
-Thomas

[p0llux]

Was ich da soweit bewiesen habe ist "3c ist falsch" und "3d ist wahr".

Als Klammerung habe ich interpretiert, also die Klammerung jeweils rechts angenommen.

Bei 3c) habe ich erfüllbar gewählt und so, dass es nicht aus abgeleitet werden kann. Damit kann man dann leicht Bespiele und einen Beweis konstruieren.

Bei der 3d) bin ich auf der Definition der semantischen Folgerungsbeziehung rumgeritten für ne halbe Zeile und das wars.

[foobar]

von was für drei möglichkeiten sprichst du?

unerfuellbar, kontingent, tautologie.

[nathan99]

Wie geht man denn Aufgabe 1(b) an?

Man kann doch nur durch ausprobieren rausfinden, ob es da eine äquivalente Hornformel zu gibt, oder?

Wie soll dann der Beweis laufen, wenn es mal keine gibt?

1b (ii) ist Horn-Formel:

(x -> y) n (x -> !z) äquivalent zu (y v z) n (z v !x)
Das ist dann eine Formel in KNF, bei der höchstens ein Literal pro Klausel positiv ist. Fertig?

grüsse

[wyverex]

also ich hab zu allen drei formeln eine äquivalente hornformel gefunden und diese als beispiel hinzuschreiben wird ja wohl ein beweis sein wenn die existenz von einer zu zeigen ist.

[Lukul]

@nathan99:

In den Platzaufgaben wurde es über den Schnitt von Modellen gemacht, also auf A. 1a) zurückgegriffen. Wenn du zwei Modelle findest, deren Schnitt kein Modell mehr ist, dann hast du gezeigt, dass es keine Äquivalenz zu einer Horn-Formel gibt. Ich habs aber selbst nich gemacht, müsste jedoch so zu machen sein!

[nathan99]

Naja, und wenn man 1(a) auch nicht beweisen kann?
(:edit: Egal, das setzt man dann vorraus. Mir jetzt Wurst.)

Possible Spoilers ahead:

1b) i - Kein Horn, Die Interpretationen 1,1,0 geschnitten mit 1,0,1 sind Modelle, aber der Schnitt nicht. Korrekt?

1b) ii - Horn

1b) iii - Lässt sich vereinfachen bis es *ziemlich* kurz ist. Horn.

Richtig, soweit?

[Coolcat]

zu Aufgabe 2)

Und das kauft mir der Lehrstuhl als "Lösung" ab?

Unser Tutor (Mo 12:00, AH II) sagte man solle bei solchen Aufgaben eine kleine Tabelle machen in welchem Durchlauf der Schleife man welche Variablen markiert hat. Also quasi immer die Menge M angeben.

Naja, und wenn man 1(a) auch nicht beweisen kann?

Also normalerweise kann man immer Ergebnisse aus vorhergehenden Aufgaben benutzen. (Sofern man nicht in Aufgabe 1 etwas aus Aufgabe 2 benutzt und in 2 wiederum was aus 1)
Allerdings explizit hat in MaLo keiner was dazu gesagt.

[Pillenfresser]

Mal davon abgesehen, dass man a) nicht braucht, weil alle 3 bei b) HF sind, sollte man a) auch ohne vorherigen Beweis benutzen dürfen.

[Stasik]

bei 5c? ist es nicht nur eine Menge mit einer Formel? und zwar mit der "laengsten" Konjunktion, das problem, es ist quasi ein widerspruch

[belnea]

@nathan

zur 1b)i) aber (1,0,1) ist doch gar kein Modell, oder?
(1->0) ^(1->0)=0^0=0

i) ist auch zu ner HF äquivalent würd ich sagen

[Coolcat]

Aufgabe 4b)
Ich habe es geschafft die unendliche aufsteigende Kette zu beweisen. Ich brauche dazu aber eine unendliche Menge von Aussagevariablen, da in jedem Schritt jeweils eine neue Variable benötigt wird.

Problem: Die Menge der Aussagevariabeln ist endlich? In der Definition (erste Vorlesung) steht:
"feste Menge von Aussagevariablen "
...mich stört das "fest"...

Coolcat

[Coolcat]

Hat sich erledigt:
Im Skript steht:
Meistens wird eine feste, abzählbar unendliche Menge T = { X_0, X_1, X_2, ... } von Aussagenvariabeln zugrundegelegt.