0
$\begingroup$

Consider the following to prove: $(A \implies B) \implies (C \implies D)$

Could this be proved by assuming A then proving B, then using A and B to prove C, then using A, B and C to prove D? or would it be enough to use just B if B was always true, ie use B to prove $(C \implies D)$?

Or should it be proved using the below structure by assuming $A \implies B$ and then assuming C to get A, which gives us B, then using C, A and B, to show D?

enter image description here

Are both these approaches the same, is one preferable to the other in certain cases, is more information needed, or is one of them completely wrong? I'm looking to understand how to deal with these kinds of proof goals in general.

I think its likely to do with the underlyling structure of the data being reasoned over e.g. if there are compositionality, as with inductions, the square like approach seems better, as structure information could be used to simplify the proofs?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This sounds like a question about pure math. Is there any reason it needs to be answered from a computer science perspective? $\endgroup$ Commented Jul 3, 2024 at 17:20
  • $\begingroup$ Hi I believe computer science and pure math are very close and overlap on areas especially around logic and elegant proofs, and proofs involving alot of implications tend to come up in structural inductions for proving properties about programs. $\endgroup$ Commented Jul 3, 2024 at 18:54
  • 1
    $\begingroup$ The question seems on-topic for Math.SE. I'm unsure whether it is on-topic here (see cs.meta.stackexchange.com/q/704/755 and cs.meta.stackexchange.com/q/260/755). Any community votes? $\endgroup$ Commented Jul 3, 2024 at 19:07

1 Answer 1

Reset to default
1
$\begingroup$

$C$ need not have any relation to $A$ or $B$. It is just the case if, assuming $A$, you can derive $B$, then assuming $C$, you can derive $D$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What about just showing B is true, is that enough to then prove C implies D? $\endgroup$ Commented Jul 6, 2024 at 19:41
  • $\begingroup$ I think i'm getting confused with showing a specific instance of the formula which evaluate to true Vs all instances that evaluate to true. B being true would be a specific instance of A=>B being true, but there is also A true and B true, for it to be true. So proving A=>B is true really means just show that if A is true B is also true, as B being true on its own just comes from it being possible for B to be true, which is would be shown by A=>B? $\endgroup$ Commented Jul 8, 2024 at 20:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.