| « previous section | next section » |
Definition 7.5.1
A predicate calculus formula α is called a tautology (or the law of the functional calculus) if its value is true regardless of the valuation of the variables and the interpretation of functional and relational symbols which occur in α, i.e. for every structure STR and for every valuation v of variables in the domaine of STR we have STR,v|= α.
Instead of " α is a tautology of
predicate calculus" we write shortly |= α.
The set of all predicate tautologies can be characterised as the
intersection of the sets of formulas valid in an arbitrary structure in
which the language of predicate calculus is interpreted.
The tautologies of the propositional calculus form the set of "patterns" for tautologies of predicate calculus. The following lemma makes the above statement precise.
Lemma 7.5.1
If α is a propositional calculus tautology, then the result of substituting predicate formulas for all propositional variables in α is a predicate calculus tautology.
We do not derive detailed proof of the above-mentioned lemma. We only remind the Reader that if α is a propositional calculus tautology, then, regardless of propositional variables' values, the value of the formula is true.
Example 7.5.1
Let p and q be the propositional variables and α(x,y)
a formula of predicate calculus with two free variables x and y.
(a) The formula (p ∨ ¬p)
is a tautology of propositional calculus, thus (according to lemma
7.5.1) the formulas
are tautologies of predicate
calculus.
However, the formula (x≤y ∨ x>y) is not tautology because the
interpretation of the symbol ≤ does
not have to be the completion of the interpretation of
>. The formula
¬ (x ≤y) over
the set of real numbers is equivalent to the formula (x > y), but
with
a different interpretation of symbols ≤ and
> in a different structure it may not be true. In
consequence, there are structures in which the formula (x≤y ∨ x>y) is
false.
(b) The formula (¬p → (p →
q)) is a propositional tautology, hence the formula
is the predicate calculus tautology, and, therefore, it is valid, in
particular, in the struture of natural numbers.
The predicate calculus tautologies are schemas of propositional
functions which are valid in any structure, i.e true for all valuations
of variables in the domain of the structure. The validity of these
formulas is not due to the assumed meaning of non-logical symbols or
due to
the accepted variable's
valuation, but it is a consequence of the structure of the formula
itself. The following
lemma presents a few examples of the predicate calculus tautologies:
Lemma 7.5.2
For any formulas α(x) and β(x) the following formulas are tautologies of predicate calculus:
Proof.
Let STR be an arbitrary structure with a non-empty domain X and let
v
be a valuation in STR.
Ad (1) If the implication ( ∀x)α(x) →
( ∃x)α(x)
is false for some
interpretation of the formula α(x) over
the structure STR, then {x ∈
X: α(x)} = X as well as {x ∈
X: α(x)} = ∅.
That is X = ∅, a contradiction.
Ad (2) If STR,v|= ¬(∀x) α(x), then the valuation v does not satisfy the formula ( ∀x) α(x). It means that the formula α(x) is false for some value of x in STR. Let us denote such value of x by b. Hence, STR, v(b/x)|= ¬ α(x). Thus, according to the definition of the existential quantifier semantics we have STR,v |= (( ∃x) ¬ α(x)).
The proof of the remaining two equivalences are left to the Reader.
Remark: The second tautology mentioned in lemma 7.5.2 is called de Morgan's law for quantifiers. There is dual de Morgan's law which is read as (¬ (∃x) α(x)) → ((∀x) ¬ α(x)).
Example 7.5.2
Question 7.5.1 Prove that for any formula α(x) and any formula β in which x is not a free variable the formula ( ∃x)( α(x) ∧ β) ↔ (( ∃x) α(x) ∧ β) is a tautology of predicate calculus (law of inclusion and exclusion of existential quantifier).
Question 7.5.2 Which of the following formulas are predicate calculus tautologies?
| « previous section | next section » |