Chapter 1 - Stanford Lagunita
Contents
1. SECTION 1 6 38 ATOMIC SENTENCES the objects 2 and 2 4 6 and if the names a and b are assigned to them then the atomic sentences must get the values indicated in the previous table The only way those values can change is if the names name different things Identity claims also work this way both in set theory and in Tarski s World Exercises 1 19 Which of the following atomic sentences in the first order language of set theory are true 7 and which are false We use in addition to a and b as above the name c for 6 and d for 2 7 2 4 6 l aec acd bec bed cEd cEb Dap wN To answer this exercise submit a Tarski s World sentence file with an uppercase T or F in each sentence slot to indicate your assessment SECTION 1 7 The first order language of arithmetic While neither the blocks language as implemented in Tarski s World nor the language of set theory has function symbols there are languages that use them extensively One such first order language is the language of arithmetic This language allows us to express statements about the natural numbers 0 1 2 3 and the usual operations of addition and multiplication There are several more or less equivalent ways of setting up this language predicates lt and The one we will use has two names 0 and 1 two binary relation symbols functions x of and lt and two binary function symbols and x The atomic sentences are arithmeti2. Exercises 1 12 Express in English the claims made by the following sentences of FOL as clearly as you can amp You should try to make your English sentences as natural as possible All the sentences are by the way true 1 Taller father claire father max 2 john father max 3 Taller claire mother mother claire 4 Taller mother mother max mother father max 5 mother melanie mother claire 1 13 Assume that we have expanded the blocks language to include the function symbols fm bm Im amp and rm described earlier Then the following formulas would all be sentences of the language 1 Tet Im e 2 fm c c 3 bm b bm e 4 FrontOf fm e e 5 LeftOf fm b b CHAPTER 1 1 14 7 1 15 FUNCTION SYMBOLS 35 6 Toa le c 7 bm Im c Im bm c 8 SameShape Im b bm r 9 d Im fm rm bm d 10 Between b Im b rm b Fill in the following table with TRUE s and FALSE s according to whether the indicated sentence is true or false in the indicated world Since Tarski s World does not understand the function symbols you will not be able to check your answers We have filled in a few of the entries for you Turn in the completed table to your instructor Leibniz s Bolzano s Boole s Wittgenstein s I TRUE 2 3 4 5 FALSE 6 TRUE 7 8 FALSE 9 10 As you probably noticed in doing Exercise 1 13 three of the sentences came out true in all fo
3. For example suppose a names the number 2 and b names the set 2 4 6 Then the following table tells us which membership claims made up using these names are true and which are false aca FALSE acb TRUE bea FALSE beb FALSE Notice that there is one striking difference between the atomic sentences of set theory and the atomic sentences of the blocks language In the blocks language you can have a sentence like LeftOf a b that is true in a world but which can be made false simply by moving one of the objects Moving an object does not change the way the name works but it can turn a true sentence into a false one just as the sentence Claire is sitting down can go from true to false in virtue of Claire s standing up In set theory we won t find this sort of thing happening Here the analog of a world is just a domain of objects and sets For example our domain might consist of all natural numbers sets of natural numbers sets of sets of natural numbers and so forth The difference between these worlds and those of Tarski s World is that the truth or falsity of the atomic sentences is determined entirely once the reference of the names is fixed There is nothing that corresponds to moving the blocks around Thus if the universe contains 2For the purposes of this discussion we are assuming that numbers are not sets and that sets can contain either numbers or other sets as members predicates of set theory membership
4. the order of the arguments of the predicates is like that in English Thus LeftOf b c means more or less the same thing as the English sentence b is left of c and Between b c d means roughly the same as the English b is between c and d Predicates and names designate properties and objects respectively What atomic sentence infix vs prefix notation SECTION 1 3 24 ATOMIC SENTENCES claims makes sentences special is that they make claims or express propositions A claim is something that is either true or false which of these it is we call truth value its truth value Thus Taller claire max expresses a claim whose truth value is TRUE while Taller max claire expresses a claim whose truth value is FALSE You probably didn t know that but now you do Given our assumption that predicates express determinate properties and that names denote definite individuals it follows that each atomic sentence of FOL must express a claim that is either true or false You try it gt 1 It is time to try your hand using Tarski s World In this exercise you will use Tarski s World to become familiar with the interpretations of the atomic sentences of the blocks language Before starting though you need to learn how to launch Tarski s World and perform some basic operations Read the appropriate sections of the user s manual describing Tarski s World before going on gt 2 Launch Tarski s World and open the files called
5. whereas this is not the case in natural languages like English Indeed even when things seem quite determinate there is often some form of context sensitivity In fact we have built some of this into Tarski s World Consider for example the difference between the predicates Larger and BackOf Whether or not cube a is larger than cube b is a determinate matter and also one that does not vary depending on your perspective on the world Whether or not a is back of b is also determinate but in this case it does depend on your perspective If you rotate the world by 90 the answer might change Open Austin s Sentences and Wittgenstein s World Evaluate the sentences in this file and tabulate the resulting truth values in a table like the one below We ve already filled in the first column showing the values in the original world Rotate the world 90 clockwise and evaluate the sentences again adding the results to the table Repeat until the world has come full circle Original Rotated 90 Rotated 180 Rotated 270 FALSE FALSE TRUE FALSE TRUE FALSE OP oe RO You should be able to think of an atomic sentence in the blocks language that would produce a row across the table with the following pattern TRUE FALSE TRUE FALSE Add a seventh sentence to Austin s Sentences that would display the above pattern Are there any atomic sentences in the language that would produce a row with this pattern FALSE TRU
6. 25 world none of the sentences using Adjoins comes out true You should try to modify the world to make some of them true As you do this you will notice that large blocks cannot adjoin other blocks 6 In doing this exercise you will no doubt notice that Between does not mean lt exactly what the English between means This is due to the necessity of interpreting Between as a determinate predicate For simplicity we insist that in order for b to be between c and d all three must be in the same row column or diagonal 7 When you are finished close the files but do not save the changes you lt have made to them a ghd Ea O sued E a E Es Ga E E cease estan ae aang 3 Congratulations Remember In FOL o Atomic sentences are formed by putting a predicate of arity n in front of n names enclosed in parentheses and separated by commas o Atomic sentences are built from the identity predicate using infix notation the arguments are placed on either side of the predicate o The order of the names is crucial in forming atomic sentences Exercises You will eventually want to read the entire chapter of the user s manual on how to use Tarski s World To do the following problems you will need to read at least the first four sections Also if you don t remember how to name and submit your solution files you should review the section on essential instructions in the Introduction starting on page 5 1 1 If you skip
7. Wittgenstein s World and Wittgenstein s Sentences You will find these in the folder TW Exercises In these files you will see a blocks world and a list of atomic sentences We have added comments to some of the sentences Comments are prefaced by a semicolon which tells Tarski s World to ignore the rest of the line gt 3 Move through the sentences using the arrow keys on your keyboard men tally assessing the truth value of each sentence in the given world Use the Verify Sentence button to check your assessments This button is on the left of the group of three colored buttons on the toolbar the one which has T F written on it Since the sentences are all atomic sentences the Game button on the right of the same group will not be helpful If you are surprised by any of the evaluations try to figure out how your interpretation of the predicate differs from the correct interpretation gt 4 Next change Wittgenstein s World in many different ways seeing what hap pens to the truth of the various sentences The main point of this is to help you figure out how Tarski s World interprets the various predicates For example what does BackOf d c mean Do two things have to be in the same column for one to be in back of the other gt 5 Play around as much as you need until you are sure you understand the meanings of the atomic sentences in this file For example in the original CHAPTER 1 ATOMIC SENTENCES
8. is decide what names and predicates you need for your translation In effect you are designing on the fly a new first order language capable of expressing the English sentence you want to translate We ve been doing this all along for example when we introduced Home max as the translation of Maz is at home and Taller claire max as the translation of Claire is taller than Maz When you make these decisions there are often alternative ways to go For example suppose you were asked to translate the sentence Claire gave Scruffy to Max You might introduce a binary predicate GaveScruffy x y meaning x gave Scruffy to y and then translate the original sentence as GaveScruffy claire max Alternatively you might introduce a three place pred icate Gave x y z meaning x gave y to z and then translate the sentence as Gave claire scruffy max There is nothing wrong with either of these predicates or their resulting translations so long as you have clearly specified what the predicates mean Of course they may not be equally useful when you go on to translate other sentences The first predicate will allow you to translate sentences like Maz gave Scruffy to Evan and Evan gave Scruffy to Miles But if you then run into the sentence Max gave Carl to Claire you would be stuck and would have to introduce an entirely new predicate say GaveCarl x y The three place predicate is thus more flexible A first order language that contained it p
9. smoothly between them At the end of most chapters we discuss common notational differences that you are likely to encounter Some notational differences though not many occur even at the level of atomic sentences For example some authors insist on putting parentheses around atomic sentences whose binary predicates are in infix position So a b is used rather than a b By contrast some authors omit parentheses surrounding the argument positions and the commas between them when the predicate is in prefix position These authors use Rab instead of R a b We have opted for the latter simply because we use predicates made up of several letters and the parentheses make it clear where the predicate ends and the arguments begin Cubed is not nearly as perspicuous as Cube d What is important in these choices is that sentences should be unambigu ous and easy to read Typically the first aim requires parentheses to be used in one way or another while the second suggests using no more than is necessary
10. CHAPTER 1 Atomic Sentences In the Introduction we talked about FOL as though it were a single language Actually it is more like a family of languages all having a similar grammar and sharing certain important vocabulary items known as the connectives and quantifiers Languages in this family can differ however in the specific vocabulary used to form their most basic sentences the so called atomic sen tences Atomic sentences correspond to the most simple sentences of English sen tences consisting of some names connected by a predicate Examples are Maz ran Max saw Claire and Claire gave Scruffy to Maz Similarly in FOL atomic sentences are formed by combining names or individual constants as they are often called and predicates though the way they are combined is a bit different from English as you will see Different versions of FOL have available different names and predicates We will frequently use a first order language designed to describe blocks arranged on a chessboard arrangements that you will be able to create in the program Tarski s World This language has names like b e and n2 and predicates like Cube Larger and Between Some examples of atomic sentences in this language are Cube b Larger c f and Between b c d These sentences say respectively that b is a cube that c is larger than f and that b is between c and d Later in this chapter we will look at the atomic sentences used in two other versio
11. E FALSE FALSE If so add such a sentence as sentence eight in Austin s Sentences If not leave sentence eight blank Are there any atomic sentences that would produce a row in the table containing exactly three TRUE s If so add such a sentence as number nine If not leave sentence nine blank Submit your modified sentence file as Sentences 1 7 Turn in your completed table to your instructor SECTION 1 3 28 ATOMIC SENTENCES SECTION 1 4 General first order languages translation designing languages choosing predicates CHAPTER 1 First order languages differ in the names and predicates they contain and so in the atomic sentences that can be formed What they share are the connectives and quantifiers that enable us to build more complex sentences from these simpler parts We will get to those common elements in later chapters When you translate a sentence of English into FOL you will sometimes have a predefined first order language that you want to use like the blocks language of Tarski s World or the language of set theory or arithmetic de scribed later in this chapter If so your goal is to come up with a translation that captures the meaning of the original English sentence as nearly as pos sible given the names and predicates available in your predefined first order language Other times though you will not have a predefined language to use for your translation If not the first thing you have to do
12. ate you use 1 Max shook hands with Claire Maz shook hands with Claire yesterday AIDS is less contagious than influenza Spain is between France and Portugal in size GTS oo Misery loves company SECTION 1 5 Function symbols Some first order languages have in addition to names and predicates other expressions that can appear in atomic sentences These expressions are called function symbols Function symbols allow us to form name like terms from names and other name like terms They allow us to express using atomic sentences complex claims that could not be perspicuously expressed using just names and predicates Some English examples will help clarify this English has many sorts of noun phrases expressions that can be combined with a verb phrase to get a sentence Besides names like Max and Claire other noun phrases include expressions like Max s father Claire s mother Every girl who knows Max No boy who knows Claire Someone and so forth Each of these combines with a singular verb phrase such as likes unbuttered popcorn to make a sentence But notice that the sentences that result have very different logical properties For example Claire s mother likes unbuttered popcorn implies that someone likes unbuttered popcorn while No boy who knows Claire likes unbuttered popcorn does not Since these noun phrases have such different logical properties they are treated differently in FOL Those that intuitively refer
13. c those that can be built up out of these symbols We will use infix notation both for the relation symbols and the function symbols Notice that there are infinitely many different terms in this language for example 0 1 1 1 1 1 1 1 1 1 4 1 and so an infinite number of atomic sentences Our list also shows that every natural number is named by some term of the language This raises the question of how we can specify the set of terms in a precise way We can t list them all explicitly since CHAPTER 1 THE FIRST ORDER LANGUAGE OF ARITHMETIC 39 there are too many The way we get around this is by using what is known as an inductive definition Definition The terms of first order arithmetic are formed in the following way 1 2 The names 0 1 are terms terms of arithmetic If t1 t2 are terms then the expressions t t2 and ti x t2 are also terms Nothing is a term unless it can be obtained by repeated application of 1 and 2 We should point out that this definition does indeed allow the function symbols to be applied over and over Thus 1 1 is a term by clause 2 and the fact that 1 is a term In which case 1 1 by clause 2 And so forth The third clause in the above definition is not as straightforward as one might want since the phrase can be obtained by repeated application of is a bit vague In Chapter 16 we will see how to give definitions like the above in a mo
14. e FOL sentence Taller father max max says that Max s father is taller than Max Thus in a language containing function symbols the definition of atomic sentence needs to be modified to allow complex terms to appear in the argument positions in addition to names Students often confuse function symbols with predicates because both take terms as arguments But there is a big difference When you combine a unary function symbol with a term you do not get a sentence but another term something that refers or should refer to an object of some sort This is why function symbols can be reapplied over and over again As we have seen the following makes perfectly good sense father father max This on the other hand is total nonsense Dodec Dodec a To help prevent this confusion we will always capitalize predicates of FOL and leave function symbols and names in lower case Besides unary function symbols FOL allows function symbols of any ar ity Thus for example we can have binary function symbols Simple English counterparts of binary function symbols are hard to come up with but they are quite common in mathematics For instance we might have a function symbol sum that combines with two terms t and t2 to give a new term sum t t2 which refers to the sum of the numbers referred to by t and tg Then the complex term sum 3 5 would give us another way of referring to 8 In a later section we will introduce a function s
15. e meanings of the corresponding English phrases The case where the discrepancy is probably the greatest is between Between and is between Remember In FOL o Every predicate symbol comes with a single fixed arity a number that tells you how many names it needs to form an atomic sentence o Every predicate is interpreted by a determinate property or relation of the same arity as the predicate ATOMIC SENTENCES 23 SECTION 1 3 Atomic sentences In FOL the simplest kinds of claims are those made with a single predicate and the appropriate number of individual constants A sentence formed by a predicate followed by the right number of names is called an atomic sentence For example Taller claire max and Cube a are atomic sentences provided the names and predicate symbols in question are part of the vocabulary of our language In the case of the identity symbol we put the two required names on either side of the predicate as in a b This is called infix no tation since the predicate symbol appears in between its two arguments With the other predicates we use prefix notation the predicate precedes the arguments The order of the names in an atomic sentence is quite important Just as Claire is taller than Maz means something different from Maz is taller than Claire so too Taller claire max means something completely different than Taller max claire We have set things up in our blocks language so that
16. hape a b a is the same shape as b Larger a b a is larger than b Smaller a b a is smaller than b SameCol a b a is in the same column as b SameRow a b a is in the same row as b a and b are located on adjacent but Adjoins a b not diagonally squares a is located nearer to the left edge of the grid than b a is located nearer to the right edge of the grid than b a is located nearer to the front of the grid than b a is located nearer to the back of the grid than b a b and c are in the same row col LeftOf a b RightOf a b FrontOf a b BackOf a b Between a b c umn or diagonal and a is between b and c an individual has the property in question or not For example Claire who is sixteen is young She will not be young when she is 96 But there is no determinate age at which a person stops being young it is a gradual sort of thing FOL however assumes that every predicate is interpreted by a deter minate property or relation By a determinate property we mean a property for which given any object there is a definite fact of the matter whether or not the object has the property This is one of the reasons we say that the blocks language predicates are somewhat consistent with the corresponding English predicates Unlike the English predicates they are given very precise interpretations interpretations that are suggested by but not necessarily identical with th
17. hat Claire is taller than Max In FOL we can have predicate symbols of any arity However in the blocks language used in Tarski s World we restrict ourselves to predicates with arities 1 2 and 3 Here we list the predicates of that language this time with their arity Arity 1 Cube Tet Dodec Small Medium Large Arity 2 Smaller Larger LeftOf RightOf BackOf FrontOf SameSize Same Shape SameRow SameCol Adjoins Arity 3 Between Tarski s World assigns each of these predicates a fixed interpretation one reasonably consistent with the corresponding English verb phrase For exam ple Cube corresponds to is a cube BackOf corresponds to is in back of and so forth You can get the hang of them by working through the first set of exercises given below To help you learn exactly what the predicates mean Table 1 1 lists atomic sentences that use these predicates together with their interpretations In English predicates are sometimes vague It is often unclear whether PREDICATE SYMBOLS 21 arguments of a predicate arity of a predicate vagueness SECTION 1 2 22 ATOMIC SENTENCES determinate property CHAPTER 1 Table 1 1 Blocks language predicates Atomic Sentence Interpretation Tet a a is a tetrahedron Cube a a is a cube Dodec a a is a dodecahedron Small a a is small Medium a a is medium Large a a is large SameSize a b a is the same size as b SameS
18. he names Thus atomic sentences of FOL often have two or more logical subjects and the predicate is so to speak whatever is left The logical subjects are called the arguments of the predicate In this case the predicate is said to be binary since it takes two arguments In English some predicates have optional arguments Thus you can say Claire gave Claire gave Scruffy or Claire gave Scruffy to Maz Here the predicate gave is taking one two and three arguments respectively But in FOL each predicate has a fixed number of arguments a fixed arity as it is called This is a number that tells you how many individual constants the predicate symbol needs in order to form a sentence The term arity comes from the fact that predicates taking one argument are called unary those taking two are binary those taking three are ternary and so forth If the arity of a predicate symbol Pred is 1 then Pred will be used to express some property of objects and so will require exactly one argument a name to make a claim For example we might use the unary predicate symbol Home to express the property of being at home We could then combine this with the name max to get the expression Home max which expresses the claim that Max is at home If the arity of Pred is 2 then Pred will be used to represent a relation between two objects Thus we might use the expression Taller claire max to express a claim about Max and Claire the claim t
19. ires some skill Usually the overall goal is to come up with a language that can say everything you want but that uses the smallest vocabulary possible Picking the right names and predicates is the key to doing this Exercises 1 8 Suppose we have two first order languages the first contains the binary predicates amp GaveScruffy x y and GaveCarl x y and the names max and claire the second contains the ternary predicate Gave x y z and the names max claire scruffy and carl 1 List all of the atomic sentences that can be expressed in the first language Some of these may say weird things like GaveScruffy claire claire but don t worry about that 2 How many atomic sentences can be expressed in the second language Count all of them including odd ones like Gave scruffy scruffy scruffy 3 How many names and binary predicates would a language like the first need in order to say everything you can say in the second SECTION 1 4 30 ATOMIC SENTENCES 1 9 Table 1 2 Names and predicates for a language ENGLISH FOL COMMENT Names Maz max Claire claire Folly folly The name of a certain dog Carl carl The name of another dog Scruffy scruffy The name of a certain cat Pris pris The name of another cat 2pm Jan 2 2011 2 00 The name of a time 2 01 pm Jan 2 2011 2 01 One minute later Similarly for other times Predicates x is a pet Pet x x is a person Person x x is a student Student x x
20. is at home Home x x is happy Happy x t is earlier than t ter Earlier than for times x was hungry at time t Hungry x t x was angry at time t Angry x t x owned y at time t x gave ytozatt x fed y at time t Owned x y t Gave x y z t Fed x y t We will be giving a number of problems that use the symbols explained in Table 1 2 Start a new sentence file in Tarski s World and translate the following into FOL using the names and predicates listed in the table You can switch to the Pets language in the Sentence toolbar When you type make sure they appear exactly as in the table for example use 2 00 not 2 00 pm or 2 pm All references to times are assumed to be to times on January 2 2011 QO AWUN Claire owned Folly at 2 pm Claire gave Pris to Max at 2 05 pm Maz is a student Claire fed Carl at 2 pm Folly belonged to Maz at 38 05 pm 2 00 pm is earlier than 2 05 pm Name and submit your file in the usual way CHAPTER 1 FUNCTION SYMBOLS 31 1 10 Translate the following into natural sounding colloquial English consulting Table 1 2 a 1 Owned max scruffy 2 00 2 Fed max scruffy 2 30 3 Gave max scruffy claire 3 00 4 2 00 lt 2 00 1 11 For each sentence in the following list suggest a translation into an atomic sentence of FOL In amp addition to giving the translation explain what kinds of objects your names refer to and the intended meaning of the predic
21. lowing list suggest a translation into an atomic sentence of FOL In amp addition to giving the translation explain what kinds of objects your names refer to and the intended meaning of the predicates and function symbols you use 1 Indiana s capital is larger than California s Hitler s mistress died in 1945 Maz shook Claire s father s hand Maz is his father s son John and Nancy s eldest child is younger than Jon and Mary Ellen s A aie ee CHAPTER 1 THE FIRST ORDER LANGUAGE OF SET THEORY 37 SECTION 1 6 The first order language of set theory FOL was initially developed for use in mathematics and consequently the most familiar first order languages are those associated with various branches of mathematics One of the most common of these is the language of set theory This language has only two predicates both binary The first is the identity symbol which we have already encountered and the second is the symbol for set membership It is standard to use infix notation for both of these predicates Thus in set theory atomic sentences are always formed by placing individual constants on either side of one of the two predicates This allows us to make identity claims of the form a b and membership claims of the form a b where a and b are individual constants A sentence of the form a b is true if and only if the thing named by b is a set and the thing named by a is a member of that set
22. lus the relevant names would be able to translate any of these sentences In general when designing a first order language we try to economize on the predicates by introducing more flexible ones like Gave x y z rather than GENERAL FIRST ORDER LANGUAGES 29 less flexible ones like GaveScruffy x y and GaveCarl x y This produces a more expressive language and one that makes the logical relations between various claims more perspicuous Names can be introduced into a first order language to refer to anything that can be considered an object But we construe the notion of an object objects pretty flexibly to cover anything that we can make claims about We ve al ready seen languages with names for people and the blocks of Tarski s World Later in the chapter we ll introduce languages with names for sets and num bers Sometimes we will want to have names for still other kinds of objects like days or times Suppose for example that we want to translate the sen tences Claire gave Scruffy to Max on Saturday Sunday Max gave Scruffy to Evan Here we might introduce a four place predicate Gave w x y z meaning w gave x to y on day z plus names for particular days like last Saturday and last Sunday The resulting translations would look something like this Gave claire scruffy max saturday Gave max scruffy evan sunday Designing a first order language with just the right names and predicates requ
23. new sentence file and translate them into FOL 1 a is a cube b is smaller than a c is between a and d d is large e is larger than a b is a tetrahedron e is a dodecahedron e is right of b a is smaller than e dis in back of a b is in the same row as d CHONAKTR WL Pre N b is the same size as c After you ve translated the sentences build a world in which all of your translations are true Submit your sentence and world files as Sentences 1 4 and World 1 4 Naming objects Open Lestrade s Sentences and Lestrade s World You will notice that none of the objects in this world has a name Your task is to assign the objects names in such a way that all the sentences in the list come out true Remember to save your solution in a file named World 1 5 Be sure to use Save World As not Save World CHAPTER 1 1 6 Gg ATOMIC SENTENCES 27 Naming objects continued Not all of the choices in Exercise 1 5 were forced on you That is you could have assigned the names differently and still had the sentences come out true Change the assignment of as many names as possible while still making all the sentences true and submit the changed world as World 1 6 In order for us to compare your files you must submit both World 1 5 and World 1 6 at the same time Context sensitivity of predicates We have stressed the fact that FOL assumes that every predicate is interpreted by a determinate relation
24. ns of FOL the first order languages of set theory and arithmetic In the next chapter we begin our discussion of the connectives and quantifiers common to all first order languages atomic sentences names and predicates SECTION 1 1 Individual constants Individual constants are simply symbols that are used to refer to some fixed individual object They are the FOL analogue of names though in FOL we generally don t capitalize them For example we might use max as an individ ual constant to denote a particular person named Max or 1 as an individual constant to denote a particular number the number one In either case they would basically work exactly the way names work in English Our blocks 19 20 ATOMIC SENTENCES names in FOL SECTION 1 2 language takes the letters a through f plus nj no as its names The main difference between names in English and the individual constants of FOL is that we require the latter to refer to exactly one object Obviously the name Maz in English can be used to refer to many different people and might even be used twice in a single sentence to refer to two different people Such wayward behavior is frowned upon in FOL There are also names in English that do not refer to any actually existing object For example Pegasus Zeus and Santa Claus are perfectly fine names in English they just fail to refer to anything or anybody We don t allow such names in FOL What we do allow tho
25. ped the You try it section go back and do it now This is an easy but crucial exercise that will familiarize you with the atomic sentences of the blocks language There is nothing you need to turn in or submit but don t skip the exercise 1 2 Copying some atomic sentences This exercise will give you some practice with the Tarski s World keyboard window as well as with the syntax of atomic sentences The following are all atomic sentences of our language Start a new sentence file and copy them into it Have Tarski s World check each formula after you write it to see that it is a sentence If you make a mistake edit it before going on Make sure you use the Add Sentence command between sentences SECTION 1 3 26 ATOMIC SENTENCES 1 4 N not the return key If you ve done this correctly the sentences in your list will be numbered and separated by horizontal lines 1 Tet a Medium a Dodec b Cube c FrontOf a b Between a b c a d Larger a b Smaller a c LeftOf b c OND eN Remember you should save these sentences in a file named Sentences 1 2 When you ve finished your first assignment submit all of your solution files using the Submit program Building a world Build a world in which all the sentences in Exercise 1 2 are simultaneously true Remember to name and submit your world file as World 1 3 Translating atomic sentences Here are some simple sentences of English Start a
26. quantifiers to the language we will be able to translate freely back and forth between the functional and relational languages 1 16 Let s suppose that everyone has a favorite movie star Given this assumption make up a first amp order language for talking about people and their favorite movie stars Use a function symbol that allows you to refer to an individual s favorite actor plus a relation symbol that allows you to say that one person is a better actor than another Explain the interpretation of your function and relation symbols and then use your language to express the following claims 1 Harrison is Nancy s favorite actor Nancy s favorite actor is better than Sean Nancy s favorite actor is better than Mazx s Claire s favorite actor s favorite actor is Brad Sean is his own favorite actor OE ses PNS 1 17 Make up a first order language for talking about people and their relative heights Instead of amp using relation symbols like Taller however use a function symbol that allows you to refer to people s heights plus the relation symbols and lt Explain the interpretation of your function symbol and then use your language to express the following two claims 1 George is taller than Sam 2 Sam and Mary are the same height Do you see any problem with this function symbol If so explain the problem Hint What happens if you apply the function symbol twice 1 18 For each sentence in the fol
27. re satisfactory way one that avoids this vague clause The atomic sentences in the language of first order arithmetic are those that can be formed from the terms and the two binary predicate symbols x 1 1 is also a term again atomic sentences of arithmetic and lt So for example the FOL version of 1 times 1 is less than 1 plus 1 is the following 1 20 1 21 1x1 lt 1 1 Exercises Show that the following expressions are terms in the first order language of arithmetic Do this by explaining which clauses of the definition are applied and in what order What numbers do they refer to 1 0 0 2 0 1 x 0 3 1 1 1 1 x 1 1 4 1 x 1 x 1 x 1 Find a way to express the fact that three is less than four using the first order lan guage of arithmetic 1 22 Q Show that there are infinitely many terms in the first order language of arithmetic referring to the number one SECTION 1 7 40 ATOMIC SENTENCES SECTION 1 8 Alternative notation CHAPTER 1 As we said before FOL is like a family of languages But as if that were not enough diversity even the very same first order language comes in a variety of dialects Indeed almost no two logic books use exactly the same notational conventions in writing first order sentences For this reason it is important to have some familiarity with the different dialects the different notational conventions and to be able to translate
28. the same column as a Thus if there are several blocks in the column with a then fm a refers to whichever one is nearest the front Notice that fm a may not itself have a name fm a may be our only way to refer to it If a is the only block in the column or is the frontmost in its column then fm a would refer to a Analogously bm Im and rm could be interpreted to mean backmost leftmost and rightmost respectively With this interpretation the term Im bm c would refer to the leftmost block in the same row as the backmost block in the same column as c The FUNCTION SYMBOLS 33 arity of function symbols functions symbols for blocks language SECTION 1 5 34 ATOMIC SENTENCES atomic sentence Larger Im bm c c would then be true if and only if this block is larger than c Notice that in this expanded language the sentence Im bm c bm Im c is not always true Can you think of an example where it is false On the other hand fm fm a fm a is always true Can you think of any other atomic sentences using these function symbols that are always true How about sentences that are always false Remember In a language with function symbols o Complex terms are typically formed by putting a function symbol of arity n in front of n terms simple or complex o Complex terms are used just like names simple terms in forming atomic sentences o In FOL complex terms are assumed to refer to one and only one object
29. to an individual are function symbols terms SECTION 1 5 32 ATOMIC SENTENCES complex terms function symbols vs predicates CHAPTER 1 called terms and behave like the individual constants we have already dis cussed In fact individual constants are the simplest terms and more complex terms are built from them using function symbols Noun phrases like No boy who knows Claire are handled with very different devices known as quanti fiers which we will discuss later The FOL analog of the noun phrase Maz s father is the term father max It is formed by putting a function symbol father in front of the individual constant max The result is a complex term that we use to refer to the father of the person referred to by the name max Similarly we can put the function symbol mother together with the name claire and get the term mother claire which functions pretty much like the English term Clatre s mother We can repeat this construction as many times as we like forming more and more complex terms father father max mother father claire mother mother mother claire The first of these refers to Max s paternal grandfather the second to Claire s paternal grandmother and so forth These function symbols are called unary function symbols because like unary predicates they take one argument The resulting terms function just like names and can be used in forming atomic sentences For instance th
30. ugh is for one object to have more than one name thus the individual constants matthew and max might both refer to the same individual We also allow for nameless objects objects that have no name at all Remember In FOL o Every individual constant must name an actually existing object o No individual constant can name more than one object o An object can have more than one name or no name at all Predicate symbols predicate or relation symbols logical subjects CHAPTER 1 Predicate symbols are symbols used to express some property of objects or some relation between objects Because of this they are also sometimes called relation symbols As in English predicates are expressions that when com bined with names form atomic sentences But they don t correspond exactly to the predicates of English grammar Consider the English sentence Maz likes Claire In English grammar this is analyzed as a subject predicate sentence It consists of the subject Maz followed by the predicate likes Claire In FOL by contrast we usually view this as a claim involving two logical subjects the names Maz and Claire and 1There is however a variant of first order logic called free logic in which this assumption is relaxed In free logic there can be individual constants without referents This yields a language more appropriate for mythology and fiction a predicate likes that expresses a relation between the referents of t
31. ur worlds It turns out that one of these three cannot be falsified in any world because of the meanings of the predicates and function symbols it contains Your goal in this problem is to build a world in which all of the other sentences in Exercise 1 13 come out false When you have found such a world submit it as World 1 14 Suppose we have two first order languages for talking about fathers The first which we ll call the functional language contains the names claire melanie and jon the function symbol father and the predicates and Taller The second language which we will call the relational language has the same names no function symbols and the binary predicates Taller and FatherOf where FatherOf c b means that c is the father of b Translate the following atomic sentences from the relational language into the functional language Be careful Some atomic sentences such as claire claire are in both languages Such a sentence counts as a translation of itself 1 FatherOf jon claire 2 FatherOf jon melanie SECTION 1 5 36 ATOMIC SENTENCES 3 Taller claire melanie Which of the following atomic sentences of the functional language can be translated into atomic sentences of the relational language Translate those that can be and explain the problem with those that can t 4 father melanie jon 5 father melanie father claire 6 Taller father claire father jon When we add connectives and
32. ymbol to denote addition but we will use infix notation rather than prefix notation Thus 3 5 will be used instead of sum 3 5 In FOL just as we assume that every name refers to an actual object we also assume that every complex term refers to exactly one object This is a somewhat artificial assumption since many function like expressions in English don t always work this way Though we may assume that mother father father max refers to an actual deceased individual one of Max s great grandmothers there may be other uses of these function symbols that don t seem to give us genuinely referring expressions For example perhaps the complex terms mother adam and mother eve fail to refer to any individuals if Adam and Eve were in fact the first people And certainly the complex term mother 3 doesn t refer to anything since the number three has no mother When designing a first order language with function symbols you should try to ensure that your complex terms always refer to unique existing individuals The blocks world language as it is implemented in Tarski s World does not contain function symbols but we could easily extend the language to include some Suppose for example we introduced the function expressions fm bm Im and rm that allowed us to form complex terms like fm a Im bm c rm rm fm d We could interpret these function symbols so that for example fm a refers to the frontmost block in
Download Pdf Manuals
Related Search