Aufgaben

Signatur (mit Stelligkeiten): Σ = {e⁰, s¹, p², m², h²}

• R_p = {p(e, y)→y, p(s(x), y)→s(p(x, y))}
• R_m = R_p∪{m(e, y)→e, m(s(x), y)→p(m(x, y), y)}
• R_h = R_m∪{h(x, e)→s(e), h(x, s(y))→m(h(x, y), x)}

Fragen (leicht):

• Menge der R_h -Normalformen?
• Normalformen (Existenz? Eindeutigkeit?) von: p(s(p(s(e), s(e))), s(e)) , m(s(s(e)), s(s(e))) , h(s(s(e)), s(s(s(e)))) .

(schwerer) Σ = {a², d⁰}, R = {a(a(d, x), y)→a(x, a(x, y))} : Normalformen? Ableitungslängen?