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) $