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.

  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)
  
The variable x in L1 is bound to the universal quantifier. The variable x in L2 is bound to the existential quantifier. The variable y is free in this expression.

Evaluating Predicates

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


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)
  
This assertion states that if x is a parent of Barney, and x is male, then x is the father of 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

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.


Evaluating Predicate Expressions: Example

Consider the following logical expression in predicate logic:
      P(x,y) -> (E z)(P(x,z) AND P(z,y))
  
We can read this as "if P(x,y) then there exists z such that 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