FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI Aufgabe 3.3

FGI Aufgabe 3.3 2008-04-25 13:46
Anonymer User
Kann mir mal bitte jemand die Aufgabe 3.3 von Blatt 3 erklären? Ich habe das Gefühl, da fehlt was.. Hoffe jemand von euch hat die Aufgabe verstanden.

http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe08/aufg03.pdf

RE: FGI Aufgabe 3.3 2008-04-25 13:47
Anonymer User
Kann mir mal bitte jemand die Aufgabe 3.3 von Blatt 3 erklären? Ich habe das Gefühl, da fehlt was.. Hoffe jemand von euch hat die Aufgabe verstanden.

http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe08/aufg03.pdf

Achja, speziell gehts mir um das auf der rechten Seite der Biimplikation. Wenn die Aj mit Oder verknüpft werden, wozu wird dann unter dem UND ein i angegeben und wozu ist das große UND dann überhaupt da??

RE: FGI Aufgabe 3.3 2008-04-25 14:52
Wulf
Ich mach einfach mal ein Beispiel, hoffe das passt so:

Für n=5 ist die Formel ausgeschrieben:

( A_1 \wedge A_2 ) \vee
( A_1 \wedge A_3 ) \vee
( A_1 \wedge A_4 ) \vee
( A_1 \wedge A_5 ) \vee
( A_2 \wedge A_3 ) \vee
( A_2 \wedge A_4 ) \vee
( A_2 \wedge A_5 ) \vee
( A_3 \wedge A_4 ) \vee
( A_3 \wedge A_5 ) \vee
( A_4 \wedge A_5 )
\Leftrightarrow
( A_2 \vee A_3 \vee A_4 \vee A_5 ) \wedge
( A_1 \vee A_3 \vee A_4 \vee A_5 ) \wedge
( A_1 \vee A_2 \vee A_4 \vee A_5 ) \wedge
( A_1 \vee A_2 \vee A_3 \vee A_5 ) \wedge
( A_1 \vee A_2 \vee A_3 \vee A_4 )

(\vee = oder, \wedge = und, \Leftrightarrow = Biimplikation)

RE: FGI Aufgabe 3.3 2008-04-25 15:41
Anonymer User
Danke erstmal. Nun verstehe ich den Formelaufbau denke ich, aber wie soll man denn für alle n >=2 zeigen, dass es eine Tautologie ist? Ich steh gerad irgendwie aufm Schlauch..

RE: FGI Aufgabe 3.3 2008-04-25 17:18
Wulf
Du kennst verschiedene Gesetze, also Zeug wie deMorgan, Distributiv, Kommutativ, Assoziativ, usw., damit dürfte sich die Aufgabe lösen lassen.
Die richtige Idee hab ich schon, aber nun frag ich mich, wie man das *formal* aufschreibt :-)

RE: FGI Aufgabe 3.3 2008-04-27 19:36
MaNeY
Das einizge was sich anwenden lässt ist doch die Distrubitivität. Intuitiv kann man das viel einfacher begründen.
Was sind denn die Bedingungen, dass die Biimplikation wahr wird? Danach brauch man nur 3 Fälle unterscheiden…

RE: FGI Aufgabe 3.3 2008-04-27 22:04
Anonymer User
Unser Übungsgruppenleiter meinte, dass wäre eine Aufgabe für vollständige Induktion….

RE: FGI Aufgabe 3.3 2008-04-28 09:29
Lehrkraft
Von vollständiger Induktion (über den Parameter n im Term) würde ich bei dieser Aufgabe abraten. Ich will nicht ausschließen, dass man damit auch zum Ziel kommt, aber ich glaube, dass die Argumentation, warum das Hinzufügen bestimmter Teilterme beim Schritt von n auf n+1 der Tautologieeigenschaft nicht schädlich ist, nicht einfacher ist als die direkte Argumentation, warum der Term für beliebiges n eine Tautologie ist.

Der Vorschlag von MaNeY hingegen scheint mir eher praktikabel zu sein. Man schaue sich den Wahrheitswertverlauf der Biimplikation an und überlege sich, wie eine Belegung aussehen muss, die die linke Seite wahr bzw. falsch werden lässt, und welchen Wahrheitswert unter so einer Belegung die rechte Seite annehmen wird. Oder man argumentiert von rechts nach links. Oder man mischt beide Richtungen. Hauptsache, man deckt alle für die Biimplikation relevanten Fälle ab.

RE: FGI Aufgabe 3.3 2008-04-28 20:36
Julian F.
Ich dachte, Antworten im Stile "Man kann sehen, dass…" sind nicht gerne gesehen, wenn in der Aufgabenstelle nicht explizit von informeller Begründung die Rede ist? Dem Aufwand pro Bewertungspunkt würde so eine Begründung an dieser Stelle natürlich am ehesten entsprechen. Meine Gruppe hatte eine solche Begründung dann auch schnell geklärt, ist aber dazu übergegangen, auf Biegen und Brechen vollständige Induktion anzuwenden oder die Formel umzuformen, so dass man die Tautologie-Eigenschaft direkt ablesen kann. Unsere abgegebene Fassung ist nun eine Mischung aus allem geworden.

Problem: Woran erkenne ich, wann ich etwas "sehen" darf und wann ich "formal" begründen muss? Sind die Bewertungspunkte ein guter Anhaltspunkt?

RE: FGI Aufgabe 3.3 2008-04-29 00:10
Wulf
Mein Ansatz wäre gewesen, die rechte Seite wie folgt umzuformen:
1. Die Formel in die ausgeschriebene Form bringen.
2. Distributivität anwenden. Nun haben wir eine Disjunktion von Konjunktionen.
3. Die Operanden der Konjunktionen mit der Kommutativität aufsteigend ordnen und doppelte Operanden wegkürzen:
"A_4 \wedge A_2 \wedge A_5 \wedge A_2 \wedge A_1" –> "A_1 \wedge A_2 \wedge A_4 \wedge A_5"
4. Zu jeder Konjunktion mit mehr als zwei Operanden gibt es mindestens eine mit genau zwei Elementen, welche in der größeren auch enthalten sind. Z. B. "A_2 \wedge A_5". Die größere kann man streichen.
5. Übrig bleibt genau die linke Seite der Gleichung.

Zum Teil braucht man da sicher paar kleinere Teilbeweise. Unschön ist auch, dass ich hier nicht die Ursprungsformel umstelle. Aber ich denke mal, dass dies trotzdem als Lösung akzeptiert würde.

Andere Möglichkeit: Man kann für beide Seiten recht einfach zeigen (beweisen??), dass die Formel genau dann wahr ist, wenn mindestens zwei der Atome wahr sind. Links sieht man es sofort, rechts mit ein wenig hingucken.

RE: FGI Aufgabe 3.3 2008-04-29 14:23
Lehrkraft
Es gibt deutlich mehr formale Beweistechniken als nur vollständige Induktion. Es gibt auch zu jeder Aufgabe mehr als eine mögliche Lösung. Die beiden von Wulf vorgeschlagenen Varianten demonstrieren das. Beide können formal korrekt durchgeführt werden:

Zur Gleichungsumstellung: Zu beachten ist, dass die Formel in parametrisierter Form gegeben ist, das Umformen muss also mit entsprechend erweiterten Regeln geschehen. Es gibt in den Folienkopien einen Satz, der einen Zusammenhang zwischen Biimplikation und Äquivalenz herstellt. Ein Verweis darauf rundet diese Lösungsvariante ab.

Zur Argumentation über den Wahrheitswert der Formeln, wenn genau zwei Atome wahr sind: In den Folienkopien werden die Semantiken von Konjunktion, Disjunktion und Biimplikation über Wahrheitswertverläufe definiert. Genau auf diese Definitionen kann man sich bei einer formalen Argumentation beziehen. Zusammen mit einer Fallunterscheidung über mögliche Belegungen (deren Vollständigkeit präzise begründet werden sollte) ist der formal korrekte Beweis fertig. Siehe Musterlösung, die folgt genau diesem Weg.