Predicate Logic Rules, Proofs, Translations, etc.

Quantifier Negation, Instantiation and Generalization Rules

Note: The existential quantifier will be noted in this document as (Ex).   The . will indicate a conjunction, = will be an equivalence symbol, and --> will be an implication.  The symbol v remains unproblematic.

I.  Quantifier Negation:

Quantifier negation is a necessary process (in many cases) in the construction of formal proofs of validity in predicate logic.  The reason that this is the case is simple.  If a statement is not in "standard form" i.e., (x), (Ex), then it is impossible to transform the statement as it appears within an argument so as to be able to use the quantifier rules (such as existential and universal instantiation).  One cannot instantiate from a negated quantifier.  The quantifier rules are rules of inference and apply only to an entire line.  QN rules are equivalence rules and apply to the quantifier only.

Each quantifier negation rule can be shown or illustrated either in its symbolic representation or in its natural language equivalent.  The process of translation is made much simpler in many cases by knowing how to verbalize the rules as well as knowing how to apply them mechanically.

First, -(x).  This means 'not all'.  If you assert in natural language, for example, that 'not all dogs are cocker spaniels', then the symbolic transformation of the statement is:

-(x)(Dx --> Cx).

But this does not allow for instantiation within an argument.

The statement means:

(Ex)~ (Dx --> Cx),

which translates verbally to:

There is an x such that it is not the case that if x is a D, then x is a C (where "D" and "C" are "dog" and "cocker spaniel", respectively).

Fortunately, however, people do not normally speak in that way and further transformation of the statement shows that

(Ex)~ (Dx --> Cx) becomes

(Ex)~ (~ Dx v Cx) by Material Implication, which becomes

(Ex)(Dx . ~ Cx) by DeMorgan's Theorem.

Now the statement can be translated in English:

There is an x such that x is a dog and x is not a cocker spaniel.  Or, in less formal language,

Some dogs are not cocker spaniels.

There are four forms of quantifier negation, each of which can be expressed easily in the following chart.  There is one name for all of them, so in the process of providing a normal form formula or in using quantifier negation in a proof, the only justification necessary is to state the line from which the transformation came and the abbreviation "QN".

~(x)~  = (Ex), not all are not = some are
~(Ex)~  = (x), not some are not = all are
~(x) = (Ex)~ , not all = some are not
~(Ex) = (x)~ , not some = all are not

II. Using the Instantiation and Generalization Rules.

The four additional rules necessary for the construction of proofs in predicate logic are "EI", "UI", "EG", and "UG".  They look worse than they actually are.  It can be quite simple.

1.  Universal Instantiation.  If a universal statement is given, then it is obvious that every x (or y or z or whatever individual variable is indicated by the universal quantifier) is referred to in the statement.  So, if something is true of every x, then it is true of any arbitrarily or individually selected x as well.  The determinant of what counts as an "arbitrary" individual and a "known" individual is also quite simple.  If the proof with which you are working uses an individual constant instead of an individual variable in a premise that leads directly (or indirectly) to the conclusion, then you should probably instantiate universally to that individual.  Otherwise, instantiate down to (in most cases) whatever variable was used at the outset.  Two examples of this appear below:

(i) In the argument:
(x)(Bx --> Cx)
Bm/Cm

it is necessary to instantiate universally to m since m is in the conclusion.  It would be useless to instantiate to x or y or b or q or anything else other than m since m is what is used in the conclusion and is part of the statement that you are attempting to find or derive.  The procedure for the proof is as follows:

1.  (x)(Bx --> Cx)
2.  Bm/ Cm
3.  Bm --> Cm  1, UI
4.  Cm 3,2, MP

(ii) If the conclusion of the argument uses a universal quantifier, then you must use universal instantiation to "get to" the conclusion.  Think of it in this way.  Suppose that you know that some person is intelligent.  Not only do you know that there is some person who is intelligent, but assume you also know who it is.  So, assume that "Frank is intelligent."  If this is the case, then there is NO instantiation at all, since Frank is an individual and the statement concerning his quality of intelligence is to be given as "If" where I=intelligent and f=Frank.  Simply because you know something about some individual who is intelligent, that hardly implies or indicates that everyone is intelligent, which is exactly what (x)(Px --> Ix) would say.  So, (x)(Px --> Ix) could not be true based only on the fact that you know that Frank is intelligent.  Thus, any known individual cannot be generalized universally.  This also implies, of course, that a statement that is existentially instantiated cannot be used in the process of deriving a statement that is to be universally generalized.  Consider the following example for a generalized explanation of the use of universal instantiation.

1.  (x)(Bx --> Dx)
2.  (x)( ~Cx --> ~ Dx)/(x)(Bx --> Cx)
3.  Bx --> Dx  1, UI
4.   ~Cx --> ~ Dx 2, UI
5.  Dx --> Cx  4, Contra.
6.  Bx --> Cx  3,5, HS
7.  (x)(Bx --> Cx)   6, UG

Since every proposition in this argument was universal, all statements were to be universally instantiated, and since one can universally instantiate to anything at all, every statement (i.e., 1 and 2) could be instantiated to the same thing in each case.  The final step in the argument is to universally generalize, but that will be explained in section 4, below.

2.  Existential Instantiation.

If you know, for example, that "some cats are persians" then you can infer that there is some unknown cat that is a persian, but you cannot necessarily infer from that that your cat or that of anyone else, for that matter, is a persian.  All you know is that some cat or other is a persian, but the proposition does not tell you which cat that might be.  Thus, the proper form for existential instantiation is to instantiate to some unknown, where the unknown can be x, y, z, or any other variable, but this variable becomes an unknown individual, rather than a variable itself.
The contention that the existential instantiation of a statement is to some unknown leads to another rather important consideration for predicate logic.  This consideration is the fact that it is not possible to existentially instantiate more than one time in the same argument to the same unknown.  Looked at in a very loose and generalized way, simply because you know that some cats are persians and you may also know that some persians are grey, it does not follow that the very same unknown persian is both a cat and grey at the same time.  In the second case, the unknown persian might be white or black or any other color.  Thus, a general rule with existential instantiation is that one must always existentially instantiate to "something new."  The "something new" is some new unknown represented by a different letter than was used in the first case.  The notion of existentially instantiating to something new also holds in cases in which a proposition was universallyl instantiated before existential instantiation was to take place.  In such a case, it is not possible to existentially instantiate to the same specific individual (in any case) or to the arbitrary individual chosen.  It is not necessarily the case that what is true of everything is true of some specific thing when the qualities are different as they must be with two different propositions.  Therefore, if there is ever a case in which you know that you must instantiate, and you have a choice between universal instantiation for one proposition and existential instantiation for another, it is always necessary first to existentially instantiate, since it is possible to universally instantiate to anything, but this is not the case with existential instantiation.

3.  Existential Generalization.

There are no significant restrictions on existential generalization.  If you know that some specific, named individual has a property, then it very clearly follows that something has that quality.  In addition, if you know that something has a property, but you do not know the "name" of the individual(s) with the property, then you must have, through the use of existential instantiation, instantiated to something unknown.  Even though something is unknown, it is still known that something does have the quality, and therefore if something has the quality, it is obviously true, speaking tautologically, that if something has the quality, then something has the quality.  Furthermore, if you know that (through universal instantiation to some arbitrarily selected individual) everything has a quality, then something has that quality as well.
This is the essence of existential generalization.  Anything that can be predicated of a subject can be stated in its existential form since if something is true of anything, then it is true of something; if something is true of some particular thing, then it is true of something; and if something is true of everything, it is true of something (or other).
Existential instantiation therefore proceeds from knowledge of the ascription of a property to some known individual, from the ascription of a property to an arbitrarily selected individual, or from the ascription of a property to an unknown, that it is true that something has that property.  The proper form for existential generalization is shown below in the argument:

All persians are cats.
Some mammals are persians.
Therefore, some mammals are cats.

The symbolic representation of the argument is:

(x)(Px --> Cx)
(Ex)(Mx .  Px)/(Ex)(Mx . Cx)

And the proof proceeds as:

1. (x)(Px --> Cx)
2. (Ex)(Mx . Px)/(Ex)(Mx . Cx)
3. Mx . Px  2, EI
4. Px --> Cx  1, UI
5. Px   3, Simp
6. Cx   4,6, MP
7. Mx   3, Simp.
8. Mx . Cx  7,6, Conj
9. (Ex)(Mx . Cx)  8, EG

In line 3, the individual chosen is an unknown.  You cannot know which cat is being referred to in this case.  But what you can know is that if there is a mammal that is a persian, and you know, further, from the first premise, that all persians are cats, then you also know that some mammals are cats.  No matter how simple this argument may appear, its explanation and the principles of the execution of the proof are good for every argument using existential generalization.

4.  Universal Generalization.

Universal generalization has some qualifications and restrictions and these must be known clearly.  You should check chapter 7 of the text for further clarification.  For now, however, consider it in this light.  If you know that something is true of everything, then there is no problem in knowing, even after you have universally instantiated to an arbitrarily selected individual, that since the arbitrary individual stands for everyone, that whatever you are able to derive will also refer to everyone.  Universal generalization cannot be done in a case in which you are dealing with some known individual or even some unknown individual.  So, you cannot universally generalize from a proposition that has been existentially insantiated, nor can you universally generalize from a statement using universal instantiation to some known individual.  This is true since it might be true that every member of a group has a quality, but if you then add the claim that some members of a group have a different quality, it does not follow that the members of of the first group are all necessarily members of the second group.  It follows that if you universally generalize, you are making a leap in the argument that is unfounded.  Look at the particular representation of this below:

All Fords are expensive.
My car is a Ford.
Therefore, all cars are expensive.

In natural language, the invalidity of the argument is not hard to see.  But where natural language may or may not indicate this quality rather clearly, the inability to work with and understand symbolic representations may make the distinction unclear.  The argument would be represented symoblically as:

(x)(Fx --> Ex)
Fc/(x)(Cx --> Ex)

If you universally instantiated the first premise to produce Fc --> Ec, you could derive the statement Ec by MP. And even though you can use conjunction to put Fc and Ec together on the same line, you cannot universally generalize since "c" (the individual constant used in the instantiation) is not representative of everything.  Only arbitrarily selected individuals represent everything or everyone.

The purpose of the preceding explanations is to clarify some of the most commonly misunderstood points in predicate logic.  It is not to be construed as a substitute for working out problems, nor is it to replace the explanations in the text.  It is simply the case that some simple examples may serve better, in the long run, than some of the more complicated examples provided in the text.

III. Using the Instantiation and Generalization Rules, Part II

ASSUME THAT THE STATEMENTS BELOW ARE THE PREMISES OF AN ARGUMENT EVEN THOUGH THERE IS NO CONCLUSION.

1.  All Italians are Europeans.
2.  Some world citizens are Italians.
3.  Everyone is a world citizen.
4.  Someone is French.
5.  All French people are Europeans.

(1) Why is it not possible to instantiate line 3, then use the same instantiation for line 2?
(2) Why is it not permissible to instantiate line 4 like this:  'Fb'?
(3) Why can you instantiate line 1 like this:  "(x)(Ix --> Ex)"?
(4) Why can you instantiate line 5 using the same constants as in 3, above?
(5) If you instantiated line 3 as "Wb", why can you not instantiate line 4 to "Fb"?
(6) Assume that a = Ann (a person with that name).  If you know that statement 1 is true, can you instantiate to "a" even if you know that Ann is not Italian and not European?  Why?  Refer to 1.
(7) If you know that b = Bob, can you instantiate to "b" in line 2?  Why?
(8) If you know that c = Carl, can you instantiate line 3 to "c"?  Why?
(9) Can you instantiate line 3 to "x"?  Why?
(10) Can you instantiate line 4 to "x" even if you instantiated line 3 to "x"?  Why?
(11) If you instantiated line 3 to "x", could you infer that (Ey)Wy?  Why?
(12) If you instantiated line 4 to x, could you infer that (y)Ey?  Why?
(13) In a proof in which these premises could appear, can you use QN on line 4?
(14) If "Alberto is an Italian" is added as a premise, can you assume that he is also a world citizen?  Why?
Though your next test (#3) will include the last sections of sentence logic as well as translations and some application of the basics of predicate logic, this document includes information that is also relevant to the last test, which will be given during final exam week.

IV. Practice PL translations and problems.

A. Translations.  Do not remove negations from quantifiers if they appear.

1.  Not every foreign car runs smoothly or is expensive.  (Use Fx, Cx, Rx, and Ex)
2.  If all the buildings in Manhattan are skyscrapers, then the Chrysler building is a skyscraper. (Use Bx, Mx, Sx, c)
3.  Swiss watches are not expensive unless they are made of gold. (Use Sx, Wx, Ex, Gx)
4.  Experienced mechanics are well-paid only if all the inexperienced ones are lazy.  (Use Ex, Mx, Px, Lx)
5.  Balcony seats are never chosen unless all the orchestra seats are taken. (Use Bx, Sx, Cx, Ox, Tx)
6.  Either some books are trash or some reviewers are incompetent. (Bx, Tx, Rx, Cx)
7.  Some rabbits are white and some are not.  (Rx, Wx)
8. There is a man who is neither loved nor hated. (Mx, Lx, Hx)

B. Prove the following arguments valid using the method of direct proof.

(1)  1. (x)(Ox -->  ~Mx)                         (2)     1. (Ex)Ax
2. (Ex)(Ax . Ox)/(Ex)(Ax .  ~Mx)                    2. (x)[(Ax v Bx) --> Cx]
3.  ~(Ex)Cx/(Ex)~Bx

(3) 1. (Ex)Ax --> (x)Bx                   (4) 1. (x)(Tx --> Vx)/ (x)[(Tx . Gx) --> Vx]
2. (Ex)Cx --> (Ex)Dx
3. An . Cn/ (Ex)(Bx . Dx)

(5) 1. (Ex)Ax --> (x)(Bx --> Cx)               (6)   1.  (Ex) ~Ax --> (x)(Bx --> Cx)
2. Am . Bm/Cm v (x)(Ax v  ~Cx)                      2.   ~(x)(Ax v Cx)/ ~(x)Bx

(7)   1. (x)[(Ax . Bx) --> Cx]
2.  ~(x)(Ax --> Cx)/  ~(x)Bx

C.  Normal Form Formulas.  For each statement, provide a normal form formula.  Justify every line.

(1) 1.  ~(x)(Cx -->  ~Dx)      (2)  1.  ~(Ex)[~(Mx v Nx)] (3) 1.  ~(x)~(Cx .  Dx)

D.   (1) Why must you instantiate ONLY TO AN UNKNOWN with "existential instantiation"?
(2) What is the relationship between an argument with consistent premises and the concepts of validity/invalidity; and the relationship between an argument with inconsistent premises and the concepts of validity/invalidity?
(3) What are the restrictions on universal generalization?  Why do they exist?
(4) Why are there no restrictions on universal instantiation?
(5) Why can existential instantiation only be done one time with the same variable in the same proof?

E. Indirect Proofs.  See also Kahane's text, chapter 7, end.

(1)  1.  ~(Ex) ~(~Ax v Bx)        (2) 1.  ~(x)Ax/(Ex)(Ax --> Bx)
2.  ~(x)Bx/ ~(x)Ax

(3) 1.  ~(Ex)Fx/Fa --> Ga        (4) 1. (x)Ax --> (y)By/ (Ex)[Ax --> (y)By]

V. General Information about PL:

1.  Property Constant.  A property is a quality of some kind that is possessed by a subject.  A property is another name for a predicate.  So if 'x is large,' x is the subject, and large is the predicate.  The predicate (property, quality) is always given as a capital letter.

2.  Individual Constant.  Constants are represented by the lower case letters a-s (some logic books vary on this).  An individual constant is a means to represent a thing by its name or designation.  So if you want to say that the Chrysler building is large, it is symbolized as Lc.  The Chrysler building is an individual building, to be distinguished from the claim that "some building is large."  (See 3, below).

3.  Individual Variable.  Variables are represented by the lower case letters t-x (again there is variation) and are used when the individual is either unknown or arbitrarily selected.  Thus, you would use an individual variable when you are instantiating from either a universal or existential statement.  "Some buildings are large" would be symbolized as (Ex)Lx or as (Ex)(Bx . Lx).

4.  Unknowns.  Unknowns are given as individual variables.  The point behind them is that when you use them, you are using them to indicate that you know that some particular thing has a quality, but you do not know which one it is.  When you use existential instantiation, you are always instantiating to an unknown.

5.  Arbitrarily selected individuals.  An arbitrarily selected individual is given as a variable.  But it is the individual who represents all individuals, similar to the way in which one triangle can represent all triangles when doing a proof in geometry.  You choose some particular triangle (which is actually no particular triangle at all) to represent all triangles.  Since this is the case, you can use an arbitrarily selected individual to universally generalize, but you cannot use an unknown for the same purpose.

6.  Existential Instantiation.  The process of removing a quantifier from an existentially quantified statement.  Use a variable as an unknown when instantiating existentially.  NEVER EXISTENTIALLY INSTANTIATE TO A KNOWN INDIVIDUAL.

7.  Universal Instantiation.  The process of removing a quantifier from a universally quantified statement.  You can universally instantiate to anything, so you can choose to use an individual constant or an individual variable.  But it does make a difference which one of these you choose, since if you need to universally generalize in the proof, you cannot do so from an individual, but only from an arbitrarily selected individual.

8.  Existential Generalization.  The process of adding a quantifier to a statement in a proof such that the resulting statement is a particular statement (an existential statement).  You can existentially generalize from anything.

9.  Universal Generalization.  The process of adding a quantifier to a statement in a proof such that the resulting statement is a universal statement.  Restrictions on univeral generalization include the fact that you cannot generalize universally from a known or an unknown individual, but only from an arbitrarily selected individual.

10. Scope of a Quantifier.  This is very similar to the scope of a negation symbol.  The negation applies to the smallest possible area in any statement in which it appears.  So, for example, in  A   B, the negation applies only to A.  But if there were parentheses around the A and B, but the negation was outside, the negation would apply to both A and B.  The same is true of a quantifier.  But even more for a quantifier, it applies only to the variable quantified.  In a statement in which you see (x)[Ax v (y)By], the (x) quantifier applies only to Ax, not to (y)By. The statement (y)By is in the scope of the quantifier, but it does not bind (y)By.  It is important to understand the difference between a quantifier binding a variable, and a variable simply being in the scope of a quantifier.  This is where the scope of the negation and the scope of a quantifier are slightly different.

(c) 1988, 1999, Nancy A. Stanlick