+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Diplom Informatik ( /forumdisplay.php?fid=114 )
+--- Forum: Unterbereich Grundstudium ( /forumdisplay.php?fid=123 )
+---- Forum: Formale Informatik ( /forumdisplay.php?fid=16 )
+---- Thema: F1 - Aufgabenzettel 5 ( /showthread.php?tid=7153 )
F1 - Aufgabenzettel 5 - MoKrates - 11.11.2002 19:21
Upps:
@Bjorn42: ich hatte nen Bug hier. Als Morpheus Nachricht erschien nur die Ueberschrift. @Morpheus: Sorry fuer die harsche Antwort, war dem Bug gedankt.
Eine Junktorenbasis ist die Menge aller Junktoren, die benutzt/benutzen darfst. Normalerweise also: B1={Not, v, ^, ->, <-> }
Ueber die Junktorenbasis B2={ NAND } kannst du zu jeder Formel, die auf B1 basiert, eine Aequivalente Formel konstruieren. Das musst Du ueber die Strukturelle Induktion zeigen.
Ungefaehr so: ('==': aequivalenz, []: indizierung)
Anfang:
Sei F[B1] atomar.
F[B1] == F[B2].
Annahme:
Seien F[B1] und G[B1] Formeln, und es gelte:
(F[B1] == F[B2]) und (G[B1] == G[B2]).
Schritt:
Fuer jede Formeln F[B1] und G[B1] gilt:
not(F[B1]) == (F[B2] NAND F[B2]).
F[B1] ^ G[B1] == not(F[B2] NAND G[B2]) ==
((F[B2] NAND G[B2]) NAND (F[B2] NAND G[B2]))
(Beachte: NAND ist nicht assoziativ, Klammern somit notwendig!)
Die anderen Junktoren aus B1 analog.
MoKrates
Re: F1 - Aufgabenzettel 5 - Morpheus - 11.11.2002 19:24
Ich hab schwierigkeiten die 2. Aufgabe zu lösen:
Was ist überhaupt eine vollständige Junktorenbasis???
Und muss man die Aufgabe per induktion beweisen?
Hier die Aufgabe:
Beweisen Sie das der Peirce Pfeil NOR eine vollständige Junktorenbasis ist.
Re: F1 - Aufgabenzettel 5 - Morpheus - 11.11.2002 20:33
np MoKrates ;)
danke für deine hilfe man :)
Re: F1 - Aufgabenzettel 5 - Morpheus - 11.11.2002 23:09
Ich brauch doch nochma hilfe MoKrates,
notFB1
FB1 /\ GB1
FB1 \/ GB1
FB1 -> GB1
FB1 <-> GB1
wie find ich raus was das für FB2 und GB2 macht, das steht nirgendwo im skript. Und um ehrlich zu sein bin ich nach reichler Betrachtung immer noch nich dahinter gekommen wie du das für NAND rausgerechnet hast...
Re: F1 - Aufgabenzettel 5 - MoKrates - 12.11.2002 00:05
Rauskriegen kannst Du das ueber Wahrheitstafeln. Du bastelst Dir ne Wahrheitstafel fuer NAND, und fuer den gesuchten Junktor. Dann bastelst Du irgendwie auf gut Glueck ne Formel aus Fs, Gs und NANDs und schaust, ob das fuer den gesuchten Junktor hinkommt.
(A NAND B) == not(A ^ B) (Vorraussetzung)
'Not' ist trivial:
A ^ A == A daher not(A) == (A NAND A)
'^' koennen wir durch eine weitere Verneinung darstellen (wie im Vorposting gemacht)
'v'... ist: (not(A) NAND not(B)) == (A NAND A) NAND (B NAND B)
Dann hast Du ^, v, und not(). Wenn Du willst kannst Du jetzt aufs Skript verweisen (weiss nicht, was der Uebungsleiter davon halten wuerde), oder du kannst jetzt mithilfe des Skripts, und den angegebenen Regeln, wie Du -> und <-> ueber ^, v, und not() darstellen kannst, und ueber Termumformungen auch noch diese ausschliesslich ueber NAND darstellen.
Uebrigens: Wenn Du etwas beweisen willst, ist es unerheblich, wie Du auf die Idee gekommen bist, dass eine Regel gelten koennte. *Dass* die Regeln gelten, kannst Du aber ganz leicht ueber Wahrheitstafeln mit jeweils 3 Spalten und 4 Zeilen belegen.
MoKrates
Re: F1 - Aufgabenzettel 5 - MoKrates - 12.11.2002 00:32
Upps, mir faellt grad auf, Du hattest ja nach B2={ NOR } gefragt... Geht aber alles analog:
not(A) == (A NOR A)
(A v B) == not(A NOR B) == ((A NOR B) NOR (A NOR B))
(A ^ B) == (not(A) NOR not(B)) == ((A NOR A) NOR (B NOR B))
MoKrates
Re: F1 - Aufgabenzettel 5 - Slater - 12.11.2002 00:57
notFB1
FB1 /\ GB1
FB1 \/ GB1
FB1 -> GB1
FB1 <-> GB1
wie find ich raus was das für FB2 und GB2 macht, das steht nirgendwo im skript. Und um ehrlich zu sein bin ich nach reichler Betrachtung immer noch nich dahinter gekommen wie du das für NAND rausgerechnet hast...
das kann man entweder wie ein computer machen, also stundenlang eine menge der möglichen kombinationen aufschreiben und immer gucken ob es äquivatent ist (gleiche wahrheitstafelbelegung)
oder halt bisschen nachdenken, das ist nicht so leicht zu beschreiben,
was haben wird denn NOR, praktisch so was wie 'not(F1 or F2)',
jetzt wollen wir erstmal das einfache not(A) damit ausdrücken, da wir eh ein NOR verwenden müssen (nix anderes da), müsste das darin in der klammer einfach A ergeben, hmm ja wie wärs mit 'A or A', oh klappt, fertig
A und B, hmm, da sollte man bisschen drüber nachdenken was das wohl ist (oder alternativ mal die passende wahrheitstafel anschauen), es ist A und B wenn keiner der beiden fälle zutrifft: not(A) oder not(B),
also kann man schon mal sagen A und B == not (not(A) or not(b)), wie schön das sind 2 bekannte not() und ein NOR drumherum, also fertig,
evetuell die einfachen not() noch ersetzten durch NOR's wie oben ja schon erkannt
A oder B, geht durch umformen wieder ähnlich, diese formel gilt genau dann, wenn nicht gilt: not(A) und not(B), also not(not(A) und not(B)),
und kennen wir schon, einfaches not kennen wir, also nur noch einsetzen
A => B, ist zufälligerweise not(A) oder B, das weiss man, überlegt man sich spontan wenn man's brauch oder schaut in eine wahrheitstafel wenn einem nix einfällt, not und oder sind bekannt, fertig
A <=> B, ist (A und B) oder (not(A) und not(B)), dito
Re: F1 - Aufgabenzettel 5 - Anonymer User - 16.11.2002 12:35
Kannst sein, daß die endgültige Form für A <-> B ein bissl länger is ? :)
Re: F1 - Aufgabenzettel 5 - Slater - 16.11.2002 12:48
kann sein, da "(A und B) oder (not(A) und not(B))" nicht die engültige form ist, da sie nicht aus NOR's besteht ;),
aber es steht ja schon da wie man normale und's, oder's und not's ersetzt, also ne reine schreibübung
edit
wenn ich mich nicht vertan habe kommt das raus ;) :
{[(A NOR A) NOR (B NOR B)] NOR (A NOR B)} NOR
{[(A NOR A) NOR (B NOR B)] NOR (A NOR B)}
Re: F1 - Aufgabenzettel 5 - Anonymer User - 17.11.2002 19:55
Also reicht die Wahrheitstafel und ein kurzer Text?
Oder muss man einen vollständigen strukturellen Induktionsbeweis durchführen?
Re: F1 - Aufgabenzettel 5 - RaggaDee - 17.11.2002 19:58
woher wisst ihr das eigentlich alles, wie man die versch. Junktoren ersetzt und so......ich komm gar nich mehr mit...
sind das feste regeln? wo stehen die, oder wie komme ich mit hilfe des aktuellen wissens und des skriptes drauf?
Re: F1 - Aufgabenzettel 5 - Zaphod - 17.11.2002 20:14
Entweder man hat das schon in der Schule gehabt, oder man findet das im Skript (da gibt es so eine Seite, auf der alle Junktoren mit einer Wahrheitstabelle abgebildet sind...), oder man googelt sich das. Als Student muss man eben auch lernen, wie man was vernünftig erklärt bekommt, wenn es einem nicht von vorn herein erklärt wird.
->zumindest das hat man bei DPF gelernt
Re: F1 - Aufgabenzettel 5 - Slater - 17.11.2002 20:21
Oder muss man einen vollständigen strukturellen Induktionsbeweis durchführen?
hmm für die NOR-Geschichte?, Induktionsbeweis nach Schema F, wie im Skript sicher ein Beispiel steht, ich nehm mal an, das man da ein bisschen abkürzen kann, so wie ich das gemacht habe (also wenn 'not', 'und', 'oder' schon gezeigt sind, führt man <-> einfach auf die 'not', 'und', 'oder' zurück und damit reicht das), kann ich aber weder 100% beurteilen noch erinnern,
wahrheitstafel ist sehr unschön, zumal du trotzdem die behauptung für beliebige formeln beweisen sollst, die schreibarbeit wird da nicht weniger um die tafeln herum,
so wie Mokrates es am anfang geschrieben hat,
und ALLEIN ZUR BEGRÜNDUNG find ich einen satz wie
-------------
'Not' ist trivial:
A ^ A == A daher not(A) == not(A ^ A) == A NOR A
------------
kürzer als ne wahrheitstafel..
sind das feste regeln? wo stehen die, oder wie komme ich mit hilfe des aktuellen wissens und des skriptes drauf?
für die wenigen junktoren, 'not', 'und', 'oder', ->, <->,
gibts ja nunmal nur 5 wahrheitstafeln, wobei man sie sich mit 10 sec nachdenken auch selber hinschreiben kann, die bedeutung der junktoren sollte man ja wissen...,
wurde auch lang und breit und garantiert mit wahrheitstafel im skript verewigt,
und so manche weitere (FESTE) wichtige umformungsregeln (etwa eines der gesetze von de morgan: 'not(A und B) <-> (not(A) oder not(B))' ) für die einfachen junktoren lernt man im laufe der zeit, bzw. schaut in die kleine formelsammlung im skript
was ein NOR ist, steht ja praktisch da, ist NOT OR,
was ein 'struktureller Induktionsbeweis' ist, steht auch im skript, lernt man nach ein paar mal anwenden, und vergisst man auch wieder,
blah blah, äh was wolltest noch mal wissen? ;)