Propositions, Logical Connectives, and Truth Tables

• Discrete Math


  The study of discrete objects. Discrete means "distinct" or "not connected"
• Discrete Math is not a branch of Mathematics. It is rather a description of set of branches that have one common property - that they are "discrete" and "not continuous".
• Proposition


  A declarative statement declaring some fact. It is either true or false but not both.
• Types of Propositions


  • Atomic Propositions
  • Compound Propositions
• Atomic Propositions


  Atomic propositions are those propositions that cannot be divided further.
• Compound Propositions


  Compound propositions are those propositions that are formed by combining one or more atomic propositions using connectives.
• Statements That Are Not Propositions

  • Command
  • Question
  • Exclamation
  • Inconsistent
  • Predicate or Proposition Function
• Logical Connectives


  • Negation (Not)
  • Conjunction (And)
  • Disjunction (Or)
  • Conditional (If-then)
  • Biconditional (If and only if)
• Negation (not)


  ∼p or ¬p
• Conjunction (and)


  p ∧ q
• Disjunction (or)


  p ∨ q
• Conditional (If-then)


  p → q
• Biconditional (If and only if)


  p ↔ q
• Conditional Statement


  An if-then statement in which p is a hypothesis and q is a conclusion. The logical connector is denoted by the symbol →.
• The conditional is defined to be true unless a true hypothesis leads to a false conclusion.
• For a conditional statement p → q

  • Converse statement: q → p
  • Inverse statement: ∼p → ∼q
  • Contrapositive statement: ∼q → ∼p
• Truth Tables of Compound Propositions

  Compound propositions are those propositions that are formed by combining one or more atomic propositions using connectives.
• Precedence of Logical Operations

  1. To reduce number of parentheses, use precedence rules

  2. Construct the truth table for the compound proposition (p ∨ q) ∧ ¬r

  3. Set up the truth table with all possible combinations of p, q, r

  4. Complete the table using the basic properties of "and", "or", and negation