INTRODUCTION to PROPOSITIONAL LOGIC - DISCRETE MATHEMATICS

Introduction

This tutorial provides an introduction to propositional logic, a fundamental concept in discrete mathematics. It focuses on understanding statements, their truth values, and how to translate between English sentences and propositional logic. This knowledge is essential for further study in logic and mathematics.

Step 1: Understanding Statements

• A statement is a declarative sentence that can be either true or false.
• Truth values are represented as:
  • True = 1
  • False = 0
• Examples of statements:
  • "Milk is white" (Usually true, but can be false for chocolate milk)
  • "The cardinality of the empty set is equal to zero" (True)
  • "Humans are just fish with legs" (False)
• Non-statements include:
  • Questions (e.g., "Will you go to the store for me?")
  • Imperatives (e.g., "Kick me.")

Step 2: Propositions and Well-Formed Formulas

• Propositions are specific instances of statements, typically denoted by capital letters (e.g., P, Q, R).
• A well-formed formula (WFF) is a statement that follows the syntax rules of propositional logic.
• Example of WFF:
  • If P represents "I cheat" and Q represents "I wrote an exam," then "P and Q" (P ∧ Q) is a WFF.

Step 3: Connectives in Propositional Logic

• Connectives combine or modify propositions:
  • Negation (not): ¬P (not P)
  • Conjunction (and): P ∧ Q
  • Disjunction (or): P ∨ Q
  • Implication (if...then): P → Q
• Each connective has specific truth conditions, which will be explored in truth tables.

Step 4: Translating WFF to English

• To translate a WFF into English, identify the propositions and connectives.
• Example:
  • WFF: R ∧ (P → Q) ∧ S
  • Translation:
    • If R = "I write an exam," P = "I cheat," Q = "I will get caught," and S = "I will fail," then it translates to "If I write an exam and I cheat, then I will get caught and I will fail."

Step 5: Translating English to WFF

• Identify key connectives in an English sentence and assign propositions.
• Example:
  • English: "If James does not die, then Mary will not get any money and James' family will be happy."
  • Assign:
    • P = "James dies"
    • Q = "Mary will get money"
    • R = "James' family will be happy"
  • WFF: ¬P → ¬Q ∧ R

Conclusion

In this tutorial, we explored the basics of propositional logic, including understanding statements, propositions, well-formed formulas, and how to translate between English sentences and logic expressions. As a next step, you can practice creating your own statements and translating them into WFF or vice versa. Additionally, familiarize yourself with truth tables to deepen your understanding of logical connectives.