DISCRETE MATH MT

• Predicate logic


  An extension of propositional logic that allows for more complex and expressive statements by introducing predicates, quantifiers, and variables
• Predicate


  A property the variable can have
• Predicate logic is also known as "first-order logic"
• Propositional logic is also known as "sentential logic"
• Predicate logic examples


  • P(x), where x > 5
  • Q(x, y), where x + y = 5
  • R(x), x is an even number
• Domain


  The set of all possible input values for which the function is evaluated
• Domain is denoted by the symbol, U, which means universe
• Examples of domain


  • For the function of f(x) = √x, the domain is the set of all non-negative real numbers (x > 0)
  • For the predicate P(x) representing "x is a prime number," the domain might be the set of positive integers
  • In the predicate statement ∀x, x > 0, the domain is typically the set of real numbers
• Propositional function


  A function that takes ONE or MORE PARAMETERS as input and outputs of a proposition
• Proposition


  A statement that is either true or false when evaluated
• Propositional function and propositions

  • Propositional function: Q(x, y) = x > y

  Propositions: Q(5,3) = 5 > 3 = T

  R(-2, 6) = -2 < 6 > 13 = (T, F) FALSE

  R(1, 15) = 1 < 15 > 13 = (T, T) TRUE
• Propositional function and propositions with variables

  • Variable: y

  Predicate: <2

  Truth Value: Q(9) = 9 < 2 = F

  Variable: x, y

  Predicate: -5=y (subtracted by 5 is equal to y)

  Truth Value: R(-5, 0) = -5 - 5 = -10 = F
• Compound expressions


  Connectives used in propositional logic are carried over to predicate logic
• Quantifiers


  Logical constructs used in predicate logic to express the extent of applicability of a statement over a domain
• Universal quantifier


  Asserts that a statement P(x) holds true for every element x in the domain
• Existential quantifier


  Asserts that there exists at least one element x in the domain for which the statement P(x) holds true
• Translating quantifiers


  • Every student in this class will pass this subject.

  Domain: Students in this class

  Variable: Student = x

  Predicate/s: x will pass this subject = P(x)

  Quantifiers: "Every", ∀

  Logical Connectives: None

  Notation: ∀x P(x)

  Read: For all x, x will pass this subject.
• Translating quantifiers with more details

  • Domain: people {person 1, person 2….}

  Variable: Student = x

  Predicate/s: x is student in this class = S(x)

  x will pass this subject = P(x)

  Quantifiers: "Every", ∀

  Logical Connectives: Implication (→); Conjunction (∧)

  Notation: ∀ x (S(x) → P(x))

  Read: For all x, if x is a student in this class, then x passes this subject.

  Notation: ∀ x (S(x) ∧ P(x))

  Can use "AND" instead of "IMPLICATION"
• Augustus De Morgan (1806-1871) was a British mathematician and logician best known for formulating De Morgan's laws
• De Morgan is also known for coining the term mathematical induction and formalizing the principles underlying induction
• De Morgan's laws


  Describes how mathematical statements and concepts are related through their opposites
• Negation of universal quantification


  "¬∀x P(x)" is equivalent to Existential Quantification of Negation "∃x ¬P(x)"
• Negation of existential quantification

  "¬∃x P(x)" is equivalent to Universal Quantification of Negation "∀x ¬P(x)"