```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)
possibly(PQ)
eventually(x corrupt_packet(x)  in_queue(x))
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
– 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╞ 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
consistent
Prolog
• 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
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 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
• 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
isa
john
mary
actor
recipient
event1
object
B1
isa
topic
book
frogs
isa
GivingEvent
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
disjunction
• examples of major ontologies in DLs:
–
–
–
–
GALEN – medical records
FMA – Foundational Model of Anatomy
Dublin Core: media (author, publisher, type, year...)
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...)
• 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
– 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)
<ril:query>
• query languages
– RIL: prolog-like
– SPARQL: extension to SQL
<dc:creator>
<ril:value>h:newton</ril:value>
<ril:variable name="X"/>
</dc:creator>
</ril:query>
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)
<exterms:weight rdf:parseType="Resource">
<rdf:value rdf:datatype="&xsd;decimal">2.4</rdf:value>
<exterms:units rdf:resource="http://www.example.org/units/kilograms"/>
</exterms:weight>
</rdf:Description>
<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">
</rdfs:Class>
<owl:ObjectProperty rdf:ID="hasBankAccount">
<rdfs:domain>
<owl:Class>
<owl:unionOf rdf:parseType="Collection">
</owl:unionOf>
</owl:Class>
</rdfs:domain>
</owl:ObjectProperty>
<rdf:RDF xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#">
<foaf:name>Jimmy Wales</foaf:name>
<foaf:mbox rdf:resource="mailto:jwales@bomis.com" />
<foaf:homepage rdf:resource="http://www.jimmywales.com/" />
<foaf:nick>Jimbo</foaf:nick>
<foaf:depiction rdf:resource="http://www.jimmywales.com/aus_img_small.jpg" />
<foaf:interest rdf:resource="http://www.wikimedia.org" rdfs:label="Wikipedia" />
<foaf:knows>
<foaf:Person> <foaf:name>Angela Beesley</foaf:name> </foaf:Person>
</foaf:knows>
</foaf:Person>
</rdf:RDF>
vs:term_status="stable" rdfs:label="personal mailbox"
rdfs:comment="A personal mailbox, i.e. foaf:mbox.">
<rdf:type rdf:resource="http://www.w3.org/2002/07/owl#InverseFunctionalProperty"/>
<rdf:type rdf:resource="http://www.w3.org/2002/07/owl#ObjectProperty"/>
<rdfs:domain rdf:resource="http://xmlns.com/foaf/0.1/Agent"/>
<rdfs:range rdf:resource="http://www.w3.org/2002/07/owl#Thing"/>
<rdfs:isDefinedBy rdf:resource="http://xmlns.com/foaf/0.1/"/>
</rdf:Property>
Protege – an Ontology Editor
Probability
• 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
IF
IF
IF
temperature
temperature
temperature
temperature
IS
IS
IS
IS
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?
min(0.2,0.6)=0.2
```