题目

COMP30026_2025_SM2 Worksheet 5

多重下拉选择题

For each of the following pairs of expressions, either choose a most general unifier (mgu) for them or indicate that they are not unifiable. P(f(a, x, y)) and P(f(a, b, u)) [ Select ] {x→b, y→u, y→a} {x→b, y→u} {x→b, y→f(b)} {b→x, y→u} Not unifiable {x→f(f(x)), y→f(x)} {x→b, y→f(b), u→b} g(x, y, b)) and f(a, b, b) [ Select ] {x→b, y→u} {x→f(f(x)), y→f(x)} {x→b, y→f(b)} {x→b, y→f(b), u→b} No unification is possible {x→b, y→u, y→a} P(g(y, u), b, f(x)) and P(g(f(u), u), x, y) [ Select ] {x→b, y→f(b)} {x→b, y→f(b), u→b} {x→b, y→u, y→a} {x→f(f(x)), y→f(x)} No unification is possible {x→b, y→u} f(g(a), g(h(a, b)), x) and f(g(x), g(y)) [ Select ] {x→f(f(x)), y→f(x)} {x→b, y→u, y→a} {x→b, y→u} {x→b, y→f(b)} No unification is possible {x→b, y→f(b), u→b} P(x, y) and P(f(y), f(x)) [ Select ] {x→b, y→u} {x→f(f(x)), y→f(x)} {x→b, y→f(b), u→b} {x→b, y→f(b)} No unification is possible {x→b, y→u, y→a} Hint: If you can't tell at a glance, use the algorithm! Check your work by performing the substitution.

查看解析

标准答案

Please login to view

思路分析

We will tackle each pair of expressions in turn, restating the problem and then examining the provided selected option for that pair. For every option, we explain why it would or would not be a correct most general unifier (MGU), drawing on standard unification rules (structure must match, function symbols must agree, arity must match, and substitutions must be consistent). 1) Pair: P(f(a, x, y)) and P(f(a, b, u)) Selected option: {x→b, y→u} Analysis: To unify P(f(a, x, y)) with P(f(a, b, u)), the outer predicate symbol P matches, and we must unify the inner terms f(a, x, y) with f(a, b, u). For two n-ary terms to unify, corresponding arguments must unify pairwise: a with a (already identical), x with b, and y with u. Therefore the most straightforward unifier is x → b and y → u. This substitution simultaneously makes the second and third arguments match, since f(a, b, u) becomes f(a, x, y) under the inverse view. Note that no additional substitutions are required, a......Login to view full explanation