First Order LogicBeyond Propositional logic • Propositional logic not expressive enough – In Wumpus world we needed to explicitly write every case of Breeze & Pit relation – Facts = propositions – “All squares next to pits are breezy” • “Regular” programming languages mix facts (data) and procedures (algorithms) – World[2,2]=Pit – Cannot deduce/compose facts automatically – Declarative vs. ProceduralNatural Language • Natural language probably not used for representation – Used for communication – “Look!”First-Order Logic • Idea: – Don’t treat propositions as “atomic” entities. • First-Order Logic: – Objects: cs4701, fred, ph219, emptylist … – Relations/Predicates: is_Man(fred), Located(cs4701, ph219), is_kind_of(apple, fruit)… • Note: Relations typically correspond to verbs – Functions: Best_friend(), beginning_of() : Returns object(s) – Connectives: , , , ,  – Quantifiers: • Universal: x: ( is_Man(x) ) is_Mortal(x) ) • Existential: y: ( is_Father(y, fred) )Predicates • In traditional grammar, a predicate is one of the two main parts of a sentence the other being the subject, which the predicate modifies. • "John is yellow" John acts as the subject, and is yellow acts as the predicate. • The predicate is much like a verb phrase. • In linguistic semantics a predicate is an expression that can be true of something WikipediaTypes of formal mathematical logic • Propositional logic – Propositions are interpreted as true or false – Infer truth of new propositions • First order logic – Contains predicates, quantifiers and variables • E.g. Philosopher(a)  Scholar(a) • x, King(x)  Greedy (x)  Evil (x) – Variables range over individuals (domain of discourse) • Second order logic – Quantify over predicates and over sets of variablesOther logics • Temporal logic • Truths and relationships change and depend on time • Fuzzy logic – Uncertainty, contradictionsWumpus • Squares neighboring the wumpus are smelly – Objects: Wumpus, squares – Property: Smelly – Relation: neighboring • Evil king john rules England in 1200 – Objects: John, England, 1200 – Property: evil, king – Relation: ruledExample: Representing Facts in First-Order Logic 1. Lucy* is a professor 2. All professors are people. 3. John is the dean. 4. Deans are professors. 5. All professors consider the dean a friend or don’t know him. 6. Everyone is a friend of someone. 7. People only criticize people that are not their friends. 8. Lucy criticized John . * Name changed for privacy reasons.Same example, more formally Knowledge base: • is-prof(lucy) •  x ( is-prof(x) → is-person(x) ) • is-dean(John) •  x (is-dean(x)  is-prof(x)) •  x ( y ( is-prof(x)  is-dean(y) → is-friend-of(y,x)  knows(x, y) ) ) •  x ( y ( is-friend-of (y, x) ) ) •  x ( y (is-person(x)  is-person(y)  criticize (x,y) → is-friend-of (y,x))) • criticize(lucy, John ) Question: Is John no friend of Lucy? is-friend-of(John ,lucy)How the machine “sees” it: Knowledge base: • P1(A) •  x (P1(x) → P3(x) ) • P4(B) •  x (P4(x)  P1(x)) •  x ( y (P1(x)  P4(y) → P2(y,x)  P5(x, y) ) ) •  x ( y (P2(y, x) ) ) •  x ( y (P3 (x)  P3(y)  P6(x,y) → P2(y,x))) • P6(A, B ) Question: P2(B ,A)?Knowledge Engineering 1. Identify the task. 2. Assemble the relevant knowledge. 3. Decide on a vocabulary of predicates, functions, and constants. 4. Encode general knowledge about the domain. 5. Encode a description of the specific problem instance. 6. Pose queries to the inference procedure and get answers. 7. Debug the knowledge base.Knowledge Engineering 1. All professors are people. 2. Deans are professors. 3. All professors consider the dean a friend or don’t know him. 4. Everyone is a friend of someone. 5. People only criticize people that are not their friends. 6. Lucy* is a professor 7. John is the dean. 8. Lucy criticized John. 9. Is John a friend of Lucy’s? General Knowledge Specific problem QueryInference Procedures: Theoretical Results • There exist complete and sound proof procedures for propositional and FOL. – Propositional logic • Use the definition of entailment directly. Proof procedure is exponential in n, the number of symbols. • In practice, can be much faster… • Polynomial-time inference procedure exists when KB is expressed as Horn clauses: where the Pi and Q are non-negated atoms. – First-Order logic • Godel’s completeness theorem showed that a proof procedure exists… • But none was demonstrated until Robinson’s 1965 resolution algorithm. • Entailment in first-order logic is semidecidable.Types of inference • Reduction to propositional logic – Then use propositional logic inference, e.g. enumeration, chaining • Manipulate rules directlyUniversal Instantiation • x, King(x)  Greedy (x)  Evil (x) – King(John)  Greedy (John)  Evil (John) – King(Richard)  Greedy (Richard)  Evil (Richard) – King(Father(John))  Greedy (Father(John))  Evil (Father(John)) • Enumerate all possibilities – All must be trueExistential Instantiation •  x, Crown(x)  OnHead(x, John) – Crown (C)  OnHead(C, John) – Provided C is not mentioned anywhere else • Instantiate the one possibility – One must be true – Skolem Constant (skolemization)Resolution Rule of Inference General Rule: Note: Eij can be negated. Example: “Resolvent”Algorithm: Resolution Proof • Negate the original theorem to be proved, and add the result to the knowledge base. • Bring knowledge base into conjunctive normal form (CNF) – CNF: conjunctions of disjunctions – Each disjunction is called a clause. • Repeat until there is no resolvable pair of clauses: – Find resolvable clauses and resolve them. – Add the results of resolution to the knowledge base. – If NIL (empty clause) is produced, stop and report that the (original) theorem is true. • Report that the (original) theorem is false.Resolution Example: Propositional Logic • To prove: P • Transform Knowledge Base into CNF • Proof 1. P  Q Sentence 1 2. Q  R Sentence 2 3. R Sentence 3 4. P Assume opposite 5. Q Resolve 4 and 1 6. R Resolve 5 and 2 7. nil Resolve 6 with 3 8.