Seite parallel anzeigen
Du befindest dich hier: Logik Einführung
/ Abschließende Betrachtung von Logiken
/ Unterschiedliche Kalküle, gleiche Logik
Funktionale Vollständigkeit
(Logik Einführung Kapitel 8.2.2)Diese Seite nimmt Bezug auf
(Seite parallel anzeigen)
- Logik Einführung: Atome & Junktoren
- Logik Einführung: Bewertungsfunktion
Einzelne Junktoren lassen sich durch Kombinationen anderer Junktoren ersetzen.
Beispiel - Ersetzung von Junktoren durch andere
Betrachten wir folgende Junktoren aus der Wumpus-Welt.
Um Platz zu sparen, schreiben wir
- W für Wumpus(A,3)
- G für Gestank(A,2)
W G W UND G falsch falsch falsch falsch wahr falsch wahr falsch falsch wahr wahr wahr allgemein:
γ δ γ UND δ falsch falsch falsch falsch wahr falsch wahr falsch falsch wahr wahr wahr
W G W ODER G falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr wahr allgemein:
γ δ γ ODER δ falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr wahr
W NICHT W falsch wahr wahr falsch allgemein:
γ NICHT γ falsch wahr wahr falsch
Die folgende Tabelle zeigt, dass wir die UND-Verknüpfung durch eine Kombination der ODER-Verknüpfung und der Verneinung ausdrücken können:
W G W UND G NICHT W NICHT G (NICHT W)ODER(NICHT G) NICHT((NICHT W)ODER(NICHT G)) falsch falsch falsch wahr wahr wahr falsch falsch wahr falsch wahr falsch wahr falsch wahr falsch falsch falsch wahr wahr falsch wahr wahr wahr falsch falsch falsch wahr
Eine Menge von Junktoren heißt bezüglich einer anderen Menge von Junktoren funktional vollständig, wenn alle Junktoren der 2. Menge durch Junktoren der 1. Menge ausgedrückt werden können.
Beispiel - Funktional vollständige Junktorenmenge
Die Menge, bestehend aus folgenden Junktoren aus dem obigen Beispiel:ist funktional vollständig bezüglich der Menge, bestehend aus folgenden Junktoren:
- ODER
- NICHT
- UND
- ODER
- NICHT
- zurück zu Mögliche Anzahl der Junktoren
- zum Seitenanfang
- weiter zu
