3. Prädikatenlogik erster Stufe

Viele praktisch relevante Problemstellungen lassen sich mit der Sprache der Aussagenlogik nicht oder nur sehr umständlich formulieren, wie man an folgenden Beispielen gut erkennt. Die Aussage

„Roboter 7 befindet sich an xy-Position (35, 79)“

kann zwar direkt als die aussagenlogische Variable

„Roboter_7_befindet_sich_an_xy-Position_(35,79)“

zum Schließen mit Aussagenlogik verwendet werden, aber das Schließen mit derartigen Aussagen wird sehr umständlich. Angenommen 100 dieser Roboter können sich auf einem Gitter mit \(100\times 100\) Punkten aufhalten. Um alle Positionen aller Roboter zu beschreiben, würde man \(100\cdot 100\cdot 100=1.000.000=10^{6}\) verschiedene Variablen benötigen. Erst recht schwierig wird die Definition von Relationen zwischen verschiedenen Objekten (hier Robotern). Die Relation

„Roboter A steht weiter rechts als Roboter B .“

ist semantisch letztlich nichts anderes als eine Menge von Paaren. Von den 10.000 möglichen Paaren aus x-Koordinaten sind \((100\cdot 99)/2=4950\) geordnet. Zusammen mit allen 10.000 Kombinationen möglicher y-Werte beider Roboter ergeben sich zur Definition dieser Relation \(100\cdot 99=9900\) Formeln der Art

Roboter_7_steht_weiter_rechts_als_Roboter_12 \(\,\Leftrightarrow\,\)

Roboter_7_befindet_sich_an_xy_Position_(35,79)

\(\,\wedge\,\) Roboter_12_befindet_sich_an_xy_Position_(10,93) \(\,\vee\,\) \(\ldots\)

mit je \((10^{4})^{2}\cdot 0{,}495=0{,}495\cdot 10^{8}\) Alternativen auf der rechten Seite. In der Prädikatenlogik erster Stufe definiert man hierfür ein Prädikat Position(nummer, xPosition, yPosition). Die obige Relation muss nun nicht mehr als riesige Menge von Paaren aufgezählt werden, sondern wird abstrakt beschrieben durch eine Regel der Formwobei als „für alle “ und als „es gibt “ gelesen wird.