Class Note for CMPSCI 601 at UMass(15)
Class Note for CMPSCI 601 at UMass(15)
Popular in Course
Popular in Department
This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(15)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 11 Boolean variables X 123 Boolean expressions 0 literals a easy T l 0 a 6 ea for a 8 Boolean eXp s Truth assignment T X Q X gt true false Xltp E X 33 occurs in 90 If Xgp Q X then T is appropriate to p T assigns truth value to 90 T t 90 or T zp Facts 1 SAT and CircuitSAT are NPcomplete 2 HornSAT and CVP are Pcomplete 3 2SAT is is NLcomplete Boolean circuits provide another model of computation analogous to Turing machine lambda calculus etc 1 CMPSCI 601 FirstOrder Logic With Equality Lecture 11 Vocabulary Z 1 H r P function symbols 77 H predicate symbols E H not mentioned 7quot arity function r 2 Variables V 33y z 331 yl zl Number Theory EN DN HN TN EN 0 0 gtlt7 7quotN0 07quotN0 17quotN rNgtlt rN 2 UN 2 2 lt 7quotN 7quotNlt 2 Graph Theory 20 ltDg H97 T9 D9 3775 7218 T905 0 H9 2 7 E Tg TgE 2 Tarski s World ET 2 CDT HT TT PT a7b7c7d787f HT 2 Tet Cube Dodec Small Medium Large SameSize SameShape Larger Smaller SameCol SameRow Adjoins LeftOf RightOf FrontOf BackOf Between ma mm do rltdgt are m o rTet rCube rD0dec rSmall rMedium rLarge 1 rSameSize rSameShape rLarger rSmaller rSameC01 rSameR0w rAdj0ins rLeftOf rR139ghtOf rBackOf 2 rBetween 3 CMPSCI 601 Syntax Lecture 11 terms 1 variables ayz 2 constants c E D rc O 3 ft1tkwheret1tk aretermsf E Drf k atomic formulas Rt1 this where t1 tk terms R E H NR k formulas 1 atomic formulas 2 A A B where A B are formulas 3 Vacl where A is a formula 32 2 set of rstorder formulas of vocabulary 2 Abbreviations in addition to A gt H 333A lt gt Wac l t1 t2 gt 1t1 t2 CMPSC1601 ZN Lecture 11 Abbreviations t1 t2 gtt1t2t1ltt2 1 C gt 00 2 9 gt 01 3 9 gt 02 11132 c gt 3xt1 x 6 212 CMPSCI 601 Lecture 11 1 WKMarty gt Ey 2 Va Easa 3 V3yE7y V Em 56 4 Va Ea7 8 5 ayzxy z E y E z 6 Vy1Z2y3E7 21 EC 22 1393733 gt 21 y2Vy1 y3Vy2 y3 CMPSCI601 Free and Bound Variables Lecture 11 An occurrence of a variable a is bound iff it occurs within the scope of a quanti er V33 or Otherwise the occurrence is free 1 Byz y z Etc 2 Etc z 2 m z 3 Vyyc y 4 m 3 Bound variables are dummy variables you can change their names without affecting the meaning A rstorder formula says something about its free vari ables You cannot determine the meaning of the formula without knowing the values of the free variables CMPSCI 601 FirstOrder Structures Lecture 11 A structure also called a model of a vocabulary Z 2 CD H r is a pair A U u such that Uzil D M V gtU i gtA H D gt total functions on U0 H31 HfAIUTf gtU M1 H gt relations on U0 3 R l gt RA c UM How s That Again We specify the universe variable values functions and relations by nite lookup tables This is the information we need to decide Whether a formula is true or false Example Any world W for Tarski s World is is struc ture of vocabulary ET ie W E STRUCZT 4 0 0 1 Figure 111 Graphs G and H G VG13EG e STRUCE 9 VG 01234 EG 17273707371737273747470 is a structure of vocabulary 29 consisting of a directed graph with two speci ed vertices s and t G has ve ver tices and Six edges See Figure 111 which shows 6 as well as another graph H which is isomorphic but not equal to G 10 Binary String w 01101 A 0 1 4 lt124gt e STRUCES ES 77lt7S7lt72gt7ltlt72gt7ltS71gt lt2731 1 3Vyy S 6 3W 2 lt yA Sa 3y gt lt z lt sentence formula with no free variables 11 CMPSCI 601 A Relational Database Lecture 11 Zgen 3F17P2732 BO 2 ltU0 F0 P0 30gt E STRUCEgen U0 2 Abraham Isaac Rebekah Sarah F0 2 Sarah Rebekah P0 ltAbraham1saac ltSarahIsaac 30 ltAbrahamSarahgt IsaacRebekahgt siblz39ng7Z E EfWXLI 9 f 7 m PU 56 PU y 13011756 PM W Wauntlt7 y E 323803 2 A Spsiblz39ng j 8 A 8 m V 333 12 N N 0 0 X T lt the standard model 0fthe nat urals 17 39 39 7p 1 07 11 177 XI T117 D p prime N ZpZ e STRUCEN MultInverses E O Elv u X 2 1 N MultInverses Z pZ MultInverses 13 Extend the function u terms gt M already de ned on variables and constants 12th 39 39 7trfj 39 7l l t7 fj Now every term has a meaning Tarski s Inductive De nition of Truth MEN t1 t2 ltgt 751 752 0117 i RN51 39 39 39 7trRj ltgt ltHltt17 39 39 39 7HlttrRjgt E R34 L4Luruw gtL4Lu99 UAMOWV lt UN 0wMUAMO 1AM i WM ltgt foralla E MUG117m afc i u y a ifyza 14 Play Tarski s Truth Game world W sentence 90 players A B A asserts that W i 90 B denies that W 90 The game rules depend inductively on the formula 90 90 is atomic A Wins iffW zp zp E OCVBC AassertsWocorAassertsW8 oc8 BdeniesWocorBdeniesW8 8 l a A and B switch roles and B asserts W i 9 ll 90 E Ede1 A chooses an element from 1W assign ing it a name n A asserts that W 243 9 p E VQLzJ B chooses an element from 1W as signing it a name n B denies that W 243 9 15 Example Does Z3Z 0 V Evu X 2 1 Z3Z no 1 0 V Evu X 2 1 ltgt forall a 6 012 Z3Zu0au u 0 V Evu X 2 Z3Z7M070U u 0 ltgt um 0uu 07 0mm ltgt00 Z3Zu01u Evu X 2 1 ltgt exists b E 012Z3Zu01ubv u X 2 1 Z3Zu01u1v u X 2 1 Similarly Z3Zu02u Evu X 2 1 16 E i E a L E qr x E E qr k E A 5 L 3 5 gr L E3 5 3 gr 2 L E E 3 Q E L E A 33 L E acch SA Enivwscg L Six 3 Si A Six N 2chch Proposition 113 MW k 39390 ltgt exists a E MUG1W CL s39 90 Proof MW 393 ltgt MW 56w ltgt 1AM WHO ltgt not for all a e moo11 MW w ltgt for some a E MWALmafc 10 ltgt for some a E MWALmafc k 90 18 De nition 114 A B E STRUCE E 2 CD Hm A is a substructure of B A S 8 iff 1 M Q 181 2 For f E D f4 f5 n MVUHI 3 For B e 11 RA 2 RB n1A1rltRgt 1 2 1 2 G I A I 4 0 4 1 S 2 1S 2 B r C A and B but not C are substructures of G 19 De nition 115 AB E STRUCE Ais isomorphic to B A quotE B iffexists 77 A gt 18 1 77is 11 and onto 2 For every R E H tuple e1 W3 6 IA lt81 r3gt 6 R H lt77el77er3gt 6 R5 3 For every f E D tuple e1 ew 6 1A HOE817 7 8w fB77 17 o o 777 rf 1 2 2 S 3 4 0 0 1 An isomorphism changes only the names of the elements of the universe All the symbols of Z are preserved De nition 116 Let AB 6 STRUCE We say that A and B are elementarl ly equivalent A E 8 iff for all sentences 90 6 132 A l 90 ltgt B l 90 Q Proposition 117 IfA quotE B then A E B 20
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'