48
Formal Logic
Validity
The truth value of a propositional wff depends on the truth values assigned to the
statement letters. The truth value of a predicate wff depends on the interpretation.
Choosing an interpretation for a predicate wff is thus analogous to choosing truth
values in a propositional wff. However, there are an infinite number of possible
interpretations for a predicate wff and only 2
n
possible rows in the truth table for
a propositional wff with n statement letters.
A tautology is a propositional wff that is true for all rows of the truth table.
The analogue to tautology for predicate wffs is validity—a predicate wff is valid
if it is true in all possible interpretations. The validity of a wff must be derived
from the form of the wff itself, since validity is independent of any particular interpretation; a valid wff is “intrinsically true.”
An algorithm exists to decide whether a propositional wff is a tautology—
construct the truth table and examine all possible truth assignments. How can we
go about deciding validity for predicate wffs? We clearly cannot look at all possible interpretations, because there are an infinite number of them. As it turns out,
no algorithm to decide validity for any wff exists. (This does not mean simply that
no algorithm has yet been found—it means that it has been proved that there is no
such algorithm.) We must simply use reasoning to determine whether the form of
a particular wff makes the wff true in all interpretations. Of course, if we can find
a single interpretation in which the wff has the truth value false or has no truth
value at all, then the wff is not valid.
Table 1.16 compares propositional and predicate wffs.
tAbLe 1.16
Propositional Wffs
Predicate Wffs
Truth values
True or false, depending on
truth value assignments to
statement letters
True, false, or perhaps (if the
wff has a free variable) neither,
depending on interpretation
“Intrinsic truth”
Tautology—true for all truth
value assignments
Valid wff—true for all
interpretations
Methodology
Algorithm (truth table) to
determine whether wff is a
tautology
No algorithm to determine
whether wff is valid
Now let’s try our hand at determining validity for specific wffs.
eXAMPLe 24
a. The wff
(4x)P(x) S (E x)P(x)
is valid. In any interpretation, if every element of the domain has a certain property, then there exists an element of the domain that has that property. (Remember
that the domain of any interpretation must have at least one object in it.) Therefore,
Formal Logic
Validity
The truth value of a propositional wff depends on the truth values assigned to the
statement letters. The truth value of a predicate wff depends on the interpretation.
Choosing an interpretation for a predicate wff is thus analogous to choosing truth
values in a propositional wff. However, there are an infinite number of possible
interpretations for a predicate wff and only 2
n
possible rows in the truth table for
a propositional wff with n statement letters.
A tautology is a propositional wff that is true for all rows of the truth table.
The analogue to tautology for predicate wffs is validity—a predicate wff is valid
if it is true in all possible interpretations. The validity of a wff must be derived
from the form of the wff itself, since validity is independent of any particular interpretation; a valid wff is “intrinsically true.”
An algorithm exists to decide whether a propositional wff is a tautology—
construct the truth table and examine all possible truth assignments. How can we
go about deciding validity for predicate wffs? We clearly cannot look at all possible interpretations, because there are an infinite number of them. As it turns out,
no algorithm to decide validity for any wff exists. (This does not mean simply that
no algorithm has yet been found—it means that it has been proved that there is no
such algorithm.) We must simply use reasoning to determine whether the form of
a particular wff makes the wff true in all interpretations. Of course, if we can find
a single interpretation in which the wff has the truth value false or has no truth
value at all, then the wff is not valid.
Table 1.16 compares propositional and predicate wffs.
tAbLe 1.16
Propositional Wffs
Predicate Wffs
Truth values
True or false, depending on
truth value assignments to
statement letters
True, false, or perhaps (if the
wff has a free variable) neither,
depending on interpretation
“Intrinsic truth”
Tautology—true for all truth
value assignments
Valid wff—true for all
interpretations
Methodology
Algorithm (truth table) to
determine whether wff is a
tautology
No algorithm to determine
whether wff is valid
Now let’s try our hand at determining validity for specific wffs.
eXAMPLe 24
a. The wff
(4x)P(x) S (E x)P(x)
is valid. In any interpretation, if every element of the domain has a certain property, then there exists an element of the domain that has that property. (Remember
that the domain of any interpretation must have at least one object in it.) Therefore,