COSC5315                                                                    Fall 2013

 

Predicate Logic

 

More expressive and applicable due to adoption of some additional syntax elements such as

1. Arguments of predicate symbols (which are the same as variables in Propositional Logic)

2. Variables and (object) constants (in addition to Boolean constants, true and false)

3. Functions with any number of arguments.

4. Two quantifiers, Universal and Existential.

Here, $ and % are to be used throughout for the former and for the latter, respectively.

Arguments of either predicate symbols or functions are object constant, variables, or functions.

Examples:

 

1. ($X) Student(X)^Hard(X)^Honest(X)^Lucky(X) -> GoodGrade(X)

Above may mean: Every hard-working (and) honest and lucky student makes good grade.

 

2. (%X) Student(X) ^Hard(X)^Honest(X)

Above may mean: Some students are hard-working and also honest.

 

3. ($X%Y) Human(X)^Sincere(X)-> Human(Y)^Love(Y,X)^Love(X,Y)

Above may mean: Every sincere human has at least one human to love each other.

4. ($X$Y) Love(X,Y) -> Love(Y,X)

Above may mean: Love is mutual.

 

5. ($X$Y$Z) L(X,Y)^L(Y,Z) -> L(X,Z)

Above may mean: Love is transitive, that is, one loves anybody loved by somebody he/she loves, with no exception.

 

 

Some Equivalences

 

1.    ($X$Y) P(X,Y)                        ($Y$X)P(X,Y)

2.    (%X%Y) P(X,Y)                      (%Y%X)P(X,Y)

 

3.    ~($X) P(X)                   (%X) (~P(X))

 

4.    ~(%X)P(X)                  ($X) (~P(X))

 

5.    ($X) (P(X)^Q(X))                    ($X) P(X) ^ ($Y) Q(Y)                         ($X) P(X) ^ ($X) Q(X)

 

6.    (%X) (P(X)+Q(X))                   (%X) P(X) + (%Y) Q(Y)          (%X) P(X) + (%X) Q(X)

 

7.    (%X) (P(X)->Q(X))      ($X) P(X) -> (%Y) Q(Y)

 

Some almost equivalent cases:

 

                   Stronger WFF                                           Weaker WFF

8.    (%X) (P(X)^Q(X))                                           (%X)P(X) ^ (%X)Q(X)

 

9.    ($X)P(X) + ($X)Q(X)                          ($X) (P(X)+Q(X))       

 

10. (%X$Y) P(X,Y)                                               ($Y%X) P(X,Y)

 

11. (%X) (P(X) -> Q(X))                            ($X)P(X) -> ($Y)Q(Y)