Matthias Bernauer - Freiburg im Breisgau
      Start > Skript-Sammlung > Logik > Induktion über Relationskalkül >>







Induktion über Relationskalkül



Satz :
Will man zeigen, dass alle Elemente einer Menge M, die mit den Regeln des Kalküls K ableitbar sind, eine Eigenschaft E haben, so genügt hierzu der Nachweis, dass für jede Regel

m1,...,mr

m

des Kalküls K gilt: Wenn m1,...,mn in K ableitbar sind und die Eigenschaft E haben (Induktionsvoraussetzung), so hat auch m die Eigenschaft E. Im Fall r=0 müssen wir also zeigen, dass m die Eigenschaft E hat (Induktionsanfang).




Satz :
Beweis durch Induktion über dem Ausdruckskalkül (über den Aufbau der Ausdrücke):
Um nachzuweisen, dass alle aussagenlogischen Ausdrücke eine Eigenschaft E haben, reicht es zu zeigen:
  1. Jede Aussagenvariable hat die Eigenschaft E.
  2. Hat der Ausdruck a die Eigenschaft E, so auch Øa.
  3. Haben die Ausdrücke a und b die Eigenschaft E, so auch (aÙb) und (aÚb).


    Lemma : Intiutiv: Ersetzt man in einer äquivalenz überall Y1, Œ, Yn durch Ausdrücke g1, Œ, gn, so bleibt die äquivalenz erhalten.

    Y1, Œ, Yn seien paarweise verschieden und g, Œ, gn Î AA. Für a Î AA definieren wir a \dfracg1 ŒgnY1 ŒYn durch Induktion über a

Google MSN Suche
Matthias Bernauer