Prädikatenlogik/Folgerung/Axiomensysteme/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Mit Axiomensystemen verbindet man die Vorstellung, dass daraus „wichtige“ weitere Eigenschaften beweisbar sind. In einer jeden Gruppe gelten nicht nur die Gruppenaxiome, sondern auch alle Gesetzmäßigkeiten, die man aus den Gruppenaxiomen folgern kann. Dies wird in der mathematischen Logik durch den Folgerungsbegriff präzisiert.


Definition  

Es sei ein Symbolalphabet erster Stufe, eine Menge von -Ausdrücken und ein -Ausdruck. Man sagt, dass aus folgt, geschrieben , wenn für jede -Interpretation mit auch gilt.

Die Folgerungsbeziehung verwendet also (wie schon im aussagenlogischen Kontext) das gleiche Symbol wie die Gültigkeitsbeziehung. Dass aus einer gewissen Ausdrucksmenge ein gewisser Audruck folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit gewissen zusätzlichen Strukturen, die erfüllt, stets auch erfüllen muss.


Beispiel  

In einer Gruppe ist das inverse Element zu einem jeden Element, das es aufgrund der Definition einer Gruppe geben muss, eindeutig bestimmt. Mathematisch wird dies so bewiesen: Sei das neutrale Element der Gruppe, sei vorgegeben und seien inverse Elemente zu , d.h. es gelte und . Dann ist insgesamt

Die Eindeutigkeit des inversen Elementes kann man mit den Symbolen , wobei eine Konstante und ein zweistelliges Funktionssymbol ist, als den Ausdruck

ansetzen, und die obige mathematische Argumentation bedeutet, dass der Ausdruck aus den Gruppenaxiomen folgt, also die Folgerungsbeziehung

vorliegt.


Da ein allgemeingültiger Ausdruck in jeder Interpretation gilt, kann man auch sagen, dass aus der leeren Ausdrucksmenge folgt, also gilt. Wenn die Gruppenaxiome sind, und die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das inverse Element ist, so ist

allgemeingültig.


Definition  

Es sei ein Symbolalphabet und es sei ein -Ausdruck in der Prädikatenlogik erster Stufe. Man nennt erfüllbar, wenn es eine -Interpretation mit gibt.

Für eine Ausdrucksmenge bedeutet die Erfüllbarkeit, dass die darin enthaltenen Ausdrücke simultan in einer Interpretation erfüllbar sind. Zwischen Allgemeingültigkeit und Erfüllbarkeit besteht die Beziehung, dass genau dann allgemeingültig ist, wenn die Negation nicht erfüllbar ist.

Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.


Lemma

Es gilt genau dann, wenn nicht erfüllbar ist.

Beweis

Siehe Aufgabe.