Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision Next revision Both sides next revision | ||
|
sav08:non-ground_instantiation_and_resolution [2008/04/01 16:00] vkuncak created |
sav08:non-ground_instantiation_and_resolution [2008/04/01 16:21] vkuncak |
||
|---|---|---|---|
| Line 39: | Line 39: | ||
| If we try to do the proof, how do we know what to instantiate with? ++|we instantiate to enable subsequent resolution rule.++ | If we try to do the proof, how do we know what to instantiate with? ++|we instantiate to enable subsequent resolution rule.++ | ||
| - | Resolution with instantiation: | + | **Resolution with instantiation** |
| \[ | \[ | ||
| \frac{C \cup \{\lnot A_1\}\ \ \ D \cup \{A_2\}} | \frac{C \cup \{\lnot A_1\}\ \ \ D \cup \{A_2\}} | ||
| {subst(\sigma,C \cup D)} | {subst(\sigma,C \cup D)} | ||
| \] | \] | ||
| - | such that $subst(\sigma,A_1) = subst(\sigma,A_2)$. | + | such that $subst(\sigma)(A_1) = subst(\sigma)(A_2)$. |
| - | Note: $\sigma$ such that $subst(\sigma,A_1) = subst(\sigma,A_2)$ is called a **unifier** for $\{A_1,A_2\}$. | + | Note: $\sigma$ such that $subst(\sigma)(A_1) = subst(\sigma)(A_2)$ is called a **unifier** for $\{A_1,A_2\}$. |
| - | Does resolution with instantiation subsume: | + | **Factoring with instantiation** |
| - | * ++non-ground resolution rule?|yes, take empty substitution++ | + | \[ |
| - | * ++instantiation rule?|not by itself++ | + | \frac{C \cup \{A_1, A_2\}} |
| + | {subst(\sigma,C \cup D)} | ||
| + | \] | ||
| + | where $subst(\sigma)(A_1)=subst(\sigma)(A_2)$. | ||
| Further step: do we need to consider all unifiers? | Further step: do we need to consider all unifiers? | ||
| - | Most general unifier. | + | Most general unifier. To compute it we can use the standard [[Unification]] algorithm. |