Predicate logic is utilized for complex system specifications.
Examples are given to illustrate the use of predicates and domains.
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.
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.
Statements:
All lions are fierce.
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:
For all x
, p(x) → q(x)
∃x (p(x) ∧ ¬r(x))
∃x (q(x) ∧ ¬r(x))
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).
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).
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.