Deductive Proofs

Introduction to Proof Techniques

  • Overview of logical laws and inference rules in proofs

  • Focus on deriving conclusions from premises

Structure of Proofs

  • Organization in terms of premises and conclusions

  • Layout is akin to transformational proof technique with differences:

    • Focus formula is central

    • Numbered lines to indicate referable steps

Example 1: From Premise to Conclusion

  • Premise: P and Q are R

  • Goal: Prove not P implies R

  • Step 1: Begin by writing down the premise

  • Step 2: Numbering lines is important for referencing

Logical Laws in Use

  • Line 1: P and Q are R is our premise

  • Line 2: By applying the logical law of commutativity of disjunction:

    • If P and Q are R is true, then R or P and Q is true

  • Result:

    • From Line 1, we conclude R or P and Q (True)

  • Line 3: Apply distributivity to get:

    • R or P and R or Q

  • Use Conceptual Equivalence:

    • Logically, these transformations are equivalent due to properties of logical laws

Application of Inference Rules

  • Line 4: Apply the rule of simplification (If P and Q are true, then P is true):

    • From R or P and R or Q to conclude R or P is true

  • Line 5: Applying commutativity again, we get P or R

  • Line 6: Apply negation law; if P is true, not not P is true

  • Final Step (Line 7): Apply the logical law of implication:

    • not P or R is concluded to be logically equivalent to P implies R

Conclusion of Example 1

  • Achieved with systematic logical transformations

Conditional Proof Method

  • Definition: A proof technique using the deduction theorem

  • Used for conclusions in the form of implications

  • Goal: Prove P implies not S

  • Lines of Evidence: Indenting portions under assumptions makes the flow clear

Inner Workings of Conditional Proof

  1. Assumption: Start with assuming P is true

  2. From Premise: P implies Q or R means from P, derive Q or R using modus ponens

  3. From not S premises simplify conclusions downward to not S or R and then to not S

  4. Final Conclusion: If P is true, then not S is true

Deduction Theorem

  • Using successive logical steps leads to validity of the implication

Indirect Proof Method

  • Formulation: Use the negation of the conclusion we want to prove

  • Aim to reach a contradiction

Steps in Indirect Proof

  1. Assumption: Assume Q is true (negating not Q)

  2. Derive R using initial premises, systematically showing conclusions that lead to the contradiction

  3. Contradictory Outcomes: Proving both P and not P must yield that not Q is true

General Review of Assumptions

  • Key to logical arguments: defining structure clearly shows reasoning paths leading to contradictions or conclusions

Example Recap and Variation

  • Conditional Proof revisits original example to show flexibility of methods

  • not P implies R also proves valid using indirect assumptions

  • Conclusion Validity: Each method adjusts per the complexity of premises and goals

Summary of Logical Equivalences

  • Review of truth tables and statements forgiveness

  • Formulas demonstrating De Morgan's Laws:

    • not (P and Q) = (not P or not Q) and not (P or Q) = (not P and not Q)

  • Applications of equivalences reinforce understanding through proof

Application in Assessments

  • Frequent review and practice in logical derivations encourages fluency in proof techniques

Conclusion

  • Understand distinct approaches in proofs, including straightforward, conditional, and indirect methods while practicing systematically to refine logical reasoning skills

Reflection Prompts

  • Assess which method fits proofs best

  • Engage with premises to derive logical conclusions rigorously