Diskrete Mathematik - Prädikatenlogik
Predicate Logic befasst sich mit Prädikaten, die Sätze sind, die Variablen enthalten.
Prädikatenlogik - Definition
Ein Prädikat ist ein Ausdruck einer oder mehrerer Variablen, die in einer bestimmten Domäne definiert sind. Ein Prädikat mit Variablen kann zu einem Satz gemacht werden, indem entweder der Variablen ein Wert zugewiesen oder die Variable quantifiziert wird.
Das Folgende sind einige Beispiele für Prädikate -
- Es sei E (x, y) "x = y"
- X (a, b, c) bezeichne "a + b + c = 0".
- Es sei M (x, y) "x ist mit y verheiratet"
Gut geformte Formel
Well Formed Formula (wff) ist ein Prädikat, das eines der folgenden Elemente enthält:
Alle Satzkonstanten und Satzvariablen sind wffs
Wenn x eine Variable und Y eine wff ist, sind $ \ forall x Y $ und $ \ vorhanden x Y $ ebenfalls wff
Wahrheitswert und falsche Werte sind wffs
Jede Atomformel ist eine wff
Alle Verbindungen, die wffs verbinden, sind wffs
Quantifizierer
Die Variable der Prädikate wird durch Quantifizierer quantifiziert. In der Prädikatenlogik gibt es zwei Arten von Quantifizierern: Universal Quantifier und Existential Quantifier.
Universal Quantifier
Der universelle Quantifizierer gibt an, dass die Aussagen in seinem Geltungsbereich für jeden Wert der spezifischen Variablen zutreffen. Es wird mit dem Symbol $ \ forall $ bezeichnet.
$ \ forall x P (x) $ wird gelesen, da für jeden Wert von x P (x) wahr ist.
Example - "Der Mensch ist sterblich" kann in die Satzform $ \ forall x P (x) $ umgewandelt werden, wobei P (x) das Prädikat ist, das bedeutet, dass x sterblich ist und das Universum des Diskurses alle Menschen sind.
Existenzieller Quantifizierer
Der Existenzquantifizierer gibt an, dass die Anweisungen in seinem Bereich für einige Werte der spezifischen Variablen zutreffen. Es wird durch das Symbol $ \ existiert $ bezeichnet.
$ \ existiert x P (x) $ wird gelesen, da für einige Werte von x P (x) wahr ist.
Example - "Manche Menschen sind unehrlich" kann in die Satzform $ \ existiert x P (x) $ umgewandelt werden, wobei P (x) das Prädikat ist, das bedeutet, dass x unehrlich ist und das Universum des Diskurses manche Menschen sind.
Verschachtelte Quantifizierer
Wenn wir einen Quantifizierer verwenden, der im Rahmen eines anderen Quantifizierers erscheint, wird er als verschachtelter Quantifizierer bezeichnet.
Example
$ \ forall \ a \: \ existiert b \: P (x, y) $ wobei $ P (a, b) $ $ a + b = 0 $ bezeichnet
$ \ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c) $ wobei $ P (a, b) $ $ a + (b + c) = ( a + b) + c $
Note - $ \ forall \: a \: \ existiert b \: P (x, y) \ ne \ existiert a \: \ forall b \: P (x, y) $