Predicate Logic - Introduction

Introduction

Propositional logic has three principal strengths:

1. For any argument valid in propositional logic, there is a corresponding valid argument in English.
2. The Truth tables in propositional logic provide easy to read decision procedures in propositional logic.
3. There is an easy-to-understand proof system.

However, there are many weaknesses to predicate logic:

1. Propositional logic is not expressive enough to capture all arguments. Ex: All men are mortal and Socrates is a man, therefore Socrates is mortal. This is translated to P and Q, therefore R.
2. Predicate logic can prove all things in propositional logic (and thus is redundant).

There are many symbols used in predicate logic which are used to express objects, variables, predicates, etc. Here we have the following symbols:

1. Names: lowercase letters a-v with or without numerical subscripts.
2. N-place Predicates: uppercase letters A-Z with or without numerical subscripts.
3. Variables: lowercase letters, w-z with or without numerical subscripts.
4. Quantifiers: ∀,∃

The following are predicate logic formation rules (proper way of combining symbols):

1. An n-place predicate P followed by n names is a wff. Ex: Rab and Pa are wffs.
2. If P is a wff, then ¬P is a wff.
3. If P and Q are wffs, then the traditional propositional logic wff’s are wffs.
4. If P is a wff containing a name a, and if P(x/a) is what results from substituting the variable x for every occurrence of a in P, then ∃xP(x⁄a)  and ∀xP(x⁄a). This rule states that if you have proposition Pa, then if you substitute the name a with variable x and get P(x). However, P(x) is not a wff. X must be bounded via a quantifier.
5. Nothing else is a wff except that which can be formed from the above rules.

Predicates are used in relational statements about things. For instance, x is tall, x is taller than y, or x is between y and z. The first example is a 1 place predicate, then 2 place, and then 3 place.

Models

In propositional logic the semantics are simple. Like in propositional logic, atomic propositions are assigned truth values via interpretation function, and compound functions are assigned truth values via valuation functions. Predicate logic needs:

1. Model:(Μ) a two-part structure consisting of: 
1. A domain of discourse (D) 
2. An interpretation function (Ι) 
2. A valuation function (v)

Therefore, Μ=⟨D, Ι⟩.

A domain is a set of things which can be restricted or unrestricted (contain all things). You can specify this in two ways:

a)      List the names of each items in the domain.

b)      Specify the property that all items in the domain have.

There are certain ways to specify a domain, here are some examples:

1. D={David,Liz,Ryan,Paul}
2. D={a,b,c,d}
3. D={Humans}

An interpretation function takes each name and assigns it an object in the domain. Example: D={a,b,c,d}, then I(b)=Liz. It should be noted that an object can have multiple names. Interpreting 1-place predicates would result in assignment of a set of objects. Ex: I(R)={2,4,6},D={1,2,3,4,5,6}, or I(P)={tall people},D={people}.

An ordered pair is a special set where order matters so 〈i,j〉≠〈j,i〉, although {i,j}={j,i}. A tuple is an ordered pair but extended to n elements. So:

1. We assign objects in D to names.
2. We assign a set of n-tuples over D to n-place predicate terms.

We can see how this works with a two-place predicate G that says x greater than y, assume we have the domain:

1. D={a,b,c}
2. I(a)=1, I(b)=2, I(c)=3
3. I(G)={〈3,2〉,〈3,1〉,〈2,1〉}

Valuation

A valuation function assigns one and only one truth value to each predicate logic wff:

1. $ v(Ra_i )=T $ iff the interpretation of $ a_i $ is in R. $ I(a_i)∈I(R) $.
2. We can also use propositional logic valuation functions.
3. Assigns truth values of quantified formula with respect to the model:
1. (∀x)Px: everything is P in the model.
2. (∃x)Px: at least one thing in P is in the model.

The following are examples of valuation. Example:

1. Circles: D={1,2,3},I(a)=1, I(b)=2, I(c)=3, I(C)={1,2,3}, I(L)={x is larger than y}={〈3,2〉, 〈3,1〉,〈2,1〉}, I(G)={red ball}={c}.
2. Valuations: I(a)∈I(G), then v(Ga)=F, I(c)∈I(G),then v(Gc)=T, 〈I(a),I(b)〉∈I(L), then v(Lab)=F, 〈I(c),I(b)〉∈I(L), then v(Lcb)=T, and x∈I(G), then v(∀xGx)=T

Translation

To translate predicate logic into natural language you must first, stipulate the domain of discourse. Then you must interpret all predicate logic names into English names. Finally, we interpret all n-place predicates into English predicates. Example: Anne is happy, then Pa. Jon is taller than Frank, then Gbc. It is not the case that both Jon is taller than Frank and Frank is taller than Jon, then ¬(Gbc∧Gcb).

Universal Quantifier: For every x, every x, for all xs, for each x.

Existential Quantifier: For some x, some xs, there exists an x, there is at least one x.