程序代写代做代考 AI database prolog CMP2020M Artificial Intelligence

程序代写 CS代考 / AI代写, database, Prolog代写代考

CMP2020M Artificial Intelligence
Dr. Bashir Al-Diri
Dr. Marc Hanheide
Dr. Patrick Dickinson
Lincoln School of Computer Science

CM2020M Artificial Intelligence
 Introduction to AI
 Knowledge Representation
 Planning
 Logic Programming(1/3)  Games AI
 Probabilistic Reasoning
CMP2020M: Lecture 5 – Logic Programming

My Lectures
1. Propositional Calculus 2. Predicate Calculus
3. Prolog Programming
CMP2020M: Lecture 5 – Logic Programming

Lecture 5: – Logic Programming  What Is Logic Programming
 The Propositional Calculus  Syntax
 Semantics  Proofs
 Next week: Predicate calculus and Unification
CMP2020M: Lecture 5 – Logic Programming

What is Logic Programming?
 In logic programming, you present facts and rules to infer new facts by just ask questions.
 When you asked a question, the run time system searches through the database of facts and rules to determine (by logical deduction) the answer.
CMP2020M: Lecture 5 – Logic Programming

Example
 Given:
 “The red block is above the blue block”  “The green block is above the red block”
 Infer?
 “The green block is above the blue block”  “The blocks form a tower”
CMP2020M: Lecture 5 – Logic Programming

Logic consists of  A language
 tells us how to build up sentences (i.e., syntax), and what that sentences mean (i.e., semantics)
 An inference procedure
 which tells us which sentences are valid inference from given sentences
CMP2020M: Lecture 5 – Logic Programming

Propositional logic
 The syntax of propositional logic consists of  the propositional symbols:
P, Q, R, S, …  and connectives:
, , , , 
 The semantics is assigning a truth value (T or F) to each sentence.
CMP2020M: Lecture 5 – Logic Programming

Propositional calculus semantics
P
P
T
F
F
T
Truth table for the operator  Negation (not) CMP2020M: Lecture 5 – Logic Programming

Propositional calculus semantics
P
Q
PQ
T
T
T
T
F
F
F
T
F
F
F
F
Truth table for the operator  Conjunction (and) CMP2020M: Lecture 5 – Logic Programming

Propositional calculus semantics
P
Q
PQ
T
T
T
T
F
T
F
T
T
F
F
F
Truth table for the operator  Disjunction (or) CMP2020M: Lecture 5 – Logic Programming

Propositional calculus semantics
P
Q
PQ
T
T
T
T
F
F
F
T
T
F
F
T
Truth table for the operator  Implication CMP2020M: Lecture 5 – Logic Programming

Truth tables can be used to prove many other logical equivalences
Propositional calculus semantics
P
Q
PQ
T
T
T
T
F
F
F
T
F
F
F
T
Truth table for the operator  Equivalence (if and only if )
CMP2020M: Lecture 5 – Logic Programming

Truth table demonstrating the equivalence of PQ and PQ
P
Q
P
PQ
PQ
(PQ)=(PQ)
CMP2020M: Lecture 5 – Logic Programming

Truth table demonstrating the equivalence of PQ and PQ
P
Q
P
PQ
PQ
(PQ)=(PQ)
T
T
T
F
F
T
F
F
CMP2020M: Lecture 5 – Logic Programming

Truth table demonstrating the equivalence of PQ and PQ
P
Q
P
PQ
PQ
(PQ)=(PQ)
T
T
F
T
F
F
F
T
T
F
F
T
CMP2020M: Lecture 5 – Logic Programming

Truth table demonstrating the equivalence of PQ and PQ
P
Q
P
PQ
PQ
(PQ)=(PQ)
T
T
F
T
T
F
F
F
F
T
T
T
F
F
T
T
CMP2020M: Lecture 5 – Logic Programming

Truth table demonstrating the equivalence of PQ and PQ
P
Q
P
PQ
PQ
(PQ)=(PQ)
T
T
F
T
T
T
F
F
F
F
F
T
T
T
T
F
F
T
T
T
CMP2020M: Lecture 5 – Logic Programming

Truth table demonstrating the equivalence of PQ and PQ
P
Q
P
PQ
PQ
(PQ)=(PQ)
T
T
F
T
T
T
T
F
F
F
F
T
F
T
T
T
T
T
F
F
T
T
T
T
CMP2020M: Lecture 5 – Logic Programming

Tautology and Contradiction
 A tautology is a formula which is “always true“.
 It is true for every assignment of truth values to its simple
components.
 The opposite of a tautology is a contradiction, a formula which is “always false”.
 It is false for every assignment of truth values to its simple components.
CMP2020M: Lecture 5 – Logic Programming

Exercise 1
 Use a truth table to demonstrate the equivalence of
(PQ) and (PQ)
P
Q
PQ
(PQ)
P
Q
PQ
(PQ)  (PQ)
T
T
T
F
F
T
F
F
CMP2020M: Lecture 5 – Logic Programming

Exercise 1 : Answer
 Use a truth table to demonstrate the equivalence of (PQ) and (PQ)
P
Q
PQ
(PQ)
P
Q
PQ
(PQ)  (PQ)
T
T
T
F
F
F
F
T
T
F
T
F
F
T
F
T
F
T
T
F
T
F
F
T
F
F
F
T
T
T
T
T
The (PQ)  (PQ) is a tautology sentence CMP2020M: Lecture 5 – Logic Programming

Proofs in Propositional Calculus
 If it is sunny today, then the sun shines on the screen. If the sun shines on the screen, the blinds are brought down. The blinds are not down.
 Is it sunny today?
 P: It is sunny today.
 Q: The sun shines on the screen.
 R: The blinds are down.
 Given: PQ, QR, R
 Question: P
CMP2020M: Lecture 5 – Logic Programming

Proof using a truth table
Variables
Given
Trial Conclusions
P
Q
R
PQ
QR
R
P
P
T
T
T
T
T
F
T
F
T
T
F
F
F
T
T
F
T
F
F
F
T
F
F
F
CMP2020M: Lecture 5 – Logic Programming

Proof using a truth table
Variables
Given
Trial Conclusions
P
Q
R
PQ
QR
R
P
P
T
T
T
T
T
F
T
F
T
T
F
T
F
T
T
F
T
F
T
F
T
F
T
F
T
F
F
F
T
T
T
F
F
T
T
T
T
F
F
T
F
T
F
T
F
T
F
T
F
F
T
T
T
F
F
T
F
F
F
T
T
T
F
T
Given:
PQ
QR
R Question: P
CMP2020M: Lecture 5 – Logic Programming

Given: PQ, QR, R Question: P
Proof using a truth table
Variables
Given
Trial Conclusions
QR
R
P
P
Q
R
PQ
P
T
T
T
T
T
F
T
F
T
T
F
T
F
T
T
F
T
F
T
F
T
F
T
F
T
F
F
F
T
T
T
F
F
T
T
T
T
F
F
T
F
T
F
T
F
T
F
T
F
F
T
T
T
F
F
T
Answer:
F
F
F
T
T
T
F
T
It is not sunny today
CMP2020M: Lecture 5 – Logic Programming

Proof procedure
 The problem with proof using truth tables is that the number of rows required grows very quickly as the number of propositional variables increases (2n).
 A proof procedure is another method of proving statements using inference rules.
CMP2020M: Lecture 5 – Logic Programming

Inference rules
 Modus ponens
If P and P  Q are true, then infer Q.
P
Q
PQ
T
T
T
T
F
F
F
T
T
F
F
T
CMP2020M: Lecture 5 – Logic Programming

Inference rules
 Modus ponens
If P and P  Q are true, then infer Q.
 Modus tollens
If P  Q and Q are true, then infer P.
P
Q
PQ
T
T
T
T
F
F
F
T
T
F
F
T
CMP2020M: Lecture 5 – Logic Programming

Inference rules
 Modus ponens
If P and P  Q are true, then infer Q.
 Modus tollens
If P  Q and Q are true, then infer P.
 And elimination
If P  Q is true, then infer both P and Q are true
P
Q
PQ
T
T
T
T
F
F
F
T
F
F
F
F
CMP2020M: Lecture 5 – Logic Programming

Inference rules
 Modus ponens
If P and P  Q are true, then infer Q.
 Modus tollens
If P  Q and Q are true, then infer P.
 And elimination
If P  Q is true, then infer both P and Q are true
 And introduction
If both P and Q are true, then infer P  Q
P
Q
PQ
T
T
T
T
F
F
F
T
F
F
F
F
CMP2020M: Lecture 5 – Logic Programming

Proof using inference rules
 P: It is sunny today.
 Q: The sun shines on the screen.  R: The blinds are down.
 Given: PQ, QR, R
 Question: P
CMP2020M: Lecture 5 – Logic Programming

Modus tollens: If P  Q and Q are true, then infer P. Proof using inference rules
 PQ, QR, R Q
P
Given
Modus Tollens
Modus Tollens
So P is false
It is not sunny today
CMP2020M: Lecture 5 – Logic Programming

Exercise 2
 Symbolise the following propositions. The meaning of symbols chosen for statements also needs to be given:
 Terry likes Science-fiction and going to the Gym.
 Lectures are valuable if and only if they are structured carefully  Today is Thursday or Yesterday was Wednesday.
 If I do not work hard then I will not pass my AI exam.
CMP2020M: Lecture 5 – Logic Programming

Exercise 2: Answer
 Terry likes Science-fiction and going to the Gym.
 T : Terry likes Science fiction, G : Terry likes going to the gym TG
 Lectures are valuable if and only if they are structured carefully  L : Lectures are valuable, S : Lectures are structured carefully LS
 Today is Thursday or Yesterday was Wednesday.
 T : Today is Thursday, Y : Yesterday was Wednesday TY
 If I do not work hard then I will not pass my AI exam.  W : I work hard, A : I will pass my AI exam
 W  A
CMP2020M: Lecture 5 – Logic Programming

Exercise 3
 Consider the following statements:
 IF food is older than 7 days THEN it is unsafe to eat. The food is 8 days old.
 What can be deduced? why?
 What inference rule has been used?
CMP2020M: Lecture 5 – Logic Programming

Exercise 3: Answer
 Consider the following statements:
 IF food is older than 7 days THEN it is unsafe to eat. The food is 8 days old.
 What can be deduced? why?  F: food is older than 7 days.  E: food is safe to eat
 given:
 F E
F  Infer
 E
 The food is unsafe to eat
 What inference rule has been used?
 Modus Ponens : If P and P  Q are true, then infer Q.
CMP2020M: Lecture 5 – Logic Programming

Next lecture: Predicate Calculus
 Predicate Calculus  Unification
 Substitution
CMP2020M: Lecture 5 – Logic Programming

A little reading
 Luger, G.F. and Stubblefield, W.A., Artificial Intelligence – Structures and Strategies for Complex Problem Solving, (Addison-Wesley, 1998).
 Chapter 2 (3rd edition) ‘The Predicate Calculus’
 take care with alternative editions – chapter numbers differ, and later editions are by Luger only
CMP2020M: Lecture 5 – Logic Programming

Thank you for listening!
CMP2020M: Lecture 5 – Logic Programming

Related Posts