Chapter 3.1 - 3.3
Up until now, our language has contained only two kinds of expressions (that is, expressions of two syntactic types): predicates and individual constants. Chapter 3 introduces a new kind of expression: connectives. We will add the following three connectives:
¬ This is called the negation symbol, and can be read as "not" (or, more long-windedly, "it is not the case that")
⋀ This is called the conjunction symbol, and can be read as "and"
⋁ This is called the disjunction symbol, and can be read as "or"
Syntax. Since we have expressions of a new type, we need to extend the syntax of our language to accommodate them. From our previous syntax, we know how to construct atomic sentences from predicates and constants. Now, in addition to atomic sentences, we can construct compound sentences (or "molecular" sentences, if we want to continue the physics metaphor).
So here are the new syntactic rules we need:
If P is a sentence (either atomic or compound), then ¬P is also a sentence. (A sentence of the form ¬P is known as a negation.)
If P and Q are sentences (either atomic or compound), then (P⋀Q) and (P⋁Q) are also sentences. (A sentence of the form (P⋀Q) is called a conjunction, and P and Q are its conjuncts; a sentence of the form (P⋁Q) is called a disjunction, and P and Q are its disjuncts.)
Those are the only "official" rules we need. Informally, however, when a sentence has a pair of parentheses enclosing the entire sentence, we will allow ourselves to drop them, as long as we remember to add them back if we use the sentence as part of a larger compound sentence. So we will allow ourselves to write the sentence (A ⋁ B) as just A ⋁ B, without the outer parentheses. But if we build a larger sentence with it, the parentheses are essential: in ((A ⋁ B) ⋀ C) we can drop the outermost parentheses to get (A ⋁ B) ⋀ C, but we cannot drop the parentheses around (A ⋁ B) to get A ⋁ B ⋀ C. That string of symbols is not a grammatical sentence of a first-order language.
Semantics. Now that we have introduced our three new symbols and explained their syntax, we may want to know what they mean.
The first symbol is the negation symbol '¬'. The negation symbol essentially flip-flops the truth value of a sentence; that is, if P is true, then ¬P is false, and if ¬P is false, then P is true. We can express this by means of a truth table:
P ¬P T F F T
The other two new symbols are the conjunction symbol ⋀ and the disjunction symbol ⋁. (These look similar -- don't forget which is which! It makes a huge difference.)
We can indicate the semantics of the conjunction symbol by this truth table:
P Q P⋀Q T T
And we can indicate the semantics of the disjunction symbol as follows:
P Q P⋁Q T T
The only line here that might seem fishy is the first line. Sometimes people interpret "or" in English as exclusive, so that 'P or Q' is false if both P and Q are true. (If the server says, "you can have a baked potato or French fries," that is most likely not meant to include the possibility that you can have both.) Our text offers an argument that even in cases like this, "or" is actually inclusive. (If the server says "you can have a baked potato or French fries," and then a few seconds later says, "Oh, or if you like you can have both," we don't understand that as contradicting the earlier assertion. This suggests that the idea that we couldn't have both was not a logical implication of the original sentence.) In any case, however "or" works in English, the symbol ⋁ in our formal language is to be understood as inclusive. If we want an exclusive or as well, we can define it in terms of our other symbols. For example, (P⋁Q) ⋀ ¬(P⋀Q) will do the trick.
Let's verify that our translation for exclusive or works as it should. It should be false when P and Q are both true; false when P and Q are both false; and true when one or the other but not both of P and Q are true. A truth table will verify that this is indeed the case.
[insert truth table here!]
The exercises on this material just give you the opportunity to become familiar with the meanings of these connectives and how they work by comparing sentences with worlds. Our text describes this as analogous to the immersion method of learning a new language, as opposed to the translation method. Our strategy in general is to begin by directly comparing our formal language with the world (well, with Tarski's worlds), and only later to translate back and forth between symbolic notation and English.
This section concerns "the game." I don't have much to say about this, but it does provide an interesting way to see what you are missing if you don't see why a sentence has the truth value Tarski's World says it has in a particular world. You can "play the game," holding that it has the truth value it seems to you to have, and then go through a series of steps that should show exactly what it is you've missed.
This section concerns ambiguity, and how to prevent it by using parentheses.
The simplest thing to do would be to simply require that every compound sentence be built up one step at a time from simpler sentences, putting parentheses around the result every time we use a connective. Thus the negation of a sentence P would be (¬P), the conjunction of sentences P and Q would be (P⋀Q), and so on. We would quickly end up with sentences that contain an awful lot of parentheses! A fairly simple example would be ((¬Tet(a)) ⋀ (¬(Cube(b) ⋁ Dodec(c)))).
Our text allows us to improve readability without introducing ambiguity by several means. First, we eliminate the outermost pair of parentheses around any formula. Second, we eliminate the parentheses around negations. This is all right because we introduce the convention that a negation symbol always negates the shortest complete formula that follows it. (Another way to put this: we have an "order of operations" convention that negation takes priority over the other connectives.)
Third, and more interestingly, we allow strings of conjunctions or disjunctions. In a sense this does introduce ambiguity, but it is an ambiguity that does not matter, because every disambiguation is guaranteed to have the same truth value. (We'll look at this by means of truth tables in class.)
Equivalences: DeMorgan's equivalences and double negation.
DeMorgan's: ¬(P⋀Q) is equivalent to ¬P ⋁ ¬Q; ¬(P⋁Q) is equivalent to ¬P ⋀ ¬Q
Double Negation: ¬¬P is equivalent to P
(It follows from the Double Negation equivalence that ¬¬¬¬¬¬P is equivalent to P, etc.)
What do we mean by "equivalent" here? The intuitive, informal notion is that of logical equivalence. Two sentences are logically equivalent if and only if, if one of them is true the other one must also be true. (And if one of them is false, the other one must be, but we don't need to state this separately because it follows from the definition already given.) Another way to the say the same thing: Two sentences are logically equivalent if they must have the same truth value.
We can introduce a formal concept that captures some (not all) of the informal notion of logical equivalence: tautological equivalence. Two sentences are tautologically equivalent if and only if they have the same truth value in every row of a joint truth table. (More on this when we get to chapter 4.)
Note that these logical equivalences are not rules in our formal system. They can't be used in a formal proof without first deriving them from the fundamental rules. (After we've done that, though, I'll let you use them as "derived rules," i.e. things which, although not basic rules, we know that we could prove from the basic rules if we had to.)
Translation. Things to remember:
the English words 'and', 'but', 'however', 'yet', 'nevertheless', and 'moreover' all get translated as '⋀'.
It is a good idea to stay fairly close to the English when doing translations, even though very different sentences may still be logically equivalent.
"Neither P nor Q" can be translated either as ¬(P ⋁ Q) or as (¬P ⋀ ¬Q). (These translations are equivalent by the DeMorgan's equivalences.)
"either" and "neither" often function like left parentheses, so they can help disambiguate sentences. Commas also often function like parentheses. So in doing translation problems, you can use these expressions in the English to determine where the parentheses go in the symbolic translation.