Summary of "Discrete Math - 1.7.1 Direct Proof"

Summary of “Discrete Math - 1.7.1 Direct Proof”

This video explains the method of direct proof in discrete mathematics, focusing on how to formally and informally prove implications of the form “if ( P ) then ( Q ).”

Main Ideas and Concepts

Direct Proof Methodology:
- Start by assuming the antecedent ( P ) is true.
- Use definitions, axioms, and rules of inference to logically deduce that the consequent ( Q ) is true.
- This proves the implication ( P \implies Q ).
Difference Between Formal and Informal Direct Proofs:
- Formal proofs explicitly cite each axiom or inference rule used.
- Informal proofs are more conversational but still logically valid.
Key Logical Structure:
- Identify the implication ( P \implies Q ).
- Assume ( P ) is true.
- Show ( Q ) must follow.

Important Definitions Used in Proofs

Even Integer: An integer ( n ) is even if it can be expressed as [ n = 2k ] where ( k ) is an integer.
Odd Integer: An integer ( n ) is odd if it can be expressed as [ n = 2k + 1 ] where ( k ) is an integer.

Example 1: Prove “If ( n ) is odd, then ( n^2 ) is odd”

Proof Steps:

Assume ( n ) is odd, so [ n = 2k + 1 ] for some integer ( k ).
Square both sides: [ n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 ]
Factor out 2 from the first two terms: [ n^2 = 2(2k^2 + 2k) + 1 ]
Since ( 2k^2 + 2k ) is an integer (call it ( r )), rewrite as: [ n^2 = 2r + 1 ]
This matches the definition of an odd integer, so ( n^2 ) is odd.

Conclusion: Therefore, ( n^2 ) is odd. (\quad \square)

Example 2: Prove “The sum of two even integers is even”

Proof Steps:

Express the statement as an implication: If ( A ) and ( B ) are even integers, then ( A + B ) is even.
Assume ( A ) and ( B ) are even: [ A = 2k, \quad B = 2m ] where ( k, m ) are integers.
Add the two: [ A + B = 2k + 2m = 2(k + m) ]
Since ( k + m ) is an integer (call it ( r )), rewrite as: [ A + B = 2r ]
This matches the definition of an even integer, so the sum is even.

Conclusion: Therefore, ( A + B ) is even. (\quad \square)

Additional Notes

The video encourages viewers to practice direct proofs independently.
The next topic to be covered after direct proofs is proof by contraposition.
Symbols like ( \therefore ), a square, triangle, or “Q.E.D.” mark the end of a proof, signifying “what was to be demonstrated.”

Speakers / Sources Featured

Primary Speaker: The video presenter (unnamed), presumably a mathematics instructor explaining discrete math concepts.
No other speakers or sources are explicitly mentioned.