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
(“∀х¬Fх”). Thus, we have the following connection between
the two quantifiers (in place of “x” can be any other variable):
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:
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:
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:
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
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 “∃х∀y∃z¬”, 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, “∃х∀y∃z¬” can be replaced with
“¬∀х∃y∀z”. The reason is as follows.
“∃х∀y∃z¬…” is logically equivalent to
“∃х∀y¬∀z…” (“∃z¬” is replaced by “¬∀z”).
The last expression is equivalent to “∃х¬∃y∀z…”
(“∀y¬” is replaced by “¬∃y”), which in turn is equivalent to
“¬∀х∃y∀z…” (“∃x¬” is replaced by “¬∀x”).
In a similar way, starting from “¬∃х∃y∀z¬…”, we can move
the first negation backwards or the second forwards switching the quantifiers,
thus getting “∀х∀y∃z¬¬…” or “¬¬∀х∀y∃z…”,
respectively. After the double negation is dropped, in both cases we get
“∀х∀y∃z…”.
Also, if we have an arbitrary sequence of quantifiers and negations (for example
“¬∀х¬∀y∃z¬”, “¬∃х∃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)
|
|
∀х(Fxa → Fxb)
|
|
∀х(Fxa → Fxb)
|
|
Fa
|
|
Fа → ¬∃yGаy
|
|
Fаa → Fаb
|
|
Fba → Fbb
|
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(Fxa → Fxb)” we can obtain “Fсa →
Fсb”, not “Fxa → Fсb” or “Fсa → Fxb”.
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
obvious.
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¬(Fx∧Gx)”
we can infer “∃x(¬Fx∨¬Gx)”. The reason behind this inference
is that the open sentence “¬(Fx∧Gx)” 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”:
We will use an indirect proof – we will assume the negation of the
conclusion and will try to reach a contradiction.
By the relationship between the quantifiers (abbreviated “RbQ”),
“¬∃хFxx” is logically equivalent to “∀х¬Fxx”:
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):
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):
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 “∃xFx → Fa” 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.
∃xFx → Fa
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:
|
∀х (Mx → Px)
|
|
∃x (Sx ∧ Mx)
|
|
∃x (Sx ∧ Px)
|
Here is a proof that this inference scheme is valid (the informal considerations
behind the instantiations are given in parentheses):
|
1.
∀х(Mx → Px)
|
|
2.
∃x(Sx ∧ Mx)
/ ∃x(Sx ∧ Px)
|
|
3.
¬∃x(Sx ∧ Px)
assumption
|
|
4.
∀x¬(Sx ∧ Px)
3, RbQ
|
|
5.
Sa ∧ Ma
2, EI (By 2., something is both S and M.
We denote that thing by “a”.)
|
|
6.
Mа → Pа
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.
¬(Sa ∧ Pa)
4, UI (By 4., each thing satisfies the condition „¬(S…
∧ P…)“. Therefore, a will satisfy it, too.)
|
|
8.
Mа
5, S
|
|
9.
Pa
6, 8, MP
|
|
10.
Sa
5, S
|
|
11.
Sa ∧ Pa
10, 9, Conj – contradicts 7
|
|
12.
∃x(Sx ∧ Px)
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
valid. In
propositional logic, we did the same to prove that certain formulas are tautologies.
As an example, we will prove the logical validity of
“∀x∃y∃z(Fxy → Fzx)”:
|
1.
¬∀x∃y∃z(Fxy → Fzx)
assumption
|
|
2.
∃x∀y∀z¬(Fxy → Fzx)
1, RbQ
|
|
3.
∀y∀z¬(Fay → Fza)
2, EI (“x” is instantiated with “a”)
|
|
4.
∀z¬(Faa → Fza)
3, UI (“y” is instantiated with “a”)
|
|
5.
¬(Faa → Faa)
4, UI (“z” is instantiated with “a”)
|
|
6.
Faa ∧ ¬Faa
7, Imp – a contradiction
|
|
7.
∀x∃y∃z(Fxy → Fzx)
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(Fx ∧ Gx)
⇔
∀xFx ∧ ∀xGx
|
|
∃x(Fx ∨ Gx)
⇔
∃xFx ∨ ∃xGx
|
We first prove that from “∀x(Fx ∧ Gx)” logically
follows “∀xFx ∧ ∀xGx”:
|
1.
∀x(Fx ∧ Gx)
/ ∀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.
Fa ∧ Ga
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.
Fb ∧ Gb
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(Fx ∧ Gx)”:
|
1.
∀xFx ∧ ∀xGx
/ ∀x(Fx ∧ Gx)
|
|
2.
¬∀x(Fx ∧ Gx)
assumption
|
|
3.
∃x¬(Fx ∧ Gx)
2, RbQ
|
|
4.
¬(Fa ∧ Ga)
3, EI
|
|
5.
∀xFx
1, S
|
|
6.
∀xGx
1, S
|
|
7.
Fa
5, UI
|
|
8.
Ga
6, UI
|
|
9.
Fa ∧ Ga
7, 8, Conj – contradicts 4
|
|
10.
∀x(Fx ∧ Gx)
2–9 reductio ad absurdum
|
Thus, the logical equivalence of “∀x(Fx∧Gx)” 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:
|
∀x(¬Fx ∧ ¬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:
|
¬∀x(¬Fx ∧ ¬Gx)
⇔
¬(∀x¬Fx ∧ ∀x¬Gx)
|
By De Morgan, the expression on the left side of “⇔” is logically equivalent
to “¬∀x¬(Fx∨Gx)” (“(¬Fx∧¬Gx)” is replaced with
“¬(Fx∨Gx)”) and the one on the right to
“¬∀x¬Fx ∨ ¬∀x¬Gx”:
|
¬∀x¬(Fx ∨ Gx)
⇔
¬∀x¬Fx ∨ ¬∀x¬Gx
|
Replacing everywhere “¬∀x¬” with “∃x” (by the relationship
between the quantifiers), we obtain the second required logical equivalence:
|
∃x(Fx ∨ Gx)
⇔
∃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(Fx ∧ Gx)”) 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
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
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
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:
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
|
∀x∀y∀z[(Fxy ∧ Fyz) → 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
|
∀x∀y∀z[(Fxy ∧ Fyz)→ ¬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 “∀x∀y∀z[(Fxy ∧ Fyz) → Fxz]” (the
condition of F being transitive), and will we show that then
“∀x∀y(Fxy → ¬Fyx)” (the condition of F being
asymmetric) is true:
|
1.
∀х¬Fxx
|
|
2.
∀x∀y∀z[(Fxy ∧ Fyz) → Fxz]
/ ∀x∀y(Fxy → ¬Fyx)
|
|
3.
¬∀x∀y(Fxy → ¬Fyx)
assumption
|
|
4.
∃x∃y¬(Fxy → ¬Fyx)
3, RbQ
|
|
5.
∃y¬(Fay → ¬Fya)
4, EI
|
|
6.
¬(Fab → ¬Fba)
5, EI
|
|
7.
(Fab ∧ Fba) → Faa
2, UI (three times)
|
|
8.
¬Faa
1, UI
|
|
9.
Fab ∧ ¬¬Fba
6, Imp
|
|
10.
Fab ∧ Fba
9, DN
|
|
11.
Faa
10, 7, MP – contradicts 8
|
|
12.
∀x∀y(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¬∀y∀z¬
¬∃x∀y¬∀z
|
|
4)
|
∀x¬¬∃y¬
¬∃x∀y
|
|
5)
|
∀x¬∀y∀z¬
∀x∃y∃z
|
|
6)
|
¬∃x∀y∀z
∀x∃y∀z¬
|
|
7)
|
∃x∃y¬∀z∀w¬
∃x∃y∃z∃w
|
|
8)
|
∃x∃y¬∀z∀w¬
¬∀x∀y∀z¬∀w
|
|
9)
|
∃x∃y¬∀z∀w¬
∃x∃y∃z¬∃w¬
|
|
10)
|
∃x∃y∀z∀w¬
¬∀x∀y∀z∃w
|
|
(2)
Is the instantiation correct? If not, what is wrong?
|
|
1)
|
∀x(Fxa → Gbx)
|
|
Fba → Gbb
|
|
2)
|
∀z(Faz ∧ ¬Fzz) → Fab
|
|
(Fab ∧ ¬Fbb) → Fab
|
|
3)
|
∃x∃y∃z[(Fxa ∧ ¬Fya) → Gxyz]
|
|
∃y∃z[(Fba ∧ ¬Fya) → Gxyz]
|
|
4)
|
∀x∃y[∀zFzxy → ∃zGaz]
|
|
∃y[∀zFzay → ∃zGaz]
|
|
5)
|
∀y(Gay ∨ ¬∀xHbxy)
|
|
Gab ∨ ¬∀xHbxa
|
|
6)
|
¬∀x(Fxa ↔ Gax)
|
|
¬(Fba ↔ Gab)
|
|
7)
|
∃x∀yFxy → ∀y∃xFxy
|
|
∀yFay → ∀yFay
|
|
8)
|
∀x[Fxbx ∧ (¬∃yGxy ↔ Hxbx)]
|
|
Fbbb ∧ (¬∃yGby ↔ Haba)
|
|
(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.
|
∃x∃yFxy
|
|
|
2.
|
∀x∃yGyx
|
|
|
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)
|
∀x(¬Fx → ¬Gx)
|
|
∀xGx
|
|
∃xFx
|
|
2)
|
∀x(Fx ∧ Gx)
|
|
∀xFx ∨ ∀xGx
|
|
4)
|
∀x(Fx ∨ Gx)
|
|
∀x(Fx∨¬Gx)
|
|
∀xFx
|
|
5)
|
∃x(Fx∧Gx) ∨ ∃x(Fx∧¬Gx)
|
|
∃xFx
|
|
6)
|
∀x(Fx → ∀y∃zGxyz)
|
|
∃x∀y¬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.
|
|
|
а 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.
|
|
|
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(∀yFy → Fx)
|
|
2)
|
∃x(∀yFy → Fx)
|
|
3)
|
∀x(Fx → ∃yFy)
|
|
4)
|
∀x∃y(∀zFyzx → Fyyx)
|
|
(8)
Using the distribution of quantifiers over conjunction or
disjunction, determine whether the formulas are logically equivalent.
|
|
1)
|
∀x(¬Fxa ∨ Gxb)
∀x¬Fxa ∨ ∀xGxb
|
|
2)
|
∀x(Fxa ∧ ¬Gax)
∀xFxa ∧ ¬∃xGax
|
|
3)
|
∃x(¬Fxb ∨ ¬Gxa)
¬∀xFbx ∧ ¬∀xGxz
|
|
4)
|
∃y(¬Gyb ∧ ¬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
|
|
1)
|
If any relation is asymmetric, it is also irreflexive.
|
|
2)
|
If any relation is intransitive, it is also irreflexive.
|
