# Artificial Intelligence 2

Artificial Artificial Intelligence Intelligence Lecture 2 Logic & Prolog Predicate calculus syntax: terms, predicates, sentences semantics: interpretations, logical consequence, inference rules, proof procedures Logic programming Prolog Prolog facts & rules, SWI Prolog http://www.swi-prolog.org/ Symbolic AI (1) GOFAI relies on the Physical Symbol System Hypothesis: Intelligent activity is achieved through the use of symbol patterns to represent the problem operations on those patterns to generate potential solutions search to select a solution among the possibilities Symbolic AI (2)

An AI representation language must handle qualitative knowledge allow new knowledge to be inferred from facts & rules allow representation of general principles capture complex semantic meaning allow for meta-level reasoning e.g., Predicate Calculus (also, the basis of Prolog) Predicate Calculus the predicate calculus (PC) is a language for representing knowledge amenable to reasoning using inference rules the syntax of a language defines the form of statements the building blocks of statements in the PC are terms and predicates terms denote objects and properties truth symbols true constant symbols dave variable symbols X

function expressions false redBlock happy Person Answer1 mother(bob) plus(1,3) predicates define relationships between objects (arity defines # of args) mother/1 above/2 likes/2 Predicate calculus: sentences sentences are statements about the world propositions (predicates applied to terms) are sentences if S, S1 and S2 are sentences, then so are

S (negation NOT) S1 S2 (conjunction AND) S1 S2 (disjunction OR) S1 S2 (implication IF-THEN) X S (universal quantification FOR ALL X) X S (existential quantification THERE EXISTS X) male(dave) parent(dave, jack) happy(chris) parent(dave, jack) parent(dave, charlie) happy(chris) happy(chris) healthy(kelly) happy(kelly) X (healthy(X) happy(X)) CP parent(P, C) X parent(dave, X) Predicate calculus:

semantics (1) the semantics of a language defines the meaning of statements an interpretation assigns meaning to terms/sentences must focus on a particular domain (universe of objects) terms are assigned values from the domain constant an object in the domain variable a subset of the domain function symbol a function mapping args to an object in the domain predicate symbols are assigned mappings from args to true/false e.g. DOMAIN: students in this class patrick, bryanP, john, bryanJ, scott : mapped to actual people partner function : maps a students to his/her partner partner(patrick) bryanP, partner(bryanP) patrick

undergrad/1: maps a student to true if an undergrad, else false grad/1: maps a student to true if a grad student, else false male/1: maps a student to true if male, else false female/1: maps a student to true if female, else false Predicate calculus: semantics (2) interpretation assigns true/false value to sentences proposition assigned true/false according to predicate mapping S true if S is false, else false S1 S2

true if both S1 and S2 are true, else false S1 S2 true if either S1 or S2 are true, else false S1 S2 false if S1 is true and S2 is false, else true X S true if S is true for all assignments to X X S true if S is true for any assignment to X e.g. the following are all assigned true under the previous interpretation grad(scott) male(john) undergrad(john) female(bryanP) undergrad(patrick) undergrad(partner(patrick)) undergrad(bryanP) undergrad(bryanJ) X male(X)

G grad(G) X (undergrad(partner(X)) undergrad(X)) undergrad(patrick) Predicate calculus: logical consequence the semantics of the predicate calculus provides a basis for a formal theory of logical inference an interpretation that makes a sentence true satisfies it a set of expressions {S1, , Sn} logically implies S if every interpretation that satisfies {S1, , Sn} satisfies S equivalently, we could say S is a logical consequence of {S1, , Sn} shorthand notation: {S1, , Sn} S e.g., {itRainsgetWet, goSwimgetWet, itRainsgoSwim } getWet {P(human(P)mortal(P)), human(socrates)} mortal(socrates) Predicate calculus: inference proving logical consequence via interpretations is difficult requires reasoning over all interpretations

alternatively, a proof procedure can generate logical consequences a proof procedure is a combination of inference rules and an algorithm for applying the rules to generate logical consequences example inference rules: Modus Ponens: And Elimination: if S1S2 is true, then infer S1 and infer S2 And Introduction: if S1 and S2 are true, then infer S1S2 Universal Instantiation: if X p(X) is true, then infer p(a) for any a if S1 and S1S2 are true, then infer S2 Inference example initial knowledge: { P(human(P)mortal(P)), human(socrates) }

extend using Universal Instantiation { P(human(P)mortal(P)), human(socrates), human(socrates)mortal(socrates) } extend using Modus Ponens { P(human(P)mortal(P)), human(socrates), human(socrates)mortal(socrates), mortal(socrates) } Another inference example initial knowledge: { P(student(P)tired(P)), S(csmajor(S)overworked(S)), X(tired(X)overworked(X)testy(X)), student(patrick), csmajor(patrick) }

AI programming languages (1) there are 2 major programming language used for AI research LISP (List Processing) older (1957), more established in U.S. uses a functional style Prolog (Programming in Logic) newer (1971), more widely used in Europe & Asia uses a declarative style, a.k.a. logic programming attractive features: built-in notion of search general data structures powerful primitives for symbol manipulation AI programming languages (2) Prolog evolved out of the automated deduction community IDEAS: (1) focus on a subset of the predicate calculus programs are collections of logical statements & relations

(2) implement a simple but efficient proof procedure Prolog interpreter applies inference rules to perform deduction logic programming: computation = logical deduction from program statements Prolog Prolog programs are statements from the Horn clause subset of the predicate calculus facts (i.e., propositions) all variables are assumed to be universally quantified, so is implicit terminate each fact with a period male(dave). parent(dave, jack). mortal(X).

rules (i.e., implications of the form: P1 Pn C ) again, is implicit & terminate rule with a period slightly different notation in Prolog (to suit standard keyboards) (1) conclusion is on the left, (2) :- replaces , (3) comma replaces e.g., C :- P1, , Pn. happy(chris) :- healthy(chris). mortal(X) :- human(X). father(F, C) :- parent(F, C), male(F). grandfather(F, G) :- father(F, C), parent(C, G). Prolog's basic model of computation (1) the programmer states relations between objects as facts & rules parent(dave, charlie). parent(dave, jack). parent(laura, charlie). parent(laura, jack). male(dave).

male(charlie). female(laura). male(jack). father(dave, charlie) :- parent(dave, charlie), male(dave). mother(M, C) :- parent(M, C), female(M). Prolog's basic model of computation (2) the job of the Prolog interpreter is to receive queries and determine whether they are logical consequences of the facts & rules in simple case, merely looks up facts ?- parent(dave, charlie). Yes more generally, may need to perform inferences using the rules

?- father(dave, charlie). Yes ?- father(charlie, dave). No may even require picking the right instances of rules ?- mother(laura, charlie). Yes Prolog's basic model of computation (3) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% family.pro Dave Reed 1/25/02 %%% %%% Encodes family relations. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% parent(dave, charlie). parent(dave, jack). parent(laura, charlie). parent(laura, jack). male(dave).

male(charlie). male(jack). female(laura). father(F, C) :parent(F, C), male(F). mother(M, C) :parent(M, C), female(M). A Prolog program is just a database of facts & rules that define relations between objects % begins a comment in Prolog name files with .pro or .pl extensions good practice to group all definitions of the same relation together (some interpreters complain otherwise) since a period marks the end of a rule, can split across lines for readability Prolog environment (1) Welcome to SWI-Prolog (Version 4.0.11) Copyright (c) 1990-2000 University of Amsterdam.

Copy policy: GPL-2 (see www.gnu.org) For help, use ?- help(Topic). or ?- apropos(Word). ?- consult('a:/family.pro')). % a:/family.pro compiled 0.00 sec, 1,516 bytes Yes ?- parent(laura, charlie). Yes ?- mother(laura, charlie). SWI-Prolog is a free Prolog interpreter/environment contains integrated help facilities online HTML reference manual: http://www.swi-prolog.org/pldoc/ref man/ to start, click the desktop icon or go through the Program menu Prolog program files are simply text files, use your favorite text editor (e.g., NotePad)

can also integrate editor into SWI once a file is created, its knowledge (facts & rules) can be loaded by consulting that file Yes ?- mother(dave, charlie). No once the facts & rules have been consulted, can enter queries and the interpreter determines logical consequence Prolog environment (2) ?- father(Who, jack). Who = dave Yes ?- father(dave, Kid). queries can contain variables in order to match a fact/rule,

must instantiate the variable interpreter reports the binding Kid = charlie ; Kid = jack ; No ?- father(dave, X), mother(laura, X). X = charlie ; X = jack Yes ?- father(Dad, jack), mother(Mom, jack). Dad = dave Mom = laura Yes multiple answers are possible can step through them by hitting semi-colon after each semi-colon rejects the answer, instructs the interpreter to look for another can have conjunctive queries

evaluated left-to-right short-circuit evaluation Prolog environment (3) ?- consult('a:/family.pro'). % a:/family.pro compiled 0.05 sec, 124 bytes Yes after making changes to a file, can reconsult it to load changes Prolog only reports the # of new bytes consulted ?- consult('a:/ages.pro'). % a:/ages.pro compiled 0.00 sec, 500 bytes Yes ?- age(jack, Age). Age = 1 Yes ?- father(dave, Child), age(Child, Age). can consult more than one file to combine collections of facts & rules knowledge from both is

active useful when you have separate but related sources of knowledge Child = charlie Age = 4 ; Child = jack Age = 1 ; No ?- halt. halt exits from the Prolog environment Recursive relations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% family.pro Dave Reed 1/25/02 %%% %%% Encodes family relations. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% parent(winnie, dave). parent(jerry, dave). parent(dave, charlie). parent(dave, jack).

parent(laura, charlie). parent(laura, jack). male(dave). male(charlie). male(jack). female(laura). father(F, C) :parent(F, C), male(F). mother(M, C) :parent(M, C), female(M). ancestor(A,P) :parent(A,P). ancestor(A,P) :parent(A,C), ancestor(C,P). Prolog rules can define recursive relations e.g., an ancestor is a parent, grandparent, great grandparent, more concisely, an ancestor is either a parent, or the parent of an ancestor

note: a relation can be defined by more than one Prolog rule ?- ancestor(winnie, dave). Yes ?- ancestor(dave, jack). Yes ?- ancestor(winnie, jack). Yes Next Lecture Prolog programming unification/matching resolution tracing lists Read Chapter 14 Be prepared for a quiz on this weeks lecture (moderately thorough) the reading (superficial)