| Comment. Sentential logic allows us to study the logical relations among sentences that hold because of their structure, insofar as that structure is determined by the presence of connectives. But sentential logic cannot handle the similarity between `Kareem is tall' and `Akeem is tall', not to mention `Someone is tall'--these would be represented as P, Q,and R, as if they had nothing in common. We now introduce a new language that accommodates this further structure. | |
| vocabulary |
Definition. The VOCABULARY OF PREDICATE LOGIC consists
of
|
| Sentence letters, connectives, and parentheses are adopted from the language of sente ntial logic. | |
| names | Definition. A NAME is a symbol from the following list: a, b, c, d, a1, b1, c1, d1,.... |
| variables | Definition. A VARIABLE is a symbol from the following list: u, v, w, x, y, z, u1 v1, w1, x1, y1, z1, u2, v2,.... |
| Comment. Names and variables are used to refer to objects in much the same way as names and certain kinds of pronouns in English. Section 3.2 deals with translation between English and the language defined in this section. | |
| 1-place predicate letter |
Definition. A 1-PLACE PREDICATE LETTER is any symbol from the following list: A1, B1, C1,..., A11, B11, C11, A12, B12, C12,... |
| 2-place | A 2-PLACE PREDICATE LETTER is any symbol from the following list: A2, B2, C2,..., A21, B21, C21, A22, B22, C22,... |
| n-place | In general, an n-PLACE PREDICATE LETTER is any symbol f rom the list: An, Bn, Cn,..., An1, Bn1, Cn1, An2, Bn2, Cn2,... |
| many-place | Comment. Predicate letters with more than one place are referred to as MANY-PLACE PREDICATE LETTERS. Predicate letters will sometimes be referred to as `predicates' for short. |
| Comment. In practice the superscripts can be omitted. Any of the capital letters may appear as sentence letters or predicate letters. It is usually possible to tell how a letter is being used in a wff by looking at the number of names or variables immediately following it. A capital letter with no names or variables is a sentence letter, one followed by one name or variable is a 1-place predicate, and so on. Also, the letters `R' and `S' are often reserved for 2-place predicates. | |
| metavariables | Comment. The Greek letters a, b, g, etc. are used as METAVARIABLES for the names and variables of predicate logic. |
| universal quantifier |
Definition. A UNIVERSAL QUANTIFIER is
any symbol of the form where a is a variable. |
| Comment. Universal quantifiers correspond to the English word `every'. | |
| existential quantifier |
Definition. An EXISTENTIAL QUANTIFIER is
any symbol of the form |
| Comment. Existential quantifiers correspond to the English word `some'. | |
| expression | Definition. An EXPRESSION OF PREDICATE LOGIC is any sequence of items from the vocabulary of predicate logic. |
| wffs |
Definition. A WELL-FORMED FORMULA of predicate logic is
any expression in accordance with the following six rules: |
| (1) | Sentence letters are wffs. |
| (2) | An n-place predicate letter followed by n names is a wff. |
| atomic sentence | [Definition. Wffs of the form specified in rule 1 or rule 2 are the ATOMIC SENTENCES of predicate logic.] |
| Comment. We adopt the practice of omitting super-scripts from predicates. | |
| (3) | Negations, conjunctions, disjunctions, conditionals, and bic onditionals of wffs are wffs. |
| Comment. The formation rules of chapter 1 are subsumed by this clause. | |
| (4) | If f is a wff, then the result of replacing a t least one occurrence of a name in f by a new variable a (i.e., a not in f) and prefixing @a is a wff. |
| universal wff | [Definition. Such wffs are called UNIVERSALLY QUAN TIFIED wffs, or UNIVERSAL wffs.] |
| (5) | If f is a wff, then the result of replacing at least one occurrence of a name in f by a new variable a (i.e., a not in f) and prefixing $a is a wff. |
| existential wff | [Definition. Such wffs are called EXISTENTIALLY QUANTIFIED wffs, or EXISTENTIAL wffs.] |
| (6) | Nothing else is a wff. |
| Examples | |
| Wffs of this language include the following: | |
((Fa v Fb) -> Gab) | |
$yFy | |
@x(Fx -> Gx) | |
@x@y(Rxy -> Ryx) | |
($xFx <-> @xGx) | |
($xFx -> P) | |
@x$yFyxb | |
| Exercise 3.1 | |
| Which of the following expressions are wffs? If an expression is a wff, say whether it is an atomic sentence, a negation, a conditional, a conjunctio n, a disjunction, a biconditional, a universal, or an existential. (Note: Any wff mus t fall into exactly one of these categories.) | |
| i* | Fz |
| ii* | @xGac |
| iii* | $x@y(Gxy & Gyx) |
| iv* | @x(Gxy <-> $yHy) |
| v* | $x(Ax -> @xFxx) |
| vi* | @x@y(Fxy -> @z(Hxyz & Jz)) |
| vii* | @xFxx <-> @x@yFxy |
| viii* | ~@x~$z(Hz v Jx) |
| ix* | ~@x~$z(Hz v Jx) |
| x* | Ga -> @x~(Ha v Fxx) |
| xi* | P -> Gab |
| xii* | ~(P & ~$xFx) |
| xiii* | @x(Fx) & P |
| xiv* | $y(Fyyy & P) |
| xv* | @xyz(Fzx <-> Hxyz) |
| quantifier convention | Comment. When a wff contains an uninterrupted convention sequence of quantifiers of the same type, existential or universal, it is often convenient to omit repetitions of $ or @. |
| Examples. | |
| The expression | |
@xyz(Fxy & Gyz <-> Hzx) | |
| will be read as shorthand for | |
@x@y@z(Fxy & Gyz <-> Hzx). | |
| The expression | |
$xy@zw(Fxyz & Gwx -> ~Hzx) | |
| is to be read as | |
$x$y@z@w(Fxyz & Gwx -> ~Hzx). | |
| open formula | Definition. An OPEN FORMULA is the result of re-placing at least one occurrence of a name in a wff by a new variable (one not alre ady occurring in the wff). |
| Comment. Open formulas are not wffs and hence never appear as sentences in proofs. The notion of an open formula is used to present the rules of proof for predicate logic. | |
| Examples. Fx is an open formula. It occurs as part of the wff @xFx. | |
|
Fxy is an open formula. It occurs as part of the open formula $yFxy, which in turn is part of the wff @x$yFxy. | |
| scope | Definition. The SCOPE of a quantifier in a given formula is the shortest open formula to the right of the quantifier. |
|
Examples. In the wff (@xFx & $y(Fy -> Gy)),Fx(Fy -> Gy). | |
In the wff$y(Fy & @z(Gz v ~Rzy)),(Fy & @z(Gz v ~Rzy)),(Gz v ~Rzy). | |
| wider and narrower | Definition. A quantifier whose scope contains another quantifier is said to have WIDER SCOPE than the second. The second is said to have NARROWER SCOPE than the first. |
| bound variable | Definition. A variable, a, that is in the sc ope of a quantifier for that variable (i.e. @a or $a) is called a BOUND VARIABLE. A variable that is not bound by a quantifier is said to be UNBOUND or FREE. |
| Exercise 3.2* | Identify all the open formulas appearing in exercise 3.1. If an open formula appears in an expression that is not well-formed, give an example of a wff in which it might appear. |
| Exercise 3.3 | In the following expressions, determine the scopes of all quantifiers. |
| i | @x(Px -> @zRxz) |
| ii | @xPx -> @zRxz |
| iii | @xPx -> @z@xRxz |
| iv | @z(Px -> @xRxz) |
| v | @x$yFyxb |
| vi | $y(Fy & @z(Gz v ~Rzy)) |
| vii | @x@y(Fxy -> @z(Hxyz & Jz)) |
| viii | @x@y(Rxy -> Ryx) |
| ix | $z$x(Fxz -> @yGyxa) |
| x | $x(Fxa -> @yGyaa) |
| universalization | Definition. A UNIVERSALIZATION of a sente nce with respect to a given name occurring in the sentence is obtained by the following two steps: |
| (1) | Replace all occurrences of the name in the sentence by a variable a, whe re a does not already occur in the sentence. |
| (2) | Prefix @a to the open formula resulting from step 1. |
|
Examples. Universalizations of (Fa -> Ga)@x(Fx -> Gx)@y(Fy -> Gy). | |
Universalizations of
Faa@xFxx@yFyy. | |
| existentialization | Definition. An EXISTENTIALIZATION of a sentence with respect to a given name occurring in the sentence is obtained by the following two steps: |
| (1) | Replace at least one occurrence of the name in the sentence by a variabl e a, where a does not already occur in the sentence. |
| (2) | Prefix $a to the open formula resulting from step 1. |
| Comment. Notice the difference between step 1 in the definition of unive rsalization and step 1 in the definition of existentialization. Universalization requir es replacement of all occurrences of the variable a. | |
|
Examples. Existentializations of (Fa -> Ga)$x(Fx -> Gx),$x(Fa -> Gx),$y(Fy -> Ga).Existentializations of Faa$xFxx$xFax,$yFya. | |
| instance | Definition. An INSTANCE of a universally or existentially q uantified sentence is the result of the following two steps: |
| (1) | Remove the initial quantifier. |
| (2) | In the open formula resulting from step 1, uniformly replace all occurrences of th e unbound variable by a name. |
| Comment. This is called INSTANTIATING the sentence. The name is called the INSTANTIAL NAME. | |
| Examples. The sentence @xFxFa, Fb, Fc, etc.The sentence $x(Fx & Gx)has instances (Fa & Ga), (Fb & Gb), (Fc & Gc), etc.The sentence $x@y(Fxy -> Gy)@y(Fay -> Gy), @y(Fby -> Gy), etc. | |
| Exercise 3.4* | Pair wffs and their instances from the list of sentences below. Some form ulas may appear in several pairs. Others may appear in none. |
| i | @xFax |
| ii | $x(Fxa & @yGyxa) |
| iii | $xFax |
| iv | Fab |
| v | $y@xFyx |
| vi | $zx(Fxz & @yGyxa) |
| vii | @xyFxy |
| viii | @xFxa |
| ix | $zx(Fxz & @yGyxz) |
| x | Fba & @yGyba |