Język RP (KRK)

W KRZ brak możliwości operowania na abstrakcyjnych
obiektach, czyli nie można formułować praw
dotyczących tych obiektów.

Rozszerzamy zatem nasz język, w którym będziemy
zapisywać formuły:

i) zmienne x

1

,x

2

,..

ii) n-argumentowe symbole funkcyjne f

1

,f

2

,.. (symbole 0-arg to

stałe)
iii) n-argumentowe symbole predykatowe P

1

,P

2

(symbole 0-arg to

zdania)
iv) symbole logiczne {, , }

v) stałe interpunkcyjne (, )

UWAGA: Pozostałe symbole logiczne {,, ,  } można

wyprowadzić za pomocą tych wymienionych w pkt. iv)



x

P(x)   (

x

 P(x))

Kwantyfikatory

- uniwersalny  - egzystencjalny

 

Zadaniem kwantyfikatora jest związanie zmiennej wymienionej

po kwantyfikatorze
W formułach KRK mogą występować zmienne „wolne” i „związane”

Przykład: z (x  z) x – zmienna wolna; z – zmienna

związana

z y (x  z  y=1 ) x – zmienna wolna; y, z –

zmienne związane

Przykład: Zapis ostatniego wyrażenia w języku predykatów

z y ( (x,z)  =(y,1) )

UWAGA: Jeśli w formule nie występują zmienne wolne, to otrzymujemy
formułę rachunku zdań
z x (x < z)

Kwantyfikatory c.d.

Zasięg kwantyfikatora – wyrażenie znajdujące się w nawiasie bezpośrednio
po kwantyfikatorze

x (x =x)  x>0

Ta zmienna

jest wolna

Jeżeli {x

1

,x

2

, .., x

n

} są zmiennymi wolnymi formuły , to

domknięciem uniwersalnym tej formuły jest formuła x

1

…x

n



domknięciem egzystencjalnym tej formuły jest formuła x

1

…x

n



Przykład:

x P(x) Q(x) formuła ta powinna być zapisana jako x P(x) Q(y)
domknięciem uniwersalnym tej formuły jest y (x P(x) Q(y))

Kwantyfikatory c.d.

Kwantyfikator uniwersalny jest uogólnieniem koniunkcji
Jeśli X={a

1

,..,a

n

} oraz P(x) jest predykatem określonym na zbiorze X, to

x P(x)  P(a

1

)P(a

2

)…P(a

n

)

Kwantyfikator egzystencjalny jest uogólnieniem alternatywy
Jeśli X={a

1

,..,a

n

} oraz P(x) jest predykatem określonym na zbiorze X, to

x P(x)  P(a

1

)P(a

2

)…P(a

n

)

Kwantyfikatory

ograniczone

Zakres zmiennej kwantyfikowanej ograniczony jest formułą
( (x)) (x)

( (x)) (x)

( (x)) (x) jest prawdziwe wttw x ( (x)(x) ) jest

prawdziwe
( (x)) (x) jest prawdziwe wttw x ( (x)(x) ) jest

prawdziwe

Przykłady:

x (xN x>0) czyli  

xN (x>0)

Język rachunku

predykatów cd.

Predykat (relacja, którą predykat wyraża) ma tyle zmiennych, ile występuje w nim
zmiennych

wolnych.

Wyrażenia nie zawierające zmiennych wolnych są zdaniami.

W mocy pozostają założenia z pierwszego slajdu, aby w pełni zdefiniować zbiór
dopuszczalnych formuł w RP wprowadzimy jeszcze pojęcie TERMU.

TERMY: Najmniejszy zbiór spełniający warunki

i) stałe indywiduowe są termami
ii) zmienne są termami
iii) jeśli f jest n-arg symbolem funkcyjnym i t

1

,..,t

n

są termami,

to f(t

1

,..,t

n

) również jest termem

Język rachunku

predykatów cd.

FORMUŁY: Najmniejszy zbiór spełniający warunki:
i) zdania są formułami
ii) jeśli R jest n-arg predykatem a t

1

,..,t

n

są termami, to R(t

1

,..,t

n

) jest formułą

iii) jeśli ,  są formułami, to , , , ,  również są formułami

iv) jeśli (x) jest formułą ze zmienną wolną, to x (x) i x (x) są formułami

Przykłady
Stałe={zeus, ares, harmonia} Zmienne={X,Y,Z}
Funkcje={Ojciec(X), Matka(X)} Predykaty={Jest_ojcem(X,Y), Bog(X)}

Termy: zeus, ares, harmonia, X,Y,Z, Ojciec(X), Matka(X), Ojciec(Matka(X))

Formuły: Jest_ojcem(zeus,X), Bog(Ojciec(X)),
X Jest_ojcem(Ojciec(X),X), Bog(zeus) <- to już są zdania
UWAGA: Zbiory Stałe, Zmienne, Funkcje, Predykaty MUSZĄ
być rozłączne

Spełnianie – przypadek

prosty

Element (stała) a spełnia predykat P(x), jeśli po wstawieniu a w
miejsce x otrzymamy zdanie prawdziwe

Ogólniej (dla formuł)
Element a spełnia formułę P(x)R(x) wttw, gdy spełnia P(x) lub

spełnia R(x);
podobnie jest z funktorami , 

Zdanie x P(x) jest prawdziwe wttw każda stała a spełnia P(x).

Zdanie x P(x) jest prawdziwe wttw istnieje taka stała a, że a

spełnia P(x).

UWAGA: Z powyższej definicji wynika, że o spełnialności i prawdziwości
mówimy w kontekście jakiejś dziedziny.

Przykłady: Możemy mówić o spełnialności lub prawdziwości formuły
x (x)  (x), jeśli ustalimy interpretację dla ,  oraz

ustalimy wartości (zakres) dla zmiennych

x (xN x>0) prawdziwa 

x (xZ x>0) spełnialna dla x naturalnych

Powtórzmy
Aby określić sens formuły rachunku predykatów należy:
i)

wybrać wartości dla zmiennych

ii) ustalić interpretację symboli funkcyjnych i predykatowych

ad i)
czyli za zmienne wstawić stałe (nie zawsze wprost, czasem

kwantyfikator)

ad ii)
Interpretacją I formuły  nazywamy dowolną parę I=(D,

m), w której D jest

dziedziną, a m jest taką funkcją, która:
1. Każdemu symbolowi stałej przyporządkowuje element ze

zbioru D

2. Każdemu n-arg symbolowi f

i

przyporządkowuje odwzorowanie

D

n

D

3. Każdemu p-arg symbolowi P

i

przyporządkowuje odwzorowanie

D

p

{0,1}

4. Każdemu zdaniu przyporządkowuje wartość logiczną {0,1}

Spełnianie

Przykład:
Formuły
B(z), B(a), O(z,a), O(a,h), O(X,Y)



D(Y,X), D(X,Y)



D(Y,Z)



W(X,Z)

O(X,X)

Stałe={z, a, h}, Zmienne={X,Y,Z}
Funkcje=



, Predykaty={W,D,O,B}

Interpretacja
D={zeus, ares, harmonia} zeus=z, ares=a, harmonia=h
m(B(zeus))=1 bezpieczniej używać nazw predykatów oddających sens relacji

Bog(zeus), Bog(ares), Ojciec(zeus,ares), Ojciec(ares, harmonia)

Ojciec(X,Y)



Dziecko(Y,X), Dziecko(X,Y)



Dziecko(Y,Z)



Wnuk(X,Z)

Ojciec(X,X)

tutaj wartość m jest 1

Przykład cz. I

aby policzyć wartości logiczne tych formuł przy naszej interpretacji musimy mieć
jeszcze wartościowanie

Interpretacja
D={zeus, ares, harmonia} zeus=z, ares=a, harmonia=h
m(B(zeus))=1 bezpieczniej używać nazw predykatów oddających sens relacji

Bog(zeus), Bog(ares), Ojciec(zeus,ares), Ojciec(ares, harmonia)
Ojciec(X,Y)



Dziecko(Y,X), Dziecko(X,Y)



Dziecko(Y,Z)



Wnuk(X,Z)

Ojciec(X,X)

Mając interpretację i wartościowanie jestem w stanie przeprowadzić

wnioskowanie dla formuł zawierających zmienne

Ojciec(zeus,harmonia)



Dziecko(harmonia,zeus)

Dziecko(harmonia,ares)



Dziecko(ares, zeus)



Wnuk(harmonia,zeus)

UWAGA: Przy naszej interpretacji i dowolnym wartościowaniu Ojciec(X,X)

wartość m jest 1

Przykład cz. II

Spełnianie i

prawdziwość formuł

Interpretacja ma zatem wpływ na wartość logiczną formuł

Formuła  jest spełniona przy interpretacji I oraz przy

ustalonych wartościach

zmiennych występujących w  wttw h

I,w

()=1

tutaj możemy powiedzieć o pewnej analogii do h

v

z KRZ

Formuła  jest prawdziwa przy interpretacji I wttw

w w:ZmienneD h

I,w

()=1

(I spełnia  ; I jest modelem dla )



jest spełnialna wttw  I  w h

I,w

()=1



jest prawdziwa (tautologia) wttw  I  w h

I,w

()=1

Przykłady tautologii

1. ( (x) (x) )  ( (x) (x) )

2. ((x) (x) )  ( (x) (x) ) prawa de`Morgana

3. x ( (x)(x) )  ( x (x)  x (x) )

4. x y (x,y)  y x (x,y)

5. x ( (x)   )  ( x (x)   ) o ile zmienna x nie występuje w



6. x y (x,y)  y x (x,y)

7. x y (x,y)  y x (x,y)

Reguły wnioskowania

, 

 



Modus ponens

(x)

x (x)

Generalizacji

(x)  

x (x)  

zakładamy, że x nie występuje w 

jako zmienna wolna

Dołączania kwantyfikatora

egzystencjalnego

Rachunek predykatów jest systemem formalnym, posiadającym

swoją

aksjomatykę i zbiór reguł wnioskowania

(x)

Podstawiania

(y)

Ograniczenie: za zmienną x w formule (x) można podstawić

zmienną y, jeśli w (x) x nie występuje w zasięgu kwantyfikatora

wiążącego zmienną y

Twierdzenie
Rachunek kwantyfikatorów nie jest rozstrzygalny
(Alonzo Church – 1936; na podstawie prac Alana Turinga).

Istotność ograniczenia w regule podstawiania (rozważmy zbiór N

0

)

y (yx)  y=0 podstawmy za x/y

y (yy)  y=0 wiemy również, że y (yy)

stosując regułę odrywania (modus ponens) otrzymamy
y=0
stosując teraz regułę podstawiania y/1 otrzymamy
1=0

Rozstrzygalność

Systemy dowodzenia

System gentzenowski
System hilbertowski

Wyprowadza się reguły wtórne (w szczególności regułę dedukcji)

Hilbertowski system dowodzenia jest poprawny i pełny

Do systemu hilbertowskiego H dodajemy dwa aksjomaty i jedną

regułę

wnioskowania (generalizacji)(x)

x (x)

Przykład

Przykład:

Skrót RZ oznacza, że przekształcenia dokonano na podstawie twierdzeń
i reguł wnioskowania Rachunku Zdań