@amazingsugar13,
amazingsugar13 wrote:
I'm really stuck on a modal logic proof
Propositional Modal Logic
Give proof or counterexample:
1) (p => q) > (~diamond q > ~diamond p), where > is " horseshoe "
How to proof this one?
There are two ways to go about proving this: 1) the informal route or 2) the formal route with deduction rules. I will do both
Prove theorem: (p > q) > (~diamond q > ~diamond q)
Proof: Since any truth also entails that it is possibly true, if p, then q entails that possibly if p, then q. According to an axiom in modal logic (I forget which one), possibly if p, then q entails that if possibly p, then possibly q. Now take the contrapositive of the consequent, which is if not possibly q, then not possibly p. Since we assumed the antecedent in our theorem, it entails the consequent, and we have thereby demonstrated that the consequent follows from the antecedent. Q.E.D
Now here's the formal route by means of deduction rules.
Prove theorem: (p > q) > (~diamond q > ~diamond q)
Proof:
Begin Subproof (1)
1. p > q assumption for conditional proof
Begin Subproof (2)
2. ~(~diamond q > ~diamond p) assumption for reductio
3. ~(~~diamond q v ~diamond p) 2, material implication
4. ~~~dimaond q & ~~diamond p) 3, demorgans
5. ~~~diamond q 4, conjunction elimination
6. ~~diamond p 4, conjunction elimination
7. ~diamond q 5, double negation
8. diamond p 6, double negation
9. box~ q 7, modal transformation
Begin Subproof (3) (I use the box subproof here)
10. ~q 9, box out
11. ~p 1, 10, modus tollens
End Subproof (3)
12. box ~p 10-11 box subproof
13. ~diamond p 12, modal transformation
14. diamond p & ~diamond p 8, 13, conjunction introduction
End Subroof (2)
15. ~diamond q > ~diamond p 2-14, reductio ad absurdum
End Subproof (1)
16. Theorem which we needed to prove
Hope this helps. If you need any more help on modal logic, ask me.