Limitations 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)
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 models
Default 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
• 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╞ a  KBb╞ a
– exceptions to default conclusions make a logic nonmonotonic
– 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
• 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 KB
Truth-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
• 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)
• represent taxonomies, object properties (slots)
defclass animal
defclass animal: subclass animal
slot warmBlooded: True
slot externalCoating: fur
defclass dog: subclass mammal
slot movement: runs
slot vocalization: barks
slot numberOfLegs: 4
defclass bird: subclass animal
slot movement: flies
slot externalCoating: feathers
slot numberOfLegs: 2
slot vocalization: chirps
definstance snoopy: instanceOf dog
definstance 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.”
Description 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
• 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 (i.e. not necessarily empty)
subsumption (is one class a subset of another)
instance checking: is X a member of class Y?
retrieval: all instances of...
categorization (most specific class for an instance)
“what part of the esophagus is not in the anterior compartment of
the neck?”
– “can a chicago-style pizza be a vegetarian pizza?”
• inference algorithms – based on “tableaux” procedures
(essentially model-checking)
• query languages
– RIL: prolog-like
– SPARQL: extension to SQL
<ril:variable name="X"/>
SELECT ?title ?price WHERE { ?x dc:title ?title .
OPTIONAL { ?x ns:price ?price . FILTER (?price < 30) } }
OWL – implementation of DL for Web
• “Semantic Web” – extend data in XML with semantics
• can allow intelligent search/query
• knowledge expressible in RDF (XML-like, with URIs)
<rdf:Description rdf:about="">
<exterms:weight rdf:parseType="Resource">
<rdf:value rdf:datatype="&xsd;decimal">2.4</rdf:value>
<exterms:units rdf:resource=""/>
<rdfs:Class rdf:ID="cd">
<rdfs:subClassOf rdf:resource="#media"/>
<rdfs:objectProperty rdf:ID="capacity" rdf:resource="&xsd;integer"/ >
<rdfs:objectProperty rdf:ID="shape" rdfs:domain="#Disc">
<owl:ObjectProperty rdf:ID="hasBankAccount">
<owl:unionOf rdf:parseType="Collection">
<owl:Class rdf:about="#Person"/>
<owl:Class rdf:about="#Corporation"/>
<rdf:RDF xmlns:foaf=""
<foaf:Person rdf:about="#JW">
<foaf:name>Jimmy Wales</foaf:name>
<foaf:mbox rdf:resource="mailto:[email protected]" />
<foaf:homepage rdf:resource="" />
<foaf:depiction rdf:resource="" />
<foaf:interest rdf:resource="" rdfs:label="Wikipedia" />
<foaf:Person> <foaf:name>Angela Beesley</foaf:name> </foaf:Person>
<rdf:Property rdf:about=""
vs:term_status="stable" rdfs:label="personal mailbox"
rdfs:comment="A personal mailbox, i.e. foaf:mbox.">
<rdf:type rdf:resource=""/>
<rdf:type rdf:resource=""/>
<rdfs:domain rdf:resource=""/>
<rdfs:range rdf:resource=""/>
<rdfs:isDefinedBy rdf:resource=""/>
Protege – an Ontology Editor
• Of course, probability forms a more rigorous way
to handle uncertainty
– “most stomach aches are cause by indigestion”
– Prob(indigestion | stomachAche) = 0.8
– use Bayes’ Rule to combine observations with prior
expectations to calculate posterior probs
– may be hard to quantify
• probabilistic logic
– attempts to synthesize FOL with probabilities
• certainty factors in expert systems
– backAche&(physicalOccupation or sportsEnthusiast)
strainedMuscles (CF=0.8)
Fuzzy Logic
• useful when rules have qualitative adjectives over
quantitative variables
• don’t want to draw precise cutoffs
– Young children should go to bed early.
– Tall people who are not thin are heavy.
• membership functions
• KB of fuzzy rules
– IF
very cold THEN stop fan
cold THEN turn down fan
normal THEN maintain level
hot THEN speed up fan
• control applications; function approximation
• inference
– if height of package is short and weight is
heavy, ship by FedEx
degree to which instance matches antecedents to rule?
conjunction: take min of memberships
suppose height=165 and weight=100; is it short and heavy?

Limitations of First