Rückführung in Aussagenlogik

Question

Zeigen Sie durch Rückführung auf die Definition, dass für beliebige Formeln F und beliebige Interpretationen I = (A, α) die folgende Äquivalenz

gilt: A |= α ∃x.∃y.F <=> A |=α ∃y.∃x.F

Hallo,

das ist die letzte Aufgabe für dieses Jahr und leider weiß ich nicht wei ich die machen soll. Wenn sich jemand in Logik auskennt würde ich mich über eine Hilfe freuen.

LG

Answer 1

Sei A |=_α ∃x.∃y.F.

Sei a ∈ A , so dass A |= _α[x→a] ∃y.F gilt. Ein solches a existiert laut Semantik der Prädikatenlogik.

Dabei ist α_[x→a] die Belegung, die man aus α erhält indem man der Variablen x den Wert a zuweißt.

Sei b ∈ A , so dass A |= _{α[x→a,y→b]} F gilt. Ein solches b existiert laut Semantik der Prädikatenlogik.

Dann ist A |= _α[y→b] ∃x.F und somit auch A |= _α ∃y.∃x.F