Recording-2025-02-09T21_06_21.236Z

Introduction to Predicate Logic

  • Predicate logic is utilized for complex system specifications.

  • Examples are given to illustrate the use of predicates and domains.

Example 1: Mail Message Compression

  • Statement: Every mail message larger than one megabyte will be compressed.

  • Implicit Domains: Discussing mail messages in general; specifically those on a computer system.

  • Predicates:

    • l(m, y): Mail message m has a size larger than y megabytes.

    • In this context, it simplifies to l(m, 1) for messages larger than 1 MB.

    • c(m): Mail message m will be compressed.

  • Logical Translation:

    • Statement: ∀m (l(m, 1) → c(m))

    • Interpretation: For all mail messages m, if m is larger than one megabyte, then m will be compressed.

Example 2: User Activity and Network Links

  • Statement: If a user is active, then at least one network link will be available.

  • Implicit Domains: Referring to all users and network links.

  • Predicates:

    • a(u): User u is active.

    • s(n, x): Network link n is in state x (where x could be available/unavailable).

  • Logical Translation:

    • Statement: ∃u (a(u) → ∃n (s(n, available)))

    • Explanation: If there exists an active user u, then there exists at least one network link n available.

    • Combining quantifiers and implication is valid.

Example from Lewis Carroll

  • Statements:

    1. All lions are fierce.

    2. Some lions do not drink coffee.

  • Conclusion: Some fierce creatures do not drink coffee.

  • Domains: All creatures.

  • Predicates:

    • p(x): x is a lion.

    • q(x): x is fierce.

    • r(x): x drinks coffee.

  • Logical Translation:

    1. For all x, p(x) → q(x)

    2. ∃x (p(x) ∧ ¬r(x))

    3. ∃x (q(x) ∧ ¬r(x))

Validity and Satisfiability in Predicate Logic

  • Valid Assertion: An assertion is valid if it is always true for all domains and propositions substituted.

  • Example: ∀x (¬s(x) ↔ ¬∃x (s(x))).

  • Satisfiable Assertion: An assertion is satisfiable if it is true at least once.

  • Unsatisfiable Assertion: An assertion is unsatisfiable if it is never true (e.g., conjunctive contradictions).

Scope of Quantifiers

  • Definition: Scope of a quantifier is the part of an assertion that is influenced by the quantifier declaration.

  • Example of Wide Scope:

    • Expression: ∀x (c(x) ∨ e(x))

    • Meaning: All students in class are either computer science majors or engineering majors.

  • Example of Narrow Scope:

    • Expression: ∀x (c(x)) ∧ ∀y (e(y)) (using different variable labels for clarity).

    • Meaning: Every student in class is a computer science major, or every student in class is an engineering major (but not both).

Implications of Scope in Logic

  • The scope alters the interpretation significantly, especially with universal quantifiers and disjunctions.

  • Distribution of Universal Quantifiers: Cannot generally distribute over disjunction (as shown in the last example).

  • Each quantifier's scope affects the logical meaning of the statement and its truth value.

robot