Lecture Notes: Introduction to Propositional Logic

Overview

• This lecture introduces the first chapter of discrete mathematics: Propositional Logic.

Key Terms

1. Propositional Logic: Composed of two words: Proposition and Logic.
   • Proposition: A declarative sentence that can be true or false, but not both.
   • Logic: The science of reasoning that helps understand and reason about mathematical statements.

Purpose of Logic

• The primary purpose of logic is to construct valid arguments (proofs).
• A statement that is proven true is referred to as a theorem.
• Logic forms the basis of mathematics.

Importance of Logic

• Logic enables reasoning about mathematical statements:
  • Validating mathematical arguments.
  • Proving or disproving statements using established rules.

Example: Sum of Positive Integers

• The formula for the sum of the first n positive integers:

  For every positive integer n, the sum of positive integers not exceeding n is ( \frac{n(n+1)}{2} ).

• This statement is a valid mathematical argument and can be proven using logic.

Application: Knights and Knaves Puzzle

• A logic puzzle involving two types of inhabitants on an island:
  • Knights: Always tell the truth.
  • Knaves: Always lie.
• Example:
  • Alice says, "Bob is a knight."
  • Bob says, "We are opposite types."
• Propositional logic can help solve such puzzles systematically.

Propositions

• A proposition is defined as:
  • A declarative sentence that can be true or false, but not both.
• Examples of propositions:
  • "Delhi is the capital of India." (Can be true)
  • "One plus one equals two." (True)

Non-Propositions

• Sentences that are not propositions:
  • Questions: "What time is it?"
  • Variable statements: "x + 1 = 2" (depends on x)
  • Commands: "Send us your resume before 11 pm."
  • Requests: "I request you to please allow me a day off."
  • Commands: "Fetch my umbrella."

Homework Assignment

• Identify propositions from the following sentences and state whether they are true or false:
  • London is in Denmark.
  • Do your homework.
  • India wins the match by two runs.
  • x is an even number.
  • Five is an odd number.
  • Five plus seven equals ten.
  • The moon is made of cheese.
  • The only odd prime number is two.
  • God bless you.

Conclusion

• Understanding propositional logic is essential and can be both fun and valuable.
• Feel free to post your homework answers in the comment section.