INTRODUCTION

• What is “Intelligence”?

• What is “Artificial Intelligence” (AI)?

• Strong AI vs. Weak AI

• Symbolic AI vs. Subsymbolic AI

• Knowledge-based systems

Introduction to Artificial Intelligence

• A human judge C engages in a natural language conversation with one human B and one machine A , each of which tries to appear human.

• All participants are placed in isolated locations.

• If the judge C cannot reliably tell the machine A from the human B , the machine is said to have passed the test.

• In order to test the machine's intelligence rather than its ability to render words into audio, the conversation is limited to a text-only channel such as a computer keyboard or screen

• Searle, a human, who does not knows Chinese, is locked in a room with an enormous batch of Chinese script.

• Slips of paper with still more Chinese script come through a slot in the wall.

• Searle has been given a set of rules in English for correlating the Chinese script coming through with the batches of script already in the room.

• Searle is instructed to push back through the slot the Chinese script with which the scripts coming in through the slot are correlated according to the rules.

• Searle identifies the scripts coming in and going out on the basis of their shapes alone. He does not speak Chinese, he does not understand them

• The scripts going in are called ‘the questions’, the scripts coming out are ‘the answers’, and the rules that Searle follows is ‘the program’.

• Suppose also that the set of rules, the program is so good and Searle gets so good at following it that Searle’s answers are indistinguishable from those of a native Chinese speaker.

• It seems clear that Searle nevertheless does not understand the questions or the answers

• But Searle is behaving just a computer does, “performing computational operations on formally specified elements”

• “The study of the computations that make it possible to perceive, reason, and act” (Winston, 1992)

• “A field of study that seeks to explain and emulate [human] intelligent behaviour in terms of computational processes” (Schalkoff, 1990)

• Intelligence emerges from the orchestration of multiple processes

• Process models of intelligent behaviour can be investigated and simulated on machines

Symbolic vs. Subsymbolic AI
Knowledge-based Systems

• Exact formulisations.

• Exemplary realisation via implementations.

• has a memory and the capability to act in his world based on it.

• has sensors to perceive information from his environment.

• has actuators to influence the external world.

• has the capability to probe actions. By that he is able to choose the best possible action.

• has internal memory for methods and the exploration of the world is guided by knowledge kept in it.

• Distributed representation

• Representation and processing of fuzziness

• Highly parallel and distributed action

• Speed and fault-tolerance

Image: http://www.neuronalesnetz.de

KNOWLEDGE-BASED SYSTEMS

• f(n)=g(n)+h(n)

• g(n) the cost to get from the star state to current state n

• h(n) estimated cost to get from current state n to end state

• f(n) estimated total cost from start state through current state n to the end state

More in Lecture 5

• It works in theory but in practice works only on toy problems (e.g. Tower of Hanoi)

• Could not solve real-world problems because search was easily lost in the combinatorial explosion of intermediate states

Knowledge-is-power hypothesis , also called the Knowledge Principle was formulated by E.A. Feigenbaum in 1977:

“knowledge of the specific task domain in which the program is to do its problem solving was more important as a source of power for competent problem solving than the reasoning method employed” [15]

3a. Newell’s 3 levels of knowledge

3b. Brachman’s 5 levels of knowledge

• How can knowledge be characterised?

• What is the relation of this characterisation and the representation of knowledge?

• What is characteristic about a system which holds knowledge?

• Knowledge Level

• Logical Level

• Implementation Level

• Knowledge Level

• The most abstract level of representing knowledge.

• Concerns the total knowledge contained in the Knowledge Base

• Example: The automated DB-Information system knows that a trip from Innsbruck to Vienna costs 120€

• Logical Level

• Encoding of knowledge in a formal language.

• Example: Price(Innsbruck, Vienna, 120)

• Implementation Level

• The internal representation of the sentences.

• Example:

• As a String “Price(Innsbruck, Vienna, 120)”

• As a value in a matrix

• Implementational Level

• Logical Level

• Epistemological Level

• Conceptual Level

• Linguistic Level

• Implementational Level

• The primitives are pointers and memory cells.

• Allows the construction of data structures with no a priori semantics

• Logical Level

• The primitives are logical predicates, operators, and propositions.

• An index is available to structure primitives.

• A formal semantic is given to primitives in terms of relations among objects in the real world

• No particular assumption is made however as to the nature of such relations

• Epistemological Level

• The primitives are concept types and structuring relations.

• Structuring relations provide structure in a network of conceptual types or units. (i.e. inheritance: conceptual units, conceptual sub-units)

• The epistemological level links formal structure to conceptual units

• It contains structural connections in our knowledge needed to justify conceptual inferences.

• Conceptual Level

• The primitives are conceptual relations, primitive objects and actions.

• The primitives have a definite cognitive interpretation, corresponding to language-independent concepts like elementary actions or thematic roles

• Linguistic Level

• The primitives are words, and (lingustic) expressions.

• The primitives are associated directly to nouns and verbs of a specific natural language

• Arbitrary relations and nodes that exist in a domain

• A PSM specifies which inference actions have to be carried out for solving a given task.

• A PSM determines the sequence in which these actions have to be activated.

• Knowledge roles determine which role the domain knowledge plays in each inference action.

• propose – derives an initial design based on the requirements;

• C-test – requires knowledge that describes which possible designs are valid (i.e., the domain constraints);

• revise – tries to improve an incorrect design based on the feedback of the C-test step.

More in Lecture 7

One of the first systems that aimed to capture common knowledge in a knowledge base

• Human experts are able to master unforeseen effects and situations.

• Human experts are able to learn from experiences.

• Human experts expand their knowledge continuously.

• Human experts derive new knowledge not only based on drawn. conclusions but via analogy and intuition.

POPULAR AI SYSTEMS

More information: [9]

• Organizing and Prioritizing Information

• Preparing Information Artifacts

• Mediating Human Communications

• Task Management

• Scheduling and Reasoning in Time

• Resource allocation

• Can be used to simulate realistic events; has a world model

• http://www.krannert.purdue.edu/centers/perc/html/aboutperc/seaslabs/seaslabs.htm

• Early machine translation system

• Foundation for Yahoo’s Babelfish or Google Translator

• http://www.systransoft.com/

• Virtual-reality based chatbot

• http://virtualwoman.net/

SUBDOMAINS OF AI

• CS are directly integrated in their environment, act in it, and are able to communicate with it.

• CS are able to direct and adapt their actions based on the environment they are situated in.

• CS typically represent system-relevant aspects of the environment.

• Their information processing capabilities are characterized through learning aptitude and anticipation

• Organisms / biological cognitive systems

• Technical systems such as robots or agents

• Mixed human-machine systems

• Formal languages for expressing knowledge

• Well understood formal semantics

• Reasoning methods to make implicit knowledge explicit

• Additional information may invalidate conclusions.

• Non-monotonic reasoning is closer to (human) common-sense reasoning.

• Most rules in common-sense reasoning only hold with exceptions (i.e. university_professors_teach)

• Default-Logics: Non-classical inference rules are use to represent defaults

• The modale approach: Modal operators are used to explicitely declare if sth. is believed in or is consistent.

• Circumscription: Validity can be restricted to specific models.

• Conditional approaches: A conditional junctor is used to represent defaults in a logical language.

• A considerable amount of cases has to be available

• Using the cases to solve the problem has to be easier than solving the problem directly.

• Available information is incomplete or unsecure and imprecise.

• The construction of a KBS and the modelling of cases is not easily possible.

• “Planning is the process of thinking about the activities required to create a desired goal on some scale” [Wikipedia]

• decide about the schedule of a production line;

• decide about the movements of an elevator;

• decide about the flow of paper through a copy machine;

• decide about robot actions.

• the problem is described to the planning system in some generic language;

• a (good) solution is found fully automatically;

• if the problem changes, all that needs to be done is to change the description.

• has a memory and the capability to act in his world based on it.

• has sensors to perceive information from his environment.

• has actuators to influence the external world.

• has the capability to probe actions

• has internal memory for methods and the exploration of the world is guided by knowledge kept in it.

SOME RELEVANT PEOPLE IN AI

SUMMARY

• Weak and strong AI

• Symbolic and subsymbolic AI

REFERENCES

• http://en.wikipedia.org/wiki/List_of_notable_artificial_intelligence_projects

• http://en.wikipedia.org/wiki/Turing_test

• http://en.wikipedia.org/wiki/General_Problem_Solver

• [1] G. Görz, C.-R. Rollinger, J. Schneeberger (Hrsg.) “Handbuch der künstlichen Intelligenz” Oldenbourg Verlag, 2003, Fourth edition

• [2] A. Turing. "Computing Machinery and Intelligence", Mind LIX (236): 433–460, Ocotober, 1950.

• [3] Aristotle “On Interpretation”, 350 B.C.E, see: http://classics.mit.edu/Aristotle/interpretation.html

• [4] A. Newell, H.A. Simon, “Human Problem Solving” Englewood Cliffs, N.J.: Prentice Hall, 1972

• [5] A. Newell. “The Knowledge Level”, AI Magazine 2 (2), 1981, p. 1-20.

• [6] F. Rosenblatt. “Strategic Approaches to the Study of Brain Models” In: Förster, H.: Principles of Self-Organization. Elmsford, N.Y.: Pergamon Press, 1962.

• [7] S. Russell, E.H. Wefald. "Do the Right Thing: Studies in Limited Rationality" MIT Press, 1991.

• [8] C. Beierle and G. Kern-Isberner "Methoden wissensbasierter Systeme. Grundlagen, Algorithmen, Anwendungen" Vieweg, 2005.

• [9] J. Weizenbaum. "ELIZA - A Computer Program For the Study of Natural Language Communication Between Man And Machine", Communications of the ACM 9 (1): p. 36–45, 1966.

• [10] W. Birmingham and G. Klinker “Knowledge Acquisition Tools with Explicit Problem-Solving Methods” The Knowledge Engineering Review 8, 1 (1993), 5-25

• [11] A. Newell and H. Simon "GPS, a program that simulates human thought" In: Computation & intelligence: collected readings, pp. 415 - 428, 1995.

• [12] R. J. Brachman “On the Epistemological Status of Semantic Networks” In: N.V. Findler (ed.): Associative Networks: Representation and Use of Knowledge by Computers. New York: Academic Press, 1979, 3-50.

• [13] G. Brewka, I. Niemelä, M. Truszczynski “Nonmonotonic Reasoning” In: V. Lifschitz, B. Porter, F. van Harmelen (eds.), Handbook of Knowledge Representation, Elsevier, 2007, 239-284

• [14] D. Fensel “Problem-Solving Methods: Understanding, Description, Development and Reuse”,, Springer LNAI 1791, 2000

• [15] E.A. Feigenbaum. “The Art of Artificial Intelligence: Themes and Case Studies of Knowledge Engineering,” Proceedings of the International Joint Conference on Artificial Intelligence, Cambridge, MA, 1977

• [16] W.J. Clancey. “Heuristic Classification”, Artificial Intelligence , 27:289-350, 1985

Questions?

Propositional Logic

• Syntax

• Semantics

• Inference

MOTIVATION

=> Logic provides a way to talk about truth and correctness in a rigorous way, so that we can prove things, rather than make intelligent guesses and just hope they are correct

• Associate natural language expressions with semantic representations

• Evaluate the truth or falsity of semantic representations relative to a knowledge base

• Compute inferences over semantic representations

• The core of (almost) all other logics

• Syntax: Vocabulary for expressing concepts without ambiguity

• Semantics: Connection to what we're reasoning about

• Interpretation - what the syntax means

• Reasoning: How to prove things

• What steps are allowed

TECHNICAL SOLUTIONS

SYNTAX

• ∧ ...and [conjunction]

• ∨ ...or [disjunction]

• →...implies [implication / conditional]

• ↔ ...is equivalent [biconditional]

• ¬ ...not [negation]

• A symbol is a sentence

• If S is a sentence, then ¬S is a sentence

• If S is a sentence, then (S) is a sentence

• If S and T are sentences, then (S ∨ T), (S ∧ T), (S → T), and (S ↔ T) are sentences

• A sentence results from a finite number of applications of the above rules

e.g. ¬ P ∨ Q ∧ R ⇒ S is equivalent to (¬ P) ∨ (Q ∧ R)) ⇒ S

SEMANTICS

v : P → {T,F}

v assigns a truth value to any atom in a given formula ( P is the set of all propositional letters, i.e. atoms)
Suppose F denotes the set of all propositional formulas. We can extend an assignment v to a function

v : F → {T,F}

which assigns the truth value v(A) to any formula A in F. v is called an interpretation.

• Suppose v is an assignment for which

v(p) = F,           v(q) = T.

• If A = (¬p → q) ↔ (p V q) , what is v(A) ?

Solution:

v(A) = v ((¬ p → q ) ↔ ( p V q ))

        = v (¬ p → q ) ↔ v ( p V q )

        = ( v (¬ p ) → v ( q )) ↔ ( v ( p ) V v ( q ))

        = (¬ v ( p ) → v ( q )) ↔ ( v ( p ) V v ( q ))

        = (¬F → T) ↔ (F V T)

        = (T → T) ↔ (F V T)

        = T ↔ T

        = T

v ( A ) = v ( B )

for all interpretations v , A is (logically) equivalent to B:

A ≡ B

• A ↔ B is a formula (syntax)

• A ≡ B is a relation between two formula (semantics)

• Theorem : A ≡ B if and only if A ↔ B is true in every interpretation; i.e. A ↔ B is a tautology .

• A is unsatisfiable (or, contradictory) if it is false in every interpretation

• U is unsatisfiable if no such interpretation exists

• If U is satisfiable, then so is U − {Ai} for any i = 1, 2,…, n

• If U is satisfiable and B is valid, then U U { B } is also satisfiable

• If U is unsatisfiable and B is any formula, U U { B } is also unsatisfiable

• If U is unsatisfiable and some A i is valid, then U − {Ai} is also unsatisfiable

• Valid (tautology):

• Not valid, but satisfiable:

  
  

• False (contradiction):

If some interpretation v is a model for the set

it must satisfy but in this interpretation, we also have

T ( U ) = { A | U ⊧ A }

is called the theory of U . The formulas in U are called the axioms for the theory T(U) .

INFERENCE

• Truth Table Method

• Deductive (Proof) Systems

• Resolution

• Step 1: Starting with a complete truth table for the propositional constants, iterate through all the premises of the problem, for each premise eliminating any row that does not satisfy the premise

• Step 2: Do the same for the conclusion

• Step 3: Finally, compare the two tables; If every row that remains in the premise table, i.e. is not eliminated, also remains in the conclusion table, i.e. is not eliminated, then the premises logically entail the conclusion

• Amy loves Pat: lovesAmyPat

• Amy loves Quincy: lovesAmyQuincy

• It is Monday: ismonday

• If Amy loves Pat, Amy loves Quincy:

• lovesAmyPat → lovesAmyQuincy

• If it is Monday, Amy loves Pat or Quincy:

• ismonday → lovesAmyPat ∨ lovesAmyQuincy

• If it is Monday, does Amy love Quincy?

• i.e. is ismonday → lovesAmyQuincy entailed by the premises?

• In other words, the premises logically entail the conclusion.

• It is a direct implementation of the definition of logical entailment.

• Validity Checking

• Unsatisfability Checking

{ φ₁,…,φ_n }

logically entails a sentence j, form the sentence

( φ₁ ∧…∧ φ_n → φ )

and check that it is valid.

(lovesAmyPat → lovesAmyQuincy) ∧ (ismonday → lovesAmyPat ∨ lovesAmyQuincy) → (ismonday → lovesAmyQuincy)

(φ₁ ∧…∧ φ_n ∧ ¬ φ)

and check that it is unsatisfiable .

• When the number of logical constants in a propositional language is large, the number of interpretations may be impossible to manipulate.

• In many cases, it is possible to create a “proof” of a conclusion from a set of premises that is much smaller than the truth table for the language;

• Moreover, it is often possible to find such proofs with less work than is necessary to check the entire truth table

• For example, the following expression is a pattern with metavariables φ and ψ.

φ → (ψ → φ)

• For example, the following is an instance of the preceding schema.

p →( q → p )

• Since the interpretations are not enumerated, time and space can often be saved

• One set of sentence schemata, called premises , and

• A second set of sentence schemata, called conclusions

φ → (ψ → φ)

(φ → (ψ → c)) → ((φ → ψ) → (φ → c))

(ψ → ¬ φ) → ((ψ → φ) → ¬ ψ)

(¬ ψ → ¬ φ) → ((¬ ψ → φ) → ψ)

(φ ↔ ψ) → (φ → ψ)

(φ ↔ ψ) → (ψ → φ)

(φ → ψ) → ((ψ → φ) → (ψ ↔ φ))

(φ ← ψ) ↔ (ψ → φ)

(φ ∨ ψ) ↔ (¬φ → ψ)

(φ ∧ ψ) ↔ ¬(¬φ ∨ ¬ψ)

• They all are valid

Δ ⊢ φ

If φ is provable from Δ, then Δ logically entails φ.

If Δ logically entails φ, then φ is provable from Δ.

• Starting from a set of premises Δ, we enumerate conclusions from this set

• If a sentence φ appears, then it is provable from Δ and is, therefore, a logical consequence

• If the negation of φ appears, then ¬φ is a logical consequence of Δ and φ is not logically entailed (unless Δ is inconsistent)

• Note that it is possible that neither φ nor ¬φ will appear

• Before the rule can be applied, the premises and conclusions must be converted to this form

• Example:

Abbreviated notation:

• l -literal, l c -complement of l

• C -clause (a set of literals)

• S -a clausal form (a set of clauses)

(1) If l appears in some clause of S , but l ^c does not appear in any clause, then, if we delete all clauses in S containing l , the new clausal form S' is satisfiable if and only if S is satisfiable

Example: Satisfiability of is equivalent to satisfiability of

(2) Suppose C = { l } is a unit clause and we obtain S' from S by deleting C and l ^c from all clauses that contain it; then, S is satisfiable if and only if S' is satisfiable

Example: is satisfiable iff is satisfiable

(3) If S contains two clauses C and C' , such that C is a subset of C' , we can delete C‘ without affecting the (un)satisfiability of S

Example: is satisfiable iff is satisfiable

Theorem : Every propositional formula can be transformed into an equivalent formula in CNF

1. Implications:

φ1 → φ2 → ¬φ1 ∨ φ2

φ1 ← φ2 → φ1 ∨ ¬φ2

φ1 ↔ φ2 → (¬φ1 ∨ φ2 ) ∧ (φ1 ∨ ¬φ2)

2. Negations:

¬¬φ → φ

¬(φ1 ∧ φ2 ) → ¬φ1 ∨ ¬φ2

¬(φ1 ∨ φ2 ) → ¬φ1 ∧ ¬φ2

3. Distribution:

φ1 ∨ (φ2 ∧ φ3 ) → (φ1 ∨ φ2) ∧ (φ1 ∨ φ3 )

(φ1 ∧ φ2) ∨ φ3 → (φ1 ∨ φ3 ) ∧ (φ2 ∨ φ3)

(φ1 ∨ φ2) ∨ φ3 → φ1 ∨ (φ2 ∨ φ3)

(φ1 ∧ φ2) ∧ φ3 → φ1 ∧ (φ2 ∧ φ3)

4. Operators:

φ1 ∨... ∨ φn → {φ1,...,φn}

φ1 ∧ ...∧ φn → {φ1}...{φn}

(p → q) → (¬q → ¬p)

into an equivalent formula in CNF

Solution:

C , the resolvent of C 1 ,C 2 is the clause

C 1 and C 2 are called the parent clauses of C.

The clauses

clash on P, ¬ P

C 1 ,C 2 also clash on Q, ¬ Q so, another way to find a resolvent for these two clauses is

Input : S – a set of clauses

Output : “S is satisfiable” or “S is not satisfiable”

¬[(p → q) → (¬q → ¬p)]

is not satisfiable.

(2) Show, using resolution, that

3. C is the empty clause

ILLUSTRATION BY LARGER EXAMPLE

(a) “If I eat spicy foods, then I have strange dreams.” “I have strange dreams if there is thunder while I sleep.” “I did not have strange dreams.”

(b) “I am dreaming or hallucinating.” “I am not dreaming.” “If I am hallucinating, I see elephants running down the road.”

(c) “If I work, it is either sunny or partly sunny.” “I worked last Monday or I worked last Friday.” “It was not sunny on Tuesday.” “It was not partly sunny on Friday.”

• s, ‘I eat spicy foods’

• d, ‘I have strange dreams’

• t, ‘There is thunder while I sleep’

• d, ‘I am dreaming’

• h, ‘I am hallucinating’

• e, ‘I see elephants running down the road’

• wm, ‘I worked last Monday’

• wf , ‘I worked last Friday’

• sm, ‘It was sunny last Monday’

• st, ‘It was sunny last Tuesday’

• sf , ‘It was sunny last Friday’

• pm, ‘It was partly sunny last Monday’

• pf , ‘It was partly sunny last Friday’

EXTENSIONS

• Propositional logic does not capture the internal structure of the propositions

• It is not possible to work with units smaller than a proposition

• “A Mercedes Benz is a Car” and “A car drives” are two individual, unrelated propositions

• We cannot conclude “A Mercedes Benz drives”

• But often this is not very efficient

• I.e. Car(Mercedes Benz).

• When the atomic sentences of propositional logic are broken up into terms, variables, predicates, and quantifiers, they yield first-order logic , which keeps all the rules of propositional logic and adds some new ones

SUMMARY

• Propositional logic commits only to the existence of facts that may or may not be the case in the world being represented

• Propositional logic quickly becomes impractical, even for very small worlds

• Syntax: Vocabulary for expressing concepts without ambiguity

• Semantics: Connection to what we're reasoning about

• Interpretation - what the syntax means

• Reasoning: How to prove things

• What steps are allowed

REFERENCES

• First-Order Logic and Automated Theorem Proofing (2nd edition) by Melvin Fitting

• Mathematical Logic for Computer Science (2nd edition) by Mordechai Ben-Ari

• http://www.springer.com/computer/foundations/book/978-1-85233-319-5

• Propositional Logic at The Internet Encyclopedia of Philosophy

• http://www.iep.utm.edu/p/prop-log.htm

• http://en.wikipedia.org/wiki/Propositional_calculus

Questions?

Predicate Logic

• Syntax

• Semantics

• Inference

MOTIVATION

Anyone standing in the rain will get wet.

and then use this knowledge. For example, suppose we also learn that

Jan is standing in the rain.

P /\ Q → R

Then, given P /\ Q , we could indeed conclude R . But now, suppose we were told

Pat is standing in the rain.

• It's the internal structure of these propositions that make the reasoning valid.

• But in propositional calculus we don't have anything else to talk about besides propositions!

⇒ A more expressive logic is needed

⇒ Predicate logic (occasionally referred to as First-order logic (FOL) )

SYNTAX

• Names of specific objects

• E.g. doreen, gord, william, 32

• Map objects to objects

• E.g. father(doreen), age(gord), max(23,44)

• For statements about unidentified objects or general statements

• E.g. x, y, z, …

• Constants: Any constant is a term

• Variables: Any variable is a term

• Functions: Any expression f(t1,…,tn) of n arguments (where each argument is a term and f is a function of arity n ) is a term

• c

• f(c)

• g(x,x)

• g(f(c), g(x,x))

• Likes(george, kate)

• Likes(x,x)

• Likes(joe, kate, susy)

• Friends (father_of(david), father_of(andrew))

• Negation: ¬p („it is not the case that p“)

• Conjunction: p ∧ q („p and q“)

• Disjunction: p ∨ q („p or q“)

• Implication: p → q („p implies q“ or “q if p“)

• Equivalence: p ↔ q („p if and only if q“)

• Apply to sentence containing variable

• “for all”: ∀

• “there exists”: ∃

• ∃ x: Mother(art) = x

• ∀ x ∀ y: Mother(x) = Mother(y) → Sibling(x,y)

• ∃ y ∃ x: Mother(y) = x

∀x∀y(P(f(x)) → ¬(P(x)) → Q(f(y), x, z)))

Semantics

• The Valuation function can be used for describing value assignments and constraints in case of nested quantifiers.

• The Valuation function otherwise determines the satisfaction of a formula only in case of open formulae.

Domain, relational Structure, Universe

D          finite set of Objects      d ¹, d ², ... , d ⁿ

R,...      Relations over D       R ⊆ D ⁿ

F,...       Functions over D       F: D ⁿ → D

Basic Interpretation Mapping

constant            I [c] = d           Object

function            I [f] = F           Function

predicate          I [P] = R          Relation

Valuation V

variable V(x) = d ∈ D

Next, determine the semantics for complex terms and formulae constructively, based on the basic interpretation mapping and the valuation function above.

Terms with variables

I [f(t₁,...,t_n)) = I [f] (I [t₁],..., I [t_n]) = F(I [t₁],..., I [t_n]) ∈D

where I[t_i] = V(t_i) if t_i is a variable

Atomic Formula

I [P(t₁,...,t_n)]           true if (I [t₁],..., I [t_n]) ∈ I [P] = R

Negated Formula

I [¬α]                      true if I [α] is not true

Complex Formula

I[α∨β]                    true if I [α] or I [β] true

I [α∧β]                   true if I [α] and I [β] true

I [α→β]                 if I [α] not true or I [β] true

Quantified Formula (relative to Valuation function)

I [∃x:α]	true if α is true with V’(x)=d for some d∈D where V’ is otherwise identical to the prior V.
I [∀x:α]	true if α is true with V’(x)=d for all d∈D and where V’ is otherwise identical to the prior V.

Note: ∀x∃y: α is different from ∃y∀x: α

In the first case ∀x∃y:α , we go through all value assignments V'(x), and for each value assignment V'(x) of x, we have to find a suitable value V'(y) for y.

In the second case ∃y∀x:α, we have to find one value V'(y) for y, such that all value assignments V'(x) make α true.

Given is an interpretation I into a domain D with a valuation V, and a formula φ .

We say that:

φ is satisfied in this interpretation       or

this interpretation is a model of φ        iff

I[φ] is true.

That means the interpretation function I into the domain D (with valuation V) makes the formula φ true.

Given a set of formulae Φ and a formula α .

α is a logical consequence of Φ iff

α is true in every model in which Φ is true.

Notation:

Φ ⊧ α

That means that for every model (interpretation into a domain) in which Φ is true, α must also be true.

Inference

• Entailment is a relation that is concerned with the semantics of statements

• Q is entailed by KB (a set of premises or assumptions) if and only if there is no logically possible world in which Q is false while all the premises in KB are true

• Stated positively: Q is entailed by KB if and only if the conclusion is true in every possible world in which all the premises in KB are true

• Provability is a syntactic relation

• We can derive Q from KB if there is a proof consisting of a sequence of valid inference steps starting from the premises in KB and resulting in Q

• If Q is derived from a set of sentences KB using a set of inference rules, then Q is entailed by KB

• Hence, inference produces only real entailments, or any sentence that follows deductively from the premises is valid

• Only sentences that logically follow will be derived

• If Q is entailed by a set of sentences KB, then Q can also be derived from KB using the rules of inference

• Hence, inference produces all entailments, or all valid senteces can be proved from the premises

• All the sentences that logically follow can be derived

• Modus Ponens, Modus tollens etc.

• Modus Ponens, Modus Tollens

• Universal elimination

• Existential elimination

• Existential introduction

• Generalized Modus Ponens (GMP)

• Based on claiming 1.) that P is true, and 2.) the implication P → Q , we can conclude that Q is true.

• If P, then Q. P, therefore, Q

• Example:

RegularlyAttends(joe, lecture),

RegularlyAttends(joe, lecture) → Pass(joe, lecture)

Allow us to conclude:

Pass(joe, lecture)

• We again make two claims. 1.) The implication P → Q, and 2.) that Q is false. We can conclude that P is false as well.

• If P , then Q . ¬Q Therefore, ¬P

• Example:

• Detects(alarm, intruder) → GoesOff(alarm),

• ¬GoesOff(alarm)

• Allows us to conclude:

• ¬Detects(alarm, intruder)

• If ∀x P(x) is true, then P(c) is true, where c is any constant in the domain of x

• Variable symbol can be replaced by any ground term

• ∀x RegularlyAttends(x, lecture) → Pass(x, lecture)

• Allow us to conclude (assuming Joe is in the domain of x):

• RegularlyAttends(joe, lecture) → Pass(joe, lecture)

• From ∃x P(x) infer P(c)

• Note that the variable is replaced by a brand-new constant not occurring in this or any other sentence in the KB

• Also known as skolemization; constant is a skolem constant

• In other words, we don’t want to accidentally draw other inferences by introducing the constant

• Convenient to use this to reason about the unknown object, rather than constantly manipulating the existential quantifier

• ∃x Pass(x)

• Allows us to conclude:

• Pass(someStudent) , where someStudent is a new constant

• Eats(Ziggy, IceCream)

• ∃x Eats(Ziggy,x)

• E.g, from P(c) and Q(c) and ∀ x (P(x) ∧ Q(x)) → R(x) derive R(c)

• subst(θ, α) denotes the result of applying a set of substitutions defined by θ to the sentence α

• A substitution list θ = {v₁/t₁, v₂/t₂, ..., v_n/t_n} means to replace all occurrences of variable symbol v_i by term t_i

• Substitutions are made in left-to-right order in the list

• subst ({x/IceCream, y/Ziggy}, eats(y,x)) = eats (Ziggy, IceCream)

• atomic sentences P₁, P₂, ..., P_N

• implication sentence (Q₁ ∧ Q₂ ∧ ... ∧ Q_N) → R

• Q₁, ..., Q_N and R are atomic sentences

• substitution subst(θ, P_i) = subst(θ, Q_i) for i=1,...,N

• Derive new sentence: subst( θ , R)

• Example: C₁ ∨ … ∨ C_n

• Example: ¬C₁ ∨ … ∨ ¬C_n ∨ H

• KB ⊨ Q ↔ KB ⊢ Q

• Gödel proved that there exists a complete proof system for FOL.

• Gödel did not come up with such a concrete proof system.

• If there’s a proof, we’ll halt with it (eventually)

• However, If there is no proof (i.e. a statement does not follow from a set of premises), the attempt to prove it may never halt

• We cannot distinguish between the non-existence of a proof or the failure of an implementation to simply find a proof in reasonable time.

• Theoretical completeness of an inference procedure does not make a difference in this cases

• Does a proof simply take too long or will the computation never halt anyway?

ILLUSTRATION BY LARGER EXAMPLE

“Anyone passing his Intelligent System exam and winning the lottery is happy. But any student who studies for an exam or is lucky can pass all his exams. John did not study but John is lucky. Anyone who is lucky wins the lottery. Mary did not win the lottery, however Mary passed her IS exam. Gary won the lottery. Gary, John, and Mary are all students.„

6. Pose queries to the inference procedure

• Is John happy?

Happy(John) ?

• Is Mary happy? Is she lucky?

Happy(Mary), Lucky(Mary)?

• Did every student pass the IS exam?

∃x Student(x) ∧ Pass(x, IS) ?

• Specific inference procedures (e.g. Resolution ) can be used to systematically answer those queries (see next lecture)

EXTENSIONS

SUMMARY

• Each interpretation of predicate logic includes a domain of discourse over which the quantifiers range.

REFERENCES

• M. Fitting: First-Order Logic and Automated Theorem Proving, 1996 Springer-Verlag New York (Chapter 5)

• Michael Huth and Mark Ryan, Logic in Computer Science(second edition) , 2004, Cambridge University Press

• http://plato.stanford.edu/entries/model-theory/

• http://en.wikipedia.org/wiki/First-order_logic

Questions?

REASONING

• Introduction to Theorem Proving and Resolution

• Description Logics

• Logic Programming

MOTIVATION

• We can do logical reasoning with a limited set of simple (computable) rules in restricted formal languages like First-order Logic (FOL)

• Computers can do reasoning

• It is expressive enough to capture many foundational theorems of mathematics

• Many real-world problems can be formalized in FOL

• It is the most expressive logic that one can adequately approach with automated theorem proving techniques

• Description Logics

• Syntactic fragments of FOL

• Focus on decidability and optimized algorithms key reasoning tasks (terminological reasoning / schema reasoning)

• Logic Programming

• Provides different expressivity than classical FOL (non-monotonic reasoning with non-classical negation)

• Provides a very intuitive way to model knowledge

• Efficient reasoning procedures for large data-sets

Theorem Proving and Resolution, Description Logics, and Logic Programming

Introduction to Theorem Proving and Resolution

where C is a conclusion sequent, and P _i ‘s are premises sequents .

• If an infererence rule does not have any premises that are taken to be true (called an axiom ), its conclusion automatically holds.

• Example:
  Modus Ponens: From P, P → Q infer Q,
  Universal instantiation: From (∀x)p(x) infer p(A)

• Expressions that can be derived from the axioms and the rules of inference.

• To prove a statement we attempt to refute its negation

• This means that every interpretation I that satisfies KB also satisfies Q

• Any interpretation I only satisfies either Q or ¬ Q, but not both

• Therefore, if in fact KB ⊧ Q holds , an interpretation that satisfies KB , satisfies Q and does not satisfy ¬ Q

⇒ Hence KB ∪ { ¬ Q } is unsatisfiable, i.e., it is false under all interpretations

• A clause is a disjunction of literals (implicitly universally quantified)

• E.g. : l₁ ∨ … ∨ l_n

• A formula in clause normal form conjunction of a set of clauses

• E.g.: C₁ ∧ … ∧ C_n = (l_n ∨ … ∨ l_m) ∧ … ∧ (l_i ∨ … ∨ l_j)

• Put the premises or axioms into clause normal form (CNF)

• Add the negation of the to be proven statement, in clause form, to the set of axioms

• Resolve these clauses together, using the resolution rule , producing new clauses that logically follow from them

• Derive a contradiction by generating the empty clause.

• The substitutions used to produce the empty clause are those under which the opposite of the negated goal is true

• Two literals are said to be complements if one is the negation of the other (in the following, ai is taken to be the complement to bj).

• The resulting clause contains all the literals that do not have complements. Formally:

• Where a₁, …, a_n, b₁, …, b_m are literals, and a_i is the complement to b_j

• A literal and its negation produce a resolvent only if they unify under some substitution σ.

• σ Is then applied to the resolvent

• However, only the pair of literals that are resolved upon can be removed: All other pairs of literals remain in the resolvent clause

• P(x, f(a)) v P(x, f(y)) v Q(y) and ¬P(z, f(a)) v ¬ Q(z)

• P(x, f(a)) and ¬P(z, f(a)) unify with substitution σ = {x/z}

• Therefore, we derive the resolvent clause (to which σ is applied):

• P(z, f(y)) v Q(y) v ¬ Q(z)

• a ↔ b = (a → b) ∧ (b → a)

• a → b = ¬ a ∨ b

• ¬ ( ¬ a) = a

• ¬ (a ∧ b) = ¬ a ∨ ¬ b

• ¬ (a ∨ b) = ¬ a ∧ ¬ b

• ¬ ( ∃ X) a(X) = ( ∀ X) ¬ a(X)

• ¬ ( ∀ X) b(X) = ( ∃ X) ¬ b(X)

• ( ∀ X) a(X) ∨ ( ∀ X) b(X) = ( ∀ X) a(X) ∨ ( ∀ Y) b(Y)

• A formula is inn prenex normal form if it is written as a string of quantifiers followed by a quantifier-free part

• Skolem constant

• (∃X)(dog(X)) may be replaced by dog(fido) where the name fido is picked from the domain of definition of X to represent that individual X.

• Skolem function

• If the predicate has more than one argument and the existentially quantified variable is within the scope of universally quantified variables, the existential variable must be a function of those other variables.

(∀X)(∃Y)(mother(X,Y)) ⇒ (∀X)mother(X,m(X))
(∀X)(∀Y)(∃Z)(∀W)(foo (X,Y,Z,W))
⇒ (∀X)(∀Y)(∀W)(foo(X,Y,f(X,Y),w))

(a ∧ b) ∨ (c ∧ d)

= (a ∨ (c ∧ d)) ∧ (b ∨ (c ∧ d))

= (a ∨ c) ∧ (a ∨ d) ∧ (b ∨ c) ∧ (b ∨ d)

(∀X)(a(X) ∧ b(X)) = (∀X)a(X) ∧ (∀ Y)b(Y)

• “Fido is a dog.”

• “All dogs are animals.”

• “All animals will die.”

• Changing premises to predicates

• ∀ (x) (dog(X) → animal(X))

• dog(fido)

• Modus Ponens and {fido/X}

• animal(fido)

• ∀ (Y) (animal(Y) → die(Y))

• Modus Ponens and {fido/Y}

• die(fido)

• Convert predicates to clause normal form

	Predicate form	Clause form
	1. ∀ (x) (dog(X) → animal(X))	¬ dog(X) ∨ animal(X)
	2. dog(fido)	dog(fido)
	3. ∀ (Y) (animal(Y) → die(Y))	¬ animal(Y) ∨ die(Y)

• Negate the conclusion

4. ¬ die(fido)                      ¬ die(fido)

• However, it cannot , in general, be used to generate all logical consequences of a set axioms

• Also, the resolution cannot be used to prove that a given sentence is not entailed by a set of axioms

• The decision which clauses will be resolved against which others define the operators in the space

• A search method is required

• N clauses → N² ways of combinations or checking to see whether they can be combined