Logische Signaturen auf funktionale Vollständigkeit prüfen

Question

Hallo Forum,

ich mache eine Übung zur funktionalen Vollständigkeit und weiss nicht, ob ich mit meinen Ergebnis richtig liege.

Die Aufgaben sind folgende:

1) {↛,1} ist funktional vollständig

2) {∧,↔,0} ist funktional vollständig

Ich habe ein Foto von meinen Lösungen gemacht.

Ich habe zwei Fragen:

1) Sind meine Lösungen richtig bzw mein Rechenansatz und

2) Was genau versteht man unter funktionalen Vollständigkeit? Wann tritt es auf und wann nicht?

EDIT:

Ich habe am Anfang den Pfeil versehentlich umgedreht aber trotzdem mit der Definition weiter gerechnet.

Danke im Voraus

Comments

Macht ihr das in Mathematik oder in Theoretischer Informatik?

Es geht wohl um Signaturen. Daher Theoretische Informatik.

Zu deinem 2. Punkt https://www.stacklounge.de/3985/funktionale-signaturen-auf-vollstandigkeit-untersuchen

Elektrotechnisch lautet die Frage: Genügen die Bauteilsorten der Signatur, um jede denkbare Schaltung zu bauen? Wenn ja, ist die Signatur "funktional vollständig".

---

Hallo Lu,

in der Tat besprechen wir diese Aufgaben in technischer Informatik.

Zu dem Punkt: Im anderen Thread steht: "damit eine Signatur funktional vollständig ist reicht es das sie { ¬, ∧ } oder { ¬, ∨ } abilden kann."

Eigentlich habe ich es geschaft in meiner Aufgabe es abzubilden. Was mich aber komplett irreführt ist, dass die 1 bei mir von Anfang an negiert wird (¬1 = 0) da dieser Pfeil ↛  x*¬y ist.

Und da wir schon das ¬x definiert haben mit x↛  ¬1 bzw x↛  0, geht das überall bei jeder Signatur.

Aber es kann an sich nicht funktional vollständig sein, weil die 1 ja im System ist und nicht die 0. Die eins wurde ja am Anfang negiert.

Ich weiss nicht ob mein Gedankengang richtig ist.

Brauche deshalb eure Hilfe.

---

Hier eine Frage, in der auch nur 1 bzw. nur 0 mit in der Signatur war. Allerdings leider mit Texterkennung fast unlesbar geworden. https://www.stacklounge.de/3534/boolesche-funktion-vereinfachung-signatur-vollstandigkeit und der Fragesteller hat damals seine Lösung dann doch nicht gepostet.

Wie ist eigentlich der Sprachgebrauch? Im Link steht "logische Signatur", in einer (weniger zuverlässigen Überschrift) steht "funktionale Signatur" und in mehreren Fragen kommen 0 und 1 gar nicht in der (ohne Adjektiv / logischen) Signatur vor, obschon dann damit gerechnet wird.

---

Hallo Lu,

danke für die Antwort.

Leider haben wir noch die kanonische KNF und DNF nicht durchgemacht. Ich habe da auch leider nichts gefunden, um meine Lösung zu vergleichen.

Answer 1

¬x = 1↛x

x ∧ y = x ↛ (1↛y)

¬x = x↔0

Was genau versteht man unter funktionalen Vollständigkeit?

Es ist |{0, 1} × {0,1}| = 4. Also gibt es 2⁴ = 16 Abbildungen von {0, 1} × {0,1} nach {0, 1}.

Eine Menge A von Abbildungen heißt funktional vollständig, wenn jede dieser 16 Abbildungen durch die Abbildungen in A dargestellt werden kann.

Bekannt sollte sein, dass {¬, ∧} funktional vollständig ist. Für einen Beweis, dass A funktional vollständig ist, genügt es also, die Abbildungen ¬ und ∧ durch Abbildungen aus A darzustellen.

Comments

Elektrotechnisch lautet die Frage: Genügen die Bauteilsorten der Signatur, um jede denkbare Schaltung zu bauen? Wenn ja, ist die Signatur "funktional vollständig".

Stimmt das denn, was ich hier kommentiert habe?

1 und 0 in der Signatur sind nicht "Zustände 1 und 0" sondern "Bauteile" für Tautologie und Widerspruch, die man physisch einbauen kann?

---

Danke für die Antwort. Ich werde das nochmal mit deinem Ansatz rechnen :)