### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# The Renaissance and the Reformation HISTORY C157

GPA 3.81

### View Full Document

## 48

## 0

## Popular in Course

## Popular in History

This 8 page Class Notes was uploaded by Garrett Harber on Thursday October 22, 2015. The Class Notes belongs to HISTORY C157 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 48 views. For similar materials see /class/226550/history-c157-university-of-california-berkeley in History at University of California - Berkeley.

## Reviews for The Renaissance and the Reformation

### 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: 10/22/15

lNFERENCE IN FIRSTORDER LOGIC CHAPTER 9 My II Outline 0 Reducing fll SPOl dSl inference to propositional inference 0 Un fication O Generalized Modus Ponens 0 Forward and backward chaining 0 Logic programming 0 Resolution My 2 A brief history of reasoning 45080 Stoics propositional logic inference maybe 32280 Aristotle syllogisms inference rules quantifiers 1565 Cardano probability theory propositional logic uncertainty 1847 oole propositional logic again 1879 irsteorder logic 1922 Wittgenstein proof by truth tables 1930 Godel 3 complete algorithm for FOL 1930 Herbrand complete algorithm for FOL reduce to propositional 1931 Godel 13 com lete algorithm for arithme ic 1960 DavisPutnam practical algorithm for propositional logic 1965 Robinson practical algorithm for FOLil SSOlUthH ll Universal instantiation UI Every instantiation of a universally quantified sentence is entailed by it VU oz Suasmug39 a for any variable U and ground term 37 E g V1 Kingz A Greedyz gt EUiZz yields KingUohn A GreedyUohn gt EUiZUohn KingRichard A GreedyRichard gt EUiZRichard KingFatherJohn A GreedyFatherJohn gt EUiZFatherJohn ll Existential instantiation El For any sentence oz variable U and constant symbol k that does not appear elsewhere in the knowledge base U at SUBSTUka E g 3 z Crownz A OnHeadz John yields Crown01 A OnHeadCh John provided 01 is a new constant symbol called a Skolem constant Another example from 3 z dzydy 1y we obtain deydyey provided 5 is a new constant symbol 39 39 39 39 A L39 39 contd U can be applied several times to add new sentences the new KB is logically equivalent to the old El can be applied once to replace the existential sentence e new KB is not equivalent to the ol but is satisfiable iff the old KB was satisfiable II n 39 to quot39 inference Suppose the KB contawnsJust the toHowwng V1 Kingz A Greedyz gt Evilz KingJohn Greedy John BrotherRiehard John Instantwatwng the unwversat sentence wn all possible ways we have KingJohn A GreedyJohn gt EUiZJohn KingRiehardAGreedyRichard gt EUiZRiehard Greedy John BrotherRiehard John The new KB ws proposwtwonahzed proposwtwon symbots are KingJohn GreedyJohn EUiZJohnKingRiehard etc II n 39 contd Ctawm a ground sentence ws entawted by new KB tt entawted by orwgwnat KB Ctawm every FOL KB can be proposwtwonathed so as to preserve entawtment Idea proposwtwonahze KB and query appty resotutwon return resutt Probtem wwth tunctwon symbots there are wntwnwtety many ground terms e g FatherFatherFatherJohn Theorem Herbrand 1930 It a sentence or ws entawted by an FOL KB wt ws entawted by a nite subset ot the proposwtwonat KB Idea Forn 0 to 00 do create a proposwtwonat KB by wnstantwatwng wwth depthen terms see wt or ws entawted by thws K Probtem works wt or ws entawted toops wt or ws not entawted Theorem Turwng 1936 Church 1936 entawtment wn FOL ws semwdecwdabte mm L I L Problems with pro Proposwtwonahzatwon seems to generate tots ot wrretevant sentences E g trom V1 Kingz A Greedyz gt Evilz KingJohn Vy Greedyy BrotherRiehard John wt seems obvwous that EUiZJohn but proposwtwonahzatwon produces tots ot tacts such as GreedyRichard that are wrretevant thh p keary predwcates and n constants there are p nquot wnstantwatwons thh tunctwon symbots wt gets nuch much worse39 Uni cation We can get the wnterence wmmedwatety wt we can twnd a substwtutwon 9 such that Kingz and Greedyz match KingJohn and Greedyy 9 zJohnyJohn works UNIV056 9 wt a9 9 20 IL 9 KnowsJohnz KnowsJohnJane KnowsJohnz Knows OJ KnowsJohnz KnowsyMotherg KnowsJohnz KnowszOJ My no N Uni cation We can get the wnterence wmmedwatety wt we can twnd a substwtutwon 9 such that Kingz and Greedyz match KingJohn and Greedyy 9 zJohnyJohn works UNIV056 9 wt a9 9 19 lg l9 KnowsJohnz KnowsJohnJane zJane KnowsJohnz KnowsyOJ KnowsJohnz KnowsyMotherg KnowsJohnz KnowszOJ M n H Uni cation We can get the wnterence wmmedwatety wt we can twnd a substwtutwon 9 such that Kingz and Greedyz match KingJohn and Greedyy 9 zJohnyJohn works UNIV056 9 wt a9 9 p q 9 KnowsJohnzlKnowsJohnJane zJane KnowsJohnz KnowsyOJ zOJyJohn KnowsJohnz KnowsyMothery KnowsJohnz Knowsz J Uni cation We can get the inference immediately if we can find a substitution 9 such that Km z and Greedyz match KingUohn and Greedyy 9 zJohn John worllts UNIFYai 9 if a9 9 p q 9 KnowonhmzlKnowonthane zJane Knowonhmz Knowsy MollyJohn Knowonhmz KnowsyMotherg yJohn Mother ohn Knowonhmz KnowszOJ Uni cation We can get the inference immediately if we can find a substitution 9 such that Km z and Greedyz match KingUohn and Greedyy 9 zJohn John worllts UNIFYai 9 if a9 9 p q 9 Knowonth Knowonthane zJane Knowonhmz KnowsyOJ zOJwJohn Knowonhmz KnowsyMotherg yJohn Mother ohn Knowonhmz KnowszOJ fa39l Standardizing apart eliminates overlap of variables e g Knows217OJ M9 is ll Generalized Modus Ponens GMP A AMA V p l p2 p p m pn q wherep9p19forallz q 171 is KingUohn 171 is Km z 172 is Greedyy 172 is Greedyz 9 is zJohn John q is Evilz q9 is EUiZUohn GMP used With KB of definite clauses exactly one positive literal All variables assumed universally quantified II C39 of GMP II Need to show that p18 m M pwvwm 49 provided that p9p19 for all 139 Lemma For any definite clause 17 we have p l p9 by U 1p1AHApngtq lp1AHApngtq9P19AvvApn9gtQ9 2 p18 in pnFMva pn lp19AApn9 3 From 1 and 2 q9 follows by ordinary Modus Ponens Example knowledge base The law says that it is a crime for an American to sell weapons to hostile nations The country Nono an enemy of America has some missiles and all of its missiles were sold to it by Colonel West who is American Prove that Col West is a criminal M9 w Example knowledge base contd H it is a crime for an American to sell weapons to hostile nations M9 in Example knowledge base contd wt ws a crwme for an Amerwcan to sell weapons to lwostwle natwons American1AWeaponyASeZl51y 2AHostiZez gt Criminal1 Nono has some mwsswles Example knowledge base contd wt ws a crwme for an Amerwcan to sell weapons to hostwle natwons American1AWeaponyASeZl51y 2AHostiZez gt Criminal1 mwsswles we 31 OwnsNono1 A Missile1 OwnsNonoM1 and MissileM1 all of wts mwsswles were sold to wt by Colonel West Example knowledge base contd wt ws a crwme for an Amerwcan to sell weapons to hostwle natwons American1AWeaponyASeZl51y 2AHostiZez gt Criminal1 ono H has some mwsswles we 31 OwnsNono1 A Missile1 OwnsNonoM1 and MissileM1 all of wts mwsswles were sold to wt by Colonel West V1 Missile1 A OwnsNltmo1 gt SellsWest1Nono Mwsswles are weapons Example knowledge base contd wt ws a crwme for an Amerwcan to sell weapons to hostwle natwons American1AWeaponyASeZl51y 2AHostiZez gt Criminal1 Nono W has some mwsswles we 31 OwnsNono1 A Missile1 OwnsNonoM1 and MissileM1 all of wts mwsswles were sold to wt by Colonel West V1 Missile1 A OwnsNltmo1 gt SellsWest1Nono Mwsswles are weapons Missile1 gt Weapon1 An enemy of Amerwca counts as hostwle Example knowledge base contd wt ws a crwme for an Amerwcan to sell weapons to hostwle natwons American1AWeaponyASeZl51y 2AHostiZez gt Criminal1 mwsswles we 31 OwnsNono1 A Missile1 OwnsNonoM1 and MissileM1 all of wts mwsswles were sold to wt by Colonel West V1 Missile1 A OwnsNltmo1 gt SellsWest1Nono Mwsswles are wea ons Missile1 gt Weapon1 An enemy of Amerwca counts as hostwle Enemy1America gt Hostile1 West who ws Amerwcan AmericanWest The country Nono an enemy of Amerwca m menuNona America Forward chaining algorithm function FOLVFCVASKKBa returns a substwtutwon or fake repeat until new l5 empty newe for each sentence 7 in KB do Pt A A pl q ESTANDARDIZEVAPARTO for each 9 such that p A A 9 p A A pm tr nmepgp tn KB aw e SUBST9 q if q l5 not a renamwng of a sentence already m KB or new then do a d ql to new rte Ummql a if l5 not far then return add new to KB return fehe II Forward chaining proof Emmymmmm Forward chaining proof maximum Emmymammm Forward chaining proof CrtmtmlWest Seuxiwmwm AmericaMWest Mtxxnle i Emmymanamma II Properties of forward chaining Sound and compiete tor i SPOi dei detinite ciauses proof simiiar to propositionai proo Dataiog tirsteorder detinite ciauses no functions e g crime KB FC terminates tor Dataiog in poiy iterations at most 17 nquot iiterais May not terminate in generai it at is not entaiied This is unavoidabie entaiiment With detinite ciauses is semidecidabie Ef ciency of forward chaining Simpie observation no need to match a ruie on iteration k if a premise wasn39t added on iteration k 7 gt match each ruie whose premise contains a newiy added iiterai Matching itseit can be expensive Database indexing aHows 01 retrievai of known facts eg query Missilez retrieves MissileM1 Matching conjunctive premises against known facts is NPehard Forward chaining is Wideiy used in deductive databases Hard matching example Dij wamt A Di wa a A i mt qDi nt so A o ij qmsw A Dij q a A Di msww A Di nsw a A Dij msa gt ColorabZeO o Di RedBZue Di RedGreen Dij Green Red Dij Green Blue Dij BZugRed Di BZugGreen ColorabZeO is inferred ifF the CSP has a soiution CSPs inciude 3SAT as a speciai case hence matching is NPehard GU II Backward chaining algorithm function FOLVBCVASKKBgoals9 returns a set of substltutmns inputs KB a knowledge base goals a hst of conjuncts tormmg a query 9 already apphed 9 the current substltutlon lnltlally the empty substltutlon local variables mumE75 a set of substltutlons lnltlally empty if goals ls empty then return 9 qeSrJesrwrresngmzs for each sentence 7 in where STANDARDleeAPARTO p pl q and 9 e Ummq q succeeds nemgrmbe A panEs goals ame7sltFOLeBCeAsKKB nan4011b COMPOSE9 9 u mums return auraE75 Backward chaining example We a Backward chaining example CnmmalWVest II Backward chaining example H Backward chaining example rWen H Backward chaining example rWen yMI CnmmalWVest H Backward chaining example xWest yMI zNana H Backward chaining example xWest yMI zNana H i Manley HMtxxtle i i OwnxNarlaM1 i EnemyWOKOMErtca i ltyM1gt gt H H M9 an H Properties of backward chaining Depthefirst recursive proof search space is iinear in size of proof Incompiete due to infinite ioo s fix by checking current goai against every goai on stack Inefficient due to repeated subgoais both success and faiiure ix using caching of previous resuits extra space39 Wideiy used Without improvements39 for iogic programming M9 w Logic p 39 Sound bite computation as inference on iogicai KBs Logic programming Ordinary programming 1 Identify probiem Identify probiem 2 Assembie information Assembie information 3 Tea brea Figure out soiution 4 Encode information in KB Program soiution 5 Encode probiem instance as facts Encode probiem instance as data 6 Ask queries Appiy program to data 7 Find faise facts Debug procedurai errors Shouid be easier to debug CapitaKNewYorgUS than 1 1 1 239 Prolog systems Basis backward chaining With Horn ciauses beHs KL whisties Wideiy used in Europe Japan basis of 5th Generation project Compiiation techniques gt approaching a biHion LIPS Program set of ciauses head literal literal Cr1m1n31X amerlcanX weaponY sellsXYZ host11eZ Efficient unification by open codin Efficient retrievai of matching ciauses by direct iinking Depthefirst ieftetoeright backward chaining Buiitein predicates for arithmetic etc eg X is YZ3 Ciosedeworid assumption negation as faiiurequot eg given aliveltXgt not deadltX aliveltjoegt succeeds if deadltjoegt faiis Prolog examples Depthefirst search from a start state X dfsltXgt goalltX dfsX successorltXSdfsS No need to ioop over S successor succeeds for each Appending two iists to produce a third appendltU YYgtr appendlt XiL Y Xi 2 appendltLYZ query appendltAB 12 397 answers A B12 A1 BZDJ A1 2 B U I n 39 brief summary n 39 proof de nite clauses FuH rsteorder verswon awnmmm V Weqvow V ampllxyz V jammy V ommm a CnmmnlWe ZtVnV k mIVan n 31Vmw vzmvvszmIVVm71Vm71Van9 where UNIFYZU m79 iiWWW VT WWW ngswwmm VTWW WWW VWme a Weapon V w ampIIW fz V a Homlqz For exampe WWI V mm Rich1 V Unhappy1 WW Vwmmm szwmm WWVMIU V mm Rich fzzgpy m WWW V jammy m V jyomemm wwth 9 1Ken a Mmmm Via yummy WWW MW Appy resohmon steps to CNFKB A at compete for FOL Mmymonomenm 39 to CNF Everyone who eves aH anwmas s oved by someone y Animaly gt Loues13 gt 33 Lovesy1 1 Ehmwnate bwcondmonab and mphcamm V1 Vy AnimaZg V LOU55Zy V 33 Lovesy1 2 Move wnwards 3V1p E31 3p 331 EV1 3 V1 3 y 33Am39maly V Loues1y V 3 y Lovesy1 V1 3 y AnimaZg A 3L0U551y V 3 y Lovesy1 V1 3 y Animaly A Loues1g V 3 y Louesy1 II Conversion to CNF contd 3 Standardwze vanabes each quanh er shoud use a dwfferent one V1 3 y Animaly A Loues1g V 3 2 Lovesz1 4 Skn emxze a more genera form of esttenhe nstanhatwon Each esttentwe vanabe s repaced by a Skt em functwon of the endoswng unwersaHy quantw ed vanabes V1 AnimaZF1 A LoUes1 V LovesG1 1 5 Drop unwersa quanhhers AnimaZF1 A LoUes1 V LOU55GZZ 6 Dwstnbute A over V AnimaZF1 V LovesG11 A LoUes1 V LovesG11

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.