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.

- 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.

- A predicate with all constant arguments is a
- If L1 and L2 are logical expressions,
then L1 AND L2, L1 OR L2, NOT L1, L1 -> L2, and
L1 == L2 are logical expressions.
- If L1 is a logical expressions,
then (A X) L1 is a logical expression.
- If L1 is a logical expressions, then (E X) L1 is a logical expression.

Quantifiers have the highest precedence in logical expressions.

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.

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.

- 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).
- 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.

- 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.

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).

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.

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