matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLogik{NAND} ist vollst. Junkt-Menge
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Logik" - {NAND} ist vollst. Junkt-Menge
{NAND} ist vollst. Junkt-Menge < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

{NAND} ist vollst. Junkt-Menge: Idee, Korrektur
Status: (Frage) überfällig Status 
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!

        
Bezug
{NAND} ist vollst. Junkt-Menge: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                
Bezug
{NAND} ist vollst. Junkt-Menge: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
{NAND} ist vollst. Junkt-Menge: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:20 Di 14.05.2013
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]