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.