Koinzidenzlemma

Aufrufe: 96     Aktiv: 09.02.2024 um 00:26

0
Sei Var_AL eine nicht-leere endliche Menge von aussagenlogischen Variablen und sei P ∈ Var_AL eine aussagenlogische Variable. Zeigen Sie die folgende Behauptung mittels struktureller Induktion über aussagenlogischen Formeln: Für eine beliebige aussagenlogische Formel F, in der P nicht vorkommt, und Interpretationen I, I′ mit I(P) ≠ I′(P) und I(Q) = I′(Q) für alle Q ∈ Var_AL \ {P} gilt val_I (F) = val_I′ (F)


Kann mir hier jemand weiterhelfen ich. Ich erkenn shon nicht die Basisfälle leider
Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0
Ich vermute, hier wird vollständige Induktion abgeragt, nur dass die Induktionskette nicht 1\(\rightarrow\)2\(\rightarrow\)3\(\rightarrow\)4\(\rightarrow\).... lautet, sondern immer komplexer werdende logische Formeln, also:
elementare Formeln \(\rightarrow\) Formeln, die mit einem logischen Operator aus elemetaren elementare Formeln \(\rightarrow\) Formeln mit einem logischen Operator aus letzteren Formeln gebildet wurden \(\rightarrow\)... .

Den Induktionsanfang bilden alle elementaren Formeln F, also Formeln, die
  1. aus nichts bestehen als einer einzelnen aussagenlogischen Variable.
  2. aus nichts bestehen aus nichts als den Konstanten "wahr" oder "falsch"
Im 2. Falle ist die Aussage trivial.
Im 1. Falle, wenn in dieser Formel P nicht vorkommt, ist F eine Variable, die nicht gleich P ist.
Wegen  \(I(Q) =I'(Q) \;\forall \mbox{Var}_\mbox{AL} \)  gilt  \(\mbox{val}_I(F)=I(Q)=I'(Q)=\mbox{val}_{I'}(F)\).

Die Induktionsvoraussetzung geht so: Für alle Formeln mit \(\le n\) logischen Operatoren gilt \(\mbox{val}_I(F)=\mbox{val}_{I'}(F)\).
Der Induktionsschluss geht so: Sei F eine Formel mit n+1 logischen Operaroren, und ohne P. Dann hat F eine der folgenden Alternativen:
  1. \(F = F' \wedge F"\)
  2. \(F = F' \vee F"\)
  3. \(F = \neg F'\)
  4. evtl. weitere
Dann können die \(F'\) und \(F''\) P nicht enthalten, und nach Induktionsvoraussetzung gilt dann:
\(\mbox{val}_I(F')=\mbox{val}_{I'}(F')\)
\(\mbox{val}_I(F'')=\mbox{val}_{I'}(F'')\).
Dann gilt auch, wie man leicht nachrechnet, in allen drei Fällen, \(\mbox{val}_I(F)=\mbox{val}_{I'}(F)\).
Diese Antwort melden
geantwortet

Punkte: 2.19K

 

Kommentar schreiben