äquivalente Formeln < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:16 Sa 28.10.2006 | | Autor: | sorry_lb |
| Aufgabe | a) Zeigen Sie, dass sich jede aussagenlogische Formel in eine äuivalente Formel umformen lässt, die nur den junktor [mm] \odot [/mm] enthält, wobei gilt (bitte tabelle denken):
a b a [mm] \odot [/mm] b
0 0 1
0 1 1
1 0 1
1 1 0
b) Zeigen Sie, dass sich jede aussagenlogische Formel in eine äquivalente Formel umformen lässt, die nur die Junktoren { [mm] \to [/mm] , [mm] \neg} [/mm] enthält.
c) Zeigen Sie, dass sich nicht jede aussagenlogische Formel in eine äquivalente Formel unformen lässt, die nur die Junktoren { [mm] \wedge [/mm] , [mm] \vee [/mm] , [mm] \to [/mm] } enthält. |
zu a) versteh ich die aufgabe nicht oder is das einfach nicht möglich, weil es gibt doch keinen junktor, für den 0 und 0 = 1 und 1 und 1 =0 wird?
zu b) ja aber wie mach ich das denn allgemein, ich mein, ich weiß, dass es so ist, aber ich kann doch jetzt nicht mir irgendeine formel hernehmen, an der das zeigen und gut?!
zu c) analog b obwohl ich hier nur ein gegenbeispiel finden müsste oder?
Danke schonmal, falls mir irgendjemand die erleuchtung bringen kann.
|
|
| |
|
Hallo,
zu a):
Ich glaube, du verstehst die Aufgabe tatsächlich nicht. Hier geht es darum, dass der Junktor vorgegeben wird und du alle anderen notwendigen mit seiner Hilfe darstellen sollst.
Zuerst: Hierbei handelt es sich nach der Tabelle um ein NAND, also ein negiertes UND. Du kannst ja mal diese Tabelle mit der UND-Tabelle vergleichen.
Nun stellt sich die Frage, was sind denn die notwendigen Junktoren? Ich gehe mal davon aus, dass ihr dafür bislang die Menge [mm]\left\{\wedge, \vee, \neg\right\}[/mm] benutzt habt. Diese Menge ist funktional vollständig und das wollen wir nun auch für die Menge [mm]\left\{\odot\right\}[/mm] zeigen:
Wir zeigen, dass wir erzeugen können:
(1) ein [mm] \neg [/mm] mittels:
[mm]\neg x = x \odot x[/mm] (Tabelle -> prüfen)
(2) ein [mm] \wedge [/mm] aus der Defintion von [mm] \odot [/mm] und (1):
[mm]x \wedge y = \neg (x \odot y) = (x \odot y) \odot (x \odot y)[/mm] (Tabelle -> prüfen)
(3) ein [mm] \vee [/mm] aus (1), (2) und de Morgan:
[mm]x \vee y = \neg (\neg x \wedge \neg)[/mm]
[mm]= \neg ( (x \odot x) \wedge (y \odot y) )[/mm]
[mm]= \neg( ( (x \odot x) \odot (y \odot y) ) \odot ( (x \odot x) \odot (y \odot y) ) )[/mm]
[mm]= \left( \left( \left(x \odot x\right) \odot \left(y \odot y\right) \right) \odot \left( \left(x \odot x\right) \odot \left(y \odot y\right) \right) \right) \odot \left( \left( \left(x \odot x\right) \odot \left(y \odot y\right) \right) \odot \left( \left(x \odot x\right) \odot \left(y \odot y\right) \right) \right)
[/mm]
Wir können also [mm] \neg, \wedge [/mm] und [mm] \vee [/mm] nur mit Hilfe von [mm] \odot [/mm] darstellen.
Zu b):
Versuch doch entweder [mm]\left\{\odot\right\}[/mm] oder [mm]\left\{\wedge,\vee,\neg\right\}[/mm] mit den gegebenen Junktoren zu realisieren.
Zu c):
Ja genau: ein Gegenbeispiel reicht.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Sa 28.10.2006 | | Autor: | sorry_lb |
Hab ganz lieben Dank, jetz hab ich erstmal die Aufgabe kapiert. a) hab ich verstanden und an b und c werd ich mich nachher nochmal ransetzen.
Werd sie aber morgen sicherlich nochmal zur korrektur reinsetzen *g
Danke und einen schönen Abend noch.
Liebe Grüße, sorry_lb
|
|
|
|
