Module 07 : Direct Proofs

Logic of Quantified Statements

Quantified Statements

• Expressions in logic that assert that a certain condition holds for all or some members of a set.

• Various logical operations can be applied to quantified statements, examining their implications and relationships through equivalencies.

Universal Instantiation and Modus Ponens

• Universal Instantiation: If a property is true for everything in a set, it is true for any specific entity from that set.

  • Example: "All men are mortal; Socrates is a man, thus Socrates is mortal."

• Universal Modus Ponens: Combination of universal instantiation with modus ponens.

  • Formal Version: ∀x, if P(x) then Q(x). P(a) [for some particular a] implies Q(a).

  • Example: If an integer is even, then its square is even; k is an even integer, so k² is even.

Conclusion Drawing using Universal Modus Ponens

• To prove properties involving specific values based on their universal properties. For example, triangles and the Pythagorean theorem or even integers and their sums.

• Application of Universal Modus Ponens: Presents structured arguments leading to codified conclusions.

Universal Modus Tollens

• Based on universal instantiation and modus tollens.

• Formal version involves negating the conclusion, leading to the conclusion that the hypothesis must also be false.

  • Example: If all humans are mortal and Zeus is not mortal, then Zeus cannot be human.

Proving Validity of Arguments

• An argument form is valid if the truth of its premises ensures the truth of its conclusion.

• Sound Argument: An argument form is valid and its premises are true.

• Knowledge of logical principles aids in evaluating the structure and validity of complex arguments.

Usage of Diagrams

• Diagrams can help visualize logical relationships between premises and conclusions.

• Valid Argument Example: Using a diagram, showing that all human beings are mortal, followed by proving that a specific individual is not mortal, thus concluding they are not human.

Converse and Inverse Errors

• Converse Error: Assuming that if Q holds for a, then P holds for a if P(x) implies Q(x).

• Inverse Error: Assuming that the failure of P for a fails Q for a.

• Examples illustrate common missteps in logic related to erroneous assumptions about relationships.

  • Importance of correctly identifying valid forms and understanding their contrapositives.

Conclusion on Validity and Techniques

• Proof by Counterexample: Disproves universal statements by finding a specific case where the hypothesis holds but the conclusion fails.

• Existential Statements: Argues for the existence of specific cases meeting defined criteria.

• The practice of mathematical reasoning cultivates precision and aids comprehensive understanding.

Method of Direct Proof

• Structure proofs using specific statements and definitions to establish truth in universal contexts.

• Ensure clarity in exposition for reproducibility by peers.

• Practical examples include proving sums of integers based on their characteristics defined earlier.

• Theorem Example: The sum of two even integers is even, justified through substitution and algebraic identities.