First-Order Logic - BCMI Homepage一阶逻辑BCMI主页.pptVIP

* * Chapter 8 First-Order Logic Outline Why FOL? Syntax and semantics of FOL Using FOL Wumpus world in FOL Knowledge engineering in FOL Pros and cons of propositional logic Propositional logic is declarative Propositional logic allows partial/disjunctive/negated information (unlike most data structures and databases) Propositional logic is compositional: meaning of B1,1 ? P1,2 is derived from meaning of B1,1 and of P1,2 Meaning in propositional logic is context-independent (unlike natural language, where meaning depends on context) Propositional logic has very limited expressive power (unlike natural language) E.g., cannot say pits cause breezes in adjacent squares“ except by writing one sentence for each square The Others First-order logic Whereas propositional logic assumes the world contains facts, first-order logic (like natural language) assumes the world contains Objects: people, houses, numbers, colors, baseball games, wars, … Relations: red, round, prime, brother of, bigger than, part of, comes between, … Functions: father of, best friend, one more than, plus, … Syntax of FOL: Basic elements Constants KingJohn, 2, NUS,... Predicates Brother, ,... Functions Sqrt, LeftLegOf,... Variables x, y, a, b,... Connectives ?, ?, ?, ?, ? Equality = Quantifiers ?, ? Atomic sentences Atomic sentence = predicate (term1,...,termn) or term1 = term2 Term = function (term1,...,termn) or constant or variable E.g., Brother(KingJohn,RichardTheLionheart) (Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn))) Complex sentences Complex sentences are made from atomic sentences using connectives ?S, S1 ? S2, S1 ? S2, S1 ? S2, S1 ? S2, E.g. Sibling(KingJohn,Richard) ? Sibling(Richard,KingJohn) (1,2) ? ≤ (1,2) (1,2) ? ? (1,2) Syntax of FOL Syntax of Propositional Logic Truth in first-order logic Sentences are true with respect to a model and an interpretation Model contains objects (domain elements) and relations among them Interpretati