Discrete Mathematics Lecture Notes: Propositions and Connectives

Overview

• Topic: Propositions, Negations, Conjunctions, Disjunctions
• Importance of truth tables

Key Terminology

Proposition

• Definition: A declarative statement that is either true or false.

• Examples of Propositions (in pink):

  • The sky is blue (P)
  • The moon is made of cheese (Q)
  • Luke, I am your father (R)

• Non-Propositions (in green):

  • "Sit down" (not a proposition, as it is a command)
  • "X + 1 = 2" (not a proposition without a specific value for X)

Connectives

• Connectives act as operators for propositions.
• Types of Connectives:
  1. Negation: Not (¬)
     • Example: If P = "The grass is green", then ¬P = "The grass is not green".
  2. Conjunction: And (∧)
  3. Disjunction: Or (∨)
  4. Implication: If-then (→)
  5. Biconditional: If and only if (↔)

Detailed Examination of Connectives

Negation

• Notation: ¬P
• Example:
  • P: "My dog is the cutest dog" (True)
  • ¬P: "My dog is not the cutest dog" (False)

Truth Tables

• Purpose: To represent all possible truth values of propositions.

• Example for P:

  • P (True) → ¬P (False)
  • P (False) → ¬P (True)

• Truth tables expand with multiple propositions:

  • For 2 propositions (P & Q) → 2² = 4 rows.

Conjunction and Disjunction

• Conjunction (P ∧ Q):

  • Both must be true for the conjunction to be true.
  • Example:
    • P: "It is raining"
    • Q: "I am home"

• Truth Table for Conjunction:

  • True True → True
  • True False → False
  • False True → False
  • False False → False

• Disjunction (P ∨ Q):

  • At least one must be true for the disjunction to be true.

• Truth Table for Disjunction:

  • True True → True
  • True False → True
  • False True → True
  • False False → False

Inclusive vs. Exclusive OR

• Inclusive OR: At least one proposition is true.

  • Example: Passing either MA 315 or MA 335.

• Exclusive OR (XOR): Only one proposition can be true.

  • Example: Choosing soup or salad (but not both).

Next Steps

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