Predicate Logic - Rensselaer Polytechnic Institute



Predicate Logic

Alphabet: The Language of Predicate Logic

A set of Individual Constants: Con = {a, b, c, …}

A set of Variables: Var = {x, y, z, …}

A set of Function Symbols: Fn = {f, g, …}

A set of Predicate Symbols: Pr = {P, Q, …}

Logical Connectives: (, (, (, (, (

Two Quantifiers: (, (

An Identity Predicate: =

Individual Constants

Individual constants are used to denote objects. These objects can be anything. A single object can be denoted by multiple individual constants, reflecting the fact that objects can have multiple names. On the other hand, any individual constant can only denote one object. So, the use of two different constants ‘a’ and ‘b’ does not mean that we are dealing with two different objects. However, every use of ‘a’ must consistently refer to the same object.

Variables

Variables are also used to denote objects, but not a specific one. That is, a variable can be used to denote some arbitrary object, just like variables in mathematics.

Functions and Predicates

Functions and predicates take an arbitrary but finite number of arguments. The difference between functions and predicates is that a function picks out some object given some other objects, whereas a predicate expresses that some object has some property or that some objects stand in some kind of relationship. Thus, predicates will be used to denote claims, whereas functions are used to denote objects. For example, with ‘father’ a function symbol used to denote the mapping from objects to their father, ‘father(a)’ picks out the object that is the father of ‘a’. On the other hand, with ‘Father’ a 2-place relationship denoting that the first argument is the father of the second argument, ‘Father(a, b)’ denotes the claim that ‘a’ is the father of ‘b’.

The number of arguments is called the arity of that function and predicate. A function and predicate with arity n is also called an n-place function and predicate. One can allow for 0-place functions and predicates; a 0-place function would take the role of an individual constant, while a 0-place predicate takes the role of an atomic proposition. However, for simplicity sake, it will be assumed from now on that the arity of any function or predicate is greater than 0. A special 2-place predicate is ‘=’, which will always be used to denote the identity relationship.

Quantifiers

There are two quantifiers: the universal quantifier ( and the existential quantifier (. The universal quantifier ( is used to make a statement about all relevant objects, whereas the existential statement is used to make a statement about some relevant objects (‘some’ meaning ‘at least one’).

Syntax: Terms, Well-Formed Formulas, and Sentences

Terms

The arguments of predicates and functions are terms. Terms are used to denote objects. Terms are recursively defined as follows:

1. Basic Terms: Every individual constant and variable is a term.

2. Complex Terms: With t1, …, tn terms and f a function, f(t1, …, tn) is a term.

Well-Formed Formulas (wff’s)

A well-formed formula is recursively defined as follows:

1. Atomic wff’s: With t1, …, tn terms and P a predicate, P(t1, …, tn) is a wff.

2. Complex wff’s: With (( wff’s and v a variable:

a. (( is a wff.

b. ( ( ( is a wff

c. ( ( ( is a wff

d. ( ( ( is a wff

e. ( ( ( is a wff

f. (v ( is a wff

g. (v ( is a wff

Sentences

A wff of the form (v ( is a universally quantified wff. A wff of the form (v ( is an existentially quantified wff. In both wff’s v is called the quantified variable, and ( is the scope of the quantifier. Every instance of a variable that is within the scope of a quantifier that quantifies that variable is said to be bound by that quantifier, except when it is already within the scope of another quantifier within ( that quantifies that variable. Any variable that is not bound by any quantifier is called free. A sentence is any wff that does not contain any free variables. A sentence of the form (v ( is called a universal quantification. A sentence of the form (v ( is an existential quantification.

Example: In the wff (x { P(x) ( (y [ S(y) ( T(z) ( (y (R(x,y) ( R(x,z))]}, all instances of x are bound by the first quantifier, the y in S(y) is bound by the second quantifier, the y in R(x,y) is bound by the third quantifier, and both instances of z are free. Hence, this wff is not a sentence.

Semantics: Interpretations and Evaluations

Interpretations

An interpretation I for a language L consists of the following:

1. A domain, or universe of discourse D. D is some non-empty set of objects.

2. A mapping I : Con ( D

3. A mapping I : Fn ( Fun, where Fun is the set of all n-place functions from Dn to D for all n, such that if I(f) = f’ and n is the arity of f, then f’ is some mapping f’: Dn (D

4. A mapping I : Pr ( Pred, where Pred is the set of all subsets of Dn for all n, such that if I(P) = P’ and n is the arity of P, then P’ ( Dn

Evaluating Terms given some Interpretation

Given some interpretation I for language L, we can recursively define a mapping from variable-free terms of L to objects in D:

1. I(f(t1, …, tn)) = f’(I(t1), …, I(tn)) where IFn(f) = f’

Evaluating Sentences given some Interpretation

Given some interpretation I for language L, we can recursively define a mapping from sentences of L to {True, False}:

1. I(P(t1, … tn)) = True iff < I(t1), …, I(tn)> ( P’ where I(P) = P’

2. I(t1 = t2) = True iff I(t1) = I(t2)

3. I((() = True iff I(() = False

4. I(( ( () = True iff I(() = True and I(() = True

5. I(( ( () = True iff I(() = True or I(() = True

6. I(( ( () = True iff I(() = False or I(() = True

7. I(( ( () = True iff I(() = I(()

8. I((v () = True iff I(([d]) = True for every d ( D

9. I((v () = True iff I(([d]) = True for some d ( D

In 8 and 9, I (([d]) is short for I[d/a](([a/v]), where ‘a’ is an individual constant symbol that does not appear in L, where I[d/a] is called a modified interpretation which is an interpretation for the extended language L ( {a} and that will be the same as I, except that ‘a’ will be mapped to d, and where ([a/v] is the result of substituting individual constant ‘a’ for all instances of variable v bound by the quantifier that is being dropped in the application of 8 or 9.

When I(([d]) = True, we say that d satisfies wff ((x).

Models, FO Consequence, Tautology, Equivalence, and Consistency

Models

An interpretation I for a sentence ( is a model for ( iff I(() = True. An interpretation I for a set of sentences ( is a model for ( iff I(() = True for all ( ( (. If I is a model for ( (or (), then I is said to satisfy ( (or (). We will write this as I ⊨ ( (or I ⊨ (). If for some interpretation I it holds true that if I ⊨ ( then I ⊨ (, then we write ( ⊨I (.

First-Order Consequence

A sentence ( is a first-order consequence of a set of sentences ( iff for any interpretation I for (({(}: ( ⊨I (. Thus, ( is a first-order consequence of a set of sentences ( iff there exists no interpretation I for (({(} such that I is a model for ( while I(() = false.

If ( is a first-order consequence of a set of sentences (, then we write ( ⊨ (. (to explicitly differentiate this from truth-functional consequence, we can use ( ⊨FO ( and ( ⊨TF ( respectively.)

A sentence ( is a first-order consequence of a sentence ( iff for any interpretation I for {(, (}: if I is a model for (, then I is a model for (. We’ll write this as ( ( (.

First-Order Tautology

A sentence ( is a first-order tautology iff any interpretation I for ( is a model for (. Obviously, ( is a first-order tautology iff {} ⊨ (. This we’ll abbreviate as ⊨ (.

First-Order Equivalence

Two sentences ( and ( are first-order equivalent iff they are first-order consequences of each other, i.e. iff ( ( ( and ( ( (. We’ll write this as ( ( (.

First-Order Consistency

A set of sentences ( is first-order consistent iff there exists a model for (.

Some Important Equivalences

Quantifier Negation:

With ((x) a wff with x as a possible free variable:

1a. ((x ((x) ( (x (((x)

1b. ((x ((x) ( (x (((x)

Null Quantification:

With ( a sentence (and hence having no free variables)

2a. (x ( ( (

2b. (x ( ( (

Replacing Bound Variables:

With ((x) a wff with x as a possible free variable, and with ((y) the result of substituting all free instances of x with y:

3a. (x ((x) ( (y ((y)

3b. (x ((x) ( (y ((y)

Aristotelean Square of Opposition:

4a. ((x (((x) ( ((x)) ( (x (((x) ( (((x))

4b. ((x (((x) ( ((x)) ( (x (((x) ( (((x))

Quantifier Distribution:

5a. (x (((x) ( ((x)) ( (x ((x) ( (x ((x)

5b. (x (((x) ( ((x)) ( (x ((x) ( (x ((x)

Prenex Laws

For conjunction and disjunction (generalize to generalized conjunctions and disjunctions):

6a1. (x (((x) ( () ( (x ((x) ( (

6a2. (x (((x) ( () ( (x ((x) ( (

6b1. (x (((x) ( () ( (x ((x) ( (

6b2. (x (((x) ( () ( (x ((x) ( (

For conditional:

6c1. (x (((x) ( () ( (x ((x) ( (

6c2. (x (((x) ( () ( (x ((x) ( (

6d1. (x (( ( ((x)) ( ( ( (x ((x)

6d2. (x (( ( ((x)) ( ( ( (x ((x)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download