Limitations of First-Order LogicDefault ReasoningDefault LogicNon-monotonic LogicPrologTruth-Maintenance SystemsFramesSemantics NetsPowerPoint PresentationDescription LogicsExample Syntax of CLASSICSlide 12Slide 13Slide 14OWL – implementation of DL for WebSlide 16Slide 17ProbabilityFuzzy LogicSlide 20Limitations of First-Order Logic•higher-order logics – quantify over predicates–define “reflexive” properties: all properties P for which x P(x,x)–induction: if a property P(n) is true for n=0, and if it is true for n then it is true for n+1, then is holds n•modal logics – contain a sentence as an “arg”–believes(john,raining v snowing)–possibly(PQ)–eventually( x corrupt_packet(x)  in_queue(x))–epistemic/modal/temporal logics add special operators to syntax, (PQ); nested P, PQ–semantics based on “possible worlds” and their relationships, not just modelsDefault Reasoning•FOL also bad at handling default information–leads to inconsistencyx bird(X)  flies(x)–bird(tweety), bird(opus), flies(opus), unsatisfiable!•excluded middle–sentences must be either True or False, but what if we want to asserting things with different strengths or degrees of belief?–“most people who have a stomach ache have indigestion.”x feel_pain(x,stomach(x))indigestion(x)? x feel_pain(x,stomach(x))  indigestion(x)?•80% of people?–“interest rates are going up next year” •strong but not certain belief – what about consequences?Default Logic•bird(X): flies(X) / flies(X)–if bird(X) is true and it is not inconsistent to believe flies(X), then infer flies(X)–antecedents : justification / consequent•semantics – based on maximal extensions–an extension is a set of additional consequences (ground literals) based on default rules–fixed-point semantics, repeat till nothing more to add–Th╞ P iff P is in all maximal extensions•there could be multiple extensions–republican(X) : pacifist(X) / pacifist(X) –quaker(X) : pacifist(X) / pacifist(X)–republican(nixon)  quaker(nixon)–extensions: { pacifist(nixon) } , { pacifist(nixon) }Non-monotonic Logic•a logic is monotonic if every thing that is entailed by a KB is entailed by a superset of the KB:–KB╞   KB╞ –exceptions to default conclusions make a logic non-monotonic –previously assumed flies(opus) until told flies(opus)•circumscription–bird(X) abnormal(X)  flies(X)–bird(tweety), bird(opus), flies(opus)–this KB allows flies(tweety), but is not inconsistent if assume abnormal(opus)–circumscription: process of finding minimal set of abnormal predicates necessary to make KB consistentProlog•negation-as-failure enables defaults–flies(X) :- bird(X),not penguin(X).–bird(tweety). bird(opus). penguin(opus).–tweety flies because he isn’t declared a penguin–if we also asserted penguin(tweety)...non-monotonic–advantage: compact, what is false can be left unsaid–disadvantage: no way to represent “unknown”•Closed-world assumption (CWA)–everything that is true is asserted; everything unsaid is assumed to be false–similar to database queries; Datalog: tuples+rules•minimal models – only believe what you have to–smallest set of tuples that satisfies KBTruth-Maintenance Systems•another approach to defaults – retract assumptions when necessary•JTMS – keep track of justifications for inferences–if previously concluded R from {PQR,P} (assuming Q) and then R is asserted, must retract R and assert Q–keep a graph where nodes are literals and (hyper-)edges are rules; mark as good/no-good or in/out; retain graph structure•ATMS –track consistent sets of assumptions•practical – many agents and intelligent systems get updated info and only want to modify their beliefs rather than re-derive everything•generalizes to belief update (minimal change to KB)Frames•represent taxonomies, object properties (slots)defclass animaldefclass animal: subclass animalslot warmBlooded: Trueslot externalCoating: furdefclass dog: subclass mammal slot movement: runs slot vocalization: barksslot numberOfLegs: 4defclass bird: subclass animal slot movement: flies slot externalCoating: feathers slot numberOfLegs: 2 slot vocalization: chirpsdefinstance snoopy: instanceOf dogdefinstance opus: instanceOf bird slot movement: waddles•inheritance – to answer a query, check most specific node; if not defined, go to parent...Semantics Nets•graphical representation of knowledge•nodes represent classes or instances•edges represent (binary) relations/properties–“isa” links – special type, or “member” and “subset”•answer queries by following edges•how to represent negation? universal quantifiers?•Conceptual graphs (John Sowa)“John gave Mary a book about frogs.” person isa isajohn mary actor recipient event1 object B1 isa topic book frogsisaGivingEventDescription Logics•natural evolution of frames•define –concepts (classes)–roles (binary relations from class to class)–restrictions (cardinality/type constraints)•correspond to “tractable” subsets of FOL–limited expressiveness makes many DLs decidable–main restriction is: can’t express negation and disjunction•examples of major ontologies in DLs:–GALEN – medical records–FMA – Foundational Model of Anatomy–Dublin Core: media (author, publisher, type, year...)–business processes, e-commerce...Example Syntax of CLASSIC•Concept  Thing | ConceptName | And(Concept,...) | All(RoleName,Concept) | AtLeast(Int,RoleName) | AtMost(Int,RoleName) | Fills(RoleName,Individual) | SameAs(RoleName,RoleName) | OneOf(Individual...)•Batchelor = And(Unmarried,Adult,Male)•Mother = And(Female,AtLeast(1,Child))•older systems: CLASSIC, KL-ONE, LOOM•more recent logics: ALC, SHIQ, SHOIN...•other DLs include syntax for:–intersection, union, and complement of classes –inverse roles: payor(.,.) = payee(.,.)– –disjoint subsets, exhaustive subsets•thing = complete(animal,vegetable,mineral)–role restrictionsR.C: student   enrolled.courseR.C: graduate  passed.requiredCourse–cardinality restrictions•mother  female  (≥1 child)•dog  animal  (= 4 legOf)  barks•DL queries –consistency of KB –satisfiability of a concept