[TI] Funktional Vollständig

[mirko]

@maolin: deiner argumentation kann ich nicht wirklich folgen

habe mir aber auch nochmal gedanken, darum gemacht und komme zumindest zum gleichen ergebnis:

funktionale vollständigkeit heißt, ich muss jede funktion realisieren können. habe ich nun eine dreistellige funktion f: B^3 -> B gegeben, die ich realisieren muss, kann ich dies grundsätzlich tun durch

f(x,y,z):=g(h(x,y),z)

für zwei zweistellige funktionen g,h. da ich ja weiß, dass ich jede zweistellige funktion darstellen kann, kann ich g und h entsprechend einsetzen und bekomme meine dreistellige funktion.

ergo kann ich jede dreistellige funktion erzeugen.

per VI könnte man das nun auch für jedes n aus N zeigen

aber ich denke für dich, dede, dürfte die aussage reichen, dass funktionale vollständigkeit unabhängig von der stelligkeit der funktionen ist.

(einschränkung: das gilt (vermutlich) nich für einstellige funktionen - mit (0,id,!,1) lassen sich beliebige einstellige funktionen realisieren (genau genommen sind das alle einstelligen funktionen) - ich finde aber gerade keinen weg, damit eine AND darzustellen...)

[MaoDelinSc]

(einschränkung: das gilt (vermutlich) nich für einstellige funktionen - mit (0,id,!,1) lassen sich beliebige einstellige funktionen realisieren (genau genommen sind das alle einstelligen funktionen) - ich finde aber gerade keinen weg, damit eine AND darzustellen...)

Natürlich gilt das grundsätzlich auch für einstellige Funktionen!
Mit (0,id,!,1) lassen sich zwar beliebige einstellige Funktionen darstellen, aber halt kein AND => (0,id,!,1) ist nicht funktional vollständig.

Funktional vollständig ist ein System ja nur dann, wenn du ALLE darstellen kannst, 1.2.3.4.5,usw stellige...

Wenn du ein System hast und zeigst, dass du alle 2-stelligen damit darstellen kannst, reicht das ja eigentlich auch nicht zum Nachweis der FuVo
In diesem Falle klappt es, weil du damit z.B. NAND nachgewiesen hast und es damit auf ein anderes FuVo reduziert hast.

[mirko]

Funktional vollständig ist ein System ja nur dann, wenn du ALLE darstellen kannst, 1.2.3.4.5,usw stellige...

hm, ok - das macht auch irgendwie mehr sinn - TI ist einfach zu lang her oO

Wenn du ein System hast und zeigst, dass du alle 2-stelligen damit darstellen kannst, reicht das ja eigentlich auch nicht zum Nachweis der FuVo

naja, es gibt aber kein system, dass alle 2-stelligen darstellen kann, nicht aber alle n-stelligen. beweis dazu in meinem letzten beitrag

In diesem Falle klappt es, weil du damit z.B. NAND nachgewiesen hast und es damit auf ein anderes FuVo reduziert hast.

das klappt natürlich bei jedem system, mit dem ich alle zweistelligen funktionen realisieren kann. schließlich ist NAND eine zweistellige funktion