Discrete Mathematics: Propositions and Connectives

Introduction

• Lecture Focus: Propositions, negations, conjunctions, disjunctions.
• Key Tool: Truth tables.
• Terminology: Proposition - A declarative statement that is either true or false.

Propositions

• Definition: Declarative statements that are either true or false.
• Examples:
  • "The sky is blue" - True (Proposition P)
  • "The moon is made of cheese" - False (Proposition Q)
  • "Luke, I am your father" - False (Proposition R)
• Non-Examples:
  • "Sit down" - Command, not true/false.
  • "X + 1 = 2" - Requires value for X to be a proposition.

Connectives (Operators)

• Types:
  • Negation (~P): Not P
  • Conjunction (P ∧ Q): P and Q
  • Disjunction (P ∨ Q): P or Q
  • Implication (P -> Q): If P then Q
  • Biconditional (P <-> Q): P if and only if Q

Negation

• Definition: Negation of P is "not P" (~P).
• Examples:
  • P: "The grass is green"
  • ~P: "The grass is not green"
  • P: "My dog is the cutest dog" - True
  • ~P: "My dog is not the cutest dog"
• Truth Table:
  • P = True -> ~P = False
  • P = False -> ~P = True

Truth Tables

• Purpose: Show all combinations of truth values for propositions.
• Setup:
  • Left side: All combinations of truth values for propositions.
  • Right side: Results of applying connectives.
• Example 1: For a single proposition P:
  • P = True, ~P = False
  • P = False, ~P = True
• Example 2: For two propositions P and Q:
  • Rows: 2^2 = 4
  • P and Q combinations:
    • True, True
    • True, False
    • False, True
    • False, False

Conjunction (AND)

• Definition: Both P and Q must be true (P ∧ Q).
• Example:
  • P: "It is raining"
  • Q: "I am home"
• Truth Table:
  • P = True, Q = True -> P ∧ Q = True
  • P = True, Q = False -> P ∧ Q = False
  • P = False, Q = True -> P ∧ Q = False
  • P = False, Q = False -> P ∧ Q = False

Disjunction (OR)

• Definition: Either P or Q must be true (P ∨ Q).
• Truth Table:
  • P = True, Q = True -> P ∨ Q = True
  • P = True, Q = False -> P ∨ Q = True
  • P = False, Q = True -> P ∨ Q = True
  • P = False, Q = False -> P ∨ Q = False
• Inclusive OR: Either or both can be true.
• Exclusive OR (XOR): Only one can be true, not both.
  • Truth Table:
    • P = True, Q = True -> P XOR Q = False
    • P = True, Q = False -> P XOR Q = True
    • P = False, Q = True -> P XOR Q = True
    • P = False, Q = False -> P XOR Q = False

Next Topics

• Upcoming: Implications and Biconditionals, converse, inverse, and contrapositive of implications.