Sztuczna inteligencja

Temat 2/3

Reguły wnioskowania, rachunek zdań, rachunek predykatów, przetwarzanie zbioru klauzul, metody przeszukiwania przestrzeni rozwiązań

Wyrażenie zawierające zmienne, np.:

nazywane jest predykatem

P(n,m), R(q), S(s)

Dla określonych n,m,q,s predykaty mogą mieć wartość prawda lub fałsz.

Przykład:

System formalny posiada zbiór twierdzeń:

pojedynczy aksjomat S:

1 + 1 = 11

widać, że
jest twierdzeniem systemu S jeśli m + n = 2.

Załóżmy, że jest twierdzeniem dla wszystkich par (m,n), takich że m+n < p,

gdzie p jest pewną dodatnią liczbą całkowitą oraz m, n > 0;

Niech m' + n' = p i m'> 0, n'>0

Jeśli m'>1, to

jest twierdzeniem, bo (m'-1) + n' = p-1 < p

Zastosowanie reguły r₁ daje :

Definicje

System formalny
,

gdzie:

1)
, gdzie p_i zmienne zdaniowe, atomowe zdania lub atomy

2) F_Po - najmniejszy zbiór formuł w
, taki, że:

3) A_Po- zbiór aksjomatów - zbiór formuł w jednej z trzech form:

4) R_Po skończony zbiór reguł wnioskowania, które są predykatami zdefiniowanymi na F_Po

(modus ponens)

lub inaczej:

Tw.1

lub

Tw.2

Jeśli

Tw 3.(dedukcyjne)

Tw. 4.

Twierdzenia systemu formalnego Po

1.

2.

3.

4.

5.

6.

7.

8.

Aspekt semantyczny systemów formalnych

Interpretacja formuł systemu Po'

System

F_Po' - najmniejszy zbiór formuł w
, taki, że:

Interpretacja (ocena, realizacja, oszacowanie) systemu F_Po', to odwzorowanie:

T - true, F - false

Oznaczenia:

Koncepcje interpretacji:

1. Formuła A jest tautologią jeśli i[A]=T dla każdej interpretacji i. Oznaczamy to następująco:

2. Formuła B jest konsekwencją A jeśli i[B] = T, gdy kiedykolwiek i[A]= T. Oznaczamy to następująco:

3. Formuła B jest konsekwencją zbioru formuł * jeśli i[B] = T, gdy kiedykolwiek i[A]= T dla wszystkich
   . Oznaczamy
   

4. Dwie formuły A i B są ekwiwalentne jeśli
   i
   . Oznaczamy
   .

5. Formuła A jest satysfakcjonująca lub spójna jeśli istnieje interpretacja, taka że i[A] = T.

6. Zbiór formuł * jest satysfakcjonujący lub spójny jeśli istnieje interpretacja, taka że
   i[A] = T dla wszystkich
   . Taką interpretację nazywamy modelem *.

7. Dwa zbiory formuł są ekwiwalentne jeśli maja identyczne modele.

8. Formuła A jest niesatysfakcjonująca lub niespójna, gdy i[A] = F dla każdej interpretacji i. A jest niespójna wtedy i tylko wtedy, gdy
   jest tautologią.

9. Zbiór formuł * jest niesatysfakcjonujący lub niespójny, jeśli dla każdej interpretacji i istnieje, taka
   , że i[A] = F. Inaczej mówiąc brak modelu *.

Tw. 5.

Jeśli A i B są formułami w F_Po'

(a)

(b)

(c) Jeśli

(d)

(e) Jeśli

Tw. 6.

Dla dowolnej formuły
, jeśli
,tzn. te formuły, które są twierdzeniami (prawdziwymi syntaktycznie) są również tautologiami (prawdziwymi semantycznie).