Vollfreie Variable

Eine Variable bezeichnet man als vollfrei in einer Formel der Prädikatenlogik, wenn sie in der Formel an wenigstens einer Stelle vorkommt, aber nirgendwo innerhalb der Formel quantifiziert ist.

Die Unterscheidung zwischen freien und vollfreien Variablen ist technischer Natur. Für die logische Bedeutung einer Formel ist sie ohne Relevanz, da man jede Formel durch gebundene Umbenennung in eine logisch äquivalente umformen kann, in der alle freien Variablen tatsächlich vollfrei sind.

Beispiele

• In der Formel ${\displaystyle P(x)\land Q(x,y)}$ sind sowohl ${\displaystyle x}$ als auch ${\displaystyle y}$ vollfreie Variablen.
• In der Formel ${\displaystyle P(x)\land \forall x\ Q(x,y)}$ ist ${\displaystyle y}$ vollfrei, ${\displaystyle x}$ hingegen nicht, da ${\displaystyle x}$ sowohl ein freies als auch ein gebundenes Vorkommen hat.

• Aus der Formel ${\displaystyle P(x)\land \forall x\ Q(x,y)}$ kann man durch gebundene Umbenennung die logisch äquivalente Formel ${\displaystyle P(x)\land \forall z\ Q(z,y)}$ erhalten, in der beide freien Variablen ${\displaystyle x}$ und ${\displaystyle y}$ vollfrei sind.

Weblinks

• Vorlesungsskriptum „Logische Grundlagen der Informatik“ (PDF-Datei; 1,07 MB)