3.5 Proof procedure

We will introduce a proof procedure through which we will be able to prove that certain formulas of predicate logic logically entail others, that two formulas are logically equivalent, and that a given formula is logically valid. Later, in Section 5.1. Completeness of Predicate Logic, we will demonstrate that this proof procedure is both correct and complete. Correctness of a proof procedure means that the conclusion of any possible proof using it truly logically follows (from a semantic point of view) from the premises, i.e., in every structure where the premises are true, the conclusion is also true (for the semantic concept of logical inference, see the previous section). Completeness is the converse of correctness. When a proof procedure is complete, we have the guarantee that if a formula logically follows (from a semantic point of view) from certain formulas as premises, then in the procedure, there exists a proof that starts from the premises and arrives at the conclusion. However, the existence of such a proof does not necessarily mean that we will be able to find it, as there are no general decision procedures for logical inference in predicate logic. This was discussed at the end of the previous section.

The relationship between the quantifiers

Intuitively, universal statements seem more general than existential ones insofar as (at first glance) the word “everything” seems to refer to all things, and the expression “at least one” does not. In fact, both have to do with everything. Through a universal statement, we say that all things satisfy a certain condition, and through an existential one we say that among all things there is at least one that satisfies a certain condition. In order to establish that a universal statement is true, we must establish that all things satisfy the condition in question. In order to establish that an existential statement is false, we must establish that nothing satisfies it. Therefore, determining the truth value of both types of statements presupposes reference to all things. Moreover, there is a semantic relationship between the existential and the universal quantifier, which allows everything that can be expressed through one of them to be expressed through the other.

To say that an F does not exist is the same as saying that everythingis a non-F. For example, to say that there is not a perfect thing (“¬∃хFх”) is the same as saying that all things are imperfect (“∀х¬”). Thus, we have the following connection between the two quantifiers (in place of “x” can be any other variable):

(1) ¬∃хх¬ …

Furthermore, to say that not everything is an F (“¬∀хFх”) is the same as saying that something is not an F (“∃x¬Fx”). For example, to say that not all things are perfect is the same as saying that some things are not perfect. So, there is also the following connection between the universal and the existential quantifier:

(2) ¬∀хх¬ …

The two connections can be summarized as follows:

When there is a negation sign on one side of a quantifier, it can pass across the quantifier, whereupon the quantifier switches to the other quantifier – if it is existential, it becomes universal, and vice versa.

By (1), “¬∃х¬” has the same meaning as “∀х¬¬” (“¬∃х” in the previous expression is replaced with “∀х¬”). Removing the double negation, we get that “¬∃х¬” has the same meaning as “∀х”. For example, to say that there are no things that are not perfect (“¬∃х¬Fx”) is the same as saying that all things are perfect (“∀xFx”). Thus, we also have the following equivalence:

(3) х ¬∃х¬ …

It follows from (3) that what can be expressed by a universal quantifier can also be expressed by an existential quantifier and negation – we can replace “∀x” with “¬∃x¬” everywhere.

By (2), “¬∀х¬” has the meaning of “∃х¬¬” (“¬∀х” in the first expression is replaced by “∃х¬”). Removing the double negation, we get that “¬∀х¬” has the meaning of “∃х”. For example, to say that not everything is imperfect is the same as saying that something is perfect. So, there is also the following relation between the quantifiers:

(4) х ¬∀х¬ …

It follows from (4) that what can be expressed by an existential quantifier can also be expressed by a universal quantifier and negation – we can replace “∃x” with “¬∀x¬” everywhere.

The following table summarizes the relationship between the quantifiers.

Everything is a non-... x¬(...x...) ¬∃x(...x...) There is nothing that is ...
Not everything is ... ¬∀x(...x...) x¬(...x...) Something is not ...
Not everything is not ... ¬∀x¬(...x...) ∃x(...x...) Something is ...
Everything is ... x(...x...) ¬∃x¬(...x...) There is nothing that is not ...

Let us see how we can use the relationship between the quantifiers. Consider the formula

хуFху

By the relation between the quantifiers, it is logically equivalent to the following formulas: “¬∃х¬∃уFху” (“∀х” is replaced by “¬∃х¬”); “∀х¬∀у¬Fху” (“∃у” is replaced by “¬∀у¬”); “¬∃ху¬Fху” (after both previous substitutions, we get “¬∃х¬¬∀у¬Fху”; then we drop the double negation).

When we have a series of quantifiers with a negation on one side, for example “∃хyz¬”, the relationship between the quantifiers (in particular (1) and (2), which we summarized in the rule that a negation sign can pass across a quantifier thereby switching it) allows the negation to pass on the other side of the whole series thereby switching each quantifier – the existential ones to universal, and vice versa. Thus, “∃хyz¬” can be replaced with “¬∀хyz”. The reason is as follows. “∃хyz¬…” is logically equivalent to “∃хy¬∀z…” (“∃z¬” is replaced by “¬∀z”). The last expression is equivalent to “∃х¬∃yz…” (“∀y¬” is replaced by “¬∃y”), which in turn is equivalent to “¬∀хyz…” (“∃x¬” is replaced by “¬∀x”). In a similar way, starting from “¬∃хyz¬…”, we can move the first negation backwards or the second forwards switching the quantifiers, thus getting “∀хyz¬¬…” or “¬¬∀хyz…”, respectively. After the double negation is dropped, in both cases we get “∀хyz…”.

Also, if we have an arbitrary sequence of quantifiers and negations (for example “¬∀х¬∀yz¬”, “¬∃хy¬∃z”, etc.), it can be converted into a series only of quantifiers (without negations between them), possibly with a negation on one side. To do this, we move all internal negations forwards or backwards (switching the quantifiers we pass through). Thus, we get two series next to each other – one consisting only of quantifiers and the other only of negations. If the negations are an even number, we remove all of them by the equivalence scheme of double negation; if they are an odd number, only one remains.

Universal and existential instantiation

Universal instantiation is a logically valid inference scheme, by which from the fact that some condition is satisfied by all things, we can infer that it is satisfied by one particular of them. Here are a few examples:

хFx x(Fx → ¬∃yGxy) х(FxaFxb) х(FxaFxb)
Fa → ¬∃yGаy FаaFаb FbaFbb

In the first example, from the fact that everything is F, we infer that the particular thing a is F. In the second, the premise is more complicated but again it is a universal statement that claims that everything satisfies a certain condition – namely, that if an arbitrary thing x is F, x is not in the relation G to anything. As everything satisfies this condition, it will be satisfied by the particular thing a; so, the two occurrences of the variable “x” in the condition are replaced by the constant “a” in the conclusion. In cases like this and the previous one, we will say that the variable of the quantifier “x” is instantiated by the constant “a”. The third and fourth example have the same premise but while the variable of the quantifier in the former is instantiated by “a”, in the latter it is instantiated by “b”.

Formally, in every instantiation we remove the quantifier at the beginning and replace all (now) free occurrences of the quantifier’s variable with the constant. If the occurrences of the variable are more than one, we have to replace all of them with the constant. For example, by universal instantiation form “∀xFxx” we can infer “Faa”, not “Fax”. Let “F” corresponds to “…is identical with…”. Form the fact that everything is identical with itself (“∀xFxx”), we can infer that a is identical with a (“Faa”), not that a is identical with x (“Fax”) – x can be anything and therefore may be different from a. Besides, “a is identical with x” is an open sentence, not a statement.

Formally, existential instantiation is just like universal with the only difference that the quantifier is existential. However, it is not a logically valid inference scheme. From “∃xFx”, by existential instantiation, we may obtain “Fa”, “Fb”, … These are not logically valid inferences, because it may be true that something is F without being true that the particular thing a (or b, ...) is F. Nevertheless, we will use existential instantiation in such a way that it will not be possible to deduce statements that do not follow logically from the premises (we will see how). As with universal instantiation, after removing the quantifier we must replace all (now) free occurrences of the quantifier’s variable with the constant. For example, from “∃x(FxaFxb)” we can obtain “FсaFсb”, not “FxaFсb” or “FсaFxb”.

The proof procedure

The proof procedure we are going to use in predicate logic is an extension of the natural deduction in propositional logic (see 1.8 Natural deduction). There we used certain inference schemes, certain equivalence schemes (together with the principle of substitution of equivalents), as well as the procedures of indirect proof (reductio ad absurdum) and conditional proof. We now add to the inference schemes universal instantiation, and to the equivalence schemes the four schemes of the relationship between the quantifiers. The last thing we will add is existential instantiation, but it will have a special status as it is not a logically valid inference scheme and we will apply it with one limitation. Before we see what the limitation is and why it is needed, let us say a few words about the principle of substitution of equivalents.

Formally, we will use it in the same way as in propositional logic – when a subformula of an already deduced formula has the form of one of the sides of an equivalence scheme, we can replace it with the formula that has the form of the other side. However, the very fact that now the principle is used on formulas of predicate logic makes it stronger and perhaps not so obvious1. The point is that by the principle we can now substitute open sentences rather than statements. The parts replaced in such cases are terms (not really sentences). For example, by De Morgan from “∃x¬(FxGx)” we can infer “∃xFx∨¬Gx)”. The reason behind this inference is that the open sentence “¬(FxGx)” is logically equivalent to the open sentence “¬Fx∨¬Gx”. Thus, if “F” corresponds to “expensive” and “G” to “mineral”, the reason in question is that the predicate “…is not an expensive mineral” is logically equivalent to the predicate “…is not expensive or is not a mineral” and therefore they can be replaced with each other. In propositional logic, for each interpretation, each formula has a truth value. Therefore, when we use the principle there, we always replace statements with equivalent statements. In predicate logic, we also replace predicates with equivalent predicates.

The restriction on existential instantiation is that the instantiated constant must be new, i.e. it must not occur in the premises, the conclusion or a previous step of the proof. Due to this limitation, the proofs in which existential instantiation is used will be logically correct, i.e. the conclusion of the proof will be a logical consequence of the premises, although the scheme itself is not logically valid. Here is an example of a correct proof that uses existential instantiation. We are going to show that the sentence “There is something that created everything” logically entails the sentence “There is something that created itself”. For this purpose, we symbolize “…created…” with “F” and will show that “∃хуFxy” entails “∃хFxx”:

1. хуFxy / ∃хFxx

We will use an indirect proof – we will assume the negation of the conclusion and will try to reach a contradiction.

2. ¬∃хFxx assumption

By the relationship between the quantifiers (abbreviated “RbQ”), “¬∃хFxx” is logically equivalent to “∀х¬Fxx”:

3. х¬Fxx 2, RbQ

As a rule, we will use the relationship between the quantifiers to move a quantifier in a formula to the front so that the formula becomes an existential or universal statement, with the idea of then making an existential or universal instantiation. 2. is a negation, but 3. is a universal statement, from which we can make а universal instantiation.

Our next step will be an existential instantiation – from 1., ∃хуFxy (“There is something that created everything”), we will derive “∀уFay” (“a created everything”). Generally, existential instantiation corresponds to the following step in one’s reasoning: based on the fact that there exists something that satisfies a certain condition, one may denote that thing by an arbitrary, hitherto unused name (a new constant in our symbolism) in order to be able to refer more easily to it in the subsequent steps of the reasoning. If there are more than one such things (existential statements tell us that there is at least one thing that is such and such, not that there is exactly one such thing), the name will refer to one of them, no matter which. In our proof, based on the fact that there exists something that created all things, we will introduce the new constant “a” to denote that thing (if more than one things created everything, “a” will denote some randomly chosen of them):

4. уFаy 1, EI2

From 4., by universal instantiation we can deduce “Faa” (from the fact that a created all things (“∀уFay”), as a itself is something, it logically follows that a created itself):

5. Fаа 4, UI3

On the other hand, from 3. (“∀х¬Fxx”), again by universal instantiation, we may infer “¬Faa”, which contradicts “Faa”:

6. ¬Fаа 3, UI – contradicts 5

Because of the contradiction, we can derive the negation of the assumption in 2. (“¬∃хFxx”), i.e. we get “∃xFxx”, which is what we wanted to prove:

7. хFxx 2–6, reductio ad absurdum

The fact that we use existential instantiation not as an inference scheme, but as a means to name things, is the reason why the instantiated constant must be new. If, for example, “a” occurs earlier in some proof (either in the premises, or in an already derived sentence, or in the conclusion we seek to prove), it will refer to something for us in the given context at that moment. The existential statement from which we make the instantiation makes sure that there exists something for which a certain condition is fulfilled, but it does not imply that this existing thing is the same as the thing we denote by “a”, it it may be another thing. Therefore, we must choose a new, unused name to denote it, say “b”. b and a may or may not be different things. If they are the same thing, the constants “a” and “b” will function as two different names, just as “morning star” and “evening star” are different names of the planet Venus. However, if they are different, it is crucial that they be denoted by different names, hence the restriction on the existential instantiation.

Let us see what would happen if we do not follow the rule that in existential instantiation the instantiated constant must be new. Then, for example, from the fact that some people are blue-eyed (“∃xFx”, D – the set of humans), we could “prove” the falsehood that all people are blue-eyed (“∀xFx”). Here is a “proof”:

1. хFx / ∀хFx
2. ¬∀хFx assumption
3. х¬Fx 2, RbQ
4. Fa 1, EI
5. ¬Fa 3, ЕI – contradicts 4
6. хFx 2–5, reductio ad absurdum

The error in the proof is in 5., where the constant “a” is not new.

In the universal instantiation we have no such restriction, because once a condition is fulfilled for all things, it will be fulfilled for every single thing, whether we have spoken of it before or not.

Unlike propositional logic, where in natural deduction one can very often get by without using indirect proofs or conditional proofs, here we will almost always use such proofs. The standard way we will use the proof procedure is to assume the negation of the conclusion and to come to a contradiction. We can use a conditional proof, too. However, when the conclusion of а conditional proof does not coincide with the conclusion of the main proof, we must be careful that the conclusion of the indirect proof does not contain constants introduced by existential instantiations within the conditional proof. The reason for this is the restriction on existential instantiation. Generally, when we use indirect proofs or conditional proofs, we are making sub-proofs within the main proof, by which we demonstrate that a certain sentence follows logically from the premises of the main proof – the sentence in question is the conclusion of the sub-proof. The restriction on EI does not allow constants introduced by EI in a proof to occur in its conclusion. Therefore, constants introduced by EI in a conditional proof must not occur in its conclusion. This cannot happen in an indirect proof, because its conclusion is the negation of its assumption – the conclusion cannot contain constants introduced by EI in the indirect proof itself. However, as the following example shows, this can happen in a conditional proof. The formula “∃xFxFa” is not logically valid (for example, “If ducks exist, Socrates is a duck” is a false sentence because ducks exist and Socrates is not a duck). However, consider this “proof” of its logical validity:

1. xFx assumption
2. Fa 1, EI
3. xFxFa 1–2, conditional proof

The error is that the conclusion of the conditional proof contains a constant introduced by EI within the conditional proof itself. The restriction on existential instantiation prohibits constants introduced in a proof by EI to occur in its conclusion. So, when we use a conditional proof, we must be careful its conclusion not to contain constants introduced by existential instantiation in the proof itself (it is not a problem if they are introduced by EI earlier).

As an example of a correct proof, let us prove the validity of the syllogism AII-1 (Darii):

All M are Р.
Some S are М.
Some S are Р.

Expressed in the language of predicate logic, the above scheme takes the following appearance:

х (MxPx)
x (SxMx)
x (SxPx)

Here is a proof that this inference scheme is valid (the informal considerations behind the instantiations are given in parentheses):

1. х(MxPx)
2. x(SxMx) / ∃x(SxPx)
3. ¬∃x(SxPx) assumption
4. x¬(SxPx) 3, RbQ
5. SaMa 2, EI (By 2., something is both S and M. We denote that thing by “a”.)
6. 1, UI (By 1., for each thing it is true that if it is S, then it is P. This will be true for the specific thing a.)
7. ¬(SaPa) 4, UI (By 4., each thing satisfies the condition „¬(S… ∧ P…)“. Therefore, a will satisfy it, too.)
8. 5, S
9. Pa 6, 8, MP
10. Sa 5, S
11. SaPa 10, 9, Conj – contradicts 7
12. ∃x(SxPx) 3–11, reductio ad absurdum

Through existential instantiations, new constants are introduced, while universal instantiations are applied to already available constants. Therefore, as a rule, we first make existential instantiations thereby obtaining constants which are then used for universal instantiations. For example, in the premises of the above proof, there were no constants. By existential instantiation, we introduced the constant “a” (in 5.), in respect of which (in 6. and 7.) we then made two universal instantiations.

If in the premises there are neither constants nor existential sentences through which to introduce such, and if we do not manage to deduce existential sentences, then, in order to start the process, we can make universal instantiation with some arbitrary constant (say, “a”). This is justified as far as in the world (the universe of discourse) there is at least one thing. That there exists at least one thing is a presupposition made by convention in the semantics of predicate logic – a world in which there is nothing is logically possible but uninteresting. (A language related to such a world cannot have constants (as they must refer to something). In addition, all universal sentences in it must be true and all existential must be false.)

In addition to proving the logical validity of inferences, the proof procedure can be used for proving the logical validity of formulas (sentences). For this purpose, it is enough to show that the negation of the formula (i.e. the assumption that it is false) leads to a contradiction. Then is logically impossible for it to be false, which means that it is true in every structure, i.e. (by definition) that it is logically valid4. In propositional logic, we did the same to prove that certain formulas are tautologies.

As an example, we will prove the logical validity of “∀xyz(FxyFzx)”:

1. ¬∀xyz(FxyFzx) assumption
2. xyz¬(FxyFzx) 1, RbQ5
3. yz¬(FayFza) 2, EI (“x” is instantiated with “a”)
4. z¬(FaaFza) 3, UI (“y” is instantiated with “a”)
5. ¬(FaaFaa) 4, UI (“z” is instantiated with “a”)
6. Faa ∧ ¬Faa 7, Imp – a contradiction
7. xyz(FxyFzx) 1–6, reductio ad absurdum

To prove that two formulas are logically equivalent, it suffices to prove that they follow logically from each other. As an example, and because they are important in themselves, we will prove the validity of the following two equivalences, which allow us to distribute universal quantifier over conjunction and existential quantifier over disjunction:

x(FxGx) xFx ∧ ∀xGx
x(FxGx) xFx ∨ ∃xGx

We first prove that from “∀x(FxGx)” logically follows “∀xFx ∧ ∀xGx”:

1. x(FxGx) / ∀xFx ∧ ∀xGx
2. ¬(∀xFx ∧ ∀xGx) assumption
3. ¬∀xFx ∨ ¬∀xGx 2, De M
4. x¬Fx ∨ ∃x¬Gx 3, RbQ
5. x¬Fx assumption
6. ¬Fa 5, EI
7. FaGa 1, UI
8. Fa 7, S – contradicts 6
9. ¬∃x¬Fx 5–8 reductio ad absurdum
10. x¬Gx 4, 9 DS
11. ¬Gb 10, EI
12. FbGb 1, UI
13. Gb 12, S – contradicts 11
14. xFx ∧ ∀xGx от 2.–13. reductio ad absurdum

We then prove that from “∀xFx ∧ ∀xGx” follows “∀x(FxGx)”:

1. xFx ∧ ∀xGx / ∀x(FxGx)
2. ¬∀x(FxGx) assumption
3. x¬(FxGx) 2, RbQ
4. ¬(FaGa) 3, EI
5. xFx 1, S
6. xGx 1, S
7. Fa 5, UI
8. Ga 6, UI
9. FaGa 7, 8, Conj – contradicts 4
10. x(FxGx) 2–9 reductio ad absurdum

Thus, the logical equivalence of “∀x(FxGx)” and “∀xFx∧∀xGx” is proved. The validity of the second equivalence (in which the existential quantifier is distributed over disjunction) can be proved directly in a similar way, or it can be proved indirectly by the following reasoning. It is obvious that everywhere in the above two proofs we can replace “Fx” with “¬Fx” and “Gx” with “¬Gx” (we can imagine that “F” and “G” were abbreviations for “¬F” and “¬G”). Therefore, the following equivalence is also logically valid:

xFx ∧ ¬Gx) x¬Fx ∧ ∀x¬Gx

When two formulas are logically equivalent, their negations are also such. The reason is that logically equivalent formulas have the same truth value in each structure (see 3.4 Syntax and semantics of predicate logic). After negating the formulas, their truth value will change to the opposite one in each structure but will remain the same for both. So, we have the following:

¬∀xFx ∧ ¬Gx) ¬(∀x¬Fx ∧ ∀x¬Gx)

By De Morgan, the expression on the left side of “⇔” is logically equivalent to “¬∀x¬(FxGx)” (“(¬Fx∧¬Gx)” is replaced with “¬(FxGx)”) and the one on the right to “¬∀x¬Fx ∨ ¬∀x¬Gx”:

¬∀x¬(FxGx) ¬∀x¬Fx ∨ ¬∀x¬Gx

Replacing everywhere “¬∀x¬” with “∃x” (by the relationship between the quantifiers), we obtain the second required logical equivalence:

x(FxGx) xFx ∨ ∃xGx

Distribution of the universal quantifier over conjunctions and of the existential quantifier over disjunctions are valid for any formula in place of “Fx” and “Gx”. In other words, if α and β are arbitrary formulas and x is an arbitrary variable (i.e. it may be “y”, “z”, …), the following two equivalence schemes are logically valid:

х(α ∨ β) хα ∨ ∃хβ
х(α ∧ β) хα ∧ ∀хβ

The first scheme allows us if the range of an existential quantifier has the form of a disjunction to distribute the quantifier over the disjunction, and (vice versa) if each part of a disjunction begins with an existential quantifier to bring the quantifier in front of the disjunction. The second allows us to do the same with a universal quantifier if its range is a conjunction.

Existential quantifier can be distributed only over disjunction and universal quantifier only over conjunction, i.e. neither “∃x(α∧β) ⇔ ∃xα ∧ ∃xβ” nor “∀x(α∨β) ⇔ ∀xα ∨ ∀xβ” is valid. That this is so can be seen with examples. The sentence “There is something that is round and there is something that is square” (“∃xFx ∧ ∃xGx”) is true, while the sentence “There is something that is round and square” (“∃x(FxGx)”) is false. Similarly, the sentence “Everything is round or not round” (“∀x(Fx ∨ ¬Fx)”) is true, while the sentence “Everything is round, or nothing is round” (“∀xFx ∨ ∀х¬Fx”) is false.

The proof procedure can be strictly proved to be sound. This means that no matter what premises we start from and how we apply the procedure, the conclusions we reach will always follow logically from the premises from a semantic point of view (i.e. the conclusions will be true in any structure in which the premises are true). The proof procedure can also be strictly proved to be complete. This means that if a conclusion follows logically from some premises from a semantic point of view (i.e. if it is true in any structure in which they are true), there is a proof in the procedure that starts from the premises and ends with the conclusion. However, the fact that there is one or more such proofs does not mean that we will be able to find any of them because in predicate logic there are no and cannot be general decision procedures for logical inference. This was discussed at the end of the previous section (see).

Properties of relations

We may refer to two-place predicates (such as “…is a teacher of…”, “…is greater than…", etc.) as (two-place) relations. Accordingly, if a two-place predicate is true of an ordered pair, we may say that the first thing in the pair is in the relation in question to the second. Two-place relations have various formal properties. We will focus on the properties of reflexivity, irreflexivity, symmetry, asymmetry, transitivity and intransitivity.

A two-place relation is reflexive in a set (universe of discourse) if each thing in the set is in the relation in question to itself. For example, the relation of identity is reflexive in any set because everything is identical to itself. Formally, an arbitrary two-place relation F is reflexive if the following sentence is true

хFxx

A relation is irreflexive in a set if none of the things in the set is in that relation to itself. Such, for example, is the relation “greater” in any set because nothing is greater than itself. Formally, a two-place relation F is irreflexive if and only if

х¬Fxx

A relation is symmetric in a set when for arbitrary things a and b in the set it is true that if a is in the relation to b, then b is also in it to a. For example, the relation “relative” is symmetric in the set of humans because if someone is a relative of someone, then the latter is also a relative of the former. Formally, F is symmetric if and only if

xy(FxyFyx)

A relation is asymmetric in a set when for any elements of the set a and b it is true that if a is in the relation to b, then b is not in the relation to a. For example, “older” is asymmetric in the set of humans, as if someone is older than the someone, the latter is not older than the former. Formally, F is asymmetric if and only if:

xy(Fxy → ¬Fyx)

A relation is transitive in a set when for any things a, b and c in the set it is fulfilled that if a is in the relation to b and b is in it to c, then a is also in it to c. For example, the relation “higher” is transitive in any set because if something is higher than something and the second thing is higher than a third thing, than the first will be higher than the third. Formally, F is transitive if and only if

xyz[(FxyFyz) → Fxz]

A relation is intransitive in a set when for any elements a, b and c of the set if a is in the relation to b and b is in it to c, then a is not in it to c. For example, the relation of fatherhood is intransitive in the set of humans because if someone is someone’s father and the second is the father of a third one, then the first is not the father of the third, but his (her) grandfather. Formally, F intransitive if and only if

xyz[(FxyFyz)→ ¬Fxz]

Different relations have different combinations of properties. For example, the relation of equality is reflexive, symmetric and transitive. The relation “higher” is irreflexive, asymmetric and transitive. “brother” is reflexive and is neither symmetric nor asymmetric (if a is b’s brother, then b may be his brother but may also be his sister, i.e. not his brother). Furthermore, it is neither transitive nor intransitive (if a and b have only a common mother and b and c only a common father, then a and c have neither father nor mother in common). “love” does not have any of the six formal properties considered.

Some properties of relations follow logically from one or more others. For example, if a relation is reflexive and transitive, it is necessarily asymmetric. We can use our proof procedure to prove this. For this purpose, we assume that for an arbitrary reation F it is true “∀x¬Fxx” (the condition of F being irreflexive) and “∀xyz[(FxyFyz) → Fxz]” (the condition of F being transitive), and will we show that then “∀xy(Fxy → ¬Fyx)” (the condition of F being asymmetric) is true:

1. х¬Fxx
2. xyz[(FxyFyz) → Fxz] / ∀xy(Fxy → ¬Fyx)
3. ¬∀xy(Fxy → ¬Fyx) assumption
4. xy¬(Fxy → ¬Fyx) 3, RbQ
5. y¬(Fay → ¬Fya) 4, EI
6. ¬(Fab → ¬Fba) 5, EI
7. (FabFba) → Faa 2, UI (three times)6
8. ¬Faa 1, UI
9. Fab ∧ ¬¬Fba 6, Imp
10. FabFba 9, DN
11. Faa 10, 7, MP – contradicts 8
12. xy(Fxy → ¬Fyx) 3–11, reductio ad absurdum

Exercises

(Download the exercises as a PDF file.)
(1) Determine whether the following pairs of expressions are logically equivalent. If not, change one of the quantifiers in the first expression (to existential if it is universal, and vice versa) so that they become equivalent.
1) ¬∀y y¬
2) ¬∃x¬ ¬¬∀x
3) x¬∀yz¬ ¬∃xy¬∀z
4) x¬¬∃y¬ ¬∃xy
5) x¬∀yz¬ xyz
6) ¬∃xyz xyz¬
7) xy¬∀zw¬ xyzw
8) xy¬∀zw¬ ¬∀xyz¬∀w
9) xy¬∀zw¬ xyz¬∃w¬
10) xyzw¬ ¬∀xyzw
(2) Is the instantiation correct? If not, what is wrong?
1) x(FxaGbx)
FbaGbb
2) z(Faz ∧ ¬Fzz) → Fab
(Fab ∧ ¬Fbb) → Fab
3) xyz[(Fxa ∧ ¬Fya) → Gxyz]
yz[(Fba ∧ ¬Fya) → Gxyz]
4) xy[∀zFzxy → ∃zGaz]
y[∀zFzay → ∃zGaz]
5) y(Gay ∨ ¬∀xHbxy)
Gab ∨ ¬∀xHbxa
6) ¬∀x(FxaGax)
¬(FbaGab)
7) xyFxy → ∀yxFxy
yFay → ∀yFay
8) x[Fxbx ∧ (¬∃yGxyHxbx)]
Fbbb ∧ (¬∃yGbyHaba)
(3) Below are parts of proofs in which instantiations are used. Are the instantiations correct? If not, what is wrong?
1) 1. ¬∀xFxx
2. zGzz
3. Gaa 2, EI
4. ¬Faa 1, UI
2) 1. xFxa
2. x¬Gxx
3. ¬Gaa 2, EI
4. Faa 1, UI
3) 1. xFxb
2. yGay
3. Fbb 1, EI
4. Gab 2, UI
4) 1. xFax
2. x¬Fax
3. Faa 1, UI
4. ¬Fab 2, EI
5) 1. ¬∀xFax
2. zGbz
3. Gba 2, EI
4. ¬Faa 1, UI
6) 1. xyFxy
2. xyGyx
3. yFay 1, EI
4. yGya 2, UI
(4) Prove (by means of predicate logic) the validity of the following syllogisms:
1) EAE-1
2) AEE-2
3) OAO-3
4) EIO-2
5) EIO-4
6) AOO-2
(5) Prove that the inferences are valid:
1) xFx → ¬Gx)
xGx
xFx
2) x(FxGx)
xFx ∨ ∀xGx
3) ухFyx7
хуFyx
4) x(FxGx)
x(Fx∨¬Gx)
xFx
5) x(FxGx) ∨ ∃x(Fx∧¬Gx)
xFx
6) x(Fx → ∀yzGxyz)
xy¬Gaxy
¬Fa
(6) Prove the validity of the following inferences using the notations:
1) No man is perfect.
Socrates is a man.
Socrates is not perfect.
F – …is a man, G – …is perfect, a – Socrates
2) Socrates is a philosopher.
Socrates is wise.
Some philosophers are wise.
F – …is a philosopher, G – …is wise, a – Socrates
3) Paul or John is not polite.
If John is polite, everyone is polite.
John is not polite.
F – …is polite, a – John, b – Paul, D – the set of humans
4) John can beat anyone on the team who is older than him.
Paul is not older than any of the team who can beat him.
Paul is not older than John.
F – …can beat…, G – …is older than…, a – John, b – Paul, D – the team members
5) All bodies attract each other.8
а and b are bodies.
b attracts a.
F – …attracts…, G – …is a body
6) Each thing either exists in space and time or it is abstract.
Numbers do not exist in space and time.
Numbers are abstract.
F – …is abstract, G – …is a number, H – …exists in space and time
7) Everyone who has read both Hamlet and Othello likes Hamlet.
Some who have read Hamlet do not like it.
Some who have read Hamlet have not read Othello.
F – …has read Hamlet, G – …has read Othello, H – …likes Hamlet, D – the set of humans
8) No vertebrates that have kidneys are amphibians.
If an amphibian has kidneys, it is a vertebrate.
No amphibians have kidneys.
F – …is a vertebrate, G – …has kidneys, H – …is an amphibian, D – animals
9) Only adults who have bought a ticket are allowed in the cinema.
Some who bought a ticket are not adults.
Some who are not allowed in the cinema have bought a ticket.
F – …is allowed in the cinema, G – …is an adult, H – …has bought a ticket, D – the set of humans
10) All circles are figures.9
Everyone who draws a circle draws a figure.
F – …is a circle, G – …is a figure, H – …draws…
11) There are actions that all people condemn.
Everyone condemns one action or another.
F –…is an action, G – …is a human, H – …condemns…
12) Everyone on the forum likes Amarcord.
Either no one on the forum has watched Amarcord or someone has watched it and likes it.
F – …is on the forum, G – …likes Amarcord, H – …has watched Amarcord, D – the set of humans
13) There are actions that are condemned by anyone who condemns any actions.
Everyone condemns one action or another.
There are actions that everyone condemns.
F – …is an action, G – …is a human, H – …condemns…
14) I like anyone who laughs at himself.
I hate anyone who laughs at all his friends.
If I hate someone, I don't like him.
If there is someone who laughs at all his friends, then there is someone who is not a friend of himself.
F – I like…, G – …laughs at…, H – I hate…, I – …is a friend of…, D – the set of humans
(7) Prove that the formulas are logically valid.
1) x(∀yFyFx)
2) x(∀yFyFx)
3) x(Fx → ∃yFy)
4) xy(∀zFyzxFyyx)
(8) Using the distribution of quantifiers over conjunction or disjunction, determine whether the formulas are logically equivalent.
1) xFxaGxb) x¬Fxa ∨ ∀xGxb
2) x(Fxa ∧ ¬Gax) xFxa ∧ ¬∃xGax
3) xFxb ∨ ¬Gxa) ¬∀xFbx ∧ ¬∀xGxz
4) yGyb ∧ ¬Hay) ¬∀yGyb ∧ ∃y¬Hay
(9) What are the formal properties of the following relations?
1) “less than or equal” in the set of natural numbers
2) “sister” in the set of humans
3) “neighbor” in the set of humans
4) „the same age as“ in the set of humans
5) “teacher” in the set of humans
6) “mother” in the set of humans
7) “greater by two” in the set of natural numbers
8) “likes” in the set of humans
9) “subordinate” in the army
10) “richer” in the set of humans
(10) Prove that:
1) If any relation is asymmetric, it is also irreflexive.
2) If any relation is intransitive, it is also irreflexive.

1. Its logical soundness can be rigorously proven, however. 2. “EI” is an abbreviation for “existential instantiation”. 3. “UI” is an abbreviation for “universal instantiation”. 4. See 3.4 Syntax and semantics of predicate logic . 5. Here, the relationship between the quantifiers is applied to a series of quantifiers with a negation on one side. As a result, the negation goes to the other side and all quantifiers are switched. 6. “x” is instantiated with “a”, “y” with “b” and “z” with “a”. 7. We talked about this inference in 3.3 The advantages of predicate logic. The premise could be “Someone loves everyone” and the conclusion “Everyone is loved by someone”. 8. We talked about this inference in 3.3 The advantages of predicate logic. 9. We talked about this inference in 3.3 The advantages of predicate logic.