Logical Expressions in Predicate Logic

A logical expression in predicate logic has much the same form as a logical expression in propositional logic, with the addition of atomic formulae (ie., predicates), and the universal and existential quantifiers.

1. An atomic formula is a logical expression.
   • A predicate with all constant arguments is a ground atomic formula.
   • A proposition is a predicate with no arguments, and therefore is a ground atomic formula.
   • A predicate with at least one variable argument is a nonground atomic formula.
   • A literal is either an atomic formula or its negation.

2. If L1 and L2 are logical expressions, then L1 AND L2, L1 OR L2, NOT L1, L1 -> L2, and L1 == L2 are logical expressions.

3. If L1 is a logical expressions, then (A X) L1 is a logical expression.

4. If L1 is a logical expressions, then (E X) L1 is a logical expression.

Quantifiers have the highest precedence in logical expressions.

Bound and Free Variables

The quantifiers E (there exists) and A (forall) introduce variables into logical expressions.

An occurrence of variable x in a logical expression is bound to the closest enclosing quantifier containing x, either (E x) or (A x).

If an occurrence of x in a logical expression is not bound to any quantifier (because there is no enclosing quantifier containing x) that occurrence of x is free.

Example:

      (A x) L1(x) OR (E x) L2(x,y)
  

Evaluating Predicates

There are two ways to evaluate the truth of a predicate P(x,y):

• Assign a real-world interpretation to P (such as addition, subtraction, or equivalence) and a domain for P (ie, the possible values for the arguments) and compute the function P(x,y) under that interpretation.

  • If we assign the interpretation "equivalence" to P, and let the domain for P be the set of integers, then we can evaluate P(1,2) by asking is 1 equivalent to 2 (false).

  • If we assign the interpretation "less than" to P, and let the domain for P be the set of integers, then we can evaluate P(1,2) by asking is 1 less than 2 (true).

  • If we assign the interpretation "brother" to P, and let the domain for P be all students on campus, then we can evaluate P(Adam,Barney) by asking whether or not Adam and Barney are brothers.

• Consult a relational database containing pairs of values for x and y and the corresponding value of P(x,y).

  • If the interpretation for P is "grade in CSC173" and the domain of x is all students on campus, and the domain of y is the set of possible grades, then we can evaluate P(Rosemary,"A") by looking up Rosemary's grade in the grade file for 173.

  • If we assign the interpretation "has a better overall record" to P, and let the domain of P be the set of professional football teams, then we can evaluate P(Buffalo, Miami) by looking up their respective records in a football database.

Evaluating Predicates: Example

Consider the following family history to be relations (or facts) in a family tree database:

      male(Adam)             female(Ann)
      male(Barney)           female(Beth)
      male(Bob)              female(Barb)
      male(Carl)             female(Carol)
      male(Chet)             female(Chris)
  
      parent(Adam,Barney)    parent(Ann,Barney)
      parent(Adam,Beth)      parent(Ann,Beth)
      parent(Adam,Bob)       parent(Ann,Bob)
      parent(Adam,Barb)
  
      parent(Barney,Carl)    parent(Carol,Carl)
                             parent(Carol,Chet)
  

To find the name of Barney's father, we can assert the following to be true:

      parent(x,Barney) AND male(x) -> father(x,Barney)
  

Note that we haven't defined a father relation in our database; asserting the above expression to be true is the only definition of "father" we need.

We know this expression evaluates to true (since we asserted it) regardless of the value of x. We can assign a constant value to x (someone's name), producing ground atomic formulae, which we can evaluate as true or false.

When we substitute Adam for x, we find parent(Adam,Barney) and male(Adam) are true, so father(Adam,Barney) must be true as well (since the whole expression must be true).

Evaluating Quantifiers

To evaluate a quantifier for a predicate we must first define

• the domain over which the quantifier varies (that is, the set of values for the predicate's arguments)
• the interpretation of the predicate (that is, the meaning of the predicate)

When we state "there exists x such that P(x)" we must be explicit about the possible values x can take (the domain of P). We evaluate P(x) for each value of x in the domain of P (according to the interpretation for P), and if P(x) is true for some x, then the expression (E x)P(x) is true.

Similarly, when we assert "for all x P(x)" we must be clear about what possible values of x we consider (again, the domain of P). We evaluate P(x) for all values of x in the domain of P (again, according to the meaning of P), and if P(x) is true for all x, then the expression (A x)P(x) is true.

Note that if the domain of P is infinite, we don't have an algorithm (which terminates) to compute the value of P.

• In many cases, we'll have a finite domain, so we do have an algorithm.
• In many cases we're concerned about whether two expressions are equivalent, and not whether a particular expression is true or not.

Evaluating Predicate Expressions: Example

      P(x,y) -> (E z)(P(x,z) AND P(z,y))
  

If we make the domain of P the set of real numbers, assign the values 5.1 and 4.2 to the free variables x and y, and interpret P to mean "greater than", then we can evaluate the expression as follows:

      P(x,y) = P(5.1,4.2)
  	   = 5.1 > 4.2
  	   = true
  
      (E z) (P(x,z) AND P(z,y))
  	   = (E z)((5.1 >z) AND (z > 4.2))
             = true (for z=4.8)
  
      true -> true = true
  

If we make the domain of P the set of integers, assign the values 5 and 4 to the free variables x and y, and interpret P to mean "greater than", then we can evaluate the expression as follows:

      P(x,y) = P(5,4)
  	   = 5 > 4
  	   = true
  
      (E z) (P(x,z) AND P(z,y))
  	   = (E z)((5 > z) AND (z > 4))
             = false
  
      true -> false = false