RACHUNEK PREDYKATÓW

Rozpatrzmy przykłady zdań:

„Warszawa jest miastem”, „ jest liczbą”, „Zosia

jest ładna”

Wyrażenia typu

„... jest A”

nazywane są

predykatami.

Na przykład „... jest

miastem”, „... jest młoda” itp. są to

predykaty

. W miejsca wykropkowane można

wstawiać nazwy indywidualne, które w tej nowej terminologii nazywa się
argumentami predykatów. Stąd też cały dział logiki nazw nazywa się często logiką
predykatów lub rachunkiem predykatów. Poza dwoma wymienionymi pojęciami tzn.
pojęciem: „predykat”, będącemu odpowiednikiem orzeczenia w zwykłej gramatyce
języka i pojęciem „argument” będącego odpowiednikiem podmiotu, w logice nazw
występuje trzecie podstawowe pojęcie, którym jest pojęcie kwantyfikatora.
Rozróżnia się dwa rodzaje kwantyfikatorów:

a) kwantyfikator ogólny
b) kwantyfikator szczegółowy

.

Pierwszy z nich odpowiada wyrażeniu „każdy” lub „dla każdego” drugi zaś
wyrażeniu „niektóre”, „dla pewnego” lub też wyrażeniu „istnieje”.
Symbolicznie powyższe dwa wyrażenia zapisywane są następująco:

 x : P(x)

x : P(x)

które odczytuje się odpowiednio w sposób następujący:

„dla każdego x, x ma własność P”
„istnieje takie x, że x ma własność P”.

Symbole



i



są to odwrócone litery A oraz E, które z kolei są pierwszymi literami

wyrazów All (wszystkie), i Exists (istnieje).

WYKŁAD 6

Ze względu na kwantyfikatory, ten dział logiki oprócz wymienionych już nazw,
nazywa się też

rachunkiem kwantyfikatorów.

Czasem też nazywa się go również

rachunkiem funkcji

zdaniowych

lub krótko rachunkiem funkcyjnym. Ta z kolei

nazwa wynika z tego, że predykat tzn. wyrażenie tego typu jak „... jest miastem”,
może być zapisane jako „x jest miastem” i traktowane jest jako funkcja, której
argumentem jest x zaś „wartością” jest prawda lub fałsz. Jeśli zamiast x wstawimy
jakąś nazwę np. „Kraków jest miastem” lub „książka jest miastem”, to otrzymamy
zdanie w sensie logicznym tzn. takie które jest albo prawdziwe albo fałszywe.
Ponieważ po podstawieniu w miejsce x nazwy otrzymujemy zdanie to wyrażenie
typu

„x jest P”

lub krócej

„P(x)”

nazywa się funkcją zdaniową.

„P(x)” odczytuje się jako „x ma własność P” lub „x ma cechę P”.

Język rachunku predykatów.

Podstawowe elementy języka, które nazywane są formułami zdaniowymi
klasycznego rachunku predykatów lub krótko formułami, czy też wyrażeniami,
oznaczone będą w metajęzyku literami A, B, C itd. Formuły te budowane są z
symboli stanowiących alfabet KRP. Alfabet ten składający się z przeliczalnie wielu
symboli podzielony jest na następujące grupy:

- zmienne indywiduowe,
- stałe nazwowe,
- symbole predykatów,
- symbole funkcji,
- stałe logiczne,
- symbole pomocnicze.

Najbardziej elementarną jednostką języka jest

term.

Termy z kolei stanowią

podstawę tworzenia

formuł atomicznych

zwanych krótko atomami. Formuły

atomiczne łączone za pomocą spójników logicznych stanowią

formuły

molekularne

. Te wreszcie stanowią podstawę tworzenia wszystkich pozostałych

wyrażeń języka KRP

, które z kolei dzielą się na formuły otwarte oraz formuły

domknięte.
Jak widać z powyższego zdefiniowania języka KRP wymaga zdefiniowaniu wielu
nowych pojęć, które w KRZ nie występowały.
Rozpatrzmy teraz podstawowe grupy alfabetu języka KRP.
Słownik czyli alfabet klasycznego rachunek predykatów (KRP) składa się z rodzajów
symboli:
a)

Zmienne indywiduowe:

x

1

, x

2

, x

3

, ...

Dla uproszczenia zapisów, kiedy numeracja zmiennych nie będzie ważna, to
stosowane też będą symbole x, y, z. Zmienne te nazywane też są zmiennymi
nazwowymi, gdyż za zmienne te można podstawiać dowolne nazwy dowolnych
przedmiotów a więc nazwy indywidualne.
b)

Stałe nazwowe:

a

1

, a

2

,...

podobnie jak poprzednio, jeśli numeracja nie będzie ważna, to stosowane będą
pierwsze litery alfabetu łacińskiego a, b, c, itd.
Stałe nazwowe reprezentują imiona własne przedmiotów. Jeżeli na przykład w KRP
opisywany byłby rachunek prawdopodobieństwa, to stałymi nazwowymi by były
dwa zdarzenia:  - niemożliwe i  - pewne.

c)

Symbole predykatowe

P

1

, P

2

,...

które będą zapisywane też jako

P, Q, R, S.

Z kontekstu będzie wiadomo czy są to predykaty jedno-, dwu- lub więcej
argumentowe.
d)

Symbole funkcyjne

F

1

, F

2

, F

3

,...,

jeśli nie będzie ku temu potrzeby, to zapisywane będą jako litery F, G, H, oraz z
kontekstu będzie wiadomym ilu argumentowe są funkcje.
e)

Stałe logiczne:

spójniki międzyzdaniowe (, , , , ), oraz kwantyfikatory (,).

f) Symbole pomocnicze:
przecinek, oraz nawiasy okrągłe.

DEFINICJE

Termem

języka KRP nazywa się każdą zmienną indywiduową, każdą stałą

indywiduową a ponadto, jeżeli



1

, 

2

,..., 

n

są to

termy,

to napis

F(

1

, ..., 

n

)

jest

również

termem.

Przykłady:

a) x

zmienna indywiduowa,

b) F(x)

symbol funkcji i jeden argument

c) G(F(x),y)

symbol funkcji i dwa argumenty: jeden jest termem z punktu b),

drugi zmienną indywiduową.
Termem nie jest na przykład napis

P(F(x),y)

gdyż litera

P

nie jest symbolem

funkcji. Napis ten jest tzw. formułą zdaniową atomową.

Formułą atomiczną

nazywa się napis postaci:

P(

1

, 

2

, ..., 

n

)

gdzie

P

jest

symbolem predykatu, zaś



1

, 

2

, n są to dowolne termy.

Formułą zdaniową

jest:

a) każda formuła atomiczna (atomowa)
b) jeśli

A

jest dowolną formułą zdaniową, to formułami zdaniowymi są też

następujące napisy:

(A), x : (A), x : (A),

c) jeśli

A

i

B

są to formuły zdaniowe, to

(A)  (B), (A)  (B), (A) (B), (A)  (B)

są to również formuły zdaniowe.

Przykłady poprawnie zbudowanych formuł zdaniowych:

a)

P(x,y)

b)

x : P(x,y)

c)

(x : P(x,y))  (y : Q (y))

Natomiast wyrażenia:
a)

F(x,y)

b)

(x : F(x,y))  (P(y))

nie są formułami zdaniowymi.
W pierwszym przypadku

F(x,y) nie jest atomem

, znakiem negacji zaś można

poprzedzać tylko atomy.
W drugim przypadku podobnie, kwantyfikator może występować tylko przed formułą
zdaniową, zaś

F(x,y) jest termem,

nie jest zaś atomem a więc nie jest też i formą

zdaniową.

Rozpatrzmy następujący przykład wyrażenia:

x : (P(x,y)  Q(y))  R(x)

Jest to poprawne wyrażenie KRP, część tego wyrażenia zawarta w nawiasach
okrągłych występująca po symbolu kwantyfikatora tzn. wyrażenie

(P(x,y)  Q(y))

nazywa się

zasięgiem kwantyfikatora.

Zmienna indywiduowa zapisana po

symbolu kwantyfikatora i znajdująca się w zasięgu kwantyfikatora nazywa się

zmienną związaną

. Jeżeli zmienna nie jest związana żadnym kwantyfikatorem, to

nazywa się ją

zmienną wolną

. Tak więc w wyrażeniu

(P (x,y)  Q(y))

zmienną

związaną jest zmienna

x,

zaś zmienna

y

jest zmienną wolną.

Zauważmy, że w wyrażeniu

x : (P(x,y)  Q(y))  R(x)

zmienna

x

występująca

jako argument predykatu

R

jest zmienną wolną, znajduje się ona bowiem poza

zasięgiem kwantyfikatora. Podobnie w wyrażeniu

x : (y : (P(x,y,z)  Q(z)) 

R(y))  Q(y)

zmienna

x

jest zmienną związaną kwantyfikatorem



, zaś zmienna

y

w wyrażeniu

P(x,y,z)  Q(z) oraz R(y)

jest zmienną związaną kwantyfikatorem



, zmienna o

takiej samej nazwie tzn.

y

w wyrażeniu

Q(y)

jest zmienną wolną, nie jest bowiem

objęta zasięgiem kwantyfikatora



. Zmienna

z

jest również zmienną wolną, gdy

mimo iż znajduje się w wyrażeniu należącym do zasięgu obu kwantyfikatorów, nie
jest jednak wiązana przez żaden z nich.
Jeżeli w danej formule

wszystkie zmienne są zmiennymi wolnymi

, to formułę

taką nazywa się

formułą otwartą

.

Jeżeli formuła otwarta poprzedzona zostanie kwantyfikatorami ogólnymi
wiążącymi wszystkie zmienne, to uzyskaną formułę nazywa się zamknięciem
formuły otwartej. Na przykład zamknięciem formuły otwartej

P(x,y)  (Q(y) 

R(y,z))

jest formuła

x : y : z : (P(x,y)  (Q(y)  R(y,z))),

którą krócej zapisuje się w postaci:

x,y,z : (P(x,y)  (Q(y)  R(y,z)))

lub nawet w postaci:

x,y,z : P(x,y)  (Q(y) 

R(y,z)).

Formuły nie zawierające zmiennych wolnych nazywa się też formułami
domkniętymi lub zdaniami języka rachunku predykatów.
Rozpatrzmy dla przykładu poniższy fragment „tekstu” zapisanego w tym
języku.

y x : (P(x,y)  Q(y)), R(F(x),y,z), x, y, Q(x)  R(y,x,z)

Przecinkami

oddzielone są tu poszczególne formuły języka.
W podanym fragmencie formuła:

y x : (P(x,y)  Q(y))

jest zdaniem

języka KRP, zaś formuła

R(F(x), y,z)

jest formułą otwartą i zdaniem nie

jest.

Można postawić pytanie: czy ktoś gdzieś tym językiem się posługuje?
jeśli tak, to gdzie i w jakich okolicznościach. Czy nie lepiej posługiwać się
zwykłym „ludzkim” językiem?
Czy znajdą się chociaż dwie osoby, które potrafią się porozumiewać za
pomocą tego języka? Otóż okazuje się, że język klasycznego rachunku
predykatów jest niezwykle ważnym językiem, jest w pewnym sensie
absolutnie uniwersalnym językiem, w którym można wyrazić prawie
wszystkie teorie.
Warto jednak pamiętać, że w pewnym sensie przedstawiony język
językiem nie jest. To co zostało tu nazwane językiem KRP stanowi w
zasadzie jedynie formę i dopiero po jej napełnieniu staje się użytecznym
językiem. Napełnianie form językowych nazywa się interpretacją języka
(formalnego).

Zapisz poniższe zdania używając kwantyfikatorów.

1. Wszystko, co jest materialne, jest poznawalne.

2. Każdy, kto potrafi pisać, potrafi tym samym czytać.

3. Żaden pisarz nie jest analfabetą.

4. Niektórzy pisarze są również poetami.

5. Niektórzy aktorzy nie są piosenkarzami.

6. Istnieją białe gęsi.

7. Wszyscy wąsacze są palaczami fajek.

8. Niektóre grzyby nie są trujące.

9. Niektórzy żonaci mężczyźni są wierni swoim żonom.

10.Jeśli istnieje sprawiedliwość, to każdy przestępca poniesie karę.

11.Jeśli ogłoszono alarm lawinowy, to każdy turysta powinien zachować ostrożność.

12.Istnieje liczba pierwsza, która jest liczbą parzystą.

13.Między dowolnymi liczbami wymiernymi znajduje się co najmniej jedna liczba

wymierna.

14.Istnieją trójkąty, w których każdy kąt jest prosty.

15.Nie istnieje wielościan mający więcej ścian niż krawędzi.

16.Po każdym piątku następuje sobota.

17.Nie istnieje największa liczba naturalna.

18.Nie ma darmowych obiadów.

19.Wszystkie kwadraty są podobne.

20.W tym mieście nie ma złodziei.