(University Discrete Structures/Math) Create Proof Sequence for (A v B) ^ (A → C) ^ (B → C) → C

[u/Agitated_Path2455]

Prompt: "Use propositional logic to prove the arguments valid; you may use any of the equivalence or inference rules."

I have this sequence but I'm not confident in #4-7

1. A v B (hyp)
2. A → C (hyp)
3. B → C (hyp)
4. (A v B)’’ (1, Double negation)
5. (A’ ^ B’)’ (4, de morgan)
6. (A’)’ (5, simplification)
7. C (2, 6 modus ponens)

---
*UPDATE*

I currently have this sequence. I was struggling, then I realised the implication rule has an error (It says 'P -> Q is equivalent to P' v Q) so I wanted to get others input on if my work is correct.

1. A v B [hyp]
2. A → C [hyp]
3. B → C [hyp]
4. A’ v C [2, implication]
5. B’ v C [3, implication]
6. (A’ v C) ^ (B’ v C) [4, 5 conjunction]
7. (C v A’) ^ (C v B’) [6, commutative]
8. C v (A’ ^ B’) [7, distributive]
9. (A’ ^ B’) v C [8, commutative]
10. (A v B)’’ [1, double negation]
11. (A’ ^ B’)’ [10, de morgan]
12. C [9, 11 disjunctive syllogism]

My additional explanation for getting #12. disjunctive syllogism

P v Q, P’ < = > Q

(A’ ^ B’) v C, (A’ ^ B’)’ < = > C

[u/AutoModerator]

Moderator Announcement Read More »

Off-topic Comments Section

---

All top-level comments have to be an answer or follow-up question to the post. All sidetracks should be directed to this comment thread as per Rule 9.

---

^{OP and Valued/Notable Contributors can close this post by using} /lock ^command

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/Alkalannar]

Looks like mine is very much like your second version!

1. A v B [given]

2. A -> C [given]

3. B -> C [Given]

4. ~A v C [2, MI]

5. ~B v C [3, MI]

6. (~A v C) ^ (~B v C) [4, 5, conjunction]

7. (~A ^ ~B) v C [6, distributive property]

8. ~(A v B) v C [7, DeMorgan]

9. (A v B) ^ [~(A v B) v C] [1, 8, conjunction]

10. [(A v B) ^ ~(A v B)] v [(A v B) ^ C] [9, distribution]

11. F v [(A v B) ^ C] [10, contradiction]

12. (A v B) ^ C [11, OR absorbs FALSE]

13. C [12, simplification, QED]

[u/TalveLumi → u/Alkalannar]

While I think in a general situation this derivation is valid, I don’t think they proved the converse of the distributive property, which is used in Step 7

[u/TalveLumi]

Your first proof is bullshit and I think you know it by now

Your second proof is, in general, valid, but unfortunately the 7th step requires an unproven property known as the converse of the distributive property (true in classical logic, but we cannot affirm that this is classical logic without proving it)

Try

1-3. (As is)
4. A’’vB (dn,1)
5. A’→B (imp,4)
6. C’→A’ (cont,2)
7. C’→B (hs,6,5)
8. C’→C (hs,7,3)
9. C‘’vC (imp, 8)
10. CvC (dn,9)
11. C (self,10)

Unfortunately, this relies on an internal use of the double negative rules. While unlike the derivational rules (which is what your first proof goes wrong on) this is in general valid, I don’t know whether that is given in your book. Better check it.

P.S. I miss Natural Deduction.