T7.1 2 of 5
We need to give a more precise statement of the semantics for PL and one which will work for all sentences of the language. (Not just for the several sentences considered on the last page!)
First notice that we define truth given an interpretation. So, first we need to specify just what an interpretation is. Keep the example about 18th century US presidents in mind as you read:
An interpretation for PL is an assignment of meaning which specifies a) a universe of discourse, b) the members of the universe of discourse to which any one-place predicates apply, c) the relationships between members of the universe of discourse to which any 2 or more-place predicates apply, d) the truth value of any 0-place predicate letters and e) the objects named by any individual constants.
Our example interpretation was: universe of discourse = US presidents of the 18th century (George Washington and John Adams), names 'g' and 'j' for these two individuals, and 'M' applies to each of the two presidents, 'F' applies to just Washington, 'S' only to Adams, and 'B' relates Washington as president prior to Adams.
We usually give an interpretations a little less formally, e.g., writing "Mx: x is male", just as we've given a symbolization key. But, either way, an interpretation associates objects with parts of the language.
To determine whether or not a sentence of PL is true, we need to look at its structure. If it's an atomic sentence, then its truth value is determined immediately by the interpretation. Thus 'Mg' is true on the interpretation we've been using in this tutorial.
As usual, if we have a sentence with main logical operator '~','&','v','>', or '=', then we can just apply the old truth table definition to ascertain its truth value.
'(^x)P' is true if and only if WHAT???
Roughly, we want to say that it's true when P holds true for every object in the universe of discourse. But not so fast! We don't really know what it means for P to hold true: P is typically not even a sentence but only a formula. (We've only seen what it is for a sentence like 'Mg' to be true. It doesn't make any sense to say that 'Mx' is true or false.)
Instead to think about the truth value of '(^x)P' we need to think about substitution instances of P. Proposal: We might want to say that '(^x)P' is true if and only if each and every substitution instance P(a/x) is true.
This proposal will work just fine for the 18th century presidents example given above. Let P = 'Mx'. Then there are only two substitution instances, 'Mg' and 'Mj'. And '(^x)Mx' means just that these two are true.
But there is a problem with our proposal. An interpretation may fail to include a name for each member of the universe of discourse. For example, let's expand our vision. Consider all US presidents past and future. If we only have names for the first two, then we've not enough to represent all presidents.
Instead, we need to be prepared to add names for all members of the universe of discourse.
In general, a quantifier's semanticssomething stated in terms of substitution instancesneeds to be defined in the presence of names for all members of the universe of discourse. So, if we need to evaluate the truth value of a sentence of PL with respect to an interpretation lacking names for some elements of its domain, we simply add names to the interpretation until each member has a name and then evaluate.
'(^x)P' is true on an interpretation I if and only if P(a/x) is true on I for all names a (where names for all members of the universe of discourse are added as necessary).
'(%x)P' is true on an interpretation I if and only if P(a/x) is true on I for at least one name a (where names for all members of the universe of discourse are added as necessary).
(Of course, when adding names, we leave the rest of the given interpretation unchanged.)
Now, here's the interpretation but with larger universe of discourse.
universe of discourse: All US presidents
Which of the following are true given this interpretation with universe of discourse of all presidents?
(Hint: You may add names for all US presidents, say 'p3', 'p4', etc. Or you could just pick 't' for Jefferson,....)