The SYNTAX of a language is given by the rules that determine the set of expressions that are said to belong to the language, or, looking at it the other way around, the rules that tell you how to combine grammatical expressions of the language to obtain new grammatical expressions. You're probably most familiar with the notion of syntax in terms of grammar -grammar and syntax are actually exactly the same thing. Thus, just as the grammar of English tells you how to combine words and phrases of English to make larger expressions, sentences, the formal syntax of sentential logic tells you how to combine expressions of sentential logic to make larger expressions, logical formulae. Looking at it in the other direction, the formal syntax of sentential logic also allows you to determine, of any expression, whether or not that expression is a syntactically well-formed formula of sentential logic.
In this chapter, we are going to study both the grammar of sentential logic and how to recognise and express the logical form of English sentences, which in turn will allow us to ''translate'' sentences of English into formulae of sentential logic and vice versa.
One of the first things you probably learned about English grammar, way back in grade school, had to do with the basic parts of speech, that is, the different categories of words, such as nouns, verbs, adjectives, and so on. We're going to start in exactly the same fashion with the syntax of sentential logic. In English there are many different categories of words to worry about, and you probably still don't even know what all of them are, or what exactly words in each category are supposed to do. What exactly is a gerund, anyway? The good news is, in sentential logic there are only two different categories of words or basic expressions: ATOMIC FORMULAE and LOGICAL CONNECTIVES. Okay, so what are atomic formulae and logical connectives?
Atomic formulae are, well, formulae that happen to have no interesting parts, at least from a particular point of view. Logical connectives, on the other hand, are things that serve to connect formulae together in order to create new and more complex formulae. The atomic formulae of sentential logic correspond to certain kinds of sentences of English (or any other language, for that matter), namely, sentences that express statements. The logical connectives correspond to certain words and phrases of English that we call LOGICAL OPERATORS., for example, "and", "or", "if then."
The big question about atomic formulae as we saw in chapter 1, has to do with what sorts of English sentences we want to consider as atomic formulae of sentential logic, rather than how we deal with atomic formulae within sentential logic itself—that's the easy part. The answer here should be reasonably obvious if you think about the fact that the only basic expressions we have to deal with in sentential logic are just atomic formulae and logical connectives—atomic formulae are going to turn out to be just those formulae that don't involve any logical connectives, so the English sentences we consider to correspond to atomic formulae will be those that do not involve any logical operators. With this in mind, we should probably say a little bit more about the logical connectives and their corresponding operators in English.
In our system of sentential logic, we have precisely four logical connectives, called CONJUNCTION, DISJUNCTION, THE CONDITIONAL, and NEGATION. These connectives correspond to logical operators in English as follows: Conjunction corresponds to the word 'and'; disjunction corresponds to 'or' (or the phrase 'either...or...'); the conditional corresponds to (the phrase) 'if...then....'; and negation corresponds to 'not.'
Of course, when we say that a connective corresponds to a particular word or phrase in English, we aren't trying to claim that the connective should be considered to have exactly the same meaning as the English word. All we are trying to claim is that the connective captures an important part of the meaning —the TRUTH-FUNCTIONAL part. The logical connectives thus represent logical IDEALISATIONS of the corresponding words and phrases in English—idealisations that allow us to focus on the logical structure of English sentences.
It's probably time we got to a few examples:
- John ran.
- Mary laughed.
- Harry said that Mary laughed.
- John thinks that Mary laughed at his running.
- John ran and Mary laughed.
- Either John ran, or Mary laughed.
- If Mary laughed, then John ran.
- John didn't run.
Which of these sentences are atomic sentences, and which ones are not? Think about it for a moment before reading on.
Okay, now that you've thought about it, we'll tell you. Since each of sentences 5-8 contains one of our logical operators, none of these sentences are atomic. Sentences 1-4, on the other hand, don't contain any of the operators, so each one of these-even 4 which doesn't look particularly simple-is an atomic sentence.
Now, take another look at sentences 5-8:
Notice how sentences 1 and 2 occur in each of these non-atomic (or COMPOUND sentences), connected by the logical operators? This is exactly what we meant earlier when we said that the logical operators serve to connect sentences to make new sentences. We'll see in just a little bit how these sentences look when translated into sentential logic.
At this point, you might be wondering about sentence 3:
This sentence also contains sentence 2, but we said that it is an atomic sentence. How can a sentence contain an atomic sentence, and yet still be an atomic sentence itself? It probably isn't particularly enlightening to say that it's because sentence 3 doesn't contain any of the logical operators, since that doesn't really do anything to explain the difference between making a new sentence out of atomic sentences by using logical operators and making a new sentence by sticking 'Harry said that' in front of an atomic sentence.
The secret here has to do with the fact that the logical operators are indeed logical, and more precisely, that they are TRUTH-FUNCTIONAL, while the expression 'Harry said that' is not. In order to get clear on this, we need to take a brief detour into SEMANTICS, which deals with the MEANING of expressions. We are, in particular, interested in the TRUTH-VALUES of sentences. Compare sentences 3 and 5:
If we wanted to determine whether or not each of these sentences were true, then we would need to know whether or not Mary laughed, as well as whether or not John ran, in order to tell if sentence 5 were true. On the other hand, we don't need to know whether or not Mary actually laughed in order to determine whether or not it was true that Harry said she had. In other words, the truth-values of sentence 2 and sentence 5 are related to one another, while the truth-values of sentences 2 and 3 are not related. Since the truth-values of sentence 2 and 3 are not related—knowing one won't help us determine the other, even though one sentence is contained in the other-these sentences must have the same truth-functional 'status': They are both atomic sentences. Since the truth-values of sentences 2 and 5 are related-we need to know the truth-value of sentence 2 in order to determine that of sentence 5-they can't have the same truth-functional 'status,' so 5 cannot be (and indeed, is not) an atomic sentence.
So that is why some sentences can contain atomic sentences as parts, and still be atomic sentences themselves. For the most part, though, all you need to know is that a sentence that doesn't contain any logical operators is an atomic sentence. We should thus go on at this point to take a look at these logical operators in more detail.
As we noted in the last section, a non-atomic sentence is called a COMPOUND SENTENCE, since it is constructed out of a compound of atomic sentences and logical connectives. Similarly, in sentential logic, any non-atomic formula is called a COMPOUND FORMULA. In this section, we'll meet each logical connective in more detail, with particular attention to recognising them as they appear in English expressions, and how to interpret them in some tricky cases. We'll also learn how to SYMBOLISE English expressions, and thereby TRANSLATE them into the language of sentential logic.
We've already seen one example of a conjunction in English:
Here we have two atomic sentences, connected into a conjunction by sticking the word 'and' between them. Why don't we go ahead and symbolise this sentence? If we replace the word 'and' with the symbol & in the above sentence, we get the following:
We are now half-way to having symbolised our first sentence. The only thing left is to determine what to do with the atomic sentences, which we call CONJUNCTS, since they are connected by a conjunction. In order to symbolise these, we'll just let a single capital letter represent each conjunct, which gives us the following translation:
We could use any capital letters we liked to stand for each atomic sentence, but it's traditional (and purely conventional) to pick a letter that has some relationship to the corresponding sentence. Here we went with the first letter of the name of the person mentioned in each sentence, but we could have used the first letter of the verb just as well:
That's pretty much all there is to symbolising a simple conjunction like this one. We replace the word 'and' with its symbol & and symbolise each of the conjuncts, the atomic sentences, with a single capital letter each. So is that all there is to conjunctions, then? Not by a long shot.
As you well know, conjunctions can come in many forms. Consider the following:
These sentences both contain the word 'and,' so they should count as conjunctions, rather than atomic sentences, right? Right. They do not consist, however, of two atomic sentences stuck together with the word 'and,' so it's not clear how we should go about symbolising them. The trick with sentences like these is to paraphrase them—get them into the form of two atomic sentences stuck together by the word 'and':
Now it's clear how we can symbolise them:
Great, so every time we see the word 'and' we know we have a conjunction on our hands, we might just need to paraphrase it, right? Unfortunately, it's not quite so simple. Consider the following:
- Two scoops of vanilla ice cream and a generous serving of chocolate syrup make a great sundae.
This is certainly true, but if we try to paraphrase it the same way as we did the previous sentences, we end up with the following:
It's pretty obvious that the paraphrase trick doesn't work right in this case- the paraphrase is evidently false, while our original sentence is true. Two scoops of ice cream by themselves, regardless of flavour, do not make a sundae at all, let alone a good one. Similarly, a generous serving of chocolate syrup by itself is just a generous serving of chocolate syrup. Since the result of paraphrasing doesn't match what we started with, it looks like we should symbolise this sentence as an atomic sentence:
To add another wrinkle, we have more words than just 'and' to worry about when it comes to conjunctions. Consider the following:
- The cat is napping, but the dog is chasing his tail.
- Although the cat is sharpening her claws on the dog, the dog is sleeping soundly.
- The cat is purring, though the dog is howling.
- Mary has just taken the dog to the vet; however, the dog's appointment is tomorrow.
- Mary is fond of cats, whereas John likes dogs.
Each of these sentences consists of two atomic sentences connected together by some word other than 'and.' If we paraphrase each sentence by removing that word and sticking 'and' between the two atomic sentences, the paraphrases have the same truth-functional meaning as the original sentences, though perhaps some of the (non-truth-functional) subtleties of the originals are lost:
The moral here is that conjunctions in English don't always contain the word 'and,' though they will always consist of two sentences, called conjuncts, connected together by means of some word or phrase which, when replaced by 'and,' results in a paraphrase that is truth-functionally equivalent in meaning, though some of the original subtlety may be lost.
Identifying conjunctions in English might be a bit tricky, as we have to look out for more words than just 'and,' as well as not always being able to count on some sentence being a conjunction just because the word 'and' occurs in it. Disjunctions are a bit easier—the only word you have to look for is 'or,' plus the occasional 'either' along with it (that is, the phrase 'either...or...'). We've already seen an example of a disjunction:
- Either John ran, or Mary laughed.
In order to symbolise this sentence, we'll take the same approach as we did with conjunction, first replacing the logical phrase with a symbol. For disjunction we use the symbol v
You'll note here that both the word 'or' between the two sentences and the word 'either' in front of them are removed from the sentence when we symbolise the connective. All we have left to do now is to symbolise the atomic sentences, which in this case we call DISJUNCTS, as they are connected by a disjunction:
Just as with our conjunction, all we do is replace each of our atomic sentence disjuncts with a suitably chosen capital letter, and our symbolisation is complete. And, just like conjunctions, disjunctions can come in many forms. Consider the following:
- Either John or Mary laughed.
- Mary either laughed or sneezed.
Here we just apply the same paraphrasing trick as we did with conjunction to figure out how to symbolise these sentences:
Now we can straightforwardly replace the logical words `or' and `either' with the appropriate symbol and replace the atomic sentences with capital letters:
You might be wondering at this point if we'll have the same sort of difficulty with 'or' as we did with 'and' in our sundae example. Fortunately not. Consider the sundae example again, this time with 'or' in the place of 'and,' plus its paraphrase:
In this case, the paraphrase does have the same meaning as the original sentence, even though the original sentence itself is obviously false. This time, we should symbolise the sentence as a disjunction, not as an atomic sentence:
At this point, you must be thinking that disjunction can't be all that easy—after all, we don't have the same wrinkles to worry about with disjunction that we do with conjunction. Unfortunately, you're right—it isn't that easy. This time, however, the tricky part has to do with the interpretation of 'or' itself. The problem is that there are two possible ways of interpreting the word 'or' as it is used in English. Consider the following:
This sentence can be interpreted in two different ways. The first way we can interpret it, it would mean that one or both of John and Mary will buy ice cream, that is, that the sentence will be true if John buys ice cream, if Mary buys ice cream, or if both of them do. This interpretation is the INCLUSIVE interpretation of 'or.' The other way to interpret the sentence is to take it to mean that either John or Mary will buy ice cream, but not both, that is, the sentence would be true if either of Mary or John bought ice cream, but false if both of them do. This is the EXCLUSIVE interpretation of 'or.'
The problem we face here is in deciding to which of these two possible interpretations we want our symbol for disjunction to correspond. As it turns out, there's a way to easily express the exclusive version of disjunction using the inclusive version(just think of the English expression 'either, but not both'), so we'll use the inclusive version as the one to which the symbol ' v ' will correspond. The tricky bit about disjunctions, then, is in determining whether you want to interpret a particular disjunction as having the inclusive or the exclusive meaning when you symbolise it. You already know how to symbolise the inclusive kind of disjunction, and we'll come back to the exclusive kind in a little while, but first we need to look at our other two logical connectives.
In English, the phrase 'if...then...' connects two sentences together to form a CONDITIONAL sentence. We've already seen one example:
- If John ran, then Mary laughed.
We can symbolise this sentence as follows, using the same old letters for our atomic sentences, and the symbol → to replace the logical phrase 'if...then...':
Unlike conjunction and disjunction, where we call the two sentences that are connected by the same name (conjuncts and disjuncts, respectively), the two sentences connected by a conditional are called by different names. The 'if' sentence, which appears to the left of the → is called the ANTECEDENT, and the 'then' sentence, which goes to the right, is called the CONSEQUENT. Thus, in the above example, the sentence J is the antecedent, and M is the consequent of the conditional J → M.
Conditionals, like conjunctions, can be a bit tricky in English, since they can disguise themselves in a number of ways. All of the following sentences are equivalent to the conditional we've just symbolised:
All of these sentences we symbolise in the same way as we did the original, despite the fact that the atomic sentences don't always appear in the same order in the English sentences as they do in the symbolisation.
While the sentences we consider to be conjunctions and disjunctions are pretty straightforward as far as their interpretations go, at least once we sort out the inclusive versus exclusive issue regarding disjunction, conditionals are anything but straightforward. In fact, there is a long—standing debate about how to interpret conditionals that occupies quite a number of philosophers and logicians to this day. Rather than get deeply into this debate here, we're just going to adopt the traditional truth-functional viewpoint on the matter, which is that a conditional sentence is true if either its antecedent is false, or if its consequent is true. While this interpretation of the conditional may be an oversimplification that doesn't do justice to actual use of conditional statements, it is the only truth-functional interpretation of the connective that accords with inferential practice.
Our final connective is negation. It might seem a bit odd to call negation a connective, since it only 'connects' one sentence, but we do indeed call it a connective, so odd it will have to be. Actually, we call negation a UNARY connective for this very reason, while the other connectives are all called BINARY connectives, as they connect two sentences.
We've already seen one example of a negation in English:
Negation is a little bit different from conjunctions, disjunctions, and conditionals in that it tends to occur in the middle of sentences in English. This not only makes it a little hard to see how to go about symbolising negations, it can also make it a bit difficult to sort out precisely what is being negated. Yet again, we have a paraphrasing trick that can help on both counts:
If you'll compare this paraphrase to our original sentence, it's clear that the truth-functional meaning is preserved, but our sentence is now in a much nicer form from a symbolisation standpoint. By taking our original atomic sentence 'John ran' and sticking the expression 'it is not the case that' in front of it, rather than sticking 'didn't' in the middle, we end up with a paraphrase that preserves the form of our original sentence, and gives us a better idea of how to symbolise this sentence. Let's go ahead and replace the expression 'it is not the case that' with our symbol for negation, ' ¬ ':
Now it's clear that all we have left to do is symbolise our atomic sentence as usual:
We've already seen two different ways that negations can manifest in English, and you've probably already realised that there are more. Consider each of the following:
Even though the word 'not' doesn't appear in any of these sentences, each of them can be interpreted as a negation, as paraphrasing illustrates:
In each case, we remove the negative prefix from one of the words in the original sentence, and insert the expression 'it is not the case that' in front of the remainder of the sentence instead. Not all negative prefixes can be treated in this fashion, but it's pretty clear when you ought not to do this, since the result of removing the prefix in such cases usually doesn't result in a real word, as would be the case with the following sentences:
Other than having to look out for negative prefixes, identifying negations is generally pretty easy, since the word 'not' is going to appear somewhere in the sentence (possibly contracted, as in 'didn't'). The big difference between negation and the other connectives is that with negation, you only have a single sentence—rather than two-to worry about.
Now that we've met all of our connectives and learned how to use them to symbolise English sentences, we should move on to take a look at some more complicated sentences, which means yep, you guessed it more than one connective at a time.
Consider the following sentence:
- Bob will either feed the ducks, or feed the chickens and gather their eggs.
This sentence obviously involves more than just one logical operator—we have both an 'and' and an 'or' to deal with—so it might not be entirely clear yet how we're going to symbolise this sentence. The first thing we need to do is to determine the top-level structure of the sentence. Paraphrasing the sentence yields the following:
It's now pretty clear that the basic structure of this sentence is that of a disjunction—two sentences connected together by the phrase 'either...or....' Accordingly, we will say that disjunction is the MAIN CONNECTIVE of the sentence, since the basic top-level structure of the sentence is that of a disjunction. We might as well go ahead and replace the `either...or' with the disjunction symbol right away:
Since one of the disjuncts is an atomic sentence, we could also go ahead and symbolise it at this point as well, leaving only the compound sentence that makes up the right disjunct to be dealt with:
The remaining compound sentence is obviously a conjunction, but we should paraphrase it in order to get clear on precisely what the conjuncts are. We'll consider just the conjunction for this part:
Okay, now that we've paraphrased it, it's clear how to symbolise it:
The only question remaining at this point, then, is how to fit this into the translation as a whole. If we just stuck it into the translation by itself, we'd get the following:
This clearly isn't going to work, though, since it isn't at all clear from this translation that the disjunction is the main connective and that F & G is one of the disjuncts. We need some sort of punctuation that indicates the fact that the conjunction as a whole represents one of the disjuncts of the original sentence. We use parentheses as punctuation, like so:
Now it's clear that the main connective is a disjunction, while the right hand disjunct is itself a conjunction.
The parentheses here indicate that the ''influence'' or SCOPE of the conjunction is contained within the parentheses—it connects only the two atomic formulae inside the parentheses—its influence does not extend as far as the disjunction. The scope of the disjunction, on the other hand, includes everything in the formula, including the conjunction-which is actually the reason we called it the main connective in the first place.
That wasn't so bad, was it? Let's try another one:
Since this sentence starts out with an 'if,' we can already tell that basic structure of this sentence is that of a conditional, so the conditional will be the main connective of the translation. We thus replace the English expression with the symbol for the conditional, doing any necessary paraphrasing along the way:
Since the antecedent of our conditional is obviously an atomic sentence, we might as well symbolise it, and while we're at it, we should insert parentheses around the consequent right away:
Now all we have to do is to translate the consequent. Thanks to our paraphrasing, we can tell that the main connective of the consequent will be a disjunction:
It's pretty obvious that each of the disjuncts is itself a negation, so all we need to do is to translate these, and we're done:
You'll note here that we don't need to put any parentheses around the negations, since there's only one sentence to which each negation could possibly ''attach.''
In the two examples we've looked at, we didn't have any trouble determining what the top-level structure, or main connective of the sentence was in either case. Sometimes, however, a sentence is AMBIGUOUS, and it's impossible to tell what the structure should be. Consider the following:
This sentence could be paraphrased in two different ways, both of which are perfectly good interpretations of the original sentence:
The original sentence is ambiguous, so we have no way of telling which of these paraphrases is the 'right' one—they are equally good. If you want to translate an ambiguous sentence like the above, what should you do? Well, you could always pick whichever disambiguation you think is appropriate, but if you are absolutely not sure, you could play it safe and just use the disjunction of the two possible translations.
Before we proceed to look at the formal syntax of sentential logic, we have to fulfill one promise we made a little while back. We mentioned that we had a way of expressing the exclusive sense of disjunction in terms of the inclusive sense-a way that corresponds to the English phrase ''either, but not both.'' At the time, we couldn't symbolise this, but now we can. Recall the example we were considering:
Here's the symbolisation of the exclusive reading of this sentence:
That promise fulfilled, we can finally head on in to formal syntax.
Any formal language can be given a definition by specifying both the simplest pieces of the language and all of the rules for combining expressions together to make new ones. You've already met the simplest pieces of the language of sentential logic. They are:
We are now in a position to state the rules that define the set of syntactically WELL-FORMED FORMULAE, or, simply, FORMULAE —the grammatical expressions of sentential logic. Here the only other thing we need is some way of talking about any formula of sentential logic. We'll use capital letters, like P and Q as VARIABLES that range over the set of all formulae of sentential logic to accomplish this. You'll note that we format these differently from the sentential letters-this is to indicate that the variables are not themselves sentential letters, nor any other formulae of sentential logic. That said, here is the formal set of rules for our language of sentential logic:
As you can see, these rules are nothing more than a precise version of the informal discussion we've presented in the earlier parts of this chapter. You should note, however, that the definition says nothing about what any of these expressions mean, despite the fact that we did make some mention of how to interpret them in the previous discussion. That's because the above rules are strictly syntactic rules—we consider the question of what the expressions mean, particularly their truth-values, or their SEMANTICS to be a separate matter from syntax. Since we were also learning how to translate from English to sentential logic, we did have to talk about the meanings of the expressions, but this is not properly part of the domain of syntax. We'll go on to look at semantics in the next chapter, but first, there are a few more syntactic issues that we need to cover, as well as looking at an example of how to build up a formula according to the syntactic rules. Let's do that right now:
You probably noticed that there were a lot of parentheses showing up in the formal rules we just presented; in fact, every compound expression we form by means of a binary connective is enclosed in parentheses. Why did we do this? Well, we need the parentheses eventually in order to keep the scope of the connectives clear and unambiguous, so it makes the most sense to simply build the parentheses into the formulae right from the beginning. Otherwise, it would be very difficult to come up with a set of rules for including the parentheses later on that always put them where we wanted them.
While we do need at least some parentheses to keep our sentential logic formulae unambiguous, when it comes to actually reading formulae we usually aren't going to need all the ones that the syntactic rules tell us to include. We've actually already been omitting the outermost pair of parentheses in each formula rather casually—after all, since they are the outermost pair, there's no way to make a formula ambiguous by omitting these parentheses, at least not until you embed that formula inside a larger one, say as a disjunct or conjunct. We also don't need parentheses around negations since negation is a unary connective.
The big question is just how many pairs of parentheses can be omitted, and which ones, before we make a sentence ambiguous. We need a set of rules for omitting parentheses that will allow us to omit as many parentheses as we find convenient, without crossing over into ambiguous territory or changing the meaning of a formula. Actually, we want the same sort of rules as those we find in arithmetic for determining the order of operations. Consider the following:
3 x 4 + 5
The order of operations in arithmetic tells us, since there are no parentheses in the above, that the multiplication should be carried out first, then the addition, like so:
3 x 4 + 5 = 12 + 5 = 17
If we had wanted the addition to be carried out first, on the other hand, we would need to include parentheses to indicate this:
3 x (4 + 5) = 3 x 9 = 27
Why do we carry out multiplication before addition if there are no parentheses? Actually, this is just a matter of CONVENTION —the order of operations could just as well be different. We just happened to settle on doing it one way, rather than the other. The same is true of our rules for parentheses in sentential logic.
The rules we need can be expressed as a procedure for inserting parentheses back into a formula from which some have been omitted. Here's that procedure:
Let's try an example:
The procedure tells us to start out by replacing the parentheses around the conjunction, as follows:
Next, we insert the outermost parentheses around the whole formula, as its main connective is the disjunction:
Pretty straightforward, actually. Let's take a look at one more example, this time with multiple occurrences of the same connective:
Stepping through the procedure, we first insert parentheses around the conjunction:
Next, we have two conditionals around which to insert parentheses. We start, as the procedure directs, with the rightmost of the conditionals:
Now we insert parentheses around the remaining conditional, which happens to be our main connective, so we're done:
That's really all there is to inserting and omitting parentheses. You will probably not want to omit as many parentheses as these rules actually allow, since a few parentheses here and there can make a formula much more easily readable. The trick lies in finding the right balance between including and omitting parentheses that makes reading the formulae easy for you —just so long as you don't omit a pair of parentheses in such a way that it changes the meaning of the formula or makes it ambiguous.
There's just one last thing regarding syntax that we need to discuss before heading on to the next chapter to look at the semantics of sentential logic, and that is the matter of parse trees.
A PARSE TREE graphically represents the internal structure of an expression of sentential logic, making it possible to test whether or not the expression is well-formed. As such, parse trees are a very important syntactic tool, so you'll need to know how to go about "constructing" them. First, however, let's take a quick look at an example of a parse tree, so you'll know just what sort of thing it is you are going to be learning how to construct:
Okay, so here's how to construct the parse tree for an expression: Start out by writing down the entire expression. It helps to write it out near the top of the page you are working on, since parse trees grow downwards. The next thing you'll need to do is to identify the general form of the expression. Is it a sentential letter, or is it of one of the following forms: ¬P , (P & Q) , (P v Q) , or (P → Q)? If your expression doesn't fit into any of these five categories, then you know that the expression is not well-formed. If it does fall into one of the categories, there is work left to be done.
Once you've identified the general form of the expression, you know how many immediate subexpressions there are: Sentential letters have no subexpressions, expressions of the form ¬P have one immediate subexpression, the expression P, and expressions of the form (P & Q) , (P v Q), and (P → Q) have two subexpressions each, the expressions P and Q. The next step in constructing the parse tree is to create one branch for each subexpression, including the subexpression itself at the end of the new branch as a "leaf" as the following examples indicate:
Repeat this process for each new leaf of the tree created that is not a sentential letter. If you are able to keep going until each branch of the tree ends in a sentential letter, the expression you started with is a well-formed formula.
Why don't we take a look at a couple of examples at this point? Let's start out by constructing the parse tree for a well-formed formula:
Now let's try constructing parse trees for expressions that are not well-formed formulae:
Parse trees are good for more than just checking well-formedness, however, as we shall see in the next chapters when we discuss some of the semantic uses to which they can be put.
That about covers it for the syntax of sentential logic. Believe it or not, in this one chapter, you've learned an entire new language! A little practice with what you've learned, and you'll be set to begin on semantics, so let's head on into the exercises.
Symbolise each of the following sentences, using the following symbolisation key:
Symbolise each of the following sentences, paraphrasing them first if necessary, using the following symbolisation key:
For each of the following sentences, provide an English translation according to the symbolisation key from the previous exercise:
For each of the following expressions of sentential logic, determine whether or not it is a well-formed formula, and if not, explain why not.
Insert the missing parentheses into each of the following formulae.
Construct a parse tree for each of the following formulae.