CMPS 2120 Lecture Notes - Introduction to Predicate Logic

We cannot assign a truth value to a statement such as

    x + 3 = 5

unless we know the value of x. The statement as written is not a proposition. If x=2 then the statement is a proposition with value true. If x=3 then the statement is a proposition with value false. Likewise, the statement

   Birds can fly

is not a proposition since some birds can fly and some birds (e.g., emus) cannot. It would be useful to make assertions such as "Some birds can fly" (T) or "Not all birds can fly" (T) or "All birds can fly" (F).

Predicate (First Order) logic is an extension to propositional logic that allows us to reason about such assertions. The following constructs are needed to do so:


 Variables: x,y,z,...  that denote the "subjects" in a statement

 Predicates: claims about variable(s), denoted by P, Q, R, ... "P: > 3"

 Predicate functions: a predicate applied to variable(s), denoted by P(x), 
 Q(y), R(x,y), etc. "P(x): x < 7"

 Quantifiers: defines the number of values of a variable that must exist for
 the claim to be true: existential (for some x), denoted by ∃ and 
 universal (for all x), denoted by ∀

 A universe of discourse (domain) for variable(s); e.g. ∃x x + 3 = 5 is 
 true over the domain of integers but false over the domain of odd integers. 

 With these additions, we can reason about statements such as x + 3 = 5.

 Example:
 P(x): x + 3 = 5, over the domain of positive integers.

 ∃x P(x) means "For some positive integer x, x+3=5 is true."  
 
 ∃x P(x) is TRUE since P(2) is TRUE. 

 ∀x P(x) means "For all positive integers x, x+3=5 is true." 

 ∀x P(x) is FALSE since P(3) is FALSE.

Negation of existential quantifiers

To show that ∀x P(x) is false, you need only one counterexample:

  ∀x P(x) is FALSE because P(5) is FALSE: 5+3=5

Thus, the negation of the universal quantifer is:

    ~∀x P(x) ≡ ∃x ~P(x)      De Morgan's Law

To show that ∃x P(x) is false, show that P(x) is never true. Thus, negation of the existential quantifier is:

     ~∃x P(x) ≡ ∀x ~P(x)      De Morgan's Law

Example in English:

 
 Universe of discourse: All doors in SCI III.
 P(x): Door x is open.

 ∀x P(x): "All doors in SCI III are open."

 ~∀x P(x): "It is not the case that all the doors are open."

     is equivalent to 

  ∃x ~P(x): "Some door is closed."

  De Morgan's applied to the existential quantifier:

  ∃x P(x): "Some door is open."

  ~∃x P(x): "It is not the case that some door is open."
 
       is equivalent to

  ∀x ~P(x): "All doors are closed."

Logical Connectives in Predicate Logic

∃x P(x) ^ ∃y Q(y), where x and y are integers, means: "P is true for some integer x and Q is true for some integer x." Note that x and y could be bound to the same value. All logical operators may be used in predicate logic with the same order of precedence as in propositional logic. Quantifiers take precedence over all logical operators. For example,

     ∀x P(x) v Q(x)

stated more precisely is

 (∀x P(x)) v Q(x)  # not a proposition since last x is unbound

and not

   ∀x (P(x) v Q(x)).

In general, use parenthesis to avoid confusion.

Bound and Free Variables

A variable is either within the scope of a quantifier (bound to a value in the domain) or is free (unbound). In the statement

      ∃x P(x,y)

x is within the scope of the existential quantifier ∃. Variable y is not within the scope of a quantifer. This statement is is not a proposition until y has a quantifier and is bound to a value.

The same variable name may refer to different variable bindings if the variables are in different scopes. Thus, in the statement

      ∃x P(x) ^ ∀x Q(x)

the x in P(x) is within the scope of ∃ and will be bound to a variable in that context. The second x in Q(x) is bound to a value within the scope of the quantifier ∀. If x and y are from the same Universe of Discourse, x and y may be bound to the same value or to different values.

Likewise, the statement

    ∃x P(x) ^ ∃x Q(x)

means "For some x, P(x) is true and for some x (the value of which may or may not be the same as used in the first x) Q(x) is true."

Whereas, in this statement

       ∃x (P(x) ^ Q(x))

x is bound to the same value since both x's are within the scope of one existential quantifier ∃. This statement means

"For some x, P(x) and Q(x) is true." (x has one value)

Another example of scoping, where x ranges over the integers,

     P(x) : x > 2        Q(x) : x < 2

This statement

       ∃x (P(x) <-> Q(x))

means

 "For some x, x > 2 is true if and only if x < 2 is true."

On the other hand, this statement

       ∃xP(x) <-> ∃xQ(x)

means "For some x, x > 2 is true if and only if for some x, x < 2 is true" (x may or may not be bound to the same value)

In conclusion, the use of two different variable names; e.g.,

   ∃x P(x) ∧ ∀y Q(y)

does not prevent x and y from being bound to the same value. Once you understand these scoping rules you will understand the following equivalences.

 DISTRIBUTION RULES FOR STATEMENTS WITH TWO PREDICATES  

 ∀x(P(x) ∧ Q(x))  ≡ ∀xP(x) ∧ ∀xQ(x)
 ∀x(P(x) v Q(x)) !≡ ∀xP(x) v ∀xQ(x)


 ∃x(P(x) v Q(x))  ≡ ∃xP(x) v ∃xQ(x)
 ∃x(P(x) ∧ Q(x)) !≡ ∃xP(x) ∧ ∃xQ(x)

We can prove the above equivalences. For example, let's try to show that

     ∀x(P(x) ^ Q(x)) ≡ ∀xP(x) ^ ∀xQ(x).

We cannot use truth tables with quantifiers but we can express the meaning of the predicates in propositional logic without the quantifiers. Then we just need to show that both expressions have the same truth values.

By definition ∀x(P(x) ^ Q(x)) means 
    (P(x_1) ^ Q(x_1)) ^ (P(x_2) ^ Q(x_2)) ^...^ (P(x_n) ^ Q(x_n)), for all x_i in U.

Since ^ is non-associative, remove the parenthesis      
     P(x_1) ^ Q(x_1) ^ P(x_2) ^ Q(x_2) ^...^ P(x_n) ^ Q(x_n)

and apply the commutative law
    P(x_1) ^ P(x_2) ^...^ P(x_n) ^ Q(x_1) ^ Q(x_2) ^...^ Q(x_n) <-------------,
                                                                              |
Likewise, for all x_i in U, ∀xP(x) ^ ∀xQ(x) means                            |
    (P(x_1) ^ P(x_2) ^ ...^ P(x_n)) ^ (Q(x_1) ^ Q(x_2) ^ ...^ Q(x_n)).        |
                                                                              |
Remove the parenthesis.                                                       |
    P(x_1) ^ P(x_2) ^...^ P(x_n) ^ Q(x_1) ^ Q(x_2) ^...^ Q(x_n)  <------------'

Since the expressions match we are done.

Second Proof.
Show that ∀x(P(x) v Q(x)) and ∀xP(x) v ∀xQ(x) do not have the same truth
values. We cannot use truth tables with quantifiers but we can express the 
meaning of the predicates in logic without the quantifiers.

Expression #1.
By definition ∀x(P(x) v Q(x)) means
   (P(x_1) v Q(x_1)) ^ (P(x_2) v Q(x_2)) ^ ... ^ (P(x_n) v Q(x_n))

Expression #2.
By definition ∀xP(x) v ∀xQ(x) means
   (P(x_1) ^ P(x_2)) ^ ... ^ P(x_n)) v (Q(x_1) ^ Q(x_2)) ^ ... ^ Q(x_n))

Let P(x_1) be true, P(x_2)..P(x_n) be false, Q(x_1) be false and Q(x_2)..Q(x_n)
be true. Then #1 is true but #2 is false.

NEGATIONS OF EXPRESSIONS WITH TWO PREDICATES ~(∀x(P(x) ∧ Q(x)) ≡ ∃x(~P(x) ∨ ~Q(x)) "Somebody dislikes either peas or carrots." ~(∀x(P(x) ∨ Q(x)) ≡ ∃x(~P(x) ∧ ~Q(x)) "Somebody dislikes both peas and carrots." ~(∃x(P(x) v Q(x)) ≡ ∀x(~P(x) ∧ ~Q(x)) "Everybody dislikes both peas and carrots." ~(∃x(P(x) ∧ Q(x)) ≡ ∀x(~P(x) ∨ ~Q(x)) "Everybody dislikes either peas or carrots." Example of Distributing Quantifers Universe of discourse: all people P(x) : x loves carrots Q(x) : x loves peas ∃xP(x) ^ ∃yQ(y) ^ x="sam" We know Sam likes peas but we cannot make a stronger claim since y may or may not be bound to Sam. The implication in Predicate Calculus is powerful; e.g., ∀x(Q(x) -> x="Sam") means "No one but Sam likes peas." In Predicate Calculus we can distribute a universal quantifier over a conjunction ('≡' means logically equivalent): ∀x(P(x)^Q(x)) ≡ ∀xP(x) ^ ∀xQ(x) In English: "Everybody likes peas and carrots" is equivalent to "Everybody likes peas and everybody likes carrots." We can distribute an existential quantifier over a disjunction: ∃x(P(x) v Q(x)) ≡ ∃x P(x) v ∃x Q(x) "Someone likes peas or carrots" is equivalent to "Someone likes peas or someone likes carrots." We CANNOT distribute a universal quantifier across a disjunction: ∀x(P(x) v Q(x)) !≡ ∀xP(x) v ∀xQ(x) "Everybody likes peas or carrots" does not necessarily mean "Everybody likes peas or everybody likes carrots." We CANNOT distribute an existential quantifier over a conjunction: ∃x(P(x) ^ Q(x)) !≡ ∃xP(x) ^ ∃xQ(x) "Somebody likes peas and carrots" does not necessarily mean "Somebody likes peas and somebody likes carrots" since the somebody could be a different person in the second statement. We CANNOT distribute a universal or existential quantifier over an implication: ∀x(P(x) -> Q(x)) !≡ ∀x P(x) -> ∀x Q(x) ∃x(P(x) -> Q(x)) !≡ ∃x P(x) -> ∃x Q(x) Example. Universe of discourse: students at CSUB P(x) = "x is taking 12 units" Q(x) = "x has 3.5 GPA" ∃x P(x) reads "for some x P(x) is true" and means "Some student is taking 12 units." ~∃x P(x) reads "it is not the case that for some x P(x) is true" and means "No student is taking 12 units." ∀x ~P(x) reads "for all x P(x) is false" and means "No student is taking 12 units." ∀x P(x) reads "for all x P(x) is true" and means "Everyone is taking 12 units." ~∀x P(x) reads "It is not the case for all x that P(x) is true" and means "Not everyone is taking 12 units." ∃x ~P(x) reads "For some x P(x) is false" and means "Some student is not taking 12 units." ~∀x~P(x) is the same as ∃xP(x) ∀x (P(x) ^ Q(x)) reads "For all x, P(x) and Q(x) are true" and means "All students are taking 12 units and have a 3.5 GPA." ∀x (P(x) -> Q(x)) "For all x, P(x) implies Q(x). If a student takes 12 units he/she will have a 3.5 GPA. ∀x P(x) -> ∀xQ(x) "For all x, P(x) implies that for all x, Q(x). If a student takes 12 units, all students will have a 3.5 GPA or If a student doesn't take 12 units all students will have a 3.5 GPA. (makes no sense) ∃x (P(x) -> Q(x)) "There is an x, such that P(x) implies Q(x). If some student takes 12 units he/she will have 3.5 GPA. ∃x P(x) -> ∃x Q(x) "There is an x, such that P(x) implies there is an x such that Q(x) is true. If some student takes 12 units then some student has a 3.5 GPA or if some student doesn't take 12 units then some student has a 3.5 GPA. (makes no sense) Example. Is ∀x(P(x) -> Q(x)) ≡ ∀xP(x) -> ∀xQ(x)? Example: Given the universe of discourse: people in {sam,joe} P(x): x is smiling Q(x): x is happy ∀x(P(x) -> Q(x)) in English means "If someone is smiling then that someone is happy." Assume sam is smiling and happy. If Joe is not happy the implication is still true. If we distribute the universal quantifier we have ∀xP(x) -> ∀xQ(x) It is a little difficult to translate the meaning into English but roughly this means "If anyone is smiling then everyone is happy (this holds true for anyone who is smiling). " So if Sam is smiling and joe is not happy the implication is false. The statements are obviously not equivalent. In summary, the universal quantifer cannot distribute over ->. The universal quantifer can distribute over ^. Example: ∀xP(x) ^ ∀xQ(x) ≡ ∀x( P(x) ^ Q(x)) Universe of discourse: all students P(x) : know C Q(x) : know Java In English, "All students know C and all students know Java" is the same as "All students know C and Java."