| « previous section | next section » |
In propositional calculus, the essential place is occupied by the formulas the value of which is always true, i.e. they are satisfied at every potential valuation of their variables. We name them valid formulas or tautologies.
Definition 6.3.1
A formula is called a tautology or valid if and only if its value is true regardless of the valuation of the propositional variables. In other words, α is a tautology iff for every v, v|= α.
A formula is contradictory or unsatisfiable iff it is false at every valuation of propositional variables. In other words, α is contradictory iff there is no valuation v, for which, v|= α.
Example 6.3.1
The following formulas are examples of the propositional calculus tautologies:
(1) (a → a) law of implication's identity,
(2) (a ∨ ¬ a) law of excluded centre (at least one of contradictory propositions must be true),
Let us calculate the
logical value of the formula (3), i.e. ¬
(a ∧
¬
a). Because α
can be true or false proposition, then it is enough to consider two
cases:
( ¬ ( α ∧ ¬ α))(v) = ¬ ( α ∧ ¬ α)(v) = ¬ ( α(v) ∧ ( ¬ α)(v)) = ¬ (0 ∧ ¬ α(v)) = ¬ (0 ∧ 1) = ¬ 0 = 1
( ¬ ( α ∧ ¬ α))(v) = ¬ ( α ∧ ¬ α)(v) = ¬ ( α(v) ∧ ( ¬ α)(v)) = ¬ (1 ∧ 0 ) = ¬ 0 = 1
It is worth remarking on the Duns Scotus' law (the formula 5). It states that if the proposition ¬ α is true, then α implies any other proposition. Let's check it: if ( ¬ α )(v) = 0, then of course ( ¬ α → (α → β ))(v) = 1. If ( ¬ α )(v) = 1, i.e. ( α )(v) = 0, then (α → β )(v) = 1, but then ( ¬ α → (α → β ))(v) = 1. Therefore, the final value of the formula does not depend on the logical value of the proposition β.
Lemma 6.3.1
The propositional calculus formula α is a tautology if and only if its negation ¬ α is a contradictory formula.
Question 6.3.1 Is the proposition "If Peter is the best student, then, if Peter is not a student, then Peter is a biologist" valid or corntradictory?
The easiest way to check whether an arbitrary formula is valid or not, is to construct its logical matrix, i.e. the table which columns correspond to the subformulas and rows to different valuations. Thus, the logical matrix of a tautology has the column which corresponds to the whole formula (usually the last column of the table) filled up only with the symbol 1. Or, according to the definition, all valuations satisfy the tautology.The logical matrix for a contradictory formula has the last column filled up only with the symbol 0 (More studies about contradictory formulas and contradictory sets of formulas will be presented in the subsection 6.6.)
This verification method is called the truth-table method or zero-one method.
If a formula has n
propositional variables each of which can take two possible values 0 or
1,
then to construct the logical matrix we need to look up 2n
disjoint variants. It is really a lot! Nevertheless, the
above-mentioned
method gives us the possibility to decide after a finite number of
steps, if
an arbitrary propositional calculus formula is a tautology or not. We
call this proprerty of propositional calculus "decidability".
Example 6.3.2
To illustrate the truth-table method we will check whether the following formula ¬ (α∨β) ↔ ( ¬ α ∧ ¬ β ), called de Morgan's law, is a propositional tautology. In order to achieve this goal we consider all its subformulas: α, β, α∨β, ¬ (α∨β), ¬ α, ¬ β, ( ¬ α ∧ ¬ β ),(¬ (α∨β) ↔ ( ¬ α ∧ ¬ β)) and all possible values of α and β. The logical matrix of the formula is presented on the Fig. 6.3.1. Because irrespective to the values of α and β the considered formula is satisfied, thus, ¬ (α∨β) ↔ (¬ α ∧ ¬ β) is a propositional calculus tautology.|
α β |
(α∨β ) |
¬ ( α∨β) |
¬ α |
¬ β |
( ¬ α ∧ ¬ β) |
( ¬ (α∨β) ↔ (¬ α ∧ ¬ β )) |
|
0 0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
1 0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
1 1 |
1 |
0 |
0 |
0 |
0 |
1 |
Fig. 6.3.1 The logical matrix for de Morgan law : ¬ (α ∨ β ) ↔ ( ¬ α ∧ ¬ β ).
Example 6.3.3
For any freely chosen propositions p, q, r the following formulas are valid:
(1) Law of transposition: (p → q) ↔ ( ¬ q → ¬ p ).
(2) Law of denial of implication: ¬ (p → q) ↔ (p ∧ ¬ q ).
(3) Law of de Morgan: ¬ ( p ∧ q) ↔ ( ¬ p ∨ ¬ q).
(4) Law of conditional syllogism: (p → ( q → r)) → ((p → q ) → (p → r))
For each of the above formulas one can construct the logical matrices
and find out
that independently of the assumed valuation of propositions p, q, r,
these
formulas are satisfied. The first
three examples are two-variable formulas and therefore, we must
consider 4
different valuations. The
last law is three-variable (p, q and r) thus, we have to verify 8
cases.
Sometimes, it is desirable to simplify our task by using the properties
of
logical functors (in this case the properties of implication).
Let us see, if the value of the variable r
is true in the valuation v, then (p →
r) and ((p → q) →
(p →
r)) are true proposals and it follows that ((p→ (
q→
r)) →
((p → q ) →
(p →
r))) (v) = 1 (notice, that if the successor of the
implication is true, then the whole
implication is true). So, it is not necessary to consider the
values of p and q in the valuation v. Only the case v(r)=0 is
still not discussed. In the
next subsection we will introduce another method which
allows to simplify the process of verifying the validity of
formulas.
The following lemma gives a method of constructing a new tautologies and justifies why tautologies are patterns of true propositions.
Lemma 6.3.2
Let α
be a propositional
tautology depending on the propositional
variables p1,...,
pn and let α1,...,
αn be arbitrary
formulas. Then the formula obtained from α
by replacing simultaneously
every occurrence of each variable pi with the corresponding
formula ai for i=1,...,n is a propositional tautology
too.
If we substitute in a tautology any arbitrary proposition
for the original propositional variable we always obtain a valid
proposition
(i.e. tautology).
Example 6.3.4
We have proved above (see example 6.3.3) that the formula ¬ (α ∨ β ) ↔ ( ¬ α ∧ ¬ β ) is a tautology. Now, let us replace α with the proposition "x is an element of the set A" and β with "x is an element of the set B". We obtain the true proposition of the following form:
"It is not the case that x is an element of the set A or x is an element of the set B if and only if x is not an element of the set A and is not an element of the set B".
This sentence can be simplified to the well-known rule of the algebra of sets: "If x does not belong to the union of sets A and B, then x does not belong either to set A or to set B.
The knowledge of tautologies and semantic properties of logical functors is crucial even for programmers. Tests (e.g. Boole's expressions) applied in the conditional instructions or loops are exactly logical formulas which sometimes turn out to be very complicated.The program' s result is strongly related with test's satisfiability at the given moment of execution. Let us consider a hypothetical instruction "while (p → (q → p)) do x := x+1 od". If someone careless places this instruction in his or hers program body, then he or she will never obtain a result, the loop will be executed infinitely many times.
Let us consider one more hypothetical instruction "if p then I1 else if q then I2 else I3 fi fi". We assume that (q → p) is true providing that we execute the above-mentioned instruction. Is the instruction I2 ever executed? No, because if p is true, then the program does not reach the instruction "if q..." and if p is not true, then, according to our assumption, q is not valid. Therefore, the instruction I3 will be executed. It follows that the considered conditional instruction can be reduced to a simpler (and equivalent) form
"if p then I1 else I3 fi".
Question 6.3.1 Let's assume that the formula (α → β ) is a tautology. Which of the following propositions is true?
| « previous section | next section » |