{NAND} ist vollst. Junkt-Menge < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:21 Mo 06.05.2013 | | Autor: | Argot |
| Aufgabe | | Nehmen Sie an, wir hätten den Junktor ⊼ (NAND), so dass für Formeln A,B Belegungen [mm] \phi [/mm] gilt: [mm] \phi(A [/mm] ⊼ B) = 1 - [mm] min\{\phi(A),\phi(B)\} [/mm] . Zeigen Sie mittels struktureller Induktion, dass die Menge [mm] \{NAND\} [/mm] eine vollständige Junktorenmenge ist. |
Hallo matheraum.de!
Ich habe bei der angegebenen Aufgabe Startschwierigkeiten. Zur Zeit existieren zwei grobe Ideen, mit welchen ich aber nicht weiterkomme. Das Ziel ist eine strukturelle Induktion.
Frage Liege ich vollständig falsch oder ist einer der beiden Ansätze eine Grundlage für den gesuchten Beweis? Wie kann ich von den bekannten Formeln A,B auf unbekannte Formeln schließen, dass diese Äquivalente haben in [mm] F(\{NAND\})? [/mm] Ist der zweite Ansatz zw. [mm] \phi(A [/mm] NAND A) überhaupt relevant für den Beweis?
Hilfs-Def. NAND Hier wird nun NAND statt ⊼ verwendet, da dieses Zeichen sich nicht immer darstellen lässt (bestimmt nutze ich es nur falsch).
Nun zu den bekannten Definitionen:
Def. F(M) Für eine Menge M von Junktoren sei F(M) die Menge der Formeln, in denen als Junktoren nur solche aus M vorkommen.
Def. Vollständiger Junktor Eine Menge M von Junktoren, heißt vollständig, wenn es für jede Formel A eine äquivalente Formel B [mm] \in [/mm] F(M) gibt.
Konzept/Ziel Gezeigt werden soll, dass man nur mit NANDs (wie in der Elektronik) jede andere logische Formel nachbilden kann. Hierfür muss dann mit der Definition der vollständigen Junktoren gearbeitet werden. Die Definition habe ich soweit verstanden.
Ansatz 1 (IA) Seien Formeln A,B beide aus der Formelmenge [mm] F(\{NAND\}) [/mm] und äquivalent (oder stärker: A [mm] \in F(\{NAND\}) [/mm] mit A = B).
Für A ist [mm] \{NAND\} [/mm] eine vollständige Junktorenmenge, da es eine äquivalente Formel B [mm] \in F(\{NAND\}) [/mm] gibt.
(IV) Es existiert eine Formel A, welche ein Äquivalent B in der Formelmenge [mm] F(\{NAND\}) [/mm] hat.
(IS) Hier komme ich nicht weiter, da ein weiteres A nicht in [mm] F(\{NAND\}) [/mm] sein muss und ich den Weg zu einem Element in dieser Menge nicht sehe.
Daher kann ich keine Brücke schlagen um diesen Ansatz weiterzuführen.
Ansatz 2 (IA) Seien Formeln A,B [mm] \in F(\{NAND\}) [/mm] und A=B (insb. äquivalent).
Dann ist [mm] \phi(A [/mm] NAND B) = 1 - [mm] min\{\phi(A),\phi(B)\} [/mm] kürzbar durch die Äquivalenz bzw. Gleichheit A=B zu: [mm] \phi(A [/mm] NAND A) = 1 - [mm] min\{\phi(A),\phi(A)\} [/mm] = 1 - [mm] \phi(A). [/mm] Das Ergebnis von [mm] \phi(A [/mm] NAND A) ist nun immer [mm] \neg [/mm] A.
Vielen Dank für das Lesen!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:59 Mo 06.05.2013 | | Autor: | Teufel |
Hi!
Ich habe nicht so viel Ahnung von struktureller Induktion, aber ich würde das einfach so zeigen, dass man AND und NOT mit NANDS nachbauen kann. Denn jede boolsche Formel kann man mit AND, NOT und OR beschreiben. Habt ihr das mal gezeigt? OR kann man schon durch AND und NOT darstellen (a OR b = NOT ((NOT A) AND (NOT B))) und den Rest musst du dann noch zeigen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mo 06.05.2013 | | Autor: | Argot |
Danke für die Antwort.
Das ist eine gute Idee, aber bestimmt nicht die gewünschte Lösung. Gezeigt wurde das in dieser Vorlesung nicht (aber in einer anderen, welche aber keine Grundlage für die Vorlesung darstellt). Bis jetzt waren alle Aufgaben und Lösungen nur theoretischer Natur.
Es gibt bestimmt einen Trick, welchen man mit den Definitionen anstellen kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Di 14.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
