Mixing
Logical consequence relation
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
How to check whether formulas have logical consequence relation or not ?
Consider the problems:
$forall xA&forall xB |= forall x(A&B) $
$forall x P&E exists Q&R |= P&Q&R$
$forall x(P implies Q lor R) |= forall xP implies Q lor R$
Where $|=$ logical consequence relation.
I can solve this problem without quantifiers using the implication instead of $|=$ and trying to find out counterexample, but with quantifiers I don't know what is the algorithm to solve this kind of problems ?
logic
asked Jul 31 at 18:22
Kevin
184
 |Â
show 1 more comment
up vote
1
down vote
favorite
How to check whether formulas have logical consequence relation or not ?
Consider the problems:
$forall xA&forall xB |= forall x(A&B) $
$forall x P&E exists Q&R |= P&Q&R$
$forall x(P implies Q lor R) |= forall xP implies Q lor R$
Where $|=$ logical consequence relation.
I can solve this problem without quantifiers using the implication instead of $|=$ and trying to find out counterexample, but with quantifiers I don't know what is the algorithm to solve this kind of problems ?
logic
asked Jul 31 at 18:22
Kevin
184
I assume that when it says $forall x A$ it is assumed that $A$ may have $x$ as a free variable? As such, can we write this as $forall x A(x)$?
– Bram28
Jul 31 at 18:29
@Bram28 yes, I forgot to write it
– Kevin
Jul 31 at 18:31
No problem! Now, do you have any thoughts about these? The first one should be fairly easy ... Oh, and the second one has something weird going on; please check the formula
– Bram28
Jul 31 at 18:36
@Bram28 for second seems like in my text book they forgot to add some brackets, therefore I don't exactly know what is the right form of it
– Kevin
Jul 31 at 18:37
OK, but what's the $Eexists Q$ part? That seems like a typo ... should that just be $exists Q$? And the right hand side has no quantifiers at all?
– Bram28
Jul 31 at 19:19
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
How to check whether formulas have logical consequence relation or not ?
Consider the problems:
$forall xA&forall xB |= forall x(A&B) $
$forall x P&E exists Q&R |= P&Q&R$
$forall x(P implies Q lor R) |= forall xP implies Q lor R$
Where $|=$ logical consequence relation.
I can solve this problem without quantifiers using the implication instead of $|=$ and trying to find out counterexample, but with quantifiers I don't know what is the algorithm to solve this kind of problems ?
logic
asked Jul 31 at 18:22
Kevin
184
How to check whether formulas have logical consequence relation or not ?
Consider the problems:
$forall xA&forall xB |= forall x(A&B) $
$forall x P&E exists Q&R |= P&Q&R$
$forall x(P implies Q lor R) |= forall xP implies Q lor R$
Where $|=$ logical consequence relation.
I can solve this problem without quantifiers using the implication instead of $|=$ and trying to find out counterexample, but with quantifiers I don't know what is the algorithm to solve this kind of problems ?
logic
asked Jul 31 at 18:22
Kevin
184
asked Jul 31 at 18:22
Kevin
184
asked Jul 31 at 18:22
Kevin
184
asked Jul 31 at 18:22
Kevin
184
184
I assume that when it says $forall x A$ it is assumed that $A$ may have $x$ as a free variable? As such, can we write this as $forall x A(x)$?
– Bram28
Jul 31 at 18:29
@Bram28 yes, I forgot to write it
– Kevin
Jul 31 at 18:31
No problem! Now, do you have any thoughts about these? The first one should be fairly easy ... Oh, and the second one has something weird going on; please check the formula
– Bram28
Jul 31 at 18:36
@Bram28 for second seems like in my text book they forgot to add some brackets, therefore I don't exactly know what is the right form of it
– Kevin
Jul 31 at 18:37
OK, but what's the $Eexists Q$ part? That seems like a typo ... should that just be $exists Q$? And the right hand side has no quantifiers at all?
– Bram28
Jul 31 at 19:19
 |Â
show 1 more comment
I assume that when it says $forall x A$ it is assumed that $A$ may have $x$ as a free variable? As such, can we write this as $forall x A(x)$?
– Bram28
Jul 31 at 18:29
@Bram28 yes, I forgot to write it
– Kevin
Jul 31 at 18:31
No problem! Now, do you have any thoughts about these? The first one should be fairly easy ... Oh, and the second one has something weird going on; please check the formula
– Bram28
Jul 31 at 18:36
@Bram28 for second seems like in my text book they forgot to add some brackets, therefore I don't exactly know what is the right form of it
– Kevin
Jul 31 at 18:37
OK, but what's the $Eexists Q$ part? That seems like a typo ... should that just be $exists Q$? And the right hand side has no quantifiers at all?
– Bram28
Jul 31 at 19:19
I assume that when it says $forall x A$ it is assumed that $A$ may have $x$ as a free variable? As such, can we write this as $forall x A(x)$?
– Bram28
Jul 31 at 18:29
I assume that when it says $forall x A$ it is assumed that $A$ may have $x$ as a free variable? As such, can we write this as $forall x A(x)$?
– Bram28
Jul 31 at 18:29
@Bram28 yes, I forgot to write it
– Kevin
Jul 31 at 18:31
@Bram28 yes, I forgot to write it
– Kevin
Jul 31 at 18:31
No problem! Now, do you have any thoughts about these? The first one should be fairly easy ... Oh, and the second one has something weird going on; please check the formula
– Bram28
Jul 31 at 18:36
No problem! Now, do you have any thoughts about these? The first one should be fairly easy ... Oh, and the second one has something weird going on; please check the formula
– Bram28
Jul 31 at 18:36
@Bram28 for second seems like in my text book they forgot to add some brackets, therefore I don't exactly know what is the right form of it
– Kevin
Jul 31 at 18:37
@Bram28 for second seems like in my text book they forgot to add some brackets, therefore I don't exactly know what is the right form of it
– Kevin
Jul 31 at 18:37
OK, but what's the $Eexists Q$ part? That seems like a typo ... should that just be $exists Q$? And the right hand side has no quantifiers at all?
– Bram28
Jul 31 at 19:19
OK, but what's the $Eexists Q$ part? That seems like a typo ... should that just be $exists Q$? And the right hand side has no quantifiers at all?
– Bram28
Jul 31 at 19:19
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
As it turns out, there is no algorithm that can check for consequence that works for any problem like this.
However, there are several methods and algorithms that often do work.
Maybe the easiest thing to do is to try and generate a counterexample: think of a domain of objects, and provide interpretations for the predicates involved so that the left hand side is true, but the right hand side is not ... if you can find such a counterexample: great; you got your answer; the statement on the right is not a consequence of the one on the left. If you can't find a counterexample ... try a little harder ... and if you still can't find one ... well, maybe it is time to see if you can derive the right side from the left side using rules of equivalence or inference. ... Are you provided with any such rules?
A very nice method that is able to figure out consequence as well as non-consequence is the tree or tableaux method ... but this will take a bit of explanation (if you're interested, just search for it online) .. and I am not sure that that is what your instructor is looking for anyway ...
answered Jul 31 at 18:32
Bram28
54.6k33880
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
As it turns out, there is no algorithm that can check for consequence that works for any problem like this.
However, there are several methods and algorithms that often do work.
Maybe the easiest thing to do is to try and generate a counterexample: think of a domain of objects, and provide interpretations for the predicates involved so that the left hand side is true, but the right hand side is not ... if you can find such a counterexample: great; you got your answer; the statement on the right is not a consequence of the one on the left. If you can't find a counterexample ... try a little harder ... and if you still can't find one ... well, maybe it is time to see if you can derive the right side from the left side using rules of equivalence or inference. ... Are you provided with any such rules?
A very nice method that is able to figure out consequence as well as non-consequence is the tree or tableaux method ... but this will take a bit of explanation (if you're interested, just search for it online) .. and I am not sure that that is what your instructor is looking for anyway ...
answered Jul 31 at 18:32
Bram28
54.6k33880
add a comment |Â
up vote
0
down vote
accepted
As it turns out, there is no algorithm that can check for consequence that works for any problem like this.
However, there are several methods and algorithms that often do work.
Maybe the easiest thing to do is to try and generate a counterexample: think of a domain of objects, and provide interpretations for the predicates involved so that the left hand side is true, but the right hand side is not ... if you can find such a counterexample: great; you got your answer; the statement on the right is not a consequence of the one on the left. If you can't find a counterexample ... try a little harder ... and if you still can't find one ... well, maybe it is time to see if you can derive the right side from the left side using rules of equivalence or inference. ... Are you provided with any such rules?
A very nice method that is able to figure out consequence as well as non-consequence is the tree or tableaux method ... but this will take a bit of explanation (if you're interested, just search for it online) .. and I am not sure that that is what your instructor is looking for anyway ...
answered Jul 31 at 18:32
Bram28
54.6k33880
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
As it turns out, there is no algorithm that can check for consequence that works for any problem like this.
However, there are several methods and algorithms that often do work.
Maybe the easiest thing to do is to try and generate a counterexample: think of a domain of objects, and provide interpretations for the predicates involved so that the left hand side is true, but the right hand side is not ... if you can find such a counterexample: great; you got your answer; the statement on the right is not a consequence of the one on the left. If you can't find a counterexample ... try a little harder ... and if you still can't find one ... well, maybe it is time to see if you can derive the right side from the left side using rules of equivalence or inference. ... Are you provided with any such rules?
A very nice method that is able to figure out consequence as well as non-consequence is the tree or tableaux method ... but this will take a bit of explanation (if you're interested, just search for it online) .. and I am not sure that that is what your instructor is looking for anyway ...
answered Jul 31 at 18:32
Bram28
54.6k33880
As it turns out, there is no algorithm that can check for consequence that works for any problem like this.
However, there are several methods and algorithms that often do work.
Maybe the easiest thing to do is to try and generate a counterexample: think of a domain of objects, and provide interpretations for the predicates involved so that the left hand side is true, but the right hand side is not ... if you can find such a counterexample: great; you got your answer; the statement on the right is not a consequence of the one on the left. If you can't find a counterexample ... try a little harder ... and if you still can't find one ... well, maybe it is time to see if you can derive the right side from the left side using rules of equivalence or inference. ... Are you provided with any such rules?
A very nice method that is able to figure out consequence as well as non-consequence is the tree or tableaux method ... but this will take a bit of explanation (if you're interested, just search for it online) .. and I am not sure that that is what your instructor is looking for anyway ...
answered Jul 31 at 18:32
Bram28
54.6k33880
answered Jul 31 at 18:32
Bram28
54.6k33880
answered Jul 31 at 18:32
Bram28
54.6k33880
answered Jul 31 at 18:32
Bram28
54.6k33880
54.6k33880
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868331%2flogical-consequence-relation%23new-answer', 'question_page');
);
Post as a guest
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
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
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
I assume that when it says $forall x A$ it is assumed that $A$ may have $x$ as a free variable? As such, can we write this as $forall x A(x)$?
– Bram28
Jul 31 at 18:29
@Bram28 yes, I forgot to write it
– Kevin
Jul 31 at 18:31
No problem! Now, do you have any thoughts about these? The first one should be fairly easy ... Oh, and the second one has something weird going on; please check the formula
– Bram28
Jul 31 at 18:36
@Bram28 for second seems like in my text book they forgot to add some brackets, therefore I don't exactly know what is the right form of it
– Kevin
Jul 31 at 18:37
OK, but what's the $Eexists Q$ part? That seems like a typo ... should that just be $exists Q$? And the right hand side has no quantifiers at all?
– Bram28
Jul 31 at 19:19