Knowledge Representation and Reasoning PDF

ARTIFICIAL INTELLIGENCE Intelligence : AI deals with machines that have intelligent traits ↳ This often intersects with simulation human cognitive attributes...

ARTIFICIAL INTELLIGENCE Intelligence : AI deals with machines that have intelligent traits ↳ This often intersects with simulation human cognitive attributes of There are two types of thinking : System # (fast thinking) (regeexes automatic it is "hard-wired" system · · a subconscia that immediately reacts to · · intuitive stimuli · Used for simple tasks and Pareidolia seeing : patterns but can be fooled , faces in random Creation · and modification can be objects or patterns expensive and takes effort Many popular DI apps are based on this : writing text - image generation and classification - - optimization - winning games -D This is MACHINE LEARNING detecting diseases Core deep learning ( - ML is useful bit has limitations and drawbacks -lack of interpretability - "hallucinations" (always produces an answer) -static (can't hard to update a me - trained on DATA , but data is not Knowledge I gustgivesanopin System I lacks the ability to REFINE/VERIFY/ CORRECT its imput or output (perception/ generation) System 2 (slow thinking) (purpose) · effortive this refers to SYMBOLIC Al conscious it manipulates extract symbols to · · logical consequences and make decisions · ↳ it (valid performa REASONINGS KRR is subject inferences) a , deduces things from that studies data/knowledge Symbolic AI only answers what is certain · It features varias advantages : interpretability - -guaranteed correctiess ambiguity > no - flexibility and modularity (knowledge can be updated easily -"Lumblewess" it is not required to answer with - something Logic is the language to express and manipulate with their Knowledge : it associates expressions meaning It is clear and not subject to interpretable answers It is ·. all abat correctness and guarantees To solve a reasoning problem , all conditions must be satisfied > Use - of PROPOSITIONAL LOGIC We do symbolic manipulation of constraints ↳ to them understandable we simplify objects make for the algorithm (e g.. Dania on Eric =- PVq) PL expressivity however is limited and caro properly represent all kinds of knowledge in real life applications PL however to different , , gives rise many repres sentational languages - different problems require different treatments ↳ for practical reasons it is impossible , to rely on one single "Unified" language It you the tools to understand how and when to gives use KR effectively , withat adding more features than necessary. History of Knowledge representation Humanity is characterised by a history of KR to pass knowledge to future generations however meanings , get altered on last as time passes , making knowledge static unable , to evolve (due to misinterpretation) The goal of KR is to manage knowledge as it is without originally intended , language ambiguities ↳ The first attempt at making a language of valid inferences by Aristole his syllogisms was : could handle knowledge abot classes Syllogisms extract consequences from sentences The premises derive twe conclusions ↳ this system had varias limitations - only two classes at a time - no disjuctions - no relationships and complex properties no evolution util Boolean Algebra 2000 years bes functional manipulation of sentences which may be the or false propositional > - logic clater extended to predicate logic Ccan't cover propositional logic is too inexpensive everything ( · predicate logic is too complex · many languages were bor to find the correct balance between expressivity and practicality One of the first approaches of AI was logical derivation > an intelligent system had to understand - what is happening and possibly infer (deduce) implicit information and actions To obtain such artificial agent through KR , we need : ① a machine readable language for KR ② a formal inference mechanism ③ a query language to interface with the machine First early attempts : · Semantic networks (graphs with connecting properties) No formal semantics > - does not satisfy preliminary gool of knowledge transmission · Frames (blocks with open windows to fill in properties) seroformalsemantieas opentointerpretat e se clear formal semantics syntax and ↳ different properties for different applications Description logics are family of KR a languages developed to find the best tradeogg > - between expressivity and practicality example : the semantic web find a way to let machines inderstand web pages as we do (inderstanding of natural language) solution : make machine-readable amotations ↳ the determined ontology is from DLs Knowledge graphs : any graph that carries information (each company gives this word a different meaning and application Sadly , reality is not as logical as we want it to be > - handling real knowledge is hand and requires ad -hoc solutions this however , , makes knowledge representation and reasoring a very fuitful and success fue field  BOOLEAN ALGEBRA BA is a formalism for manipulating truth volves Clogical operators) > - true (1) and fase (0) conjunction , disjuction , negation · Conjunction x (AND) Cother operators true both values trae exists these iff are : are the elementary · Disjuction v (OR) ones) true at least one is tre (both tool if value · Negation ~(NOT) negation of a trth makes its value false You can use operators to compute the value of a complex expression > you can substitute - constants (0 a) with variables (p a) , , Atomic state propositions one specific fact on property. Formulas are combinations of propositions that can be studied via tuth valves. Logic is a language > - it has syntax and semantics Operation precedence - : v The truth of formules is determined its value by individual components Valuation, an assignment of tuth value to each variable valuations determine the truth value of the whole formula Tautology is · a · Contradiction is 0 Formulas can have equivalento = two formules have the same truth are equivalent if they table T & 1 Properties · YxT = e neutral element (1) · ev = C · evT = T absorbing element (0) · ex1 = t Fundamental equivalences DeMorgan theoreem & Distribution. & Involution. KNOWLEDGE AS RULES CLAUSES are disiuctions with at least one negation (v) · a horn clause is a classe with at most one positive variable equivalent representation : 7 x vx... ViXm vy = allx are tre then must (x if , y , XXz... xxm) = y be the as well a simple horn case is called a fact consider X = XV1 = XV 11 becomes T= X , if the (tantology) is the , then X must be the if a form clause lacks a positive litene , it is equivalent to a constraint : the variables cannot be all twe simultaneously 74. VTeV... Vixm = x, Via... VI = (X. XX2x... XXm) > = + (contradition) Consequences motation (rules) a knowledge base is a (finite) set of rules ↳ as knowledge , we consider them to be true A knowledge base is a set of ferlas C.... Om. We consider them the otherwise , they have no sense) ↓ is a the consequence if Ya... Ym - TV is twe Jaka , a tautology) Notation : KF7 · Kentaies & y is a consequence of K · K = is 4 a toutology Unit resolution is a simplification method of knowledge It uses. what is already tre to simplify the solution (truth propagation) X Xn if each x is tre , the..... Y to be the y is gueranteed If you have previs knowledge that on object that is tre, you can use fact to simplify base your knowledge ⑪ If you have a fact where X is guaranteed to be the ② you check subsequent facts and remove x from the formula : it will not impact the final result REDUX KB : a KB with simplified facts but that outputs the same result as the original Statement example : you cen simplify redut / & any consequence formla that has prerequi * sites that have previously been proved as neces. sarily the Unit resolution is sand (it states facts that are consequences of other facts) ↳ it only returns consequences This fact is a of something : consequence it has no false positive/negative · · it does NOT complete resoltiol give a empty - robe it shows I : a contrediction and is impost sible to satisfy (inconsistent knowledge base) T = I is a contradition is inconsistent iff # KB K a I contains the its redux empty rale Since unit resolution is sand , satisfying a lB must satisfy its redux - if redux camet be sa tisfied , then the original KB is inconsistent and has no solution Consequence of inconsistency : iff KEY , then I is a consequence of K every valuation that satisfies K also satisfies. , ↳ if no valuation satisfies K it , is inconsistent and the consequence can't be satisfied too · if K is consistent , mit resortion is complete with respect to facts M · if x is not a fact in K , then it is not a consequence in K (redux) ↳ the process of unit resolution extracts all land only) the facts entailed by K In a complex implicatio n... ⑨ if X In is tree then..... , y k + is tre y4X..... Ym ② K has to be the the relevant valuations are those that satisfy K and all X..... Im COMPUTATIONAL COMPLEXITY : the number of operations to an get answer (how long will it take with the best possible regantem ?) · worst case : each variable has to be removed from each rula if K has u ales and m variables , we need (m. r) steps Properties : rules define asimple KR language useful for expressing base properties > easy to- exl-nact consequences. it has limitations : as it is inexpressive , it camat & define relationships between objects ↳ use of Predicate Logic RULES WITH PREDICATES Predicate logic is abot giving tre/false attributes to objects * the object Mammal (Dumbo ↳ the property We want to have placeholders for constants if we have information abot a relation , but not about its object. to give X a meaning , we have to give it a scope · 74 parent(ava X). , - at least one constant makes it the ("exists") ·X parent lama X) => constant makes it true. , any L'every") Syntax of predicate logic ① terms 8 > - a "predicate" is the main ⑨ building block P(t) LITERAL predicate its negation · : a or PREDICATE HORN CLAUSE : a disjunction of literals with at most one positive (predicate rule) ⑨ omeTredicate predicates sevenal Universo quantification of a variable a predicate : or property holds for all possible values of That variable within the domain of discourse (the "universe") grandparent (x y) , < parent (x z) parent , , (z y), "z" that this rule true, if we can find a makes then it's tre regardless of the value of X and y Predicates represent : properties of (umany) (manmae) objects relationships between objects (bimany) (parent of · It to is a must specify which objects satisfy which properties and relations -S interpretation based semantics An interpretation consists of: · a domain /F I are all objects of interest I which objects an interpretation function states. have a property SF objects affected by the same D XF. function other are related with each Egraphical representation] · constant : object · unary predicate : class binary predicate relation · : · at EXF if I have a constant , that constant is contained and expressed in the domain Plumany) DFXF · · P(bimany) DFCX, relation between objects the of same set. AF( +, y , z} labeleed graph 3 * ((xy) (xz) (xx) = · y = x ,... , a b graphical representation & to from picture relations easily a human por PREDICATE RULE : a predicate clause P(F) Q (F)... - Qu(Fi) such that all variables in PCE) appear body in the ↳ a predicate knowledge base is a finite set of predicate rules · Variables that appear or the left its appear an the right Variables that appear the CouLD appear on right · or the left , but it's not mandatory When is the PR trive ? it is when the body is tre ↳ we only case abat interpretations that make it treve Formally : If I can find variables that make it true, then all of this is true The interpretation I satisfies the rule I makes iff the body true /via substitution) , then it also makes the head true moder I is a model of > - the KB K interpretations iff it · - : satisfies all rules in K (entailment) bäg FAISE TRE/FALSE body > - head > - makes body trae, but head folse not : entailment a model We consider as entailments only predicates that have no variables (ground predicates) ↳ "emtails" (involved in ) if there is nothing in the the head must body , contain only constats -minimal representation of all possible models KNOWLEDGE PROPAGATION by building : a minimal representation (in terms of restrictions) we can propagate or knowledge > canonical inter - pretation. CI can be queried to decide entailments Construction of Camonical Interpretation KB have bu model any can a CF CI is not necessarily a - , built from : an empty interpretation (graph) = by adding only the necessary ingredients ① create all relevant modes (the constants) ② add facts (arrows batters) , ③ propagate rules (substitution , deduction of men simplified relations) every step progressively adds elements (never deletes) 1 This approach is good for definite horn couses · (you can add the head) but it's not good for mon-definite horm clouses · (constraints)-we ignore then when building CI this is why it always exists , but isn't necessa rily a model ⑪RELEVANT NODES The domain of the : CI is the set all constraints in the KB of · they are as themselves interpreted ↳ you construct them with the same name Q FACT ENCODING unary/binary facts · for each P(a) - (UNARY FACT) add the label P to the mode a for each Q(a b) (BINARY FACT) add · , - an anow labeled Q to b from a ⑤ RULE PROPAGATION take a rule with variables in it - > substitute , if tre, relevant values in place of the variables (obtained from previas knowledge) example 32d Step is the most a time consining ① ista , z-b and handest C · after all the possible resve. i If the KB is consistent, then the canonical interpretation is a model of the KB ↳ By construction , all definite clauses in the KB are satisfied (guamente CANONICAL MODEL (Every rule that has something in the head is satisfied) assuming that a KB is consistent : Reasoning with consistent knowledge bases Fact > - true > - entailed by KB iff the camonical model satisfies the fact ↳ (if the corresponding labelledge appear in the graph) Suppose wanting to know all the objects with a given property > Query P(X) ( ask) -... how toanswers explore the graph and drow conclusions Only named objects as part of the answer · Find all objects within the knowledge base that make our request true Correctness : we may guarantee that the method is complete > finds all answers · - all answers correct sound > are logically · - Completemess counterproing · If fact ↑ does not satisfy CM , then fact is not part of KB Fear is a moder -> a consequence is something that holds in all models Soundness We show that model includes" I con " of 1 · every ↳ Whatever I can says , I says it as well Calthough itcold say more)  HOMOMORPHISM Take any model I = (AFF) - reclamat * is the set all constant in the KB of K we define the function Every constant is mapped to some object (interpretation) in the domain. I res All the information we have all b X about a constant in the for a, e : canonical model appears in any · if a E picau then , h(a) EPF (a cpF) + other model same thing but for binary predicate (pair) proof by induction - we build the interpretation through the steps, making sure that each condition you add doesn't change the satisfability of the Icon. every constant is mapped -- every fact is satisfied and belongs to the predicate P(a) 4 means that a Ep I pinterpretation of p belongs a to = h(a) If we add men information (something in place of a constant gets added it will still satisfy , as long as the body of the interpretation ("the formule where you put the variable") is tre Body of interpretation is true > - I is a model > - Head HAS to be true (conditions) conclusion) It is sufficient to look at I cam to derive all atomic consequences of a consistent IB ↳ (facts denived from KB) Icam can always be constructed effectively buithas toincludeeveryreasempl results (since a kB isfinite this will , be a finite umber of operations) · grand predicates are added once · check each rice and substitutions and amotate where they God ⑭h for i constatsees I substitutions (checks) and IMkhI substitutions if there are m rules (checks) with u variables Queries. conjuctive complex e can be. g , queries (conjuction of predicates) ↳ Entaiement of general clauses is not possible with the construction of a CI it will be seen in exercises INCONSISTENT KBS constraints may lead to knowledge that contradicts itself & it's impossible that a individual can be bothe (principle of explosion) an interpretation is usand with respect to a specific constraint -Q (E) ,.... Qm(Fm) * if there exists a substitution VX such o : that all all predicates in the body becomes tre Olti) e QiF for all i , asism ↳ an interpretation is usand if it does not satisfy the constraints RB is inconsistent its canonical a if interpretation is usand ↳ , requires looking reasoning at the camonical interpretation Limitations : -queries can speak of at most 2 types of predicates (umany/bimary could use m- any predicates but - We we , lose the graphical representation Predicate rules were introduced to handle individuals and their relations (hom clauses all variables in the head Constraint of · : have to appear in the a wee body Rule propagation : for each variable substitution ,. if o (Fi) EQ for all i then the fact P(o(E) , cam be added to I can The grounding of a rll is the set of all its instantations (no variables but every constant , the is put in body) The kB is the granding granding of a all its rules of ↳ The grounding of a predicate B is a propositional KB with elaborate propositional variables predicate representation is more compact EXTENSION OF RULES & DL * rule is imposted to propagate knowledge ↓ & B propagates knowledge in one direction (if Bis tre , 14 is true) But it doesn't limit other objects to be true , besides constraints can't picture all kBs with this you  I hou,e · People have at most 2 parents · People have at least 2 parents · Someone is alive iff they are not dead THINGS TO DEAL WITH : Negation : Constraints only partially represent negations with a constrant someone , can bemon alive mon dead Domain closure : Rules camet represent knowledge if there are individuals involved amonymas Disjuction : As we use Hom clauses , we can't use emuneration Weekday > monday on Tuesday - ? University -> student on teacher? ↳ we want to include these in the extension on language... by of weakenings our constraints (and making things more complicated) Amonymas objects we allow new variables · : in the head & New veriables are existentially quantified For all X, if X is a parent, there exists an object Y which is a child of X Disjuctions and negations no more horm · : clauses , just arbitrary clauses Changes affect reasoning (techniques Anonymous objects may propagate : infinite propa. gation... pensan Peusen ⑳b * Disos.. They could lead to inconsistencies without an enough complete language ↳ big or infinite model , slow to process mallowing variables in the head that are not in body Existential rules are good for reasoning or facts , but formally speaking their Syntax is too free arbitrary combinations of predicates · un bodies. new variables in head Idea : care about general consequences rather than single facts > Are all bipeds - Normal animals ? Datalogt languages that existential rules which study restrictions an , guarantee : ① a camonical interpretation [Datalog ② comect reasoning with it umbrallen] ↳a the is to construction and goal make reasoning in a finite time ELLANGUAGE (DESCRIPTION LOGIC that limits the expressivity of KR language · a predicate rules · allows constraints and objects amonymes · has effective and efficient reasoning methods ↳ Description Language (DLs) are a family of KR languages characterized by : clear syntax · formal mambiguous semantics · DLs evolved from semantic networks as languages to represent terminological knowledge of something - -> they describe the vocabulary of said field (classes, > relations) specifying restrictions on their interpretation An early system was called KL-ONE : modern systems still follow its basic idea This system answered to the tradeoff between expressivity and complexity more expressivity > more cases to · - analyse more time , and memory required · DLs created a spectrum , mix and match of languages depend on the specific use case The scope of DLs is to provide reasoning. The main goal is that what you want to ask has an answer (decidable reasoning service) -> first order predicate logic expressed with at most 2 variables ATTRIBUTE LANGUAGE The DL first - ↳ included with complements later or (121) (regations) Can represent : complex clauses  I First theoretical results : -the goal was to complexity results express more but · optimol algorithms keeping things simple · · relationship to other logic (decidable) From big KB to minimizing to expressivity only what was for a simple needed and faster approach Later on, OWL, the standard ontology ER only + and I language for the semantic web, · Flo · only 7 and introduced various profiles based on · DL-eite the different sub languages here..and further development follows, but let’s stick with standard reasoning DESCRIPTION LOGIC EL : EL only uses 1 and J constructors but as , we will also hand be disjointness (E2 stor Syntax Concepts : Unary predicates Nc concept name Roles : Binary predicates NR robe name No constants the moment for EL CONCEPTS CLASS : · conceptnameisacone/contrediction) are come e if Cand Dane concepts then CMD is concept · a , · if C is a concept and r a role name , Ir. C is a concept Semantics · Concepts (names) are unary predicates (sets) · Role (names) are binary predicates (pairs) T tatology calways tre) · is a · I is a contradition (always false) · M is a conjutic (x) · 7 is about role successors Cexistention restriction) Er C individuals who are ⑳. linked to individuals with property C An interpretation is a pair I = (AF of) , whereAF is · mon-empty set a called DOM is the function which maps all concepts ross * extended · is to complex concepts : · TF = AF = · I = & * · (rD) = CFnD (intersection) se E · ↓ element element relationship to from the in interpre. are related objects with domains tation of C through r property ( graphicale follow the then arcaus backwards  A concept C is satisfable iff there exists an interpretation I such that CF & ↳ concept is mon empty > - property makes sense ↳ AT solution autside of the doman but still SAT & ↳ needs Unsat to if be non-empty doesn't exist I = (A F vEx}) EL withat1 : same DL but withat ↓ (it's a sublogie of 22 + ) + ↳ El concept C is SATISFIABLE it is am iff an EL concept (doesn't use +) + concept with t in its description Any EL · a is equivalent to - - UNSATISFIABLE Subsumption + C and D are two EL concepts C is subsumed by D iff for all interpretations # , CFCDF ↳ Sup Example one is a subconcept --- the other has of exactly has properties properties A and B but could A and B have more C more specific than D La more specific hence subsumed , Concept tree : graphical representation of a concept B AB , E S --- · C ( · modes > - concept names a canonical · branches > - role names model for the concept Homomorphism between trees : is a function that "keeps the same shape" · for every mode of a tree , assigns the mode to the other twee h(root (T)) roet(T2) = · for every ne modes (Ti) , all concept names in the first tree have to be present in the second label (m) label (h(n) · if a mode has a successor , then the imege has the image the successor of the mode of M> m then h(m) I h(m) example : Theorem : Ti C subsumed is by BB there T - Diff is ti Y homenorplism au from T(D) to T(c) A, B - A B - proof Homomophism : ⑧ is a sort of inclusion canonical - > if T(C) Satisfies TCD) then all moder objects in CF belong to DF I just idea an Deciding subsumption requires polynonial time based on the size of the concepts Equivalence : the concepts are equivalent CED and DEC CED if -> We express knowledge relevant through constraints and interpretations ↳ subsumptions (knowledge about the terminology - a. K. a. TBoxes) Terminological Box : (TBox) imposes restrictions on the interpretation of concepts class of Pletypi is Platypus [ Mammal always contained in class memmals of general concept. CED (EL"concepts) inclusion (G() TBox set a is a finite of GC an interpretation satisfies the cal CED iffCFDF ↳ I is a model of the TBox T if it all T satisfies acls in In of TBox presence a reasoning is the class of models restricted to only  Satisfiabilitythere e · is a model · Subsumptich CFCDF has to hold for all models of T Consistency needs to have model T a · · note : concepts can be unsatisfiable even if the TBox is consistent O - contradition Algorithm bilding : 1) Forget consistency Definition of subsumption : C is subsumed by D iff CFCDF - - Tisnot subsumedy something exists here 71 = (D F , ) , 76eXt GeCF+ - xF Sc D = 6 Key idea : you can use the subsumption algorithm to define consistency 2) Forget satisfiability : Definition of satisfiability : a conceptC is satisfiable if it is not subsumed by ↓ - > there is at least one model of a TBox which makes the concept men-empty Key idea , subsumption con decide satisfiability T CID in model of T C is subset D every , a of ↳ C+ B (shorter motation for models) EL TBox is an E2 + TBox withat I they are all consistent and a model · > - # ([53 [d3rF E(d d)} , 7) # = = , every EL concept is satisfiable w r t EL TBox ·... an ↳ no bottom = always sat in EL recoll the universal model, the CI that is the "Cargest" and guarantees consisteng and satisfiability Building a subsumption algorithm Homomorphism isn't directly applicable to TBoxes , as GCls add objects to the concept tree * &7r B -"A How avoid BTBB-. can we B5Js A. & infinite construction? ? BIA TFA & ArC Isame thing langer TBox , with infinity issue) New approach based on consequence propagation ↳ Rather theu building a model , try to derive all possible consequences of a kB (combine the clauses - ACI - to delive a new one) Theprevisteisdingsimplification se NORMAL FORM TBOY A GCI is in moral form if it is written as : AIB concepts the left on always · ore · A MAz. [B concept names (T). AE Fr B. concepts on the right can be · Fr A [B. (T +), If all GCIs are in nomal for , so is c TBOX · AIB > - A subcass of B · A , MAz[B- > A.. Ar both contained in B Ad Fr B A , then have in B > - If belong to you an -successer ·. you · Jr A[B. > - If -successer in A exists , it belongs to B - at most a constructor -no conjuctions on the right I Normal form. X 2 constructors X conjuction not alloved on the right  ACIs in normal fors are existential rules with constrants : objecty is becomes zie connected to a x via the relationship SrB ↓- there can be eX parents who > -. Somebody that has a child is a parent do not have childen no additional > properties passed to If something is a parent it must have a child the child > A mammal can’t also be a reptile All TBoxes can be transformed to moral fan , always ↳ by applying monalization wes Basically decomposition of GCIs until they're simple > - * ⑦ define complex property * with name "A" (variable replacing) g substituted complex concept an the left, bigger concept on the right Ibasically transitive A property ( & in Q divide conjunctions half to simplify and minimize relations ⑫ normalization * ~Jr. (BrC)[X , X. 57s (Am]m.. D)]s. B · AmXz5 X. &m. (BMC) &42 X. 57s. (Am]r D). · X. 57s B. · Er X3[X2. · BMC & X3 · X , 27s Xn. XnSAmIr D. Note: the two KBs are not · Xu S A equivalent (X2 is not necessarily an object in the · Xn & Fr D. original KB, but here it has a stated purpose CONSERVATIVE EXTENSION T - a TBox morm (T) > - its normalization - they are not equivalent , but morm(T) is conservative extension T: a of it will lead to the exact same consequences a. k. a. we are adding information that doesn't modigy al knowledge base card I Darbitra concepts ! Normalization keeps the same subsumption relations introduced (not as long as no new symbols get remaning objects , but proper new individuals) proof : ⑪ by construction , every model of norm (T) is also model a ② every model T of can be extended to mon (T) by interpreting the new symbols back to what they are supposed to mean (interpret ↳TECID)Aasc)MOMITECID = consequence : normal form is enough to be able to decide subsumption > - which is are how do we do it ? gooe , CONSEQUENCE-BASED COMPLETION ALGORITUM make derived consequences explicit > - based on other · explicit stuff ⑪ INITIALIZATION : Start with obvious tontologies ② SATURATION : apply completion rules while possible COMPLETION RULES 1. TFASBad BICT Ac t[ C. TFASB TF AIB2 , and BiMBSCeT-Ac 3. TFAIB and BEIrCeTERDI TF CED 4. TFAS7r Band. fr. BECTAc r By construction, the completion algorithm can’t derive ALL consequences. (It needs infinite time). It can however derive atomic subsumptions ↳ "CLASSIFICATION" One rule to handle bottom I missing : 3. TFASFr 1. then concede SOUNDNESS : all denived consequences should be entailed by T This. is a consequence of : ① initialization is trically true ASA , AIT are tatologies ② Rules do not create new content > - if a rule can be applied to model, then the added still within the a knowledge is model COMPLETENESS : Show that if a consequence is a denived , then T does not entail it I build a model that verifies this (ASB not delived - AFGBF) model construction : PC - all concept names A in T such that TFAI I is not derived by the algorithm > - domain (properties) > - elements belong to A r- successore > - If anything that is not on the “list” does not appear in the drawn model, then the TBox is shown consistent Complexity : completion algorithm only gene rates axioms in normoe for (concept names subsumed by themselves , other concepts of existential nestr ). in T ma consequences M symbols - max To shald apply a rule we find : at most 2 consequences > - dable check one GCF > - Single check through the TBox overall time to check polynomide How to consequences with this get complex algorithm : by making reductions example : C D , : complex concepts X, X : new concept names (not in T) check if model holds ⑳ Give names to complex concepts and check subsumption between them. Normalize first if necessary ELI : Ed with INVERSE ROLES you can read role relationships backwards its GCIs in normal form can be represented as predicate rules bit... s altha