F1 - Aufgabenzettel 5
2002-11-11 19:21
MoKrates
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
@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