Day 05Part 01-Discrete mathematics-First order Predicate logic or predicate calculus with example

Day 05Part 01-Discrete mathematics-First order Predicate logic or predicate calculus with example

Discrete Mathematics – First Order Predicate Logic (Predicate Calculus) | Day 05 Part 01

What is Predicate Logic?

Predicate Logic (also known as First-Order Logic or Predicate Calculus) is an extension of propositional logic. It allows expressions with quantifiers and variables, providing more expressive power.

Components of Predicate Logic:

1. Predicates: Functions that return True or False based on inputs.
   • Example: $P(x)$: “x is a student.”
2. Variables: Represent entities in the domain.
   • Example: $x,y,z$
3. Quantifiers: Indicate the scope of variables.
   • Universal Quantifier ( ∀ ): Means “for all.”
     • Example: ∀x P(x) — “For all x, P(x) is true.”
   • Existential Quantifier ( ∃ ): Means “there exists.”
     • Example: ∃x P(x) — “There exists an x such that P(x) is true.”
4. Logical Connectives:
   • ∧ (AND), ∨ (OR), ¬ (NOT), → (IMPLIES), ↔ (IF AND ONLY IF)

Example of Predicate Logic:

• Statement: “All humans are mortal.”
• Predicate Representation:
  • Let $H(x)$: “x is a human.”
  • Let $M(x)$: “x is mortal.”
  • Logical Form: ∀x (H(x) → M(x))
• Interpretation: For every x, if x is a human, then x is mortal.

Example of Existential Quantifier:

• Statement: “There exists a student who is intelligent.”
• Predicate Representation:
  • $S(x)$: “x is a student.”
  • $I(x)$: “x is intelligent.”
  • Logical Form: ∃x (S(x) ∧ I(x))
• Interpretation: There exists an x such that x is a student and x is intelligent.

Negation in Predicate Logic:

• Negating Universal Quantifier:
  • ¬(∀x P(x)) ↔ ∃x ¬P(x)
• Negating Existential Quantifier:
  • ¬(∃x P(x)) ↔ ∀x ¬P(x)

Example:

• “Not all birds can fly.”
  • $B(x)$: “x is a bird.”
  • $F(x)$: “x can fly.”
  • Logical Form: ¬∀x (B(x) → F(x))
  • Equivalent: ∃x (B(x) ∧ ¬F(x)) — “There exists a bird that cannot fly.”

Applications of Predicate Logic:

• Computer Science: Database querying and AI.
• Mathematics: Formal proofs and set theory.
• Linguistics: Analyzing sentence structures.

Practice Problems:

1. Express the following statements in predicate logic:
   • (a) “Every person loves pizza.”
   • (b) “There is a number that is greater than 10.”
2. Write the negation of the statement: “All dogs are loyal.”

If you need help solving the problems or understanding the concepts further, feel free to ask!

Day 05Part 01-Discrete mathematics-First order Predicate logic or predicate calculus with example

I. Practice in 1st-order predicate logic – with answers.

Discrete Mathematics Introduction to First-Order Logic