First-Order Logic

Last Time Logical agents apply inference to a knowledge base to derive new information and make decisions Entailment vs. Inference Two ways to prove a...

0 downloads 219 Views 355KB Size
First-Order Logic Chapter 8 (Please turn your mobile devices to silent. Thanks!) CS 3243 - FOL and Prolog

1

Last Time    

Logical agents apply inference to a knowledge base to derive new information and make decisions Entailment vs. Inference

 

Two ways to prove a query 1.  Application of inference rules 2.  Model checking

 

Soundness and Completeness as conditions for inference

 

Resolution is complete for propositional logic in CNF Forward, backward chaining are linear-time, complete for Horn clauses

 

CS 3243 - FOL and Prolog

2

Outline          

Why FOL? Syntax and semantics of FOL Using FOL Wumpus world in FOL Knowledge engineering in FOL

CS 3243 - FOL and Prolog

3

Pros and cons of propositional logic  Propositional logic is declarative  Propositional logic allows partial/disjunctive/negated information  

(unlike most data structures and databases)

 Propositional logic is compositional:  

meaning of B1,1 ∧ P1,2 is derived from meaning of B1,1 and of P1,2

 Meaning in propositional logic is context-independent  

(unlike natural language, where meaning depends on context)

 Propositional logic has very limited expressive power    

(unlike natural language) E.g., cannot say "pits cause breezes in adjacent squares“   except

by writing one sentence for each square

CS 3243 - FOL and Prolog

4

First-order logic    

Whereas propositional logic assumes the world contains facts, first-order logic (like natural language) assumes the world contains  

  One to one mapping

 

Objects: people, houses, numbers, colors, baseball games, wars, … Relations: red, round, prime, brother of, bigger than, part of, comes between, … Functions: father of, best friend, one more than, plus, …

CS 3243 - FOL and Prolog

5

Syntax of FOL: Basic elements              

Constants KingJohn, 2, NUS,... Predicates Brother, >,... Functions Sqrt, LeftLegOf,... Variables x, y, a, b,... Connectives ¬, ⇒, ∧, ∨, ⇔ Equality = Quantifiers ∀, ∃ CS 3243 - FOL and Prolog

6

Atomic sentences Atomic sentence = predicate (term1,...,termn) or term1 = term2 Term = function (term1,...,termn) or constant or variable  

Functions can be viewed as complex names for constants

E.g., Brother(KingJohn,RichardTheLionheart) > (Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))

CS 3243 - FOL and Prolog

7

Complex sentences  

Made from atomic sentences using connectives ¬S, S1 ∧ S2, S1 ∨ S2, S1 ⇒ S2, S1 ⇔ S2,

e.g., Sibling(KingJohn,Richard) ⇒ Sibling (Richard,KingJohn) >(1,2) ∨ ≤ (1,2) >(1,2) ∧ ¬ >(1,2)

CS 3243 - FOL and Prolog

8

Truth in first-order logic  

Sentences are true with respect to a model and an interpretation

 

Model contains objects (domain elements) and relations among them

 

Interpretation specifies referents for constant symbols predicate symbols function symbols

 

→ → →

objects relations functional relations

An atomic sentence predicate(term1,...,termn) is true iff the objects referred to by term1,...,termn are in the relation referred to by predicate

CS 3243 - FOL and Prolog

9

Model Example

CS 3243 - FOL and Prolog

10

Universal quantification  



Everyone at NUS is smart: ∀x At(x,NUS) ⇒ Smart(x)  

∀x P is true in a model m iff P is true with x being each possible object in the model

 

Roughly speaking, equivalent to the conjunction of instantiations of P ∧ ∧ ∧ ...

At(KingJohn,NUS) ⇒ Smart(KingJohn) At(Richard,NUS) ⇒ Smart(Richard) At(NUS,NUS) ⇒ Smart(NUS)

CS 3243 - FOL and Prolog

11

Blank spaces to fill in on this slide

A common mistake to avoid  

Typically, ⇒ is the main connective with ∀

 

Common mistake: using ∧ as the main connective with ∀: ∀x At(x,NUS) ∧ Smart(x) means “Everyone is at NUS and everyone is smart”

CS 3243 - FOL and Prolog

12

Existential quantification  



Someone at NUS is smart: ∃x At(x,NUS) ∧ Smart(x)  

∃x P is true in a model m iff P is true with x being some possible object in the model

 

Roughly speaking, equivalent to the disjunction of instantiations of P ∨ ∨ ∨ ...

At(KingJohn,NUS) ∧ Smart(KingJohn) At(Richard,NUS) ∧ Smart(Richard) At(NUS,NUS) ∧ Smart(NUS)

CS 3243 - FOL and Prolog

13

Blank spaces to fill in on this slide

Another common mistake  

Typically, ∧ is the main connective with ∃

 

Common mistake: using ⇒ as the main connective with ∃: ∃x At(x,NUS) ⇒ Smart(x) is true if there is anyone who is not at NUS!

CS 3243 - FOL and Prolog

14

Properties of quantifiers  

∀x ∀y is the same as ∀y ∀x ∃x ∃y is the same as ∃y ∃x

 

∃x ∀y is not the same as ∀y ∃x

 

∃x ∀y Loves(x,y)  

“There is a person who loves everyone in the world”

∀y ∃x Loves(x,y)  

     

“Everyone in the world is loved by at least one person”

Quantifier duality: each can be expressed using the other ∀x Likes(x,IceCream) ¬∃x ¬Likes(x,IceCream) ∃x Likes(x,Broccoli) ¬∀x ¬Likes(x,Broccoli)

CS 3243 - FOL and Prolog

15

Equality  

term1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same object

 

E.g., definition of Sibling in terms of Parent: ∀x,y Sibling(x,y) ⇔ [¬(x = y) ∧ ∃m,f ¬ (m = f) ∧ Parent(m,x) ∧ Parent(f,x) ∧ Parent(m,y) ∧ Parent(f,y)]

CS 3243 - FOL and Prolog

16

Using FOL In the kinship domain:  

Brothers are siblings ∀x,y Brother(x,y) ⇒ Sibling(x,y)

 

One's mother is one's female parent ∀m,c Mother(c) = m ⇔ (Female(m) ∧ Parent(m,c))

 

“Sibling” is symmetric ∀x,y Sibling(x,y) ⇔ Sibling(y,x) CS 3243 - FOL and Prolog

17

Using FOL The set domain:                

∀s Set(s) ⇔ (s = {} ) ∨ (∃x,s2 Set(s2) ∧ s = {x|s2}) ¬∃x,s {x|s} = {} ∀x,s x ∈ s ⇔ s = {x|s} ∀x,s x ∈ s ⇔ [ ∃y,s2} (s = {y|s2} ∧ (x = y ∨ x ∈ s2))] ∀s1,s2 s1 ⊆ s2 ⇔ (∀x x ∈ s1 ⇒ x ∈ s2) ∀s1,s2 (s1 = s2) ⇔ (s1 ⊆ s2 ∧ s2 ⊆ s1) ∀x,s1,s2 x ∈ (s1 ∩ s2) ⇔ (x ∈ s1 ∧ x ∈ s2) ∀x,s1,s2 x ∈ (s1 ∪ s2) ⇔ (x ∈ s1 ∨ x ∈ s2) CS 3243 - FOL and Prolog

18

Interacting with FOL KBs  

Suppose a wumpus-world agent is using an FOL KB and perceives a smell and a breeze (but no glitter) at t=5: Tell(KB,Percept([Smell,Breeze,None],5)) Ask(KB,∃a BestAction(a,5))

i.e., does the KB entail some best action at t=5?  

Answer: Yes, {a/Shoot}

 

Given a sentence S and a substitution σ, Sσ denotes the result of plugging σ into S; e.g.,

 

← substitution (binding list)

S = Smarter(x,y) σ = {x/Hillary,y/Bill} Sσ = Smarter(Hillary,Bill)  

Ask(KB,S) returns some/all σ such that KB╞ σ CS 3243 - FOL and Prolog

19

KB for the wumpus world  

Perception  

 

∀t,s,b Percept([s,b,Glitter],t) ⇒ Glitter(t)

Reflex  

∀t Glitter(t) ⇒ BestAction(Grab,t)

CS 3243 - FOL and Prolog

20

Deducing hidden properties  

∀x,y,a,b Adjacent([x,y],[a,b]) ⇔ [a,b] ∈ {[x+1,y], [x-1,y],[x,y+1],[x,y-1]}

Properties of squares:   ∀s,t At(Agent,s,t) ∧ Breeze(t) ⇒ Breezy(s) Squares are breezy near a pit:  

Diagnostic rule - infer cause from effect ∀s Breezy(s) ⇒ ∃r Adjacent(r,s) ∧ Pit(r)

 

Causal rule - infer effect from cause ∀r Pit(r) ⇒ [∀s Adjacent(r,s) ⇒ Breezy(s) ] CS 3243 - FOL and Prolog

21

Knowledge engineering in FOL 1.  2.  3.  4.  5.  6.  7. 

Identify the task Assemble the relevant knowledge Decide on a vocabulary of predicates, functions, and constants Encode general knowledge about the domain Encode a description of the specific problem instance Pose queries to the inference procedure and get answers Debug the knowledge base

CS 3243 - FOL and Prolog

22

The electronic circuits domain One-bit full adder

CS 3243 - FOL and Prolog

23

The electronic circuits domain 1. 

Identify the task  

2. 

Assemble the relevant knowledge    

3. 

Does the circuit actually add properly? (circuit verification)

Composed of wires and gates; Types of gates (AND, OR, XOR, NOT) Irrelevant: size, shape, color, cost of gates

Decide on a vocabulary  

Alternatives: Type(X1) = XOR Type(X1, XOR) XOR(X1)

CS 3243 - FOL and Prolog

24

The electronic circuits domain 4. 

Encode general knowledge of the domain          

 

 

 

∀t1,t2 Connected(t1, t2) ⇒ Signal(t1) = Signal(t2) ∀t Signal(t) = 1 ∨ Signal(t) = 0 1≠0 ∀t1,t2 Connected(t1, t2) ⇒ Connected(t2, t1) ∀g Type(g) = OR ⇒ Signal(Out(1,g)) = 1 ⇔ ∃n Signal(In (n,g)) = 1 ∀g Type(g) = AND ⇒ Signal(Out(1,g)) = 0 ⇔ ∃n Signal(In (n,g)) = 0 ∀g Type(g) = XOR ⇒ Signal(Out(1,g)) = 1 ⇔ Signal(In (1,g)) ≠ Signal(In(2,g)) ∀g Type(g) = NOT ⇒ Signal(Out(1,g)) ≠ Signal(In(1,g))

CS 3243 - FOL and Prolog

25

The electronic circuits domain 5. 

Encode the specific problem instance Type(X1) = XOR Type(A1) = AND Type(O1) = OR

Type(X2) = XOR Type(A2) = AND

Connected(Out(1,X1),In(1,X2)) Connected(Out(1,X1),In(2,A2)) Connected(Out(1,A2),In(1,O1)) Connected(Out(1,A1),In(2,O1)) Connected(Out(1,X2),Out(1,C1)) Connected(Out(1,O1),Out(2,C1))

CS 3243 - FOL and Prolog

Connected(In(1,C1),In(1,X1)) Connected(In(1,C1),In(1,A1)) Connected(In(2,C1),In(2,X1)) Connected(In(2,C1),In(2,A1)) Connected(In(3,C1),In(2,X2)) Connected(In(3,C1),In(1,A2))

26

The electronic circuits domain 6. 

Pose queries to the inference procedure What are the possible sets of values of all the terminals for the adder circuit? ∃i1,i2,i3,o1,o2 Signal(In(1,C1)) = i1 ∧ Signal(In(2,C1)) = i2 ∧ Signal(In(3,C1)) = i3 ∧ Signal(Out(1,C1)) = o1 ∧ Signal(Out (2,C1)) = o2

7. 

Debug the knowledge base May have omitted assertions like 1 ≠ 0

CS 3243 - FOL and Prolog

27

Summary  

First-order logic:  

 

 

objects and relations are semantic primitives syntax: constants, functions, predicates, equality, quantifiers

Increased expressive power: sufficient to define wumpus world CS 3243 - FOL and Prolog

28

PROgramming in LOGic

A crash course in Prolog Slides edited from William Clocksin’s versions at Cambridge Univ.

29

CS 3243 - FOL and Prolog

What is Logic Programming?  

A type of programming consisting of facts and relationships from which the programming language can draw a conclusion. – 

– 

 

30

In imperative programming languages, we tell the computer what to do by programming the procedure by which program states and variables are modified. In contrast, in logical programming, we don’t tell the computer exactly what it should do (i.e., how to derive a conclusion). Userprovided facts and relationships allow it to derive answers via logical inference.

Prolog is the most widely used logic programming language.

CS 3243 - FOL and Prolog

Prolog Features  

 

   

Prolog uses logical variables. These are not the same as variables in other languages. Programmers can use them as ‘holes’ in data structures that are gradually filled in as computation proceeds. Unification is a built-in term-manipulation method that passes parameters, returns results, selects and constructs data structures. Basic control flow model is backtracking. Program clauses and data have the same form. – 

31

A Prolog program can also be seen as a relational database containing rules as well as facts. CS 3243 - FOL and Prolog

Example: Concatenate lists a and b

32

In an imperative language

list procedure cat(list a, list b) { list t = list u = copylist(a); while (t.tail != nil) t = t.tail; t.tail = b; return u; }

In a functional language

cat(a,b) ≡ if b = nil then a else cons(head(a), cat(tail(a),b))

In a declarative language

cat([], Z, Z). cat([H|T], L, [H|Z]) :- cat(T, L, Z). CS 3243 - FOL and Prolog

Outline          

33

General Syntax Terms Operators Rules Queries

CS 3243 - FOL and Prolog

Syntax    

.pl files contain lists of clauses Clauses can be either facts or rules

Predicate, arity 1 (male/1) Terminates a clause male(bob). Argument to predicate male(harry). child(bob,harry). Indicates a rule son(X,Y):male(X),child(X,Y). “and” No space between functor and argument list

34

CS 3243 - FOL and Prolog

Complete Syntax of Terms N.B. : case of Variables and terms and constants switched from FOL

Term Constant Names an individual

Atom alpha17 gross_pay john_smith dyspepsia + =/= ’12Q&A’

35

Number 0 1 57 1.618 2.04e-27 -13.6

Compound Term Names an individual that has parts

Variable Stands for an individual unable to be named when program is written

likes(john, mary) X book(dickens, Z, cricket) Gross_pay f(x) Diagnosis [1, 3, g(a), 7, 9] _257 -(+(15, 17), t) _ 15 + 17 - t A list is made of a terms, separated by commas and enclosed by brackets. CS 3243 - FOL and Prolog

Compound Terms The parents of Spot are Fido and Rover. parents(spot, fido, rover)

Functor (an atom) of arity 3.

components (any terms)

It is possible to depict the term as a tree: parents spot

36

fido

rover CS 3243 - FOL and Prolog

Examples of operator properties Prolog has shortcuts in notation for certain operators (especially arithmetic ones) Position Prefix: Infix:

Operator Syntax -2 5+17

Associativity: left, right, none. X+Y+Z is parsed as (X+Y)+Z because addition is left-associative.

Normal Syntax -(2) +(17,5)

These are all the same as the normal rules of arithmetic.

Precedence: an integer. X+Y*Z is parsed as X+(Y*Z) because multiplication has higher precedence.

37

CS 3243 - FOL and Prolog

Rules  

Rules combine facts to increase knowledge of the system

son(X,Y):male(X),child(X,Y).  

38

X is a son of Y if X is male and X is a child of Y

CS 3243 - FOL and Prolog

Interpretation of Rules Rules can be given a declarative reading or a procedural reading. Form of rule: Declarative reading:

Procedural reading:

39

H :- G1, G2, …, Gn. “That H is provable follows from goals G1, G2, …, Gn being provable.” “To execute procedure H, the procedures called by goals G1, G2, …, Gn are executed first.”

CS 3243 - FOL and Prolog

Queries      

Prolog is interactive; you load a KB and then ask queries Composed at the ?- prompt Returns values of bound variables and yes or no

?- son(bob, harry). yes ?- king(bob, france). no

40

CS 3243 - FOL and Prolog

Another example likes(george,kate). likes(george,susie). likes(george,wine).

41

?- likes(george,X) X = kate ; X = susie ; Answer: kate or susie or wine or false X = wine ; no CS 3243 - FOL and Prolog

Quantifiers When a variable appears in the specification of a database, the variable is universally quantified . Example: likes(susie,Y)

One interpretation: ‘Susie likes everyone’

For the existential quantifier one may do two things: a.  Enter the value directly into the database likes(george,Z) becomes likes(george,wine) b. Query the interpreter ?- likes(george,Z) returns a value for Z if one exists

42

CS 3243 - FOL and Prolog

Points to consider  

Variables are bound by Prolog, not by the programmer – 

 

Successive user prompts ; cause the interpreter to return all terms that can be substituted for X. –  – 

 

You can’t assign a value to a variable.

They are returned in the order found. Order is important

‘;’ means Or ‘,’ means And

PROLOG adopts the closed-world assumption: –  –  – 

All knowledge of the world is present in the database. If a term is not in the database assume is false. Prolog’s ‘yes’ = I can prove it, ‘no’ = I can’t prove it.

Two things to think about: When would the closed-world assumption lead to false inferences? When would the different ordering of solutions cause problems?

43

CS 3243 - FOL and Prolog

Blank spaces to fill in on this slide

Queries Can bind answers to questions to variables   Who is bob the son of? (X=harry) ?- son(bob, X).   Who is male? (X=bob, harry) ?- male(X).   Is bob the son of someone? (yes) _ = Anonymous ?- son(bob, _). variable, don’t care  

– 

44

No variables bound in this case!

what it’s bound to.

CS 3243 - FOL and Prolog

Lists The first element of a list can be separated from the tail using operator |  

Example: Match the list [tom,dick,harry,fred] to [X|Y] [X,Y|Z] [V,W,X,Y,Z|U] [tom,X|[harry,fred]]

45

then X = tom and Y = [dick,harry,fred] then X = tom, Y = dick, and Z = [harry,fred] will not match gives X = dick

CS 3243 - FOL and Prolog

Example: List Membership  

We want to write a function member that works as follows:

?- member(a,[a,b,c,d,e]) yes ?- member(a,[1,2,3,4]) no ?- member(X,[a,b,c]) X=a ; X=b ; X=c ; no

46

Can you do it?

CS 3243 - FOL and Prolog

Function Membership Solution Define two predicates:    

member(X,[X|T]). member(X,[Y|T]) :- member(X,T).

A more elegant definition uses anonymous variables:    

member(X,[X,_]). member(X,[_|T]) :- member(X,T).

Again, the symbol _ indicates that the contents of that variable is unimportant.

47

CS 3243 - FOL and Prolog

Notes on running Prolog You will often want to load a KB on invocation of Prolog   Use “consult(‘mykb.pl’).” at the “?-” prompt.   Or add it on the command line as a standard input “pl < mykb.pl” If you want to modify facts once Prolog is invoked:   Use “assert(p).”   Or “retract(p).” to remove a fact

48

CS 3243 - FOL and Prolog

Prolog Summary  

   

 

49

A Prolog program is a set of specifications in FOL. The specification is known as the database of the system. Prolog is an interactive language (the user enters queries in response to a prompt). PROLOG adopts the closed-world assumption How does Prolog find the answer(s)? We return to this next week in Inference in FOL

CS 3243 - FOL and Prolog