MHB Find Proofs for the following 5 propositional logic statements

AI Thread Summary
The discussion focuses on finding proofs for five propositional logic statements, with participants providing detailed proofs and methodologies. Key techniques mentioned include hypothetical syllogism, modus ponens, and contradiction for deriving conclusions. The proofs demonstrate the use of assumptions and logical deductions to establish the validity of each statement. Participants emphasize the importance of understanding axioms and rules of inference in propositional logic. Overall, the thread serves as a collaborative effort to clarify and validate logical propositions.
josephmary
Messages
1
Reaction score
0
i came acroos the below while studying propositional Logic, can anyone find the proofs

1) P ⊢ P

2) P → Q, Q→R ⊢ P → R

3) P → Q, Q→R, ¬R ⊢ ¬P

4) Q→R ⊢ (PvQ) → (PvR)

5) P →Q ⊢ (P&R) → (Q&R)
 
Physics news on Phys.org
Can you state the axioms you are allowed to use?
 
josephmary said:
i came acroos the below while studying propositional Logic, can anyone find the proofs

1) P ⊢ P

2) P → Q, Q→R ⊢ P → R

3) P → Q, Q→R, ¬R ⊢ ¬P

4) Q→R ⊢ (PvQ) → (PvR)

5) P →Q ⊢ (P&R) → (Q&R)

1)$P$..................Assumption

2)$\neg P$................Hypothesis for contradiction

3)$P\wedge\neg P$............(1),(2) and using addition Introdaction

4)$\neg\neg P$..................From (2) to (3) and using contradiction

5) $P$..................(4) negation elimination

(2) and (3) are easy to do ,you can use hypothetical syllogism for (2) or conditional proof and modus ponens

And hypothetical syllogism , contrapositive and modus ponens for (3) or contradiction,and modus ponens

I will do (4) :

1)$Q\Rightarrow R$..............Assumption

2)$P\vee Q$..................Hypothesis for conditional proof

3)$\neg(P\vee R)$................Hypothesis for contraction

4)$(\neg P\wedge\neg R)$............From (3) and using de Morgan

5)$\neg P$..................(4), Addition elimination (AE)

6)$\neg R$..................(4),AE

7)$\neg R\Rightarrow\neg Q$.............(1),Contrapositive

8)$\neg Q$..................(6),(7),Modus Ponens(MP)

9)$\neg P\Rightarrow Q$..............(2),material implication

10)$Q$.....................(5),(9) MP

11)$Q\wedge\neg Q$................(8),(10) Addition Introduction (AI)

12)$\neg\neg(P\vee R)$...............from (3) to (11) and using contradiction

13)$(P\vee R)$...................(12),negation elimination

14)$(P\vee Q)\Rightarrow(P\vee R)$............from (2) to (13) and using conditional proof

(5) is on the same style with (4) and even easier
 

Similar threads

Back
Top