funktional vollständig

Vorlesungen, Seminare und Praktika aus dem Bereich Theoretische Informatik (Abkürzungen)
Lectures, seminars and labs from the area Theoretical Foundations (Abbreviations)

funktional vollständig

Beitragvon guguli » 25.07.13 12:40

Hallo zusammen,

Kann mir bitte einer bei dieser Frage helfen.
Sei f elemnt B ³ die durch f(x,y,z) := y, falls x = 0 und z, falls x = 1 definierte boolsche funktion. {f,o,1} it funktional vollständig weil:

negetation X = f(x,1,0)
x und Y = f(x,0,y)

Kann mir einer erklären wie man drauf kommen kann. THX
guguli
 
Beiträge: 7
Registriert: 19.09.10 11:14
Studiengang: Informatik (B.Sc.)
Studiert seit: SS 10
Anwendungsfach: Medizin

Re: funktional vollständig

Beitragvon HE » 25.07.13 16:00

Ich verstehe Deine Frage nicht recht.
Dass Negation und Konjunktion funktional vollständig sind, steht im passendem Skript (z.B. TI oder MaLo).
Wenn man also eine Menge von Funktionen hat und aus denen z.B. Negation und Konjunktion (oder eine beliebige andere funktional vollständige Menge) basteln kann, hat man dann gezeigt, dass diese Menge auch funktional vollständig ist. An welcher Stelle genau ist Dein Verständnisproblem?

Marc
Benutzeravatar
HE
 
Beiträge: 453
Registriert: 09.03.07 12:20
Wohnort: Aachen
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: funktional vollständig

Beitragvon guguli » 26.07.13 11:20

Also die Belegung von f. Was bedeutet denn f (x, 1, 0) ????
guguli
 
Beiträge: 7
Registriert: 19.09.10 11:14
Studiengang: Informatik (B.Sc.)
Studiert seit: SS 10
Anwendungsfach: Medizin

Re: funktional vollständig

Beitragvon HE » 26.07.13 12:08

f(x, 1, 0) ist eine einstellige Funktion, die ein (boolsches) Argument x nimmt und sein Negat zurückgibt. Genauso ist f(x, 0, y) eine zweistellige Funktion mit Parametern x und y, die wahr zurückgibt, genau dann wenn x und y wahr sind.

Marc
Benutzeravatar
HE
 
Beiträge: 453
Registriert: 09.03.07 12:20
Wohnort: Aachen
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: funktional vollständig

Beitragvon guguli » 26.07.13 13:31

ok, und wieso wählt man da noch zusätzlich 0??? Also z.B. für nnegetation X = f(x,1,0), wieso denn 1,0?
guguli
 
Beiträge: 7
Registriert: 19.09.10 11:14
Studiengang: Informatik (B.Sc.)
Studiert seit: SS 10
Anwendungsfach: Medizin

Re: funktional vollständig

Beitragvon AGo » 26.07.13 14:09

Schreib dir mal auf, was für d rauskommt wenn du d = f(a,b,c) für alle möglichen Belegungen von a, b und c berechnest.

Bei so kleinen Funktionen lohnt sich immer ne Wertetabelle wenn man auf den ersten Blick keine Lösung sieht.
Benutzeravatar
AGo
0x41476F
 
Beiträge: 2181
Registriert: 09.09.05 18:21
Wohnort: Awf
Studiengang: Informatik (Dipl.)
Anwendungsfach: BWL


Zurück zu Theoretische Informatik / Theoretical Foundations