October 5th, 2015: Sections 1-7 and 1-8 - Delving into Logic and Proofs

Welcome to Professor Baker's Math Class! In today's session, we're tackling Sections 1-7 and 1-8 of our Discrete Mathematics journey. These sections are foundational, building the bedrock upon which more complex concepts will rest. Let's get started!

Section 1-7: Introduction to Proofs

Section 1-7 is all about proofs! Understanding how to construct a valid argument is vital. Here are some key concepts we explored:

  • Quantifiers: Recognizing when quantifiers are explicitly stated versus when they are implied. For example, in the statement "The product of two negative numbers is positive," the implied quantifier is "For all."
  • Direct Proofs: Constructing a direct argument to show that a statement is true. For example, proving that if $n$ is odd, then $5n + 3$ is even.
  • Proofs by Contraposition: Proving a statement by showing that if the conclusion is false, then the premise must also be false.
  • Proofs by Contradiction: Assuming the negation of the statement and arriving at a contradiction, thus proving the original statement.

Here's an example to ponder: Prove that if $n$ is an even integer, then $3n + 7$ is odd. Try tackling this using a proof by contradiction!

Section 1-8: Proof Methods and Strategy

Now that we've covered the basics of proofs, let's delve into different methods and strategies to help us approach them:

  • Proof by Cases: Breaking down a problem into different cases and proving the statement for each case.
  • Counterexamples: Disproving a universal statement by providing a counterexample. For example, disproving the statement "Every integer is less than its cube" by showing that 1 is not less than 1 cubed.
  • Exhaustive Proof: Verifying a statement by checking every possible case.
  • The Importance of Definitions: Always refer back to the definitions. For example, when proving something about odd integers, remember that an odd integer is one that can be written as $2k+1$ for some integer $k$.

Remember the famous Four Color Theorem, which states that any map can be colored with at most four colors so that no two adjacent regions have the same color. The complicated and very lengthy proof used an adaptation of a simpler proof for five colors. You can use others’ proofs to obtain new results!

Resources for Further Study

Remember, discrete mathematics is not just about memorizing rules, it's about understanding the 'why' behind them! Keep practicing, keep questioning, and you'll be well on your way to mastering these concepts.

See you in the next class!