Artificial Intelligence 2

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)

Questions & Answers ???????

Recently Viewed Presentations

  • Modeling Consumer Decision Making and Discrete Choice Behavior

    Modeling Consumer Decision Making and Discrete Choice Behavior

    Nonparametric Regression. Klein and Spady Model. Probit. Logit. Bivariate Probit. Recursive Bivariate Probit. Multivariate Probit. Sample Selection. Panel Probit. Central PropositionA Utility Based Approach. Observed outcomes partially reveal underlying preferences.
  • Chapter 2 Interpreting Social Problems: Aging Social Problems:

    Chapter 2 Interpreting Social Problems: Aging Social Problems:

    Define ourselves and others Relationships Self-concept Development of Symbolic Interactionism Charles Horton Cooley (1864-1929) Looking-glass self George Herbert Mead (1863-1931) Role of the other and generalized other Peter Berger (1929-) and Thomas Luckmann (1927-) Social construction of reality Charles Horton...
  • Overall Planned effort -in days for WSEI

    Overall Planned effort -in days for WSEI

    Stage 1 - Socio-demographic survey - filled by all subjects.. Stage 2 - Depending on survey's results, exploration of 1 st layer - exploration of interests. In accordance with the results from this layer and responds for survey'squestions, subject is...
  • The Impact of Dams and Reservoirs on Public Health

    The Impact of Dams and Reservoirs on Public Health

    Malaria Water-washed Preventable by increased hand-washing eg. trachoma Dams' Threat to Public Health Stagnant water in reservoirs and irrigation ditches provide habitat for vectors Constant supply of water - Dry season no longer limits vectors Relocated population Merowe Health Impact...
  • What kind of people are we?

    What kind of people are we?

    The Ethical Leadership Commission. Amongst others. Leora Cruddas . FASNA. Professor Becky Francis . UCL IoE. The Rev Nigel Genders . C of E. Anne Lyons . NAHT. Dr Peter Kent
  • Introducing Microsoft 365 A1 - mepnprod.azureedge.net

    Introducing Microsoft 365 A1 - mepnprod.azureedge.net

    Choose from a great selection of devices with Windows 10 Pro Education and Windows 10 S - Meagan Jones. Third Grade Teacher. ... Educators will now have an easy way to reuse their previous and existing Teams. When clicking on...
  • The Global Aviation Maintenance Industry: Overview and Issues

    The Global Aviation Maintenance Industry: Overview and Issues

    : Directs FAA to promote U.S. safety standards abroad and work with foreign governments to facilitate acceptance of FAA approvals and standards, report to Congress on international engagement Sec. 1956
  • What do we do when punishment and reward

    What do we do when punishment and reward

    Louise Bomber - Writes a series of books about attachment and the classroom/schools. Inside I'm Hurting. What About Me? Attachment Research Consortium - annual conference held which has some fabulous speakers. John Timpson is on the board as is Andy...