Wyman wrote:It depends on what your professor is requiring of you. Do you have axioms and rules of inference or are less formal proofs allowed?
If you are working with only modus ponens (including conditional proof):
Assume A (whatever follows from assuming A will create a conditional, If A then....)
Assuming A, by MP and the premises you stated, B follows
If B folllows, then C follows by MP and then D
So your conditional 'If A then ....' has given you B, C and D to work with.
From that, 'If A then C and D' follows directly by conditional proof
You now have to prove that 'C and D' is equivalent to not (not C or not D) and substitute it into the previous step to arrive at the conclusion.
I think you need more than modus ponens here, what do you think?
That is a good strategy too, and as you rightly pointed out though, one would need more than MP in this strategy. One can show that (C & D) is equivalent to ~(~C v ~D) and as you will recall that is the famous DeMorgan Theorem. So that works too. So, with your strategy, it would look like this:
............(1) A→B...................Premise
............(2) B→ C................. Premise
............(3) C→D..................Premise
............(4) A...................... Assumption
.......1, 4(5) B.......................1, 4 →E (or MP)
.....1,2,4(6) C.......................2,5 →E (or MP)
...1,2,3,4(7) D ......................3,6 →E (or MP)
...1,2,3,4(8) C&D...................6,7 &I
..1,2,3,4 (9) ~(~C v ~D)........... 8 DeMorgan
..…1,2,3(10) A→ ~(~C v ~ D).....4, 9 →I □
But now to prove De Morgan, you have to make use of the disjunction elimination rule, as I did in my proof but without using DeMorgan. It looks like this:
DeMorgan Theorem states: C & D therefore ~(~C v ~D).
Proof:
.....(1) C & D.................Premise
.....(2) ~C v ~D..............Assumption
.....(3) ~C....................Assumption
...1(4) C......................1, &E
1,3 (5) ꓕ (contradiction)...3,4 ~E
.....(6) ~D....................Assumption
...1 (7) D.....................1, &E
1,6 (8) ꓕ (contradiction)...6,7 ~E
1,2 (9) ꓕ (contradiction)...2,3,5,6,8 vE
…1 (10) ~(~C v ~D)..........2, 9 ~I □
In this strategy, if there is a need to prove DeMorgan, you end up writing more lines! And thus it boils down to the same thing I wrote.
Wyman wrote:Suppose (C and D) is equivalent to NOT(not (notC and notD))
Then we use the inference rule that says that double negatives cancel
This gives (C and D ) is equivalent to (notC and notD)
We then need the rule of separation (separating a conjunction into its component parts) applied several times, but it is fairly obvious already that (C and D) is contradictory to (notC and notD) - thus the conclusion is proven
You mention assuming a semantic equivalence between (C&D) and ~(~(~C
& ~D)) in an attempt to derive a contradiction, however, with that you cannot arrive at the conclusion because firstly they are not contradictory statements and secondly, in the conclusion to be proved there is a disjunction of negation, while in your assumption there is a conjunction of negation. But I think it was a typing mistake on your part which you then carried forward, as you had correctly mentioned a disjunction of negation before that line. So what you meant to assume to be equivalent (in a Reductio strategy I guess) was (C&D) and ~(~(~C v ~D)). But you could just as well have assumed (~C v ~D) and derive your contradiction before introducing a negation. In this way you would save yourself the step of having to apply a DN to get to the conclusion. And that is how DeMorgan was proved above.
As you mentioned equivalence, for completeness lets prove the other side as well, as an equivalence is a biconditional relation.
DeMorgan: ~(~C v ~D) therefore (C & D)
....(1) ~(~C v ~D)..............Premise
....(2) ~C........................Assumption
..2 (3) ~C v ~D..................2, vI (disjunction introduction)
1,2 (4) ꓕ (contradiction).... 1,3, ~E
..1 (5) ~~C .....................2, 4 ~I
..1 (6) C........................5 DN (Double Negation)
....(7) ~D......................Assumption
..7 (8) ~C v ~D ...............7, vI
1,7 (9) ꓕ (contradiction)....1, 8 ~E
1 (10) ~~D.....................7, 9 ~I
1 (11) D.......................10 DN
1 (12) C & D..................6, 11 &I □
Wyman wrote:can anyone do it with less rules of inference?
I do not think so. The way I did it is the strict minimum. Or else, one can consider writing the truth table, in which case there would be no need of any rules of inference at all!