Unification in First Order Logic Resolution
up vote
0
down vote
favorite
I struggling to understand the intuition behind the following first order resolution problem:
Using resolution, show that
begin{equation} F = forall x (P(x) wedgeneg P(f(x)) end{equation}
is unsatisfiable, where $P$ is a predicate and $f$ is a function.
I got the following:
The set of clauses is $${{P(x)},{neg P(f(x)}}$$
So we can rename $x$ in the first clause to $z$ and then substitute $theta = {z|f(x)}$ giving us $${{P(f(x))},{neg P(f(x)}}$$
which we can resolve to
$$frac{{{P(f(x))},{neg P(f(x)}}}{{}}$$
and thus $F$ is unsatisfiable.
But what i don't get is why $x$ in the second clause is not affected by the renaming. I can see that the substitution would then lead to infinite recursion, which is obviously not desirable.
What is the intuition behind this and why can we do it?
first-order-logic substitution unification
asked Nov 21 at 10:47
hh32
1083
add a comment |
up vote
0
down vote
favorite
I struggling to understand the intuition behind the following first order resolution problem:
Using resolution, show that
begin{equation} F = forall x (P(x) wedgeneg P(f(x)) end{equation}
is unsatisfiable, where $P$ is a predicate and $f$ is a function.
I got the following:
The set of clauses is $${{P(x)},{neg P(f(x)}}$$
So we can rename $x$ in the first clause to $z$ and then substitute $theta = {z|f(x)}$ giving us $${{P(f(x))},{neg P(f(x)}}$$
which we can resolve to
$$frac{{{P(f(x))},{neg P(f(x)}}}{{}}$$
and thus $F$ is unsatisfiable.
But what i don't get is why $x$ in the second clause is not affected by the renaming. I can see that the substitution would then lead to infinite recursion, which is obviously not desirable.
What is the intuition behind this and why can we do it?
first-order-logic substitution unification
asked Nov 21 at 10:47
hh32
1083
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I struggling to understand the intuition behind the following first order resolution problem:
Using resolution, show that
begin{equation} F = forall x (P(x) wedgeneg P(f(x)) end{equation}
is unsatisfiable, where $P$ is a predicate and $f$ is a function.
I got the following:
The set of clauses is $${{P(x)},{neg P(f(x)}}$$
So we can rename $x$ in the first clause to $z$ and then substitute $theta = {z|f(x)}$ giving us $${{P(f(x))},{neg P(f(x)}}$$
which we can resolve to
$$frac{{{P(f(x))},{neg P(f(x)}}}{{}}$$
and thus $F$ is unsatisfiable.
But what i don't get is why $x$ in the second clause is not affected by the renaming. I can see that the substitution would then lead to infinite recursion, which is obviously not desirable.
What is the intuition behind this and why can we do it?
first-order-logic substitution unification
asked Nov 21 at 10:47
hh32
1083
I struggling to understand the intuition behind the following first order resolution problem:
Using resolution, show that
begin{equation} F = forall x (P(x) wedgeneg P(f(x)) end{equation}
is unsatisfiable, where $P$ is a predicate and $f$ is a function.
I got the following:
The set of clauses is $${{P(x)},{neg P(f(x)}}$$
So we can rename $x$ in the first clause to $z$ and then substitute $theta = {z|f(x)}$ giving us $${{P(f(x))},{neg P(f(x)}}$$
which we can resolve to
$$frac{{{P(f(x))},{neg P(f(x)}}}{{}}$$
and thus $F$ is unsatisfiable.
But what i don't get is why $x$ in the second clause is not affected by the renaming. I can see that the substitution would then lead to infinite recursion, which is obviously not desirable.
What is the intuition behind this and why can we do it?
first-order-logic substitution unification
first-order-logic substitution unification
asked Nov 21 at 10:47
hh32
1083
asked Nov 21 at 10:47
hh32
1083
asked Nov 21 at 10:47
hh32
1083
asked Nov 21 at 10:47
hh32
1083
asked Nov 21 at 10:47
hh32
1083
1083
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3007555%2funification-in-first-order-logic-resolution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
