Lecture Notes: Discrete Mathematics - Propositions, Negations, Conjunctions, and Disjunctions

Introduction

• Topics Covered: Propositions, Negations, Conjunctions, Disjunctions, Truth Tables
• Connectives: Negations, Conjunctions, Disjunctions

Propositions

• Definition: A declarative statement that is either true or false.
• Examples:
  • The sky is blue. (Proposition - True)
  • The moon is made of cheese. (Proposition - False)
  • Luke, I am your father. (Proposition - False)
  • Sit down. (Not a proposition - command)
  • X + 1 = 2 (Not a proposition unless a value is assigned to X)
• Representation: Propositions are represented by lowercase letters (p, q, r, etc.).

Connectives

• Definition: Operators for propositions.
• Types:
  • Negation: Represented by ¬ (not p)
  • Conjunction: Represented by ∧ (p and q)
  • Disjunction: Represented by ∨ (p or q)
  • Implication: Represented by → (if p then q)
  • Biconditional: Represented by ↔ (p if and only if q)

Negation

• Explanation: Turns the truth value of a proposition to its opposite.
• Example:
  • Proposition: The grass is green (p)
  • Negation: The grass is not green (¬p)
• Truth Table:

  p	¬p
  True	False
  False	True

Truth Tables

• Purpose: To show all possible truth values of propositions and their connectives.
• Structure: Left side for the combinations of truth values, right side for the result of the connective.
• Example: One proposition (p)

  p	¬p
  True	False
  False	True

• Multiple Propositions: For n propositions, there are 2^n rows.
• Example: Two propositions (p, q)

  p	q	p ∧ q
  True	True	True
  True	False	False
  False	True	False
  False	False	False

Conjunction (AND)

• Definition: Both propositions must be true for the conjunction to be true.
• Example:
  • p: It is raining
  • q: I am home
  • p ∧ q: It is raining and I am home
• Truth Table:

  p	q	p ∧ q
  True	True	True
  True	False	False
  False	True	False
  False	False	False

Disjunction (OR)

• Definition: Either proposition must be true for the disjunction to be true.
• Example:
  • p: It is raining
  • q: I am home
  • p ∨ q: It is raining or I am home
• Truth Table:

  p	q	p ∨ q
  True	True	True
  True	False	True
  False	True	True
  False	False	False

• Inclusive OR: Either or both can be true.
  • Example: Course prerequisites (ma 315 or ma 335)
• Exclusive OR (XOR): Only one can be true, not both.
  • Example: Soup or salad with entree
  • Truth Table for XOR:

    p	q	p ⊕ q
    True	True	False
    True	False	True
    False	True	True
    False	False	False

Next Topics

• Implications and Biconditionals
• Converse, Inverse, and Contrapositive of Implications