# Proof of Logical Expression

I came across an exercise and I'm stuck with one part:

4. Check the validity of the formula that follows:
A ∧ C → A ∨ B


This are the 8 axioms I will be working with:

├ A → ( B → A)
├ (A → B) → ((A → (B → (B → C) ) → (A → C))
├ A → (B → A ∧ B)
├ A ∧ B → A,,    A ∧ B → B
├ A → A ∨ B,,    B → A ∨ B
├ (A → C) → ((B → C ) → (A ∨ B → C))
├ (A → B) → (( A → ~B) → ~A )
├ ~~A → A


The correct solution that was given is:

1. ⊢ (A ∧ C → A) → ((( A ∧ C → (A → A ∨ B))) → (A ∧ C → A ∨ B))) A2 (Substituting A: A ∧ C, B: A, C: A ∨ B)
2. ⊢ A ∧ C → A A4 (Substituting A: A, B: C)
3. ⊢ ( A ∧ C → ( A → A ∨ B ) ) ) → ( A ∧ C → A ∨ B ) MP 1,2.
4. ⊢ A → A ∨ B A5 (substituting A: A, B: B)
5. ⊢ (A → A ∨ B) → (((A ∧ C)→(A → A ∨ B))) A1 (Substituting A: A → A ∨ B, B: A ∧ C )
6. ⊢ ( A ∧ C ) →( A → A ∨ B ) MP 5.4.
7. ⊢ A ∧ C → A ∨ B MP 3,6


I understand the proof, but I was wondering if I could have simply applied the transitive law:

 1. ├ A ∧ C → A        Axiom 4
2. ├ A → A ∨ B        Axiom 5
3. ├ A ∧ C → A ∨ B    MP 1,2


Is there something wrong with my approach?

Your line 3 is not an instance of Modus Ponens. Modus Ponens is of the form:

$$P \to Q$$

$$P$$

$$\therefore Q$$

What you did on line 3 was of the form:

$$P \to Q$$

$$Q \to R$$

$$\therefore P \to R$$

While perfectly logically valid (you call it the 'transitive law' ... but it is more commonly referred to as Hypothetical Syllogism, or HS for short), this latter rule is unfortunately not a rule that is part of the system that is given to you.

In other words: your proof makes perfect logical sense ... but it is not accepted as a formal-proof-within-the-system.

• Thanks, this is exactly what I was asking. Mar 8, 2022 at 12:55
• @Stack You're welcome! Mar 8, 2022 at 12:57
• I have another question, If we were working with a system that allowed us to use the Hypothetical Syllogism, would it make sense to continue using the first proof? Or the shorter the proof, the better Mar 8, 2022 at 12:58
• @Stack It wouldn't make much sense to do all the work in the first proof and then do HS, since you showed that with HS you can get a much shorter proof. So in that sense your proof is 'better': there is less for any 'consumer' to process when reading the proof, and your proof would make it more clear what is at the 'core' of why the argument is valid. The first proof would still be equally valid though: if all the steps are valid, the whole proof is valid, no matter how many steps are taken. Mar 8, 2022 at 14:34