Posted on by rpicard92

Formal Methods 101: First-Order Logic (FOL)

Introduction:

  • First-Order Logic extends Zero-Order Logic (or Propositional Logic) to include variables and quantifiers.
  • First-Order Logic operators are used to form expressions over variables. These expressions over variables are known as ‘predicates’. Predicates are Boolean-valued functions that return either TRUE or FALSE depending on the value assignments of their variables.
  • First-Order Logic is made of up Logical Symbols (Negations, Binary Connectives, and Quantifiers) and Non-Logical Symbols (Predicate Symbols).

Non-Logical Symbols:

  • Predicate Variable (symbol):
    • Ex. 1 – Predicate Variable (symbol) with a valence of 0: A
    • Ex. 2 – Predicate Variable (symbol) with a valence of 2: A(b,d)
    • A predicate variable is a Boolean-valued variable that may take on the value of TRUE (1) or FALSE (0). Therefore, the Predicate variable A may be either TRUE or FALSE.
    • A predicate may have N-arguments and is said to have valence (or arity, i.e. number of arguments) of between 0 and N; depending on the number of arguments. The argument values determine the whether the predicate variable evaluates to TRUE or FALSE.
  • Function:
    • Ex. Function: f(b,v)
    • This is in line with the standard definition of a function that is not required to return a Boolean value.

Logical Symbols:

  • Negation (NOT): ¬
    • Ex. Predicate: ¬A
    • This negation relation, means the negation (opposite) of the assigned Boolean-valued variable A is TRUE. (If A is assigned TRUE, the predicate expression ¬A evaluates to FALSE. If A is assigned FALSE, the predicate expression ¬A evaluates to TRUE
  • Conjunction (AND): ∧
    • Ex. Predicate: A ∧ B
    • This conjunction operator means the predicate is TRUE if and only if (iff) predicate variables A AND B are assigned the value of TRUE.
  • Disjunction (OR): ∨
    • Ex. Predicate: A ∨”B”
    • This conjunction operator means the predicate is TRUE if and only if (iff) predicate variables A OR B are assigned the value of TRUE.
  • Material Implication: →
    • Ex. Predicate: A→B
    • This material implication operator means if predicate variable A is TRUE, then predicate variable B is TRUE. (Note: it gives not information about what B is if A is not TRUE.)
    • Note: This predicate may be TRUE or FALSE depending on if it breaks the rules of the material implication operations.
  • Material Bijection: ↔
    • Ex. Predicate: A↔B
    • This material bijection operator means, if A is TRUE, then B is TRUE, and if B is TRUE, then A is TRUE, if A is FALSE, then B is FALSE, and if B is FALSE, then A is FALSE. (In other words the Boolean value for both A and B is never different.)
    • Note: This operator is equivalent to implication both ways; in other words (A→ B) ∧ (B ← A).
    • Note: This predicate may TRUE or FALSE depending on if it breaks the rules of the material bijection operations.

Order of operations for FOL:

  1. ¬ is evaluated first
  2. ∧ is evaluated next
  3. ∨ is evaluated next
  4. ∀ & ∃ quantifiers are evaluated next
  5. → is evaluated last (thus so is ↔)

Example FOL Predicate:

  • ∀B∃A ( (C(x,y)∧¬D)→((A∧E(t,z))∨F) )
  • This is read for all B, there exist an A, such that, C and not D, implies A and E or F.
  • As seen, FOL is very expressive. This can be used to build extensive complex models of the domains of discourse.