Syntaktische u. semantische Äq. von Termen

Bsp. E = {P(Z, y) $\approx$ y, P(S(x), y) $\approx$ S(P(x, y))} .

• syntaktische Äquivalenz: $\approx_{E}^{}$

• semantische Äquivalenz: E $\models$ s $\approx$ t

  • Def. E $\models$ s $\approx$ t : für jedes Modell A von E gilt A $\models$ s $\approx$ t .
  • Bsp: E $\models$ P(S(S(Z)), y) $\approx$ S(S(y)) .
  • Übung: gilt E $\models$ P(x, y) $\approx$ P(y, x) ?

Satz (Birkhoff): s $\approx_{E}^{}$ t$\iff$E $\models$ s $\approx$ t .