Introduction to Proofs in Propositional Logic using Fitch-Style System

What is a Proof?

• A proof is a method to derive conclusions from a set of premises systematically.
• Example: With premises P and Q, not Q, P → R, we can prove R.
• Purpose: Provide mathematical and systematic rules to ensure each step in the proof is true.

Proof Rules in Fitch System

Assumption Rule

• If a statement a is an assumption, it can be reiterated anywhere.
• Example: Line 1: a, can be rewritten at line n with justification "1 reit" (reiteration).

Modus Ponens (Conditional Elimination)

• If line i: a and line j: a → b, then we can conclude b.
• Justified by writing lines i, j, mp.

And Elimination

• From A and B, you can derive A or B individually.
• Justify by writing line i for and elimination.

And Introduction

• If A is on line i and B on line j, you can derive A and B.
• Justified by stating lines i, j for and introduction.

Or Introduction

• From statement p on line i, you can write p or q on line j.
• Justified with or introduction.

Biconditional Elimination and Introduction

• A ↔ B means A → B and B → A.
• Introduction is the reverse process.
• Acceptable to use interchangeably depending on proof requirements.

Proof Examples

Example 1

• Goal: Prove H from F and F or G → H.
  • Use or introduction to introduce F or G.
  • Apply modus ponens to conclude H.

Example 2

• Goal: Prove not A and B or C from b ↔ d ↔ not a and b and d.
  • Use and elimination to derive individual statements.
  • Apply biconditional elimination to reach not A.
  • Use or introduction to get B or C.
  • Conjoin using and introduction to conclude not A and B or C.

Practice Problems

• Problem 1: Given A → B and not C, A and B, prove not C.
• Problem 2: From not B → D and E, A and not B and C, prove E and D and not B and C.
• Problem 3: Starting with a and not b, a or not c → d, prove d and not b.
• Problem 4: Given not F and not G, not G → H, H and not F ↔ not I, prove H and not I.

Conclusion

• Practice is crucial for mastering proof techniques.
• Students are encouraged to write out their proofs fully to build confidence and understanding before advancing to more difficult proofs.
• Encouragement to engage with practice problems and seek help if needed.