Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:instantiation_plus_ground_resolution [2008/04/01 18:19] vkuncak |
sav08:instantiation_plus_ground_resolution [2009/05/14 11:57] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Gdound Instantiation plus Ground Resolution as a Proof System ====== | + | ====== Ground Instantiation plus Ground Resolution as a Proof System ====== |
We introduce this proof system as an intermediate step between the naive enumeration algorithm based on Herbrand's theorem and resolution for first-order logic. | We introduce this proof system as an intermediate step between the naive enumeration algorithm based on Herbrand's theorem and resolution for first-order logic. | ||
Line 29: | Line 29: | ||
==== Example ==== | ==== Example ==== | ||
+ | |||
===== Completeness ===== | ===== Completeness ===== | ||
Line 34: | Line 35: | ||
The proof is based on [[Herbrand's Expansion Theorem]] (see also the proof of [[Compactness for First-Order Logic]]). | The proof is based on [[Herbrand's Expansion Theorem]] (see also the proof of [[Compactness for First-Order Logic]]). | ||
- | Suppose a set $S$ of clauses is contradictory. By [[Herbrand's Expansion Theorem]] and [[Compactness Theorem|Compactness Theorem for Propositional Formulas]], there is some finite subset $S_0 \subseteq expand(S)$ is contradictory. Then there exists a derivation of empty clause from $S_0$ viewed as set of propositional formulas, using propositional resolution. In other words, there exists a derivation of empty clause from $S_0$ using ground resolution rule. Each element of $S_0$ can be obtained from an element of $S$ using instantiation rule. This means that there exists a proof tree that starts by a single application of instantiation rule, and then performs ground resolution. | + | Suppose a set $S$ of clauses is contradictory. By [[Herbrand's Expansion Theorem]] and [[Compactness Theorem|Compactness Theorem for Propositional Formulas]], there is some finite subset $S_0 \subseteq expand(S)$ is contradictory. Then there exists a derivation of empty clause from $S_0$ viewed as set of propositional formulas, using propositional resolution. In other words, there exists a derivation of empty clause from $S_0$ using ground resolution rule. Each element of $S_0$ can be obtained from an element of $S$ using instantiation rule. This means that there exists a proof tree whose leaves are followed by a single application of instantiation rule, and inner nodes contain ground resolution steps. |