Chapter Five
Identity and Operation Symbols
1 IDENTITY
A certain relation is given a special treatment in logic. This is the identity relation — the relation that relates each thing to itself and relates no thing to another thing. It is represented by a two-place predicate. For historical reasons, it is usually written as the equals sign of arithmetic, and instead of being written in the position that we use for other predicates, in front of its terms:
Copyright By PowCoder代写 加微信 powcoder
it is written in between its terms:
Except for its special shape and location, it is just like any other two-place predicate. So the following are formulas:
b=z ∨ ~b=c
∀x∀y[x=a → [a=y → x=y]] ∀x[Bx → ∃y[Cy ∧ x=y]]
This sign is used to symbolize the word ‘is’ in English when that word is used between two names. For example, according to the famous story, Dr. Jekyll is Mr. Hyde, so using ‘e’ for Jekyll and ‘h’ for Hyde we write ‘Jekyll is Hyde’ as ‘e=h’. And using ‘c’ for ‘ ‘, ‘a’ for ‘Superman’, and ‘d’ for we can write:
a=c ∧ ~a=d Superman is but Superman is not
It is customary to abbreviate the negation of an identity formula by writing a slash through the identity sign:
‘≠’ instead of putting the negation sign in front. So we could write:
a=c ∧ a≠d Superman is but Superman is not
We can represent the following argument:
Superman is either or
Superman is not ∴ Superman is
a≠j ∴ a=c
with the short derivation: 1. Show a=c
There are other ways of saying ‘is’. The word ‘same’ sometimes conveys the sense of identity — and sometimes not. Consider the claim:
Bozo and Herbie were wearing the same pants.
This could simply mean that they were wearing pants of the same style; if so, that is not identity in the logical sense. But it could mean that there was a single pair of pants that they were both inside of; that would mean identity.
Copyrighted material Chapter 5 — 1 Version of Aug 2013
CHAPTER 5 SECTION 1
a=c pr1 pr2 mtp dd
The word ‘other’ is often meant as the negation of identity. In the following sentences:
Agatha saw a dragonfly and Betty saw a dragonfly Agatha saw a dragonfly and Betty saw another dragonfly
the first sentence is neutral about whether they saw the same dragonfly, but in the second sentence Betty saw a dragonfly that was not the same dragonfly that Agatha saw:
∃x[Dx ∧ S(ax)] ∧ ∃y[Dy ∧ S(by)] ∃x[Dx ∧ S(ax) ∧ ∃y[Dy ∧ y≠x ∧ S(by)]]
y is other than x
1. Say which of the following are formulas:
a. Fa∧Gb∧F=G
b. ∀x∀y[R(xy) → x=y]
c. ∀x∀y[R(xy) ∧ x≠y ↔ S(yx)]
d. R(xy) ∧ R(yx) ↔ x=y
e. ∃x∃y[x=y ∧ y≠x]
2. Symbolize the following English sentences:
a. is Batman
b. isn’t Superman
c. If is Superman, is not from Earth
d. If is Superman, Superman is a reporter
e. Felecia chased a dog and Cecelia chased a dog.
f. Felecia chased a dog and Cecelia chased the same dog. g. Felecia chased a dog and Cecelia chased a different dog.
CHAPTER 5 SECTION 1
Copyrighted material Chapter 5 — 2 Version of Aug 2013
2 AT LEAST, AT MOST, EXACTLY, AND ONLY
The use of the identity predicate lets us express certain complex relations using logical notation.
At least one: If we want to say that Betty saw at least one dragonfly we can just write that there is a dragonfly that she saw:
∃x[Dx ∧ S(bx)]
At least two: If we want to say that Betty saw at least two dragonflies, we can say that she saw a
dragonfly and she saw another dragonfly, i.e. a dragonfly that wasn’t the first dragonfly: ∃x[x is a dragonfly that Betty saw ∧ ∃y[y is a dragonfly other than x that Betty saw]]
∃x[Dx ∧ S(bx) ∧ ∃y[Dy ∧ y≠x ∧ S(by)]]
This makes use of a negation of the identity predicate to symbolize ‘another’.
The position of the second quantifier is not crucial; we could also write the slightly simpler formula: ∃x∃y[Dx ∧ S(bx) ∧ Dy ∧ S(by) ∧ y≠x]
The non-identity in the last conjunct is essential; without it the sentence just gives the information that Betty saw a dragonfly and Betty saw a dragonfly without saying whether it was the same one or not.
At least three: If we want to say that Betty saw at least three dragonflies we can say that she saw a dragonfly, and she saw another dragonfly, and she saw yet another dragonfly — i.e. a dragonfly that is not the same as either the first or the second:
∃x[Dx ∧ S(bx) ∧ ∃y[Dy ∧ y≠x ∧ S(by) ∧ ∃z[Dz ∧ z≠x ∧ z≠ y ∧ S(bz)]]] Again, the quantifiers may all occur in initial position:
∃x∃y∃z[y≠x ∧ z≠x ∧ z≠ y ∧ Dx ∧ S(bx) ∧ Dy ∧ S(by) ∧ Dz ∧ S(bz)]
At most one: If we want to say that Betty saw at most one dragonfly, we can say that if she saw a
dragonfly and a dragonfly, they were the same:
∀x∀y[x is a dragonfly that Betty saw ∧ y is a dragonfly that Betty saw → x=y]
∀x∀y[Dx ∧ Dy ∧ S(bx) ∧ S(by) → x=y]
This doesn’t say whether Betty saw any dragonflies at all; it merely requires that she didn’t see more than
one. We can also symbolize this by saying that she didn’t see at least two dragonflies: ~∃x∃y[Dx ∧ Dy ∧ S(bx) ∧ S(by) ∧ y≠x]
It is easy to show that these two symbolizations are equivalent:
1. Show ∀x∀y[Dx ∧ Dy ∧ S(bx) ∧ S(by) → x=y] ↔ ~∃x∃y[Dx ∧ Dy ∧ S(bx) ∧ S(by) ∧ y≠x]
At most two: If we want to say that Betty saw at most two dragonflies either of the above styles will do: ∀x∀y∀z[Dx ∧ Dy ∧ Dz ∧ S(bx) ∧ S(by) ∧ S(bz) → x=y ∨ x=z ∨ y=z]
~∃x∃y∃z[Dx ∧ Dy ∧ Dz ∧ x≠y ∧ y≠z ∧ x≠z ∧ S(bx) ∧ S(by) ∧ S(bz)]
Exactly one: There are two natural ways to say that Betty saw exactly one dragonfly. One is to conjoin
the claims that she saw at least one and that she saw at most one: ∃x[Dx ∧ S(bx)] ∧ ∀x∀y[Dx ∧ Dy ∧ S(bx) ∧ S(by) → x=y]
Or we can say that she saw a dragonfly, and any dragonfly she saw was that one: ∃x[Dx ∧ S(bx) ∧ ∀y[Dy ∧ S(by) → x=y]]
Or, even more briefly:
∃x∀y[Dy ∧ S(by) ↔ y=x]
Copyrighted material Chapter 5 — 3 Version of Aug 2013
CHAPTER 5 SECTION 2
~∃x∃y[Dx ∧ Dy ∧ S(bx) ∧ S(by) ∧ y≠x] ∀x∀y~[Dx ∧ Dy ∧ S(bx) ∧ S(by) ∧ y≠x] ∀x∀y[Dx ∧ Dy ∧ S(bx) ∧ S(by) → x=y]
2 ie/qn ie/qn 3 ie/nc bd
Exactly two: Similarly with exactly two; we can use the conjunction of she saw at least two and she saw at most two:
∃x∃y[Dx ∧ S(bx) ∧ Dy ∧ S(by) ∧ y≠x] ∧
∀x∀y∀z[Dx ∧ Dy ∧ Dz ∧ S(bx) ∧ S(by) ∧ S(bz) → x=y ∨ x=z ∨ y=z]
or we can say that she saw two dragonflies, and any dragonfly she saw is one of them: ∃x∃y[Dx ∧ S(bx) ∧ Dy ∧ S(by) ∧ y≠x ∧ ∀z[Dz ∧ S(bz) → x=z ∨ y=z]]
or, even more briefly:
∃x∃y[y≠x ∧ ∀z[Dz ∧ S(bz) ↔ z=x∨z=y]]
Talk of at least, or at most, or exactly, frequently occurs within larger contexts. For example:
Some giraffe that saw at least two hyenas was seen by at most two lions
∃x[x is a giraffe ∧ x saw at least two hyenas ∧
x was seen by at most two lions] i.e.
∃x[Gx ∧ ∃y∃z[Hy ∧ Hz ∧ y≠z ∧ S(xy) ∧ S(xz)] ∧
∀u∀v∀w[Lu ∧ Lv ∧ Lw ∧ S(ux) ∧ S(vx) ∧ S(wx) → u=v ∨ v=w ∨ u=w]]
Only: In chapter 1 we saw how to symbolize claims with ‘only if’, and in chapter 3 we discussed how to symbolize ‘only As are Bs’. When ‘only’ occurs with a name, it has a similar symbolization. Saying that only giraffes are happy is to say that anything that is happy is a giraffe:
∀x[Hx → Gx]
or that nothing that isn’t a giraffe is happy:
~∃x[~Gx ∧ Hx]
With a name or variable the use of ‘only’ is generally taken to express a stronger claim. For example, ‘only Cynthia sees Dorothy’ is generally taken to imply that Cynthia sees Dorothy, and that anyone who sees Dorothy is Cynthia:
S(cd) ∧ ∀x[S(xd) → x=c] This can be symbolized briefly as:
∀x[S(xd) ↔ x=c]
We have seen that ‘another’ can often be represented by the negation of an identity; the same is true of
‘except’ and ‘different’:
No freshman except Betty is happy.
~∃x[x is a freshman ∧ x isn’t Betty ∧ x is happy] ~∃x[Fx ∧ ~x = b ∧ Hx]
This has the same meaning as ‘No freshman besides Betty is happy’. Notice that neither of these sentences entail that Betty is happy. That is because one could reasonably say something like ‘No freshman except Betty is happy, and for all I know she isn’t happy either’. So the sentence by itself does not say that Betty herself is happy, although if you knew that the speaker knew whether or not Betty is happy then since the speaker didn’t say ‘No freshman is happy’, you can assume that the speaker thinks Betty is happy.
Each giraffe that saw exactly one hyena saw a lion that exactly one hyena saw
∀x[x is a giraffe ∧ x saw exactly one hyena → ∃y[Ly ∧ exactly one hyena saw y ∧ x saw y]] ∀x[Gx ∧ ∃z[Hz ∧ S(xz) ∧ ∀u[Hu ∧ S(xu) → u=z]] →
∃y[Ly ∧ ∃v[Hv ∧ S(vy) ∧ ∀w[Hw ∧ S(wy) → w=v]] ∧ S(xy)]]
Copyrighted material Chapter 5 — 4 Version of Aug 2013
CHAPTER 5 SECTION 2
Betty groomed a dog and Cynthia groomed a different dog.
∃x[x is a dog ∧ Betty groomed x ∧ ∃y[y is a dog ∧ y is different from x ∧ Cynthia groomed y]] ∃x[Dx∧ G(bx) ∧ ∃y[Dy ∧ ~y = x ∧ G(cy)]]
1. Symbolize each of the following,
a. At most one candidate will win at least two elections
b. Exactly one election will be won by no candidate
c. Betty saw at least two hyenas which (each) saw at most one giraffe.
2. The text states that one can symbolize ‘Betty saw exactly one dragonfly’ as:
∃x∀y[Dy ∧ S(by) ↔ y=x].
Prove that this sentence is equivalent to one of the other symbolizations given in the text for ‘exactly one’. 3. Similarly show that one can symbolize ‘Betty saw exactly two dragonflies’ as:
∃x∃y[x≠y ∧ ∀z[Dz ∧ S(bz) ↔ z=x ∨ z=y]]
by showing that this is equivalent to one of the other symbolizations given in the text.
4. Show that the two symbolizations proposed above for only Cynthia sees Dorothy are equivalent:
∴ S(cd) ∧ ∀x[S(xd) → x=c] ↔ ∀x[S(xd) ↔ x=c]
CHAPTER 5 SECTION 2
Copyrighted material Chapter 5 — 5 Version of Aug 2013
3 DERIVATIONAL RULES FOR IDENTITY
Identity brings along with it two fundamental logical rules. One stems from the principle that everything is identical to itself. This rule, called “self-identity”, allows one to write a self-identity on any line of any derivation:
This rule is not often used, but when it is needed, it is straightforward. For example, it can be used to show that this argument is valid:
2. 3. 4. 5. 6. 7.
Or, more briefly:
1. Show P 2.
~∀x x=x ∃x~x=x ~u=u u=u
2 pr1 mt 3 qn
Show ∀x x=x
P pr13mp dd
x=x sid ud
The more commonly used rule is called Leibniz’s Law, for the 17-18th century philosopher von Leibniz. It is an application of the principle that if x=y then whatever is true of x is true of y. Specifically:
Cynthia saw a rabbit, and nothing else.
Cynthia saw Henry ∴ Henry is a rabbit
∃x[Rx ∧ S(cx) ∧ ∀y[S(cy) → ~y≠x]] S(ch)
Copyrighted material
Chapter 5 — 6
Version of Aug 2013
CHAPTER 5 SECTION 3
Rule sid (“self-identity”)
On any line one may write two occurrences of the same term flanking the identity sign. As justification write “sid”.
∀x x=x → P ∴P
Rule LL (“Leibniz’s Law”)
If a formula of the form ‘a=b’ (or ‘b=a’) occurs on an available line, and if a formula containing ‘a’ also occurs on an available line, then one may write the same formula with any number of free occurrences of ‘a’ changed to free occurrences of ‘b’. As justification, write the line numbers of the earlier lines along with ‘LL’.
This rule applies whether ‘a’ and ‘b’ are variables or names (or complex terms — to be introduced below). (Occurrence of names are automatically considered free.)
1. Show Rh
2. 3. 4. 5. 6. 7. 8.
It is convenient to also have a contrapositive form of Leibniz’s law, saying that if something that is true of a is not true of b, then a≠b. For example:
Fa ∧ S(ac)
~[Fb ∧ S(bc)] ∴ a≠b
This inference is easily attainable with an indirect derivation: assume ‘a=b’ and use LL with the premises to derive a contradiction. But it is convenient to include this as a special case of Leibniz’s law itself:
CHAPTER 5 SECTION 3
Ru ∧ S(cu) ∧ ∀y[S(cy) → ~y≠u] ∀y[S(cy) → ~y≠u]
S(ch) → ~h≠u
Rule LL (contrapositive form)
The formula ‘a≠b’ may be written on a line if a formula containing ‘a’ occurs on an available line, and if the negation of that same formula occurs on another available line with any number of free occurrences of ‘a’ changed to free occurrences of ‘b’. As justification, write the line numbers of the earlier lines along with ‘LL’.
This rule applies whether ‘a’ and ‘b’ are variables or names (or complex terms — to be introduced below). (Occurrences of names are automatically considered free.)
An additional rule is derivable from the rules at hand. It is called Symmetry because it says that identity is symmetric: if x=y then y=x:
Rule sm (symmetry)
If an identity formula (or the negation of an identity formula) occurs on an available line or premise, one may write that formula with its left and right terms interchanged.
As justification, write the earlier line number and ‘sm’.
Examples of derivations using this rule are:
∃x[x=b ∧ Fx]
∀x[b=x → Gx] ∴ ∃x[Fx ∧ Gx]
2. 3. 4. 5. 6. 7. 8. 9. 10.
Show ∃x[Fx ∧ Gx]
u=b ∧ Fu u=b
b=u → Gb b=u
∧ Gb ∃x[Fx ∧ Gx]
pr2 ui 3 sm
Copyrighted material
Chapter 5 — 7
Version of Aug 2013
∴ ∀x[x=a → a=x]
1. Show ∀x[x=a → a=x]
CHAPTER 5 SECTION 3
Show x=a → a=x
x=a ass cd a=x 3 sm cd
1. Produce derivations for the following theorems:
T301 ∀x x=x
T302 ∀x∀y[x=y ↔ y=x]
T303 ∀x∀y∀z[x=y ∧ y=z → x=z]
T304 ∀x∀y[x=y → [Fx↔Fy]]
T306 ∀x[Fx ↔ ∀y[y=x → Fy]]
T307 ∀x[Fx ↔ ∃y[y=x ∧ Fy]]
T322 ∃x∀y y=x ↔ ∀x∀y y=x
T323 ∃x∃y x≠y ↔ ∀x∃y x≠y
T329 ∀y∃x x=y
T330 ∀y∃z∀x[x=y ↔ x=z]
identity is “reflexive” identity is “symmetric” identity is “transitive”
2. Produce derivations for the following valid arguments.
No cat that likes at least two dogs is happy. Tabby is a cat that likes Fido.
Tabby likes a dog that Betty owns.
Fido is a dog.
Tabby is happy. Betty owns Fido.
a. ∀x[Fx → x=a ∨ x=b] ~Fa
∴ ∀x[Fx → ~Gx]
b. ∃x∀y[Ay ↔ y=x]
∴ ∃x[Ax ∧ ~Bx] ↔ ~∃x[Ax ∧ Bx]
c. ∃x∃y[x≠y ∧ Gx ∧ Gy] ∀x[Gx → Hx]
∴ ~∃x∀y[Hy ↔ y=x]
d. ∃x∃y[Fx ∧ Fy ∧ x≠y] ∃x∃y[Gx ∧ Gy ∧ x≠y] ∴ ∃x∃y[Fx ∧ Gy ∧ x≠y]
3. Symbolize these arguments and produce derivations to show that they are valid.
a. Every giraffe that loves some other giraffe loves itself. Every giraffe loves some giraffe.
∴ Every giraffe loves itself.
Copyrighted material
Chapter 5 — 8
Version of Aug 2013
CHAPTER 5 SECTION 3
Each widget fits into a socket.
Widget a doesn’t fit into socket f
Widget a fits into some socket other than f
Only Betty and Carl were eligible Somebody who was eligible, won Carl didn’t win
Copyrighted material Chapter 5 — 9 Version of Aug 2013
4 INVALIDITIES WITH IDENTITY
The presence of the identity relation does not change our technique for showing invalidity. The only addition is the constraint that the identity predicate must have identity as its extension. That is, its extension must consist of all the ordered pairs whose first and second member are the same. So, if the universe is {0, 1, 2}, the extension of identity must be:
=: {<0,0>, <1,1>, <2,2>}
Since this is completely determined, it is customary to take this for granted, and not to bother stating an extension for the identity sign.
An example of an invalid argument involving identity is:
Fa ∧ Gb ∧ a≠b
Gb ∧ Fc ∧ b≠c ∴ Fa ∧ Fc ∧ a≠c
COUNTER-EXAMPLE:
Universe: {0, 1,} a: 0
F: {0} G: {1}
Andrews is fast and Betty is good, but Andrews isn’t is good and Cynthia is fast, but Betty isn’t is fast and Cynthia is fast, but Andrews isn’t first premise is true because 0 is F and 1 is G and 0≠1. The second premise is true because 1 is G and 0 is F and 1≠0. But the last conjunct of the conclusion is false, since 0 is 0.
As before, sometimes a counter-example requires an infinite universe. An example is this argument:
∀x[R(xc) → x=c]
∀x∃y[R(xy) ∧ x≠y]
∴ ~∀x∀y∀z[R(xy) ∧ R(yz) → R(xz)]
COUNTER-EXAMPLE
Universe: {0,1,2,…} c: 0
R(): ≤
The first premise is true because the only thing in the given universe less than or equal to 0 is 0 itself. The second is true because for each thing there is something greater than it (and different from it). And the conclusion is false because ≤ is transitive.
CHAPTER 5 SECTION 4
4. Gertrude sees at most one giraffe Gertrude sees Fred, who is a giraffe Bob is a giraffe
∴ Gertrude doesn’t see Bob
1. Only Betty and Carl were eligible Nobody who wasn’t eligible won
Carl didn’t win ∴ Betty won
2. Ann loves at least one freshman. Ann loves David.
Ed is a freshman.
David isn’t Ed.
∴ There are at least two freshmen
3. Lois sees Clark at a time if and only if she sees Superman at that time. ∴ Clark is Superman
Copyrighted material Chapter 5 — 10 Version of Aug 2013
5 OPERATION SYMBOLS
So far we have dealt only with simple terms: variables and names. In mathematics and in science complex terms are common. Some familiar examples from arithmetic are:
−x, x2, √x, . . . negative x, x squared, the square root of x x+y,x−y,x×y,… xplusy, xminusy, xtimesy
These complex terms consist of variables combined with special symbols called operation symbols. The operation symbols on the first line are one-place operation symbols; they each combine with one variable to make a complex term. The two-place operation symbols on the second line each combine with two variables to make a complex term. Operation symbols also combine with names. It is customary in arithmetic to treat numerals as names of numbers. When numeral names combine with operation symbols we get complex signs such as:
−4, 72, √9, . . .
4+7, 21−13, 5×8, . . .
Each of these is taken to be a complex term. For example, ‘−4′ is a complex term standing for the number, negative four; ’72’ is a complex term standing for the number forty-nine; ‘5×8’ is a complex term standing for the number forty, and so on.
In logical notation we use any small letter between ‘a’ and ‘h’ as an operation symbol; the terms that they combine with are enclosed in parentheses following them. So if ‘a’ stands for the squaring operation, we write ‘a‹x›’ for what is represented in arithmetic as ‘x2’ and if ‘b’ stands for the addition operation, we write ‘b‹xy›’ for what is represented in arithmetic as ‘x+y’. Specifically:
The same letters are used both for names and for operation symbols. (It is often held that names are themselves zero-place operation symbols; a name makes a term by combining with nothing at all.) You can tell quickly whether a small letter between ‘a’ and ‘h’ is being used as a name or as an operation symbol: if it is directly followed by a left parenthesis, it is being used as an operation symbol; otherwise it is being used as a name.
Examples of terms are: ‘b’, ‘w’, ‘e‹x›’, ‘f‹by›’, ‘h‹zbx›’. Since an operation symbol may combine with any term, it may combine with complex terms. So ‘f‹z e‹x››’ is a term, which consists of the operation symbol ‘f’ followed by the two terms: ‘z’ and ‘e‹x›’. Terms can be much more complex than this. Consider the arithmetical expression:
a×(b2 +c2)
If ‘d’ stands for the multiplication operation, ‘e’ for addition, and ‘f’ for squaring, this will be expressed in
logical notation as: d‹a e‹f‹b›f‹c›››
In arithmetic, operation symbols can go in front of the terms they combine with (as with ‘−4’), or between the terms they combine with (as with ‘5×8′), or to-the-right-and-above the terms they combine with (as with ’72’), and so on. The logical notation used here uniformly puts operation symbols in front of the terms that they combine with.
We are used to seeing arithmetical notation used in equations with the equals sign. If numerals are names of numbers, then the equals sign can be taken to mean identity, and we can use our logical identity sign — which already looks exactly like the equals sign — for the equals sign. For example, we ca
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com