hab da verständnis probs mit der fragestellung der aufgabe 2:

Versuchen Sie für alle möglichen Wahrheitswertverläufe zu den beiden aussagensymbole A und B eine reduzierte hornformel zu finden, die aus den beiden atomaren Formeln A und B gebildet ist. …bla bla bla…

Frage: muss mann nun separat für A und B eine wahrheitswerttabelle formen, und dann einmal für 0 eine hornformel angeben und dann für 1 eine hornformel angeben.(unwahrscheinlich, aba mann weiss nie ;))
Oda muss man alle formeln betrachten die man aus A und B formen kann, und dann für je 0 und 1 eine hornformel angeben??? Meine Frage iss n bissel unklar: wenn ihr nix verstehen, dann bitte bescheid sagen ;)

vollständige aufgabe oder link wär schon recht hilfreich..,
http://www.informatik.uni-hamburg.de/WSV/f1/2002/Aufgaben/Blatt8.pdf

meine interpretation:
für A und B gibt es die üblichen 16 wahrheitsverläufe

A|B|…..
-+-+—————
0|0|0000000011111111
0|1|0000111100001111
1|0|0011001100110011
1|1|0101010101010101

einer davon ist 'A->B', einer 'A' usw.

dann bitte schön für jeden fall eine red. hornformel angeben
für 'A' z.b.: "A" ;)

begründung, warum es beispielsweise für 'A oder B' keine red. hornformel gibt siehe skript 7[ 8 ]

Ich hab mal eine Frage zu Aufgabe 1..

bei der zweiten Formel hab ich das hier raus:

(top ->B) und (top -> I) und ( (I und B) -> E) und ((E und A und D) -> bottom) und ((A und C) -> D) und (A -> bottom) und D -> C)

so.. B und I sind dann schon markiert (nach Folie 7(11) 1.), als nächstes wird E markiert und als letztes C..

und jetzt gibts ja eigentlich kein Vorkommen mehr der Form (A1…An)-> Ai oder (A1…An)-> bottom, wo die A1…An´s bereits markiert wären. Die Formel ist also erfüllbar??

Vielleicht kann mir ja mal jemand sagen, ob das so stimmt oder ob ich was falsch gemacht habe..

Grüsse, R.

C wird doch gar nicht markiert,Formel erfüllbar!

ach so ja richtig.. quatsch da ;)

Also danke Slater erstmal für deine Antwort, aba leider werd ich daraus nich ganz schlau.

Im Skript seite 3-[ 10 ] stehen die 16 möglichen wahrheitsverläufe, wobei ich da schon nicht verstehe welche junktoren die Spalten 1 und 16 repräsentieren. Dann, wie soll ich die antwort gestalten?
16 tabellen machen wo ich zeige das es eine red. Hornformel gibt oda auch nich und dann sagen "wie man sehen kann gibt es (k)eine red. Hornformel"? ( sowie auf seite 7-[ 9 ])

o ja schicke grafik, ist in meinem skript auf 3 [ 12 ], also ist das andere wohl auch bisschen weiter ;)

ich würd die tabelle aufschreiben, und dann

red. hornf. zu (1) = A und nicht(A)
red. hornf. zu (2) = [edit] A und B [end edit] usw.

für die paar formel a la A oder B dann eine begründung WIE auf der entsprechenden skriptseite,
also zum beispiel: keine der 7 möglichen klauseln hat 1 in den ersten 3 zeilen, damit auch keine konjugation davon, damit kann es einen wahrheitverlauf wie den von A oder B nicht geben,
das ganze mit der der wahrheitstabelle wie dort angegeben und begründung wieso es nur die 7 klauseln geben kann,

bei weiteren nicht-hornformeln muss man dann nur wenige weitere kurze sätze schreiben,

denk ich mir alles so..

edit
zur sms, da du keine antworten erlaubst:
ich seh sowas sofort ;)

Hi Leuddde,

bin gerade dabei meine Zeit mit F1 zu vertreiben, hätte da zwei Fragen:


Sind diese Ergebnisse richtig?

red. hornf. zu (15) = not(A) und not(B)
red. hornf. zu (16) = not(A) OR (A)

Gibt es für (10) eine red. hornf.?

Ich würde sagen nein, weil es keine Formel mit höhstens einem positiven Literal zu (10) gibt…

In peace SilentK

red. hornf. zu (15) = not(A) und not(B)

[besser wegeditiert ;) ]
not(A) OR not(B) ist besser

red. hornf. zu (16) = not(A) OR (A)

edit
ist wohl keine reduzierte hornformel
/edit

Gibt es für (10) eine red. hornf.?

Ich würde sagen nein, weil es keine Formel mit höhstens einem positiven Literal zu (10) gibt…

hmm versteh den satz nicht so richtig

(10) ist A <=> B, das kann man entweder versuchen umzuformen,
oder man schaut so, ob man aus den 7 möglichen klauseln eine knf basteln kann, die den gleichen verlauf hat,
das kommt mit (A oder not(B)) und (not(A) oder B) doch ganz gut hin..

Mal eine Frage…ist es nicht so, dass die Werte übereinstimmen müssen? Also die der Belegungen von A und B mit denen, der dazugehörigen Hornformel ?

wie meinst das?
wenn du für eine beliebige formel, zum beispiel A <=> B, eine äquivalente red. hornformel angeben willst, dann muss die natürlich schon äquivalent sein ;), also den gleichen wahrheitswertverlauf haben..

für (2) gibt es keine lösung, oder ?

wie wärs mit A und B ?..

fragt jetzt hier jeder einzelnd? ;)

immerhin hast damit einen fehler in meinem 2. post entdeckt, da stand nämlich schon eine red. hornformel zu (2).., wenn auch falsch bisher ;)

A und B is auch falsch, darf nur ein postives drin sein, sonst keine hornformel

definition hornformel bei mir 7 [2 ]

hornformel: formel in knf aus hornklauseln

hornklausel: z.b. ein positives literal

-> A ist hornklausel, B ist hornklausel

-> A und B ist hornformel

oder warum nicht?

z.b.
hat 1.2. auf den gleichen zettel 2 positive literale..

okay, hab klausel mit formel verwechselt, sorry

ach so ja richtig.. quatsch da ;)

HI ich verstehe noch nicht ganz warum die zweite Formel von Aufgbl8 Nr.1 erfüllbar ist. Man muss doch E,A und D markieren wegen ((E und A und D)-> bottom) und damit ist doch die gesamte Formel unerfüllbar?

HI ich verstehe noch nicht ganz warum die zweite Formel von Aufgbl8 Nr.1 erfüllbar ist. Man muss doch E,A und D markieren wegen ((E und A und D)-> bottom) und damit ist doch die gesamte Formel unerfüllbar?

wieso musst du die markieren?

liess mal den algoritmus nach,
nur WENN E und A und D BEREITS markiert WÄREN, wäre daraufhin die formel unerfüllbar,
aber sie sind es ja zum glück nicht,

markierungsregeln:
Ai markieren, wenn
1. (top -> Ai)
oder 2. ((A1 und … und An) -> Ai) mit A1 bis An bereits markiert

hmm, hast mal die folie 7[ 8] oder da in der nähe gesehen:
"Gib es eine zu A oder B äquivalente Hornformel?"
die hat den gleichen wahrheitsverlauf..,

ausserdem steht da bei (15) extra NAND dran ;), also
not(A und B)
das ist äquivalent zu A oder B

dafür gibts keine hornformel

Slater, A OR B hat einen anderen Wahrheitsverlauf als not(A AND B), die Formeln können nicht Äquivalent sein oder irre ich mich da?


Wäre nicht not(A) OR not(B) nicht eine Hornformel für (15)?


SilentK

NAND = OR.., aua aua [img]http://www.sternenvolk.de/symb/2.gif[/img]

jo der typische zu-schnell-hingeschrieben-fall, hab ich ja öfters ;)

not(A) OR not(B) is besser

also immer selber nachrechnen was ich so behaupte

Ist es richtig das es für die Wahrheitsverläufe [7,8,12,14] keine red. Hornformeln gibt oder lieg ich damit falsch?

zum glück ist heute abgabe..

- soll für not stehen

(1) A und -A
(2) A und B
(3) A und -B
(4) A
(5) -A und B
(6) B
(7) /
(8) /
(9) -A und -B
(10) (A oder -B) und (-A oder B)
(11) -B
(12) A oder -B
(13) -A
(14) -A oder B
(15) -A oder -B
(16) / (A oder -A ist nicht reduziert würd ich mal behaupten)

so oder ähnlich

A &#8743; ¬A ist eine reduzierte Hornformel. Allerdings wird B nicht benutzt. (oder A, je nachdem) Nicht, dass es schwer einzufuegen waere, aber ich denke, dann waere es nicht mehr reduziert.

Fuer (1) und (16) wuerde ich allerdings einfach T bzw. _|_

MoKrates

was sagst du zu dem argument, das eine reduzierte hornklausel nur aus verschiedenen literalen bestehen darf, was bei A oder -A nicht der fall ist?

was sagst du zu dem argument, das eine reduzierte hornklausel nur aus verschiedenen literalen bestehen darf, was bei A oder -A nicht der fall ist?

Dazu sage ich, dass A und -A verschiedene Literale sind. Dummerweise folgt aus der Definition (Folie 7 [ 3 ]), dass die Aussagensymbole paarweise verschieden sein muessen - naja, sollte nur ein halber Punkt Abzug sein. *hoff*
<edit>spuddelige auto-smileys</edit>

1. A und &not;A sind verschiedene Literale.
2. Aus der Folie geht nicht eindeutig hervor, dass auch keine gleichen Aussagensymbole verwendet werden duerfen.

Allerdings: Durch die Einfuehrung von \top und \bot koennen wir (A &and; &not; A) und (A &or; &not; A) kuerzer darstellen. Dann waere das die reduzierte Form.

Denke ich mal.

MoKrates

2. Aus der Folie geht nicht eindeutig hervor, dass auch keine gleichen Aussagensymbole verwendet werden duerfen.

Ich glaube mal doch:
"Hornklauseln heissen reduziert, wenn alle A_i in K verschieden sind." (Folie 7 [ 3 ])

Dazu passt dann auch Satz 7.3:
"Fuer jede nicht allgemeingueltige Hornformel existiert eine aequivalente reduzierte Hornformel" (Folie 7 [ 8 ])
Man beachte das _nicht allgemeingueltige_

btw: Dein \top und \bottom sind nach Definition auch keine Hornformeln.

Aeh… Warum sind \top und \bot keine Hornklauseln/formeln?

zur Erinnerung: Def 7.1
Eine Klausel (\top & \bot sind beides Klauseln!) ist eine Hornklausel, falls K hoechstens ein positives Literal enthaelt. In der Tat enthalten diese beiden Klauseln ueberhaupt keine Literale.

Eine Hornformel ist eine Konjunktion von Hornklauseln. Auch das ist gegeben.

MoKrates

nun ja was sind klauseln, so geht das immer weiter ;)

klauseln bestehen nur aus literalen

literale sind atomare formeln oder deren negation

top und bottom sind nach definition keine atomaren formeln..

aber ob A oder -A nun reduziert ist oder nicht, kann ich nicht 100%ig rauslesen, ich tendiere zu nicht, wegen des bereits erwähnten ominösen satzes "für jede nicht allgemeingültige …"

\top & \bot sind beides Klauseln!

Und das steht genau wo?

"\top und \bot sind logische Konstanten, also keine Aussagensymbole." (7 [ 4 ])
"Aussagensymbole und ihre Negationen werden als Literale bezeichnet." (Def. 4.11, 4 [ 18 ])
"Literale und Disjunktionen von Literalen werden als (nicht leere) Klauseln bezeichnet." (Def. 4.12, 4 [ 20 ])

<edit>Ich bin zu langsam…</edit>

nun ja was sind klauseln, so geht das immer weiter ;)

Ein bisschen Wiederholen von Definitionen kann nie schaden, besonders fuer die Leute, die da drueber noch eine Pruefung schreiben muessen :)

Hm. Dann ergibt das aber alles keinen Sinn:
"A und nicht A" laesst sich nicht reduzieren (d.h. eigentlich muesste es doch IIRC reduziert sein!), es sei denn zu \bot. Wenn aber \bot nicht dieselben Eigenschaften hat, wie "A und nicht A", dann sollte man es doch auch nicht als abkuerzende Schreibweise verwenden duerfen, oder?

MoKrates

In meinem Script steht bei 7[img]http://www.sternenvolk.de/symb/3.gif[/img] u.a.:

1. K= -A1 v -A2 v … v -Ai v Ak

Hornklauseln heißen reduziert, wenn alle Ai in K verschieden sind.

Bei -A v A gibt es nur ein Ai, das positive Literal ist Ak.
Daher ist -A v A reduziert.

Wie habt ihr eure Begründungen für die Nichtexistenz von Hornformeln für die WW-Verläufe 7 u. 8. geschrieben?
Nur einen Verweis auf die ominösen Tabellen zu AvB im Script oder hat jemand eine tiefergehende Begründung gefunden?

Gruß,
Jan

"\top und \bot sind logische Konstanten, also keine Aussagensymbole." (7 [ 4 ])
"Aussagensymbole und ihre Negationen werden als Literale bezeichnet." (Def. 4.11, 4 [ 18 ])
"Literale und Disjunktionen von Literalen werden als (nicht leere) Klauseln bezeichnet." (Def. 4.12, 4 [ 20 ])

interessant wie sich die formulierungen ändern, in meinem skript ist von atomaren formeln die rede..

zu top, bottom:

tja, top und bottom sind nur repräsentanten der äquivalenzklassen der tautologien und der unerfüllbarkeitologien
und zwar nur im belegungstechnischen sinne,

mit 'T === A oder -A' (=== soll belegungsäquivalent heissen) kann man ausdrücken, dass 'A oder -A' eine tautologie ist, mehr aber auch nicht, eine äquivalente formel wäre jede andere tautologie, nicht aber der belegungstechnische repräsentant (klingt bisschen komisch, aber auch gar nicht so schlecht ;) )

A oder -A ist nicht mehr zu reduzieren

zu red. hornfomel oder nicht:

weiss ich wie gesagt auch nicht, sieht reduziert aus, aber der ominöse satz.., fragt denn keiner mal in der übung nach?

zu begründung für (7) und (8):

aus A und B gibt es nur 7 reduzierte hornklauseln nach dem beispiel im buch
(AHA, A v -A ist nicht dabei, also wohl auch nicht erlaubt..),
begründung warum nicht mehr: mehr als 2 literale in einer klausel -> 2 gleich also nicht reduziert, die nicht erlaubten unter den 2er-klauseln ('A oder -A' und 'B oder -B') sind ja anscheinend verboten, aber warum?, wer weiss..

nur '-A und -B' hat 1en in der 2. und 3. zeile, aber da '-A und -B' nicht zu (7) oder (8) äquivalent ist, müsste man noch einige der anderen 6 hornklauseln konjunktiv dazunehmen,
da keine von diesen weiten 6 hornklausel 1en in der 2. und 3. zeile hat, kann keine formel entstehen, die zu (7) oder (8) äquivalent ist