Mixing
How to prove the following formula using an indirect proof
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far.
From here I'm stuck (and I'm not even sure if this is correct). My idea is to use negation intro by assuming the opposite and coming up with a contradiction. I assumed $A$ which led to $B vee C$ and, as you can see, I'm trying or elim but the only way I can think of doing this is to use conditional intro and then or intro but that seems to only work for a single subproof. In other words, I can't use the assumption of $B$ to say $A to B$. This is called an indirect proof.
logic proof-writing propositional-calculus natural-deduction formal-proofs
edited Jan 27 at 0:54
Bram28
63.8k44793
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
$endgroup$
add a comment |
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far.
From here I'm stuck (and I'm not even sure if this is correct). My idea is to use negation intro by assuming the opposite and coming up with a contradiction. I assumed $A$ which led to $B vee C$ and, as you can see, I'm trying or elim but the only way I can think of doing this is to use conditional intro and then or intro but that seems to only work for a single subproof. In other words, I can't use the assumption of $B$ to say $A to B$. This is called an indirect proof.
logic proof-writing propositional-calculus natural-deduction formal-proofs
edited Jan 27 at 0:54
Bram28
63.8k44793
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
$endgroup$
add a comment |
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far.
From here I'm stuck (and I'm not even sure if this is correct). My idea is to use negation intro by assuming the opposite and coming up with a contradiction. I assumed $A$ which led to $B vee C$ and, as you can see, I'm trying or elim but the only way I can think of doing this is to use conditional intro and then or intro but that seems to only work for a single subproof. In other words, I can't use the assumption of $B$ to say $A to B$. This is called an indirect proof.
logic proof-writing propositional-calculus natural-deduction formal-proofs
edited Jan 27 at 0:54
Bram28
63.8k44793
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
$endgroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far.
From here I'm stuck (and I'm not even sure if this is correct). My idea is to use negation intro by assuming the opposite and coming up with a contradiction. I assumed $A$ which led to $B vee C$ and, as you can see, I'm trying or elim but the only way I can think of doing this is to use conditional intro and then or intro but that seems to only work for a single subproof. In other words, I can't use the assumption of $B$ to say $A to B$. This is called an indirect proof.
logic proof-writing propositional-calculus natural-deduction formal-proofs
logic proof-writing propositional-calculus natural-deduction formal-proofs
edited Jan 27 at 0:54
Bram28
63.8k44793
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
edited Jan 27 at 0:54
Bram28
63.8k44793
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
edited Jan 27 at 0:54
Bram28
63.8k44793
edited Jan 27 at 0:54
Bram28
63.8k44793
edited Jan 27 at 0:54
Bram28
63.8k44793
63.8k44793
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
asked Jan 26 at 21:17
Josh SusaJosh Susa
785
785
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far. ...
A disjunction is usually proven by reduction to absurdity. Assume its negation and derive a contradiction. Typically this involves further assuming the negation of one disjunct aiming to derive the other. $$deffitch#1#2{quadbegin{array}{|l}#1\hline #2end{array}}fitch{Ato (Bvee C)}{fitch{lnot((Ato B)lor(Ato C))}{fitch{lnot (Ato B)}{fitch A{~vdots\C}\Ato C\(Ato B)vee(Ato C)\bot}\lnotlnot(Ato B)\Ato B\(Ato B)vee(Ato C)\bot}\lnotlnot((Ato B)vee(Ato C))\(Ato B)lor (Ato C)}$$
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
$endgroup$
add a comment |
$begingroup$
It is always a very bad sign when someone has started a bunch of subproofs without indicating what happens at the end of the subproof.
A proof should always have a plan or outline, and subproofs provide the skeleton to do so. But again, you need to indicate what you want to do with the subproof, and that involves indicating what you want as the last line of your subproof. You haven't done that for any of the three subproofs you started, which is exactly why you get in trouble, and get see the forest for the trees.
Now, it is clear that with your first subproof you are hoping to do a proof by contradiction. So, start by creating the proper setup for that:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B) lor (A rightarrow C))$
$quad text{... skip a bunch of lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
Ok, now that we have set that up properly, let's go back inside the subproof, and see how we can derive the contradiction from the premise and the assumption.
Now, it is at this point that you assume $A$. Why?
Actually, I think I know why, because I have seen it all too often: you are probably thinking "ooh, it would be nice to have $A$, because then I can combine that with the premise! OK, so let's jist assume $A$"
OK, the problem with this kind of thinking is that you end up assuming something that you want ... which is always a bad ide, as that will often lead to a circular proof. Indeed, suppose you were indeed to combone $A$ with the premise, and get $B lor C$ ... OK .... now what?! Well, one thing you can do is to then close the subproof and conclude $A rightarrow (B lor C)$ .... but note that now you just get the very premise, i.e. You are getting nowhere.
Here is some general advice on subproofs, that goes back to my initial point about having a plan: before starting any subproof, you should already know how you are going to use that subproof, and in particular, what the last line of your subproof should be, and what rule you will apply after the subproof is done.
Ok, let's regroup. There is really no good reason to assume $A$. Ok, but what should you do on line 3? Well, again, if you had $A$, you could combine that with the premise, but rather than assuming $A$, you could try and make $A$ your new goal. And, to prove $A$, one thing you could do is to assume $neg A$, and show that that leads to a contradiction.
However, there is a much more straightforward thing to do. The assumption $neg ((A rightarrow B) lor (A rightarrow C))$ is a negation of a disjunction, and you are probably aware of how by DeMorgan that is equivalent to the conjunction of the negated disjuncts, i.e. to $neg (A rightarrow B) land neg (A rightarrow C)$. Now, I suspect you don't have DeMorgan as an inference rule in your specific system, but think about it this way: apprently you should be able to derive both $neg (A rightarrow B)$ as well as $neg (A rightarrow C)$ from the Assumption. Now, both of those statements are negations, and you probably know the best strategy to prove negations: Proof bu Contradiction!
OK, so we have another piece of our plan:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B ) lor (A rightarrow C))$
$quad quad A rightarrow B$
$quad quad text{skip a few lines...}$
$quad quad bot$
$quad neg (A rightarrow B)$
$quad quad (A rightarrow C)$
$quad quad text{skip a few lines ...}$
$quad quad bot$
$quad neg (Arightarrow C)$
$quad text{few lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
OK, see how this is all nicely organized? How you now have an outline, to which you can add details and provide the missing steps at some later point? That is what you are supposed to do! That is how you keep your proof, and your very thinking organized. Indeed, the very point of doing formal logic proofs is to teach you that very skill of careful organization!
Now, I am going to leave those details to you, but leave you with one more hint: what is $neg (A rightarrow B)$ equivalent to? .... try and derive that, do the same for $neg (A rightarrow C)$, and you're pretty much done! Good luck!
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
$endgroup$
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
add a comment |
$begingroup$
Hint: if you assume $A to (B lor C)$, $lnot(A to B)$ and $A$, then you can conclude $B lor C$ and $lnot B$. Can you take it from there?
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
$endgroup$
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
|
show 18 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3088766%2fhow-to-prove-the-following-formula-using-an-indirect-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far. ...
A disjunction is usually proven by reduction to absurdity. Assume its negation and derive a contradiction. Typically this involves further assuming the negation of one disjunct aiming to derive the other. $$deffitch#1#2{quadbegin{array}{|l}#1\hline #2end{array}}fitch{Ato (Bvee C)}{fitch{lnot((Ato B)lor(Ato C))}{fitch{lnot (Ato B)}{fitch A{~vdots\C}\Ato C\(Ato B)vee(Ato C)\bot}\lnotlnot(Ato B)\Ato B\(Ato B)vee(Ato C)\bot}\lnotlnot((Ato B)vee(Ato C))\(Ato B)lor (Ato C)}$$
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
$endgroup$
add a comment |
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far. ...
A disjunction is usually proven by reduction to absurdity. Assume its negation and derive a contradiction. Typically this involves further assuming the negation of one disjunct aiming to derive the other. $$deffitch#1#2{quadbegin{array}{|l}#1\hline #2end{array}}fitch{Ato (Bvee C)}{fitch{lnot((Ato B)lor(Ato C))}{fitch{lnot (Ato B)}{fitch A{~vdots\C}\Ato C\(Ato B)vee(Ato C)\bot}\lnotlnot(Ato B)\Ato B\(Ato B)vee(Ato C)\bot}\lnotlnot((Ato B)vee(Ato C))\(Ato B)lor (Ato C)}$$
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
$endgroup$
add a comment |
$begingroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far. ...
A disjunction is usually proven by reduction to absurdity. Assume its negation and derive a contradiction. Typically this involves further assuming the negation of one disjunct aiming to derive the other. $$deffitch#1#2{quadbegin{array}{|l}#1\hline #2end{array}}fitch{Ato (Bvee C)}{fitch{lnot((Ato B)lor(Ato C))}{fitch{lnot (Ato B)}{fitch A{~vdots\C}\Ato C\(Ato B)vee(Ato C)\bot}\lnotlnot(Ato B)\Ato B\(Ato B)vee(Ato C)\bot}\lnotlnot((Ato B)vee(Ato C))\(Ato B)lor (Ato C)}$$
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
$endgroup$
I need to prove that the premise $A to (B vee C)$ leads to the conclusion $(A to B) vee (A to C)$. Here's what I have so far. ...
A disjunction is usually proven by reduction to absurdity. Assume its negation and derive a contradiction. Typically this involves further assuming the negation of one disjunct aiming to derive the other. $$deffitch#1#2{quadbegin{array}{|l}#1\hline #2end{array}}fitch{Ato (Bvee C)}{fitch{lnot((Ato B)lor(Ato C))}{fitch{lnot (Ato B)}{fitch A{~vdots\C}\Ato C\(Ato B)vee(Ato C)\bot}\lnotlnot(Ato B)\Ato B\(Ato B)vee(Ato C)\bot}\lnotlnot((Ato B)vee(Ato C))\(Ato B)lor (Ato C)}$$
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
answered Jan 31 at 1:24
Graham KempGraham Kemp
87.2k43579
87.2k43579
add a comment |
add a comment |
$begingroup$
It is always a very bad sign when someone has started a bunch of subproofs without indicating what happens at the end of the subproof.
A proof should always have a plan or outline, and subproofs provide the skeleton to do so. But again, you need to indicate what you want to do with the subproof, and that involves indicating what you want as the last line of your subproof. You haven't done that for any of the three subproofs you started, which is exactly why you get in trouble, and get see the forest for the trees.
Now, it is clear that with your first subproof you are hoping to do a proof by contradiction. So, start by creating the proper setup for that:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B) lor (A rightarrow C))$
$quad text{... skip a bunch of lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
Ok, now that we have set that up properly, let's go back inside the subproof, and see how we can derive the contradiction from the premise and the assumption.
Now, it is at this point that you assume $A$. Why?
Actually, I think I know why, because I have seen it all too often: you are probably thinking "ooh, it would be nice to have $A$, because then I can combine that with the premise! OK, so let's jist assume $A$"
OK, the problem with this kind of thinking is that you end up assuming something that you want ... which is always a bad ide, as that will often lead to a circular proof. Indeed, suppose you were indeed to combone $A$ with the premise, and get $B lor C$ ... OK .... now what?! Well, one thing you can do is to then close the subproof and conclude $A rightarrow (B lor C)$ .... but note that now you just get the very premise, i.e. You are getting nowhere.
Here is some general advice on subproofs, that goes back to my initial point about having a plan: before starting any subproof, you should already know how you are going to use that subproof, and in particular, what the last line of your subproof should be, and what rule you will apply after the subproof is done.
Ok, let's regroup. There is really no good reason to assume $A$. Ok, but what should you do on line 3? Well, again, if you had $A$, you could combine that with the premise, but rather than assuming $A$, you could try and make $A$ your new goal. And, to prove $A$, one thing you could do is to assume $neg A$, and show that that leads to a contradiction.
However, there is a much more straightforward thing to do. The assumption $neg ((A rightarrow B) lor (A rightarrow C))$ is a negation of a disjunction, and you are probably aware of how by DeMorgan that is equivalent to the conjunction of the negated disjuncts, i.e. to $neg (A rightarrow B) land neg (A rightarrow C)$. Now, I suspect you don't have DeMorgan as an inference rule in your specific system, but think about it this way: apprently you should be able to derive both $neg (A rightarrow B)$ as well as $neg (A rightarrow C)$ from the Assumption. Now, both of those statements are negations, and you probably know the best strategy to prove negations: Proof bu Contradiction!
OK, so we have another piece of our plan:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B ) lor (A rightarrow C))$
$quad quad A rightarrow B$
$quad quad text{skip a few lines...}$
$quad quad bot$
$quad neg (A rightarrow B)$
$quad quad (A rightarrow C)$
$quad quad text{skip a few lines ...}$
$quad quad bot$
$quad neg (Arightarrow C)$
$quad text{few lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
OK, see how this is all nicely organized? How you now have an outline, to which you can add details and provide the missing steps at some later point? That is what you are supposed to do! That is how you keep your proof, and your very thinking organized. Indeed, the very point of doing formal logic proofs is to teach you that very skill of careful organization!
Now, I am going to leave those details to you, but leave you with one more hint: what is $neg (A rightarrow B)$ equivalent to? .... try and derive that, do the same for $neg (A rightarrow C)$, and you're pretty much done! Good luck!
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
$endgroup$
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
add a comment |
$begingroup$
It is always a very bad sign when someone has started a bunch of subproofs without indicating what happens at the end of the subproof.
A proof should always have a plan or outline, and subproofs provide the skeleton to do so. But again, you need to indicate what you want to do with the subproof, and that involves indicating what you want as the last line of your subproof. You haven't done that for any of the three subproofs you started, which is exactly why you get in trouble, and get see the forest for the trees.
Now, it is clear that with your first subproof you are hoping to do a proof by contradiction. So, start by creating the proper setup for that:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B) lor (A rightarrow C))$
$quad text{... skip a bunch of lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
Ok, now that we have set that up properly, let's go back inside the subproof, and see how we can derive the contradiction from the premise and the assumption.
Now, it is at this point that you assume $A$. Why?
Actually, I think I know why, because I have seen it all too often: you are probably thinking "ooh, it would be nice to have $A$, because then I can combine that with the premise! OK, so let's jist assume $A$"
OK, the problem with this kind of thinking is that you end up assuming something that you want ... which is always a bad ide, as that will often lead to a circular proof. Indeed, suppose you were indeed to combone $A$ with the premise, and get $B lor C$ ... OK .... now what?! Well, one thing you can do is to then close the subproof and conclude $A rightarrow (B lor C)$ .... but note that now you just get the very premise, i.e. You are getting nowhere.
Here is some general advice on subproofs, that goes back to my initial point about having a plan: before starting any subproof, you should already know how you are going to use that subproof, and in particular, what the last line of your subproof should be, and what rule you will apply after the subproof is done.
Ok, let's regroup. There is really no good reason to assume $A$. Ok, but what should you do on line 3? Well, again, if you had $A$, you could combine that with the premise, but rather than assuming $A$, you could try and make $A$ your new goal. And, to prove $A$, one thing you could do is to assume $neg A$, and show that that leads to a contradiction.
However, there is a much more straightforward thing to do. The assumption $neg ((A rightarrow B) lor (A rightarrow C))$ is a negation of a disjunction, and you are probably aware of how by DeMorgan that is equivalent to the conjunction of the negated disjuncts, i.e. to $neg (A rightarrow B) land neg (A rightarrow C)$. Now, I suspect you don't have DeMorgan as an inference rule in your specific system, but think about it this way: apprently you should be able to derive both $neg (A rightarrow B)$ as well as $neg (A rightarrow C)$ from the Assumption. Now, both of those statements are negations, and you probably know the best strategy to prove negations: Proof bu Contradiction!
OK, so we have another piece of our plan:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B ) lor (A rightarrow C))$
$quad quad A rightarrow B$
$quad quad text{skip a few lines...}$
$quad quad bot$
$quad neg (A rightarrow B)$
$quad quad (A rightarrow C)$
$quad quad text{skip a few lines ...}$
$quad quad bot$
$quad neg (Arightarrow C)$
$quad text{few lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
OK, see how this is all nicely organized? How you now have an outline, to which you can add details and provide the missing steps at some later point? That is what you are supposed to do! That is how you keep your proof, and your very thinking organized. Indeed, the very point of doing formal logic proofs is to teach you that very skill of careful organization!
Now, I am going to leave those details to you, but leave you with one more hint: what is $neg (A rightarrow B)$ equivalent to? .... try and derive that, do the same for $neg (A rightarrow C)$, and you're pretty much done! Good luck!
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
$endgroup$
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
add a comment |
$begingroup$
It is always a very bad sign when someone has started a bunch of subproofs without indicating what happens at the end of the subproof.
A proof should always have a plan or outline, and subproofs provide the skeleton to do so. But again, you need to indicate what you want to do with the subproof, and that involves indicating what you want as the last line of your subproof. You haven't done that for any of the three subproofs you started, which is exactly why you get in trouble, and get see the forest for the trees.
Now, it is clear that with your first subproof you are hoping to do a proof by contradiction. So, start by creating the proper setup for that:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B) lor (A rightarrow C))$
$quad text{... skip a bunch of lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
Ok, now that we have set that up properly, let's go back inside the subproof, and see how we can derive the contradiction from the premise and the assumption.
Now, it is at this point that you assume $A$. Why?
Actually, I think I know why, because I have seen it all too often: you are probably thinking "ooh, it would be nice to have $A$, because then I can combine that with the premise! OK, so let's jist assume $A$"
OK, the problem with this kind of thinking is that you end up assuming something that you want ... which is always a bad ide, as that will often lead to a circular proof. Indeed, suppose you were indeed to combone $A$ with the premise, and get $B lor C$ ... OK .... now what?! Well, one thing you can do is to then close the subproof and conclude $A rightarrow (B lor C)$ .... but note that now you just get the very premise, i.e. You are getting nowhere.
Here is some general advice on subproofs, that goes back to my initial point about having a plan: before starting any subproof, you should already know how you are going to use that subproof, and in particular, what the last line of your subproof should be, and what rule you will apply after the subproof is done.
Ok, let's regroup. There is really no good reason to assume $A$. Ok, but what should you do on line 3? Well, again, if you had $A$, you could combine that with the premise, but rather than assuming $A$, you could try and make $A$ your new goal. And, to prove $A$, one thing you could do is to assume $neg A$, and show that that leads to a contradiction.
However, there is a much more straightforward thing to do. The assumption $neg ((A rightarrow B) lor (A rightarrow C))$ is a negation of a disjunction, and you are probably aware of how by DeMorgan that is equivalent to the conjunction of the negated disjuncts, i.e. to $neg (A rightarrow B) land neg (A rightarrow C)$. Now, I suspect you don't have DeMorgan as an inference rule in your specific system, but think about it this way: apprently you should be able to derive both $neg (A rightarrow B)$ as well as $neg (A rightarrow C)$ from the Assumption. Now, both of those statements are negations, and you probably know the best strategy to prove negations: Proof bu Contradiction!
OK, so we have another piece of our plan:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B ) lor (A rightarrow C))$
$quad quad A rightarrow B$
$quad quad text{skip a few lines...}$
$quad quad bot$
$quad neg (A rightarrow B)$
$quad quad (A rightarrow C)$
$quad quad text{skip a few lines ...}$
$quad quad bot$
$quad neg (Arightarrow C)$
$quad text{few lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
OK, see how this is all nicely organized? How you now have an outline, to which you can add details and provide the missing steps at some later point? That is what you are supposed to do! That is how you keep your proof, and your very thinking organized. Indeed, the very point of doing formal logic proofs is to teach you that very skill of careful organization!
Now, I am going to leave those details to you, but leave you with one more hint: what is $neg (A rightarrow B)$ equivalent to? .... try and derive that, do the same for $neg (A rightarrow C)$, and you're pretty much done! Good luck!
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
$endgroup$
It is always a very bad sign when someone has started a bunch of subproofs without indicating what happens at the end of the subproof.
A proof should always have a plan or outline, and subproofs provide the skeleton to do so. But again, you need to indicate what you want to do with the subproof, and that involves indicating what you want as the last line of your subproof. You haven't done that for any of the three subproofs you started, which is exactly why you get in trouble, and get see the forest for the trees.
Now, it is clear that with your first subproof you are hoping to do a proof by contradiction. So, start by creating the proper setup for that:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B) lor (A rightarrow C))$
$quad text{... skip a bunch of lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
Ok, now that we have set that up properly, let's go back inside the subproof, and see how we can derive the contradiction from the premise and the assumption.
Now, it is at this point that you assume $A$. Why?
Actually, I think I know why, because I have seen it all too often: you are probably thinking "ooh, it would be nice to have $A$, because then I can combine that with the premise! OK, so let's jist assume $A$"
OK, the problem with this kind of thinking is that you end up assuming something that you want ... which is always a bad ide, as that will often lead to a circular proof. Indeed, suppose you were indeed to combone $A$ with the premise, and get $B lor C$ ... OK .... now what?! Well, one thing you can do is to then close the subproof and conclude $A rightarrow (B lor C)$ .... but note that now you just get the very premise, i.e. You are getting nowhere.
Here is some general advice on subproofs, that goes back to my initial point about having a plan: before starting any subproof, you should already know how you are going to use that subproof, and in particular, what the last line of your subproof should be, and what rule you will apply after the subproof is done.
Ok, let's regroup. There is really no good reason to assume $A$. Ok, but what should you do on line 3? Well, again, if you had $A$, you could combine that with the premise, but rather than assuming $A$, you could try and make $A$ your new goal. And, to prove $A$, one thing you could do is to assume $neg A$, and show that that leads to a contradiction.
However, there is a much more straightforward thing to do. The assumption $neg ((A rightarrow B) lor (A rightarrow C))$ is a negation of a disjunction, and you are probably aware of how by DeMorgan that is equivalent to the conjunction of the negated disjuncts, i.e. to $neg (A rightarrow B) land neg (A rightarrow C)$. Now, I suspect you don't have DeMorgan as an inference rule in your specific system, but think about it this way: apprently you should be able to derive both $neg (A rightarrow B)$ as well as $neg (A rightarrow C)$ from the Assumption. Now, both of those statements are negations, and you probably know the best strategy to prove negations: Proof bu Contradiction!
OK, so we have another piece of our plan:
$A rightarrow (B lor C)$
$quad neg ((A rightarrow B ) lor (A rightarrow C))$
$quad quad A rightarrow B$
$quad quad text{skip a few lines...}$
$quad quad bot$
$quad neg (A rightarrow B)$
$quad quad (A rightarrow C)$
$quad quad text{skip a few lines ...}$
$quad quad bot$
$quad neg (Arightarrow C)$
$quad text{few lines ...}$
$quad bot$
$neg neg ((A rightarrow B) lor (A rightarrow C))$
$(A rightarrow B) lor (A rightarrow C)$
OK, see how this is all nicely organized? How you now have an outline, to which you can add details and provide the missing steps at some later point? That is what you are supposed to do! That is how you keep your proof, and your very thinking organized. Indeed, the very point of doing formal logic proofs is to teach you that very skill of careful organization!
Now, I am going to leave those details to you, but leave you with one more hint: what is $neg (A rightarrow B)$ equivalent to? .... try and derive that, do the same for $neg (A rightarrow C)$, and you're pretty much done! Good luck!
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
answered Jan 27 at 0:54
Bram28Bram28
63.8k44793
63.8k44793
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
add a comment |
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
Ok I'm completely stuck at the very end. I have $neg(A to B)$ and $neg(A to C)$ but I have no idea where to go from here. I know I can use conjunction intro to bring them together but I have no idea where to go from there.
$endgroup$
– Josh Susa
Jan 27 at 4:16
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@JoshSusa OK, remember that $A rightarrow B$ is equivalent to $neg A lor B$, which means that $neg (A rightarrow B)$ is equivalent to $neg (neg A lor B)$, and thus to $A land neg B$. So, you should be able to derive both $A$ and $neg B$ from $neg (A rightarrow B)$. HINT: do this using a proof by contradiction.
$endgroup$
– Bram28
Jan 27 at 13:34
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
@Bram: your comment is essentially the same as the hint in my answer to this question. The OP obstinately refuses to tell us what logic he or she is working in.
$endgroup$
– Rob Arthan
Jan 30 at 1:47
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
$begingroup$
That's possibly a weakness of proofs.openlogicproject.org which looks like where the OP's screenshot came from: It does allow you to put in empty spaces to be filled in, but it doesn't automatically adjust line numbers below where you insert lines so you would need to readjust the line numbers cited afterwards. (And by the way, that does have de Morgan rules as "derived rules" cited as "DeM".)
$endgroup$
– Daniel Schepler
Jan 31 at 1:44
add a comment |
$begingroup$
Hint: if you assume $A to (B lor C)$, $lnot(A to B)$ and $A$, then you can conclude $B lor C$ and $lnot B$. Can you take it from there?
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
$endgroup$
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
|
show 18 more comments
$begingroup$
Hint: if you assume $A to (B lor C)$, $lnot(A to B)$ and $A$, then you can conclude $B lor C$ and $lnot B$. Can you take it from there?
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
$endgroup$
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
|
show 18 more comments
$begingroup$
Hint: if you assume $A to (B lor C)$, $lnot(A to B)$ and $A$, then you can conclude $B lor C$ and $lnot B$. Can you take it from there?
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
$endgroup$
Hint: if you assume $A to (B lor C)$, $lnot(A to B)$ and $A$, then you can conclude $B lor C$ and $lnot B$. Can you take it from there?
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
answered Jan 26 at 21:27
Rob ArthanRob Arthan
29.5k42967
29.5k42967
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
|
show 18 more comments
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
So if you assume the negation of the conditional then you can use conditional elim to assume the negation of the proposition letter itself?
$endgroup$
– Josh Susa
Jan 26 at 21:33
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
From $lnot (A to B)$ you can conclude $A land lnot B$.
$endgroup$
– Rob Arthan
Jan 26 at 21:37
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
You said assume $neg (A to B)$ as well as $A$. Which subproof do I start with or does that matter?
$endgroup$
– Josh Susa
Jan 26 at 21:41
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
So I checked and I'm confused about how you concluded $neg B$
$endgroup$
– Josh Susa
Jan 26 at 21:44
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
$begingroup$
If $B$ is true, $A to B$ is true. The only way to make $lnot(A to B)$ true is to have $A$ true and $B$ false.
$endgroup$
– Rob Arthan
Jan 26 at 21:46
|
show 18 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3088766%2fhow-to-prove-the-following-formula-using-an-indirect-proof%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
