Seite parallel anzeigen





Du befindest dich hier: Aussagenlogik / Umwandlung von Formeln

Substitution

(Aussagenlogik Kapitel 6.1)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Jede Formel kann als Formelschema angesehen werden, indem man die Variablen (in der Aussagenlogik die Atome) als Platzhalter für beliebige Formeln interpretiert.

Eine Substitution auf eine Formel anzuwenden, bedeutet, alle Vorkommen bestimmter Variablen durch andere Formeln zu ersetzen.

In der Aussagenlogik ist eine Substitution also eine Ersetzung von Atomen einer Formel durch beliebige Formeln.

Beispiel - Substitution

Betrachten wir die Formel
  • γ = p->p|q
Substituieren (ersetzen) wir
  • p durch x|!y und
  • q durch !x&y,
so erhalten wir
  • δ = x|!y->x|!y|!x&y
Man kann zeigen, dass die Gültigkeit oder die Unerfüllbarkeit der Ursprungsformel erhalten bleibt - eine gültige Formel bleibt gültig, eine unerfüllbare Formel unerfüllbar.
Wendet man die gleiche Substitution auf zwei äquivalente Formeln an, bleibt die Äquivalenz erhalten.

Beispiel - Substitution ist gültigkeitserhaltend

Betrachten wir das obige Beispiel:
Da γ gültig ist, ist auch δ gültig, wie an den folgenden Tabellen zu sehen ist.
p q p|q p->p|q
0  0  0  1 
0  1  1  1 
1  0  1  1 
1  1  1  1 
x y !y x|!y !x !x&y x|!y|!x&y x|!y->x|!y|!x&y
0  0  1  1  1  0  1  1 
0  1  0  0  1  1  1  1 
1  0  1  1  0  0  1  1 
1  1  0  1  0  0  1  1 

Beispiel - Gleiche Substitution auf äquivalenten Formeln ist äquivalenzerhaltend

Wir haben im Kapitel "Formeln & Interpretationen" gezeigt, dass die folgenden zwei Formeln äquvalent sind:
  • γ = !(a&b), und
  • δ = !a|!b.
Betrachten wir γ und δ als Formelschemata und substituieren wir z.B.
  • a durch !p und
  • b durch !q,
so erhalten wir
  • γ' = !(!p&!q), und
  • δ' = !!p|!!q

Wie die folgenden Tabellen zeigen, gilt
  • γ' ≡ δ'
p q !p !q !p&!q !(!p&!q)
0  0  1  1  1  0 
0  1  1  0  0  1 
1  0  0  1  0  1 
1  1  0  0  0  1 
p q !p !!p !q !!q !!p|!!q
0  0  1  0  1  0  0 
0  1  1  0  0  1  1 
1  0  0  1  1  0  1 
1  1  0  1  0  1  1 
Nun wissen wir also, was eine Substitution ist und welche Konsequenzen sie hat.
Als nächstes wollen wir uns ansehen, was es bedeutet, ganze Teilformeln zu ersetzen.