Da für jede Menge variabler Werte aus dem Definitionsbereich des Prädikats diese in eine Aussage umgewandelt wird, werden für die Menge der Prädikate die gleichen logischen Operationen definiert wie für Aussagen. Gleichzeitig wird der Inhalt der Prädikate abstrahiert. Prädikate werden nur im Hinblick auf ihre Bedeutung betrachtet. Mit anderen Worten: Äquivalente Prädikate unterscheiden sich nicht.

Definition 1: Durch Verleugnung - lokales Prädikat
, am Set definiert
, genannt neu - Lokales Prädikat, das auf derselben Menge definiert ist. Angezeigt durch:
. Darin heißt es: „Das stimmt nicht
" Prädikat
wird nur für die Argumente als wahr ausgewertet, für die der Wert des Prädikats gilt
es gibt eine „Lüge“ und umgekehrt. Mit anderen Worten, das Prädikat
wird durch diejenigen und nur durch diejenigen Argumente erfüllt, die das gegebene Prädikat nicht erfüllen
.

Doppeltes Prädikat
wird für diese und nur diese Variablenwerte als wahr ausgewertet
aus dem Definitionsbereich des Prädikats, für das das Prädikat gilt
nimmt den Wert „false“ an, d.h.

Definition 2: Durch Konjunktion - lokales Prädikat
, am Set definiert
, Und
- lokales Prädikat
, am Set definiert
, genannt neu
- Lokales Prädikat, definiert für eine Menge
, bezeichnet durch Es liest: "
Und
" Dieses Prädikat wird nur für die Argumentwerte, für die die Prädikate gelten, als wahr ausgewertet
Und
nehmen gleichzeitig den Wert „true“ an.

Wenn zum Beispiel
- ein zweistelliges Prädikat, das auf einer Menge definiert ist
, A
– ein unäres Prädikat, das auf einer Menge definiert ist , dann die Konjunktion dieser Prädikate
Auf der Menge ist ein dreistelliges Prädikat definiert
. Dieses neue Prädikat wird für solche Elementtripel als wahr ausgewertet
,
,
,
, wofür
Und
.

Disjunktion, Implikation und Äquivalenz von Prädikaten werden ähnlich definiert. Die Werte von Prädikaten für gegebene Werte freier Variablen werden gemäß bestimmten logischen Operationen bestimmt. Operationen
kann auch auf Prädikate angewendet werden, die gemeinsame Variablen haben. In diesem Fall ist die Anzahl der Variablen des resultierenden zusammengesetzten Prädikats gleich der Anzahl der verschiedenen Variablen in seinen Mitgliedern. Insbesondere wenn Operationen
auf zwei anwenden - Lokale Prädikate, die von denselben Variablen abhängen, dann erhalten wir als Ergebnis der Anwendung logischer Operationen - ein lokales Prädikat, das von denselben Variablen abhängt.

Lassen
Und
- zwei - lokale Prädikate, die von denselben Variablen abhängen. Dann:

a) die Wahrheitsmenge einer Konjunktion ist gleich dem Schnittpunkt der Wahrheitsmengen ihrer Mitglieder;

b) Die Wahrheitsmenge einer Disjunktion ist gleich der Vereinigung der Wahrheitsmengen ihrer Mitglieder.

Es ist nicht schwer zu zeigen, dass die Konjunktion zweier Prädikate genau dann identisch wahr ist, wenn beide gegebenen Prädikate identisch wahr sind. Eine Disjunktion zweier Prädikate ist genau dann erfüllbar, wenn mindestens eines davon erfüllbar ist. Eine Disjunktion zweier Prädikate ist genau dann identisch falsch, wenn beide gegebenen Prädikate identisch falsch sind. Implikation von zwei - lokale Prädikate, die von denselben Argumenten abhängen, ist genau dann identisch wahr, wenn ihre Schlussfolgerung eine Konsequenz der Prämissen ist. Gleichwertigkeit von zwei - Lokale Prädikate, die von denselben Variablen abhängen, sind genau dann identisch wahr, wenn beide Prädikate äquivalent sind.

Jede Gleichung (Ungleichung), die Variablen enthält, ist ein Prädikat, das auf derselben Menge definiert ist, auf der die Gleichung (Ungleichung) angegeben ist. Die Menge der Lösungen einer Gleichung (Ungleichung) ist nichts anderes als die Wahrheitsmenge des Prädikats. Dies bedeutet, dass man wahre Aussagen erhält, wenn man anstelle der Unbekannten die Wurzeln einer Gleichung (oder Lösungen einer Ungleichung) einsetzt. Wenn anstelle von Variablen Zahlen in die Gleichung eingesetzt werden, die keine Lösungen sind (Ungleichung), so erhält man falsche Aussagen. Jedes Gleichungssystem (Ungleichungen) kann als Konjunktion von Prädikaten betrachtet werden. Ein System zu lösen bedeutet, den Wahrheitsbereich der Konjunktion von Prädikaten zu finden. Eine Menge von Gleichungen (Ungleichungen) ist nichts anderes als eine Disjunktion von Prädikaten. Unter der Äquivalenz von Gleichungen (Ungleichungen) versteht man die Äquivalenz der entsprechenden Prädikate.

Wenn
, dann sagen sie, dass das Argument
erfüllt dieses Prädikat. Beispielsweise erfüllt die Zahl 3 das Prädikat
, und die Nummer 1 befriedigt ihn nicht.

In der mathematischen Logik gibt es neben logischen Operationen an Prädikaten auch Operationen Quantifizierung , die die Prädikatenlogik im Vergleich zur Aussagenlogik wesentlich inhaltsreicher machen. In diesem Fall werden Prädikate, wie auch bei den einfachsten Operationen, nur unter dem Gesichtspunkt ihrer Bedeutung betrachtet, d.h. Äquivalente Prädikate unterscheiden sich nicht. Die wichtigsten Quantifiziereroperationen sind: der allgemeine Quantifizierer und der Existenzquantifizierer, die zueinander dual sind.

Definition 3: Lassen
– ein unäres Prädikat, das auf einer nicht leeren Menge definiert ist

in eine Aussage umwandeln:
(lautet: „für jeden durchgeführt
"), angerufen allgemeiner Quantor (oder eine universelle Aussage). Stellungnahme
wahr genau dann, wenn das gegebene Prädikat vorliegt
identisch wahr (d. h. der Wahrheitsbereich des Prädikats).
stimmt mit der Menge überein
).

Symbol wird ein allgemeiner Quantor in Bezug auf eine Variable genannt Dort heißt es: „Für alle " oder "für alle " Sie sagen, dass das Sprichwort
ist das Ergebnis der Anwendung eines allgemeinen Quantifizierers auf ein Prädikat
. Symbol kommt vom englischen Wort „All“ (übersetzt: „alle“).

Zum Beispiel für die Prädikate „
" Und "
", definiert auf der Menge der reellen Zahlen, haben die entsprechenden universellen Aussagen die Form:
– „jede reelle Zahl ist sich selbst gleich“ (wahr) und
– „Jede reelle Zahl ist größer als 2“ (falsch).

Satz 1: Wenn
- ein einstelliges Prädikat, das auf einer endlichen Menge definiert ist, bestehend aus
Elemente ,,…,, dann ist die entsprechende universelle Aussage äquivalent zur Konjunktion
Sprüche:

Nachweisen. In der Tat, nach der Definition des allgemeinen Quantifizierers, der Aussage

identisch wahr, d.h. wenn alles wahr ist
Aussagen, die aus einem gegebenen Prädikat durch Ersetzen der Variablen erhalten werden Argumente ,,…,jeweils. Die letzte Bemerkung ist genau dann möglich, wenn die Konjunktion dieser
Aussagen. Diese. Die Bedingungen der Äquivalenz sind sowohl wahr als auch falsch, und daher ist die Äquivalenz bewiesen.

Der Satz zeigt, dass für Prädikate, die auf einer endlichen Menge definiert sind, die Operation der Anwendung eines allgemeinen Quantors durch eine Konjunktion ausgedrückt werden kann. Für Prädikate, die auf einer unendlichen Menge definiert sind, ist dies nicht möglich; in diesem Fall ist die Anwendung des allgemeinen Quantifizierers völlig neu.

Definition 4: Lassen
– ein unäres Prädikat, das auf einer Menge definiert ist
. Operation, die ein Prädikat transformiert
in eine Aussage umwandeln
(lautet: „Es gibt , das Prädikat erfüllend
"), angerufen Existenzquantor (oder eine existentielle Aussage). Stellungnahme
wird genau dann wahr sein, wenn das Prädikat
ausführbar. Diese Aussage ist falsch, wenn das Prädikat
identisch falsch.

Symbol wird als Existenzquantor in Bezug auf eine Variable bezeichnet . Es ist zu lesen: „Es gibt so dass
“, oder „Es wird solche geben , Was
" Symbol kommt vom englischen Wort „Exist“ (existiert).

Satz 2: Wenn
– ein einstelliges Prädikat, das auf einer endlichen Menge von definiert ist
Elemente ,,…,, dann ist die entsprechende existentielle Aussage äquivalent zur Disjunktion
Sprüche:

Nachweisen: Definition: Aussage
wird genau dann falsch sein, wenn alle falsch sind
Aussagen, die aus einem gegebenen Prädikat durch Ersetzen einer Variablen erhalten werden Argumente ,,…,jeweils. Die letzte Bemerkung ist genau dann möglich, wenn die Disjunktion dieser beiden erfolgt
Aussagen. Diese. Die Bedingungen einer Äquivalenz sind sowohl wahr als auch falsch, daher ist die Äquivalenz wahr.

Dieser Satz besagt, dass für Prädikate, die auf endlichen Mengen definiert sind, die Operation der Anwendung eines Existenzquantifizierers durch Disjunktion ausgedrückt werden kann. Für Prädikate, die auf unendlichen Mengen definiert sind, ist dies nicht möglich. Die Operation der Anwendung des Existenzquantors ist dann völlig neu.

Das sollte bei jedem Prädikat beachtet werden
, am Set definiert
Ausdrücke
Und
Dies sind Aussagen, keine Prädikate. Vorhandensein einer Variablen hier ist rein äußerlich, bezogen auf die Notationsmethode. Daher die Variable , in den Ausdrücken enthalten
Und
, angerufen zugehörige Variable, im Gegensatz zu der im Prädikat enthaltenen Variablen
, wo die Variable aufgerufen wird frei. Wenn wir die Operation „hängender“ Quantoren auf ein zweistelliges Prädikat anwenden
durch eine Variable, dann wird aus dem zweistelligen Prädikat ein einstelliges Prädikat mit einer freien Variablen. Ähnliche Überlegungen lassen sich auch für die zweite Variable anstellen. Die Variable, auf die der Quantor angewendet wurde, wird aufgerufen Liaison Variable. Wenn wir die Quantifiziereroperation anwenden auf - ein lokales Prädikat in Bezug auf eine Variable, dann wird es zu
- lokales Prädikat.

Wenn in einem Prädikat alle Variablen miteinander in Beziehung stehen, dann ist dieses Prädikat eine Aussage. Betrachten Sie zum Beispiel das Prädikat
, definiert auf einem Zahlensatz. Geben wir eine Erklärung ab
. Dies ist eine falsche Aussage, die besagt, dass es eine solche Zahl gibt , die größer als jede Zahl ist (- Singularnummer für alle ). Durch Vertauschen der Quantoren erhalten wir eine neue Aussage:
. Diese Aussage besagt, dass für jede Zahl Sie können eine Zahl wie diese wählen , dass die Ungleichung gilt
(für jede es gibt eine nummer ). Diese Aussage ist wahr. Es ist ersichtlich, dass sich die Bedeutung der Aussage ändert, wenn Quantoren neu angeordnet werden. Auf diese Weise, Im Gegensatz zu Quantifizierern ist das Neuanordnen ein inakzeptabler Vorgang. Gleichnamige Quantoren können vertauscht werden. Darüber hinaus können gleichnamige Quantoren zu einem zusammengefasst werden, zum Beispiel: . Es ist auch nicht akzeptabel, mehrere Quantoren für dieselbe Variable zu verwenden, zum Beispiel:
.

Definition 5: Durch eine universelle Aussage , dazugehörigen - lokales Prädikat
, am Set definiert

konsequente Anwendung Quantifizierer der Allgemeinheit über Variablen
In irgendeiner Reihenfolge.

Diese Aussage wird wie folgt bezeichnet und kurz gelesen: „für alle.“
durchgeführt
».

Definition 6: Durch eine existentielle Aussage, relevant - lokales Prädikat
, am Set definiert
ist eine Aussage aus
konsequente Anwendung Existenzquantoren über Variablen
In irgendeiner Reihenfolge.

Die resultierende existentielle Aussage wird wie folgt bezeichnet und lautet: „Es gibt eine solche Menge
, die durchgeführt wird
».

Zum Beispiel für das zweistellige Prädikat „
» Die entsprechenden Aussagen haben die Form:
– „für zwei beliebige reelle Zahlen: die erste ist größer als die zweite“ (falsch), und
– „Es gibt zwei reelle Zahlen, von denen die erste größer als die zweite ist“ (wahr).

Satz 3: (Bedingung für die identische Wahrheit eines quantifizierten Prädikats).

-lokales Prädikat abgeleitet von - lokales Prädikat
, am Set definiert
, indem ein allgemeiner Quantor in Bezug auf eine beliebige Variable angewendet wird, ist genau dann identisch wahr, wenn das gegebene Prädikat vorliegt
– identisch wahr.

Nachweisen: In der Tat, lass es gegeben sein
- lokales Prädikat
, am Set definiert
. Per Definition ist dieses Prädikat genau dann identisch wahr, wenn sein Wert für beliebige Werte der Argumente „wahr“ ist. Dies bedeutet, dass die universelle Aussage wahr ist

, am Set definiert
. Die letzte Bemerkung ist genau dann möglich, wenn das Prädikat
– genauso wahr, aber weil Argumente
wurden willkürlich gewählt, so ist dies gleichbedeutend mit der identischen Wahrheit des Gegebenen - lokales Prädikat
. Der Satz ist bewiesen.

Satz 4: (Bedingung für die identische Falschheit eines quantifizierten Prädikats).

-lokales Prädikat abgeleitet von - lokales Prädikat
, am Set definiert
, durch Anwenden eines existenziellen Quantifizierers in Bezug auf eine Variable, ist genau dann identisch falsch, wenn das gegebene Prädikat identisch falsch ist.

Nachweisen: Lass uns haben
- lokales Prädikat
, am Set definiert
. Es ist genau dann identisch falsch, wenn sein Wert für willkürlich genommene Argumente gilt
es liegt eine „Lüge“ vor. Das bedeutet, dass die Existenzaussage falsch ist
, entsprechend dem unären Prädikat
, am Set definiert
. Letzteres ist genau dann möglich, wenn das Prädikat
ist identisch falsch, und da Argumente
zufällig ausgewählt wurden, dann dies - lokales Prädikat
ist identisch falsch. Q.E.D.

Bisher haben wir Prädikate und Propositionen gegenübergestellt. Es ist jedoch bequemer, Aussagen zu zählen 0 - lokale Prädikate. Dann sollten zwei beliebige wahre und zwei beliebige falsche Aussagen als einander gleichwertig angesehen werden.

Der Begriff eines Prädikats

Definition 1

Prädikat– eine Anweisung, die Variablen enthält, die abhängig von den Werten der Variablen den Wert $1$ oder $0$ (wahr oder falsch) annehmen.

Beispiel 1

Beispielsweise ist der Ausdruck $x=x^5$ ein Prädikat, weil es ist wahr für $x=0$ oder $x=1$ und falsch für alle anderen Werte von $x$.

Definition 2

Eine Menge, auf der ein Prädikat nur wahre Werte akzeptiert, wird aufgerufen Wahrheitsmenge des Prädikats$I_p$.

Das Prädikat heißt identisch wahr, wenn es bei einer Reihe von Argumenten als wahr ausgewertet wird:

$P (x_1, \dots, x_n)=1$

Das Prädikat heißt identisch falsch, wenn es bei irgendeinem Satz von Argumenten als falsch ausgewertet wird:

$P (x_1, \dots, x_0)=0$

Das Prädikat heißt machbar, wenn es bei mindestens einem Satz von Argumenten als wahr ausgewertet wird.

Weil Prädikate können nur zwei Werte annehmen (wahr/falsch oder $0/1$), dann können alle Operationen der logischen Algebra auf sie angewendet werden: Negation, Konjunktion, Disjunktion usw.

Beispiele für Prädikate

Das Prädikat $R(x, y)$: $“x = y“$ bezeichne die Gleichheitsrelation, wobei $x$ und $y$ zur Menge der ganzen Zahlen gehören. In diesem Fall gilt das Prädikat R für alle gleichen $x$ und $y$.

Ein weiteres Beispiel für ein Prädikat ist WORKS($x, y, z$) für die Relation „$x$ arbeitet in Stadt y für Firma $z$.“

Ein weiteres Beispiel für ein Prädikat ist LIKE($x, y$) für „x mag y“ für $x$ und $y$, die zu $M$ gehören – der Menge aller Menschen.

Ein Prädikat ist also alles, was über den Gegenstand des Urteils behauptet oder verneint wird.

Operationen auf Prädikaten

Betrachten wir die Anwendung logischer Algebraoperationen auf Prädikate.

Logische Operationen:

Definition 3

Konjunktion zweier Prädikate $A(x)$ und $B(x)$ sind ein Prädikat, das einen wahren Wert für diejenigen und nur die Werte von $x$ aus $T$ annimmt, für die jedes der Prädikate einen wahren Wert annimmt und immer ein falscher Wert. In allen anderen Fällen. Die Wahrheitsmenge $T$ eines Prädikats ist der Schnittpunkt der Wahrheitsmengen der Prädikate $A(x)$ und $B(x)$. Zum Beispiel: Prädikat $A(x)$: „$x$ ist eine gerade Zahl“, Prädikat $B(x)$: „$x$ ist durch $5$ teilbar.“ Das Prädikat wäre also „$x$ ist eine gerade Zahl und durch 5 $ teilbar“ oder „$x$ ist durch 10 $ teilbar“.

Definition 4

Disjunktion zweier Prädikate $A(x)$ und $B(x)$ sind ein Prädikat, das für diejenigen und nur die Werte von $x$ aus $T$, für die jedes der Prädikate falsch und in wahr ausgewertet wird, als falsch ausgewertet wird alle anderen Fälle. Die Wahrheitsmenge eines Prädikats ist die Vereinigung der Wahrheitsbereiche der Prädikate $A(x)$ und $B(x)$.

Definition 5

Negation eines Prädikats $A(x)$ ist ein Prädikat, das für alle Werte von $x$ in $T$, für die $A(x)$ falsch ist, als wahr ausgewertet wird und umgekehrt. Die Wahrheitsmenge des Prädikats $A(x)$ ist das Komplement von $T"$ zur Menge $T$ in der Menge $x$.

Definition 6

Prädikatsimplikation $A(x)$ und $B(x)$ ist ein Prädikat, das für diejenigen und nur die Werte von $x$ aus $T$ falsch ist, für die $A(x)$ wahr ist und $B( x )$ ist falsch und wird in allen anderen Fällen als wahr ausgewertet. Es lautet: „Wenn $A(x)$, dann $B(x)$.“

Beispiel 2

Sei $A(x)$: „Die natürliche Zahl $x$ ist durch $3$ teilbar“;

$B(x)$: „Die natürliche Zahl $x$ ist durch $4$ teilbar.“

Erstellen wir ein Prädikat: „Wenn eine natürliche Zahl $x$ durch $3$ teilbar ist, dann ist sie auch durch $4$ teilbar.“

Die Wahrheitsmenge eines Prädikats ist die Vereinigung der Wahrheitsmenge des Prädikats $B(x)$ und des Komplements zur Wahrheitsmenge des Prädikats $A(x)$.

Zusätzlich zu logischen Operationen können Quantenoperationen an Prädikaten durchgeführt werden: die Verwendung des universellen Quantifizierers, des Existenzquantifizierers usw.

Quantifizierer

Definition 7

Quantifizierer– logische Operatoren, deren Anwendung auf Prädikate diese in falsche oder wahre Aussagen umwandelt.

Definition 8

Quantor– logische Operationen, die den Wahrheitsbereich eines Prädikats begrenzen und eine Aussage erzeugen.

Die am häufigsten verwendeten Quantoren sind:

universeller Quantor (gekennzeichnet durch das Symbol $\forall x$) – der Ausdruck „für alle $x$“ („für jedes $x$“);

Existenzquantifizierer (gekennzeichnet durch das Symbol $\exists x$) – der Ausdruck „es existiert $x$, so dass …“;

Eindeutigkeits- und Existenzquantor (gekennzeichnet durch $\exists !x$) – der Ausdruck „es gibt genau ein $x$, so dass ...“.

In der mathematischen Logik gibt es ein Konzept binden oder Quantifizierung, die die Zuordnung eines Quantors zu einer Formel bezeichnen.

Beispiele für die Verwendung von Quantoren

Sei das Prädikat „$x$ ist ein Vielfaches von $7$“.

Mit dem universellen Quantor können wir die folgenden falschen Aussagen schreiben:

jede natürliche Zahl ist durch $7$ teilbar;

jede natürliche Zahl ist durch $7$ teilbar;

alle natürlichen Zahlen sind durch $7$ teilbar;

was so aussehen wird:

Bild 1.

Um wahre Aussagen zu schreiben, verwenden wir Existenzquantor:

es gibt natürliche Zahlen, die durch $7$ teilbar sind;

Es gibt eine natürliche Zahl, die durch $7$ teilbar ist;

Mindestens eine natürliche Zahl ist durch $7$ teilbar.

Der Eintrag sieht folgendermaßen aus:

Figur 2.

Das Prädikat sei für die Menge $x$ der Primzahlen gegeben: „Eine Primzahl ist ungerade.“ Wenn wir das Wort „any“ vor das Prädikat setzen, erhalten wir eine falsche Aussage: „Jede Primzahl ist ungerade“ (z. B. $2$ ist eine gerade Primzahl).

Wir setzen das Wort „existiert“ vor das Prädikat und erhalten eine wahre Aussage: „Es gibt eine Primzahl, die ungerade ist“ (zum Beispiel $x=3$).

So kann ein Prädikat in eine Aussage umgewandelt werden, indem man dem Prädikat einen Quantor voranstellt.

Operationen an Quantoren

Um die Negation von Aussagen zu konstruieren, die Quantoren enthalten, verwenden wir Regel der Negation von Quantoren:

Figur 3.

Betrachten wir die Sätze und wählen wir Prädikate aus ihnen aus, wobei wir den Wahrheitsbereich jedes einzelnen von ihnen angeben.

1 . Negationsoperation.

Verweigerung Prädikat P(x), am Set gegeben X, ist ein Prädikat, das auf derselben Menge definiert ist und für diese und nur diese Werte wahr ist XX, unter dem das Prädikat P(x) nimmt die Bedeutung einer Lüge an.

2 . Operation der Konjunktion.

Verbindung Prädikate P(x) Und Q(x), am Set definiert X, heißt Prädikat P(x)Q(x), gegeben auf derselben Menge und wird zu einer wahren Aussage für diese und nur diese Werte XX, in dem beide Prädikate Wahrheitswerte annehmen.

Wenn wir benennen TR P(x), TQ- Wahrheitsmenge des Prädikats Q(x) und die Wahrheitsmenge ihrer Konjunktion TPÙQ, dann, anscheinend, TPÙQ = TP Ç T.Q.

Beweisen wir diese Gleichheit.

1. Lass A X und das ist bekannt AÎ TPÙQ . Nach der Definition einer Wahrheitsmenge bedeutet dies, dass das Prädikat P(x)Q(x) wird zu einer wahren Aussage, wenn x = a, d.h. Stellungnahme R(a)F(a) ist wahr. Da diese Aussage eine Konjunktion ist, erhalten wir durch die Definition einer Konjunktion, dass jede der Aussagen R(a) Und F(a) auch wahr. Das bedeutet es ATR Und ATQ. Damit haben wir das gezeigt TPÙQ Ì TRÇ TQ.

2. Beweisen wir die umgekehrte Aussage. Lassen A- ein beliebiges Element der Menge X und das ist bekannt AÎ TP Ç TQ. Nach der Definition der Schnittmenge von Mengen bedeutet dies Folgendes ATR Und ATQ, woher wir das haben R(a) Und F(a)- wahre Aussagen, also die Konjunktion von Aussagen R(a)F(a) wird auch wahr sein. Dies bedeutet, dass das Element A gehört zur Wahrheitsmenge des Prädikats P(x)Q(x), d.h. AÎ TPÙQ .

Aus 1 und 2 folgt aufgrund der Definition gleicher Mengen die Gleichheit TPÙQ =TRÇ TQ, was bewiesen werden musste.

Visuell lässt sich dies wie folgt darstellen.

3. Operation der Disjunktion.

Disjunktion Prädikate P(x) Und Q(x) heißt Prädikat P(x)Q(x X und sich in eine wahre Aussage für diese und nur diese Werte verwandeln XX, wobei mindestens eines der Prädikate den Wert der Wahrheit annimmt P(x) oder Q(x).

Ebenso ist es bewiesen TPÚQ = TP È T.Q.

4 .Operation der Implikation.

Implizit Prädikate P(x) Und Q(x), am Set definiert X, heißt Prädikat P(x)Q(x), definiert auf demselben Satz X und sich in eine falsche Aussage für diese und nur diese Werte verwandeln XX, bei dem P(x) den Wert der Wahrheit annimmt, und Q(x)- die Bedeutung von Lügen.

5 .Äquivalenzoperation.

Gleichwertigkeit Prädikate P(x) Und Q(x), am Set definiert X, heißt Prädikat P(x)Q(x), definiert auf demselben Satz X und den Wert der Wahrheit für diese und nur diese Werte zu akzeptieren XX, für die die Werte jedes der Prädikate entweder wahr oder falsch sind. Die in diesem Fall festgelegte Wahrheit sieht folgendermaßen aus:

TPÛQ = .

Beispiel. Am Set M=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} Prädikate sind gegeben: Oh)- "Nummer X nicht teilbar durch 5 », B(x) - « X- die Zahl ist gerade", C(x) - « X- die Zahl ist eine Primzahl", D(x)- "Nummer X mehrere 3 " Finden Sie die Wahrheitsmenge der folgenden Prädikate:

A) Oh)B(x); B) Axt); C) C(x)A(x); D) B(x)D(x) und stellen Sie sie mithilfe von Euler-Venn-Diagrammen dar.

Lösung: a) Finden Sie die Wahrheitsmenge der Prädikate.

A(x): T = (1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19);

B(x): T = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20).

Wahrheitsmenge einer Konjunktion Oh)B(x) Es gibt Wahrheiten T Und T .

Informell kann ein Prädikat als eine bestimmte Aussage definiert werden, deren Bedeutung von den Werten objektiver Variablen aus der Menge abhängt M, auf dem das Prädikat definiert ist.

A) P(x): “X ist eine Primzahl“;

(Hier und im Folgenden verwenden wir zur Spezifizierung eines Prädikats eine Kurzform der Notation, die im Detail wie folgt beschrieben wird: „ X ist eine Primzahl.")

B) D(x,y) : “X ist vollständig teilbar durch j”;

C) R(x,y): “X > j”.

Als Subjektmenge für diese Beispiele kommen beliebige Zahlenmengen in Betracht, insbesondere in den Beispielen a), b) – M= Í , und in c) – M= Ñ .

Genauer gesagt Prädikat kann als Mapping definiert werden N Potenz des Sets M, genannt die Lokalität oder Arität eines Prädikats in einer Zwei-Elemente-Menge B = {1, 0}

Beim Einsetzen in ein Prädikat Anstelle von Wertsatzsubjektvariablen wir erhalten eine logische Aussage (also , a ). Ein Prädikat ist also eine variable Aussage (oder ein Aussagesystem), deren Wahrheit durch die Substitution verschiedener Werte der Subjektvariablen bestimmt wird.

Da Prädikate Werte aus der Menge annehmen B , dann werden für sie logische Operationen ~ definiert. Darüber hinaus werden für Prädikate die Operationen der Universalitätsbehauptung und der Existenzbehauptung eingeführt.

Die Operation der Bestätigung der Universalität bringt die Ausdrucksform in Übereinstimmung P(x) Aussage (gelesen als, P(x) gilt für alle X Von vielen M, auf dem das Prädikat definiert ist). Eine Aussage ist genau dann wahr, wenn die Aussage P(a) gilt für jedes Element.

Die Operation Existenzbehauptung bringt die Ausdrucksform in Übereinstimmung P(x) Aussage (gelesen als, es gibt eine solche X Von vielen M, für die die Aussage P(x) WAHR). Eine Aussage ist genau dann wahr, wenn die Aussage P(a) wahr für mindestens ein Element.

Die Zeichen „ und $ heißen Quantoren der Universalität und Existenz (Quantor übersetzt aus dem Lateinischen – Bestimmung der Menge). Übergang von der Ausdrucksform P(x) an Aussagen oder wird als Anhängen eines Quantors oder Binden einer Variablen bezeichnet X(manchmal durch Quantifizierung der Variablen X). Eine Variable mit einem Quantor heißt gebunden, eine ungebundene Variable heißt frei. Die Bedeutung gebundener und freier Variablen in Prädikatausdrücken ist unterschiedlich. Eine freie Variable ist eine gewöhnliche Variable, die verschiedene Werte annehmen kann M, und der Ausdruck P(x)– eine variable Aussage je nach Bedeutung X. Ausdrücke und hängen nicht von einer Variablen ab X und zwar fest P Und M haben eine ganz bestimmte Bedeutung. Variablen, die im Wesentlichen miteinander in Zusammenhang stehen, finden sich nicht nur in der mathematischen Logik. Zum Beispiel in Ausdrücken oder Variablen X verbunden, fest F Der erste Ausdruck ist gleich einer bestimmten Zahl und der zweite ist eine Funktion von A Und B.

Die Aussagen sagen also nichts über die Eigenschaften einzelner Elemente der Menge aus M, sondern über die Eigenschaften der Menge selbst M. Ob diese Aussagen wahr oder falsch sind, hängt nicht von der Bezeichnung der darin enthaltenen Subjektvariablen ab und kann beispielsweise durch jede andere Subjektvariable ersetzt werden j, und erhalten Sie Aussagen und , die dieselbe Bedeutung und dieselben Wahrheitswerte wie die ursprünglichen Aussagen haben.

Im Allgemeinen, z N-ary-Prädikat, wenn die Operationen zur Behauptung von Universalität oder Existenz ausgeführt werden können k mal (die Reihenfolge der Auswahl der Variablen, denen der Quantor zugewiesen wird, kann beliebig sein, mit Ausnahme ihrer Wiederholung) und den Ausdruck erhalten

wo bezeichnet den Quantor der Universalität oder Existenz. Variablen in Anweisungsform (1) sind gebunden und frei.

Auftragsbeziehung. Bestellte Sets

Definition. Attitüde R auf einem Set X heißt Ordnungsrelation, wenn sie transitiv und asymmetrisch oder antisymmetrisch ist.

Definition. Attitüde R auf einem Set X heißt eine strikte Ordnungsrelation, wenn sie transitiv und asymmetrisch ist.

Beispiele Beziehungen strenger Ordnung: „mehr“ auf der Menge der natürlichen Zahlen, „höher“ auf der Menge der Menschen usw.

Definition. Attitüde R auf einem Set X heißt eine nichtstrikte Ordnungsrelation, wenn sie transitiv und antisymmetrisch ist.

Beispiele Beziehungen nicht strenger Ordnung: „nicht mehr“ auf der Menge der reellen Zahlen, „ein Teiler sein“ auf der Menge der natürlichen Zahlen usw.

Definition. Ein Haufen X heißt geordnet, wenn darauf eine Ordnungsrelation angegeben ist.

Beispiel. Am Set X= (1; 2; 3; 4; 5) zwei Beziehungen sind gegeben: „ X £ bei" Und " X- Teiler bei».

Beide Beziehungen haben die Eigenschaften Reflexivität, Antisymmetrie und Transitivität (konstruieren Sie Graphen und überprüfen Sie die Eigenschaften selbst), d. h. sind Beziehungen nicht strenger Ordnung. Aber die erste Beziehung hat die Eigenschaft der Verbundenheit, die zweite jedoch nicht.

Definition. Auftragsbeziehung R auf einem Set X heißt lineare Ordnungsrelation, wenn sie die Eigenschaft des Zusammenhangs besitzt.

In der Grundschule werden viele Ordnungsbeziehungen untersucht. Bereits in der ersten Klasse gibt es Relationen „weniger“, „mehr“ auf der Menge der natürlichen Zahlen, „kürzer“, „länger“ auf der Menge der Segmente usw.

Kontrollfragen

1. Definieren Sie eine binäre Beziehung auf einer Menge X.

2. Wie schreibe ich eine Aussage über die Elemente? X Und bei sind in einer Beziehung R?

3. Listen Sie Möglichkeiten auf, Beziehungen zu definieren.

4. Formulieren Sie die Eigenschaften, die Beziehungen haben können. Wie spiegeln sich diese Eigenschaften im Diagramm wider?

5. Welche Eigenschaften muss eine Relation haben, damit sie eine Äquivalenzrelation ist?

6. Wie hängt die Äquivalenzrelation mit der Aufteilung einer Menge in Klassen zusammen?

7. Welche Eigenschaften muss eine Relation haben, damit sie eine Ordnungsrelation ist?

Kapitel 5. Prädikate und Theoreme

In der Mathematik gibt es oft Sätze, die eine oder mehrere Variablen enthalten, zum Beispiel: „ X+ 2 = 7“, „die Stadt liegt an der Wolga“. Diese Sätze sind keine Aussagen, denn Es ist unmöglich, über sie zu sagen, ob sie wahr oder falsch sind. Allerdings beim Ersetzen einer Variablen durch bestimmte Werte X sie verwandeln sich in wahre oder falsche Aussagen. Also im ersten Beispiel mit X= 5 erhalten wir eine wahre Aussage und wann X= 3 – falsche Aussage.

Definition. Ein Satz mit Variablen, der bei bestimmten Werten der Variablen in eine Aussage übergeht, wird als Satzform oder Prädikat bezeichnet.

Basierend auf der Anzahl der im Prädikat enthaltenen Variablen werden sie in einfache, doppelte usw. unterschieden. Prädikate und bezeichnen A(X), IN(x;y)…

Beispiel: A(X): « X ist durch 2 teilbar – ein einstelliges Prädikat, IN(X; bei): "gerade X senkrecht zu einer Geraden bei„ ist ein zweistelliges Prädikat.

Es ist zu beachten, dass das Prädikat implizit Variablen enthalten kann: „Die Zahl ist durch 2 teilbar“, „Der Student hat in der Mathematikprüfung eine hervorragende Note erhalten.“

Die Angabe eines Prädikats beinhaltet in der Regel auch die Angabe einer Menge, aus der die Werte der im Prädikat enthaltenen Variablen ausgewählt werden.

Definition. Die Menge (Domäne) der Definition eines Prädikats ist die Menge X, bestehend aus allen Werten von Variablen, wenn es in ein Prädikat eingesetzt wird, wird dieses zu einer Aussage.

Also das Prädikat „ X> 2" kann auf der Menge der natürlichen Zahlen oder reellen Zahlen berücksichtigt werden.

Jedes Prädikat A(X), X Î X definiert eine Menge TÌ X, bestehend aus Elementen, die, wenn sie in das Prädikat eingesetzt werden A(X) anstatt X Es stellt sich heraus, dass es sich um eine wahre Aussage handelt.

Definition. Die Menge aller Werte, deren Einsetzung in das Prädikat eine wahre Aussage ergibt, wird als Wahrheitsmenge des Prädikats (bezeichnet) bezeichnet T).

Beispiel. Betrachten Sie das Prädikat A(X): « X < 5», заданный на множестве натуральных чисел. T = {1; 2; 3; 4}.

Prädikate können wie Aussagen elementar oder zusammengesetzt sein. Zusammengesetzte Prädikate werden aus elementaren Prädikaten mithilfe logischer Verknüpfungen gebildet.

Lassen T A A(X), FERNSEHER– Wahrheitsbereich des Prädikats IN(X).

Definition. Konjunktion von Prädikaten A(X) Und IN(X) heißt Prädikat A(X) Ù IN(X X Î X, für die beide Prädikate wahr sind.

Zeigen wir das T A Ù IN = T AÇ FERNSEHER.

Nachweisen. 1) Lass A Î T A Ù IN Þ A(A) Ù IN(A) ist eine wahre Aussage. Per Definition einer Konjunktion gilt: A(A) - WAHR, IN(A) – wahr Þ A Î T AÙ A Î FERNSEHERÞ A Î T AÇ FERNSEHERÞ T A Ù IN Ì T AÇ FERNSEHER.

2) Lass BÎ T AÇ FERNSEHERÞ B Î T AÙ B Î FERNSEHERÞ A(B) - WAHR, IN(B) – wahr Þ gemäß Definition der Konjunktion A(B) Ù IN(B) – wahre Aussage Þ B Î T A Ù IN Þ T AÇ FERNSEHERÌ T A Ù IN .

Weil T A Ù IN Ì T AÇ FERNSEHER Und T AÇ FERNSEHERÌ T A Ù IN, dann durch die Eigenschaft der Mengengleichheit T A Ù IN = T AÇ FERNSEHER, was bewiesen werden musste.

Beachten Sie, dass die resultierende Regel auch für Prädikate gilt, die mehr als eine Variable enthalten.

Beispiel. Schauen wir uns die Prädikate an A(X): « X < 10», IN(X): « X A(X) Ù IN(X): « X < 10 и делится на 3».

T A= {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, FERNSEHER= (3; 6; 9; 12; 15; …), dann T A Ù IN = {3; 6; 9}.

Definition. Prädikatsdisjunktion A(X) Und IN(X) heißt Prädikat A(X) Ú IN(X), was für diese und nur diese Werte gilt X Î X, für die mindestens eines der Prädikate wahr ist.

Das können Sie (selbst) beweisen T A Ú IN = T AÈ FERNSEHER.

Beispiel. Schauen wir uns die Prädikate an A(X): « X teilbar durch 2", IN(X): « X ist durch 3 teilbar, gegeben auf der Menge der natürlichen Zahlen. Finden wir den Wahrheitsbereich des Prädikats A(X) Ú IN(X): « X teilbar durch 2 oder 3.“

T A= {2; 4; 6; 8; 10;…}, FERNSEHER= {3; 6; 9; 12; 15; …}, T A Ú IN = {2; 3; 4; 6; 8; 9; …}.

Definition. Negation des Prädikats A(X) ein Prädikat genannt . Es gilt für diese und nur für diese Werte X Î X, für das das Prädikat A(X) ist falsch und umgekehrt.

Beachten Sie, dass = .

Definition. Durch Implikation von Prädikaten A(X) Und IN(X) heißt Prädikat A(X) Þ IN(X) (lesen Sie: „Wenn A(X), Das IN(X)"). Es wird zu einer falschen Aussage über diese Werte X Î X, für das das Prädikat A(X) ist wahr, und das Prädikat IN(X) ist falsch.

Aus der Definition ergibt sich das Prädikat A(X) Þ IN(X) ist am Set falsch T AÇ und gilt daher für das Komplement dieser Menge. Unter Verwendung der Gesetze der Operationen auf Mengen gilt: .

Kontrollfragen

1. Was nennt man eine Ausdrucksform oder ein Prädikat?

2. Welche Prädikate zeichnen sich durch die Anzahl der darin enthaltenen Variablen aus? Nenne Beispiele.

3. Welche Menge wird als Definitionsbereich des Prädikats bezeichnet?

4. Welche Menge wird als Wahrheitsmenge eines Prädikats bezeichnet?

5. Was nennt man eine Konjunktion von Prädikaten? Beweisen Sie eine Gleichheit, die den Wahrheitsbereich einer Konjunktion von Prädikaten mit dem Wahrheitsbereich dieser Prädikate verbindet.

6. Geben Sie Definitionen von Disjunktion, Negation und Implikation von Prädikaten an. Schreiben Sie Gleichheiten auf, die die Wahrheitsbereiche einer Konjunktion von Prädikaten mit den Wahrheitsbereichen dieser Prädikate verbinden.