• No results found

CS344 : Introduction to Artificial Intelligence

N/A
N/A
Protected

Academic year: 2023

Share "CS344 : Introduction to Artificial Intelligence"

Copied!
18
0
0

Loading.... (view fulltext now)

Full text

(1)

CS344 : Introduction to Artificial Intelligence

Pushpak Bhattacharyya

CSE Dept., IIT Bombay

Lecture 5- Deduction Theorem

(2)

Formalization of propositional logic (review)

Axioms :

A1 A2 A3 Inference rule:

Given and A, write B A Proof is:

A sequence of i) Hypotheses ii) Axioms

iii) Results of MP A Theorem is an

Expression proved from axioms and inference rules

)) (

(A B A

))) (

) ((

)) (

((A B C A B A C

) )

)

(((A F F A

) (A B

(3)

Example: To prove

i) A1 : P for A and B

ii) A1: P for A and for B

iii)

A2: with P for A, for B and P for C

iv) MP, (ii), (iii)

v) MP, (i), (iv)

) (P P

) )

((P P P

P

)

(P P

P

))]

( ))

( ((

)) )

((

[(P P P P P P P P P

) (P P ))

( )

(

(P P P P P )

(P P

) (P P

(4)

Shorthand

1. is written as and called 'NOT P'

2. is written as and called

'P OR Q’

3. is written as and called

'P AND Q' Exercise: (Challenge)

- Prove that

¬P P F

) )

((P F Q (P Q)

) ))

(

((P Q F F (P Q)

)) (

( A

A

(5)

A very useful theorem (Actually a meta theorem, called deduction theorem)

Statement If

A1, A2, A3 ... An ├ B then

A1, A2, A3, ...An-1

├ is read as 'derives' Given

A1 A2 A3 . .. . An

B Picture 1

A1 A2 A3 . . .. An-1

Picture 2 B

An

B An

(6)

Use of Deduction Theorem Prove

i.e.,

├ F (M.P)

A├ (D.T)

(D.T)

Very difficult to prove from first principles, i.e., using axioms and inference rules only

)) (

( A

A

) )

((A F F

A

F A

A,

F F

A ) (

) )

((A F F

A

(7)

Prove i.e.

├ F

(D.T)

├ Q (M.P with A3)

P

) (P Q P

) )

((P F Q

P

F Q

F P

P, ,

F P

P, (Q F) F

Q F

P ) (

) )

((P F Q

P

(8)

More proofs

) )

((

) (

. 3

) (

) (

. 2

) (

) (

. 1

Q P

Q Q

P

P Q

Q P

Q P

Q P

(9)

Proof Sketch of the Deduction Theorem

To show that If

A1, A2, A3,… An |- B Then

A1, A2, A3,… An-1 |- An B

(10)

Case-1: B is an axiom

One is allowed to write A1, A2, A3,… An-1 |- B

|- B(AnB)

|- (AnB); mp-rule

(11)

Case-2: B is A

n

AnAn is a theorem (already proved) One is allowed to write

A1, A2, A3,… An-1 |- (AnAn) i.e. |- (AnB)

(12)

Case-3: B is A

i where (i <>n)

Since Ai is one of the hypotheses One is allowed to write

A1, A2, A3,… An-1 |- B

|- B(AnB)

|- (AnB); mp-rule

(13)

Case-4: B is result of MP

Suppose

B comes from applying MP on Ei and Ej

Where, Ei and Ej come before B in A1, A2, A3,… An |- B

(14)

B is result of MP

(contd)

If it can be shown that

A1, A2, A3,… An-1 |- An Ei and

A1, A2, A3,… An-1 |- (An (EiB)) Then by applying MP twice

A1, A2, A3,… An-1 |- An B

(15)

B is result of MP

(contd)

This involves showing that If

A1, A2, A3,… An |- Ei Then

A1, A2, A3,… An-1 |- An Ei

(similarly for AnEj)

(16)

B is result of MP

(contd)

Adopting a case by case analysis as before,

We come to shorter and shorter length proof segments eating into the body of

A1, A2, A3,… An |- B

Which is finite. This process has to terminate. QED

(17)

Important to note

Deduction Theorem is a meta-theorem (statement about the system)

PP is a theorem (statement belonging to the system)

The distinction is crucial in AI

Self reference, diagonalization

Foundation of Halting Theorem, Godel Theorem etc.

(18)

Example of ‘ of-about’

confusion

“This statement is false”

Truth of falsity cannot be decided

References

Related documents

[1] Peter Lucas, The Representation of Medical Reasoning Models in Resolution based Theorem Provers Artificial Intelligence Published Resolution-based Theorem Provers,

documents retrieved are ranked and thus the above expressions need to be modified.... Precision at

Bayesian Belief networks describe conditional independence among subsets of variables. allows combining prior

In this project ,a different approach is used to tackle the proposed p-Laplacian problem which is by the variational method by using the mountain pass theorem which

is in L, and hene ounting the number of perfet mathings in a planar graph is in GapL.. Our main theorem is similar in spirit to Theorem 1 in [MV97℄, though there are essential

 The agent has complete information of the domain (perception is perfect), actions are instantaneous and their effects are deterministic..  The agent knows the world completely,

• Execution of a plan: achieved through a data structure called Triangular Table....

Key words and phrases : Poisson limit theorem, Markov chain, finitary process, Jordan form, matrix limit theorem... The finitary processes form a fairly rich