INFO282 theory

An agents attitude towards a proposition.

Use symbols or combinations of them to stand for objects and propositions about them

• one plus one equals two
• 1+1=2
• terms: 1+1, 2
• predicate: =

• marys boss is evil
• evil(boss(Mary))
• terms: boss(Mary))
• predicate: evil

‘Knowledge representation is the field of study concerned with using formal symbols to represent a collection of propositions believed by some putative agent.’

• The agent may believe more propositions than is explicitly
• represented. Other propositions may follow from them.
• The agent gains access to the implicit beliefs through
• inference. This is the process we refer to as reasoning.
• … the formal manipulation of the symbols representing a collection of believed propositions to produce representations of new ones…

• Any mechanically embodied intelligent process will be comprised of structural ingredients that
• a) We as external observers naturally take to represent a propositional account of the knowledge that the overall process exhibits

b) Independent of such external semantic attribution, play a formal but causal and essential role in engendering the behaviour that manifests that knowledge.

• Topic from Artificial Intelligence :
• The study of intelligent behavior achieved through computational means… concerned with how an agent uses what it knows in deciding what to do.

• Backbone of a strategy for designing programs:
• …The ability to make behavior depend on explicitly represented knowledge seems to pay off when we cannot specify in advance how that knowledge will be used.

• D is a set of elements (Non-empty).
• I is a mapping from:
• Constants to elements in the domain - I(luna) = Luna
• Predicates to (cartesian products of) elements in the domain
• - MoonOf(earth, luna) - MoonOf(earth, luna) is true iff <earth, luna> is an element of I(MoonOf)
• Functions to - Moon(earth) = luna - Moon(earth) is luna iff <earth, luna> is in I(Moons)

an interpretation where every sentence of S is true

• Used to eliminate existential quantifiers (When making CNF)
• Result of skolemization is not logically equivalent, but satisfiability is preserved

• Ey is bound by Ax, therefore y must be skolemized a function of x
• P(x,f(y))

Answer S logically entails A if for every interpretation I, if I makes true all sentences in S, it also makes A true

• A Horn clause is a clause with at most one positive literal.
• A unit clause is a clause with one literal.
• A positive Horn clause contains one positive literal.
• A negative Horn clause has no positive literals. The empty clause is negative.

the domain-specific relations, functions and constants in the language that may vary between applications

Pair <D,I> where D is a nonempty set, I maps function – and relation-symbols onto corresponding relations and functions over D

Given a set S of sentences, an interpretation M is a model for S iff for all sES M|=s, i.e. all sentences in S are true in M

is read “KB entails S.”– Means “S is true in every world (model) in which KB is true.”– Means “In the world, S follows from KB.”

– Means “True implies S.”– Means “S is valid.”– In Horn form, means “S is a fact.”

Let S be the set of all right answers. A sound algorithm never includes a wrong answer in S , but it might miss a few right answers. => not necessarily "complete". 

Any mechanism (set of inference rules, or computational procedure) for determining entailment is sound iff anything determined to be an entailment actually is an entailment. I.e. it determines correctly.

A computational procedure is sound, if it can only compute entailments

A complete algorithm should get every right answer in S : include the complete set of right answers. But it might include a few wrong answers.

Any mechanism (set of inference rules, or computational procedure) for determining entailment is complete iff every entailment is determined to be so. i.e. it does not miss anything.

The computational procedure is complete if any entailment can be computed

Indefinite knowledge is inexpressible with Horn Clauses. This reduces the complexity of checking entailment. Specifically, resolution-derivations can be expected to follow a certain pattern, and this greatly reduces the search-space of derivations.

Resolution derivation of [] starting with a (negative) query, and in each subsequent step, the most recent resolvent is resolved with a sentence in the KB.

Making terms identical by substitution

A sentence s is a logical consequence of a set S of sentences iff s is true in every model for S. ie S |= a iff for any interpretation I: I |= S implies I |= a

A knowledge base entails a proposition P iff P is necessarily true when all propositions in the KB are true.

CNF. A formula is Conjuctive Normal Form iff it is a conjunction of disjunctions of literals. 

(a v b) ^ (c v d)

• IF
• antecedent
• (Conditions for the rule to fire)
• THEN 
• consequent
• (Actions to perform)

• Basic Actions:
• ADD pattern: inserts into WM
• REMOVE i: deletes the WME that matches the i-th condition, provided it is positive
• MODIFY i (attr spec): replace the current value of attr with the value given by spec in the WME that matches the i-th condition, provided it is positive

• ex. IF (moves person:x to:y)
• (person name:x)
• THEN MODIFY 2 (home y)
• REMOVE 1

• WME is a production system
• (type attribute1:value1 . . . attributen:valuen )
• where type, attributei and valuei are all atoms

• example
• (person age:27 home:toronto)
• (goal task:putDown importance:5 urgency:1)

• 1. recognize: find applicable rules (ie. where the conditions are satisfied by the current state of the WM)
• 2. resolve conflict: decide which of the applicable rules should be applied
• 3. act: apply the actions of the chosen rules to the WM

Repeat until there are no applicable rules

• Most General Unifier. Least specialized unification of two clauses.
• We can compute the MGU using the disagreement set Dk = {e1, e2}: the pair of expressions where two clauses first disagree. REPEAT UNTIL no more disagreement → found MGU.

• Negate conclusion we want to prove
• Make everything CNF
• Resolve to the empty clause
• Shows that if we negate the conclusion, we are able to derive a contradiction, therefore negated conclusion is unsatisfiable and conclusion must be valid
• Refutation Complete

«A production system is a forward-chaining reasoning system that uses rules of a certain form called production rules as its representation of general knowledge.»

• Facts + Rules = New facts
• • PRODUCES NEW INFORMATION

Describes noun phrases

Constants: john, 5, titanic, Knife3, cocaColaComp

• Category nouns describing classes of objects (CONCEPT)
• Concepts: Person, Girl, Hunter, Teenager, Number, Ship, Tool, Company

• Relational nouns describing parts or attributes (ROLE). Describes relations/connections between objects, ex. relationships or attributes.
• Roles
• :Child, :Age, :Employee

• [ALL :Role Concept]
• all r d
• things r related only belonging to concept d

• [EXISTS number :Role]
• exists n r
• things r related to at least n distinct things, n is positive int

• [FILLS :Role constant]
• fills r c
• things r related to the thing denoted by c

• [AND Concept1 … ConceptN]
• and d...d
• things belonging to each of the concepts d1...dn

d is an arbitrary concept

• SENTANCES:
• (c -> d) thing c belongs to concept d
• (d ⊑ d') all things d belong to d'
• (d ≐ d') d and d' denote the same concept

• Someone related through :Role to every individual belonging to Concept
• • [ALL :Employee Competent] Something whose all employees are competent

• All individuals related to number of other individuals through :Role
• • [EXISTS 5 :Brother] Someone who has at least five brothers

• • Everything related to constant through :Role
• • [FILLS :Child john] All of John’s children

• • Everything in Concept1 that is also in Concept2 … also in ConceptN
• • [AND Dog MickeysFriend NamedPluto] Is Pluto

• Regent ⊑ Royal 'Regents are royal'
• [AND Surgeon Female] ⊑ Doctor 'Female surgeons are doctors'

• Mother ≐ [AND Female [EXISTS 1 :child]] 'Mothers are females with children'
• Actress ≐ [AND Female [FILLS :occupation actor]] 'An actress is a female actor'

• harald → King 'Harald is a king'
• drEvil → [AND Mad Scientist] 'Dr. Evil is a mad scientist'

1. Expand: For (a ≐ expression)∈TD, replace occurrences of a within a concept with expression.

• 2. Flatten AND: Simplify
• [AND … [AND d1 … dn] …] ⇨ [AND … d1 … dn …]

• 3. Combine ALL: Simplify
• [AND … [ALL r d1] … [ALL r d2] …]
• ⇩
• [AND … [ALL r [AND d1 d2] …]

• 4. Combine EXISTS: Simplify
• [AND … [EXISTS n1 r] … [EXISTS n2 r] …]
• ⇩
• [AND … [EXISTS n r] …] where n = max{n1, n2}

5. Remove vacuous concepts: Thing, [AND] and [ALL r Thing]

• 6. Remove redundant expressions:
• Eliminate any expression that is an exact duplicate of another within the same AND-expression

• [AND Company
• [ALL :Manager [AND
• B-SchoolGrad
• [EXISTS 2 :TechnicalDegree]]]
• [FILLS :Exchange nasdaq]]

• FIRST, everything is a Thing
• (flo, Thing) (otto, Thing) osv
• Then replace Thing with facts from TD
• check if you can change/add facts based on what is currently there
• so the fact that alex has a child otto and child is evil, that implies that otto is evil, add to TD
• same with flo and good

• [ALL r d]
• [ALL :Employee Human]

• Selected literals
• Linear form
• Definite clauses

• An SLD derivation of a clause c from a set of clauses S is a sequence of clause c1,c2,...,cn such that cn=c and 
• 1. c1 ∈ S (∈ means element of)
• 2. ci+1 is a resolvent of ci and a clause in S

Write S→c

uncapitalized mixed case bestFriend, denote generally using a,b,c,f,g,h. nearestPlanet.

• a,b,c used for function symbols of arity 0, constants
• g,h for nonzero arity

function takes terms

capitalized mixed case OlderThan, denote generally using P,Q,R. Planet, Moon.

term: every variable, if t1...tn are terms and f is a function symbol of arity n, then f(t1...tn) is a term

formula: term=term, predicate P(t1...tn), predicate taking a constant

¬ is a junction only applied to formulas, so if ¬s4(s5,s6) is a formula, then s4 is a predicate and s5/ s6 are terms

• Reification is the trick of representing relationship-instances as ‘abstract’ objects. ontological choice for pragmatic reasons.
• Fix: let relation-instances materialize into entities. Reification provides the flexibility to avoid rigid commitments

turning predicates to objects.