Wst

ęp do logiki

Klasyczny Rachunek Predykatów I

2

KRP: preliminaria

KRZ jest teori

ą stanowiącą wstępną część logiki formalnej, część zakładaną przez inne teorie.

Przypomnijmy, jest on teori

ą związków logicznych między zdaniami dowolnego języka

naturalnego. W centrum swego zainteresowania stawia struktur

ę formalną zdań złożonych,

koncentruj

ąc swą uwagę na spójnikach zdaniowych. Zdania proste – składniki zdań złożonych –

traktuje jako nierozkładalne dalej atomy. Powoduje to,

że w ramach języka KRZ nie można

uzasadni

ć poprawności formalnej wielu wnioskowań, które intuicyjnie uważamy za formalnie

poprawne. Przeprowad

źmy następujące rozumowanie:

Ka

żdy filozof jest omylny. Sokrates jest filozofem. A zatem, Sokrates jest omylny.

Zastosujmy tu metod

ę badania niezawodności wnioskowań, opisaną w ramach KRZ.

3

KRP: preliminaria

Schematem pierwszej przesłanki, zapisanym w j

ęzyku KRZ, będzie zmienna p, bo z punktu

widzenia KRZ jest to zdanie proste (nie zawiera ona

żadnego spójnika); schematem drugiej

przesłanki b

ędzie zmienna q, a schematem wniosku będzie zmienna r. Tak więc, schemat tego

wnioskowania ma posta

ć:

r

q

p,

Łatwo sprawdzi

ć, że nie jest to reguła niezawodna, gdyż formuła: p ∧ q → r nie jest tautologią

KRZ. Znaczy to,

że wniosek nie wynika logicznie z przesłanek. Nasuwa się jednak nieodparte

wra

żenie, że wnioskowanie to jest formalnie poprawne w tym sensie, iż wniosek wynika

logicznie z przesłanek oraz i

ż opiera się ono na jakieś niezawodnej regule wnioskowania. Rodzi

si

ę więc przypuszczenie, że język KRZ jest za mało precyzyjny, by w jego ramach uzasadnić

formaln

ą poprawność tego wnioskowania. Przypuszczenie to jest słuszne.

4

KRP: preliminaria

Do pokazania,

że rozważane tu wnioskowanie jest formalnie poprawne, niezbędny jest rachunek

umo

żliwiający precyzyjniejszą analizę budowy zdań, mianowicie taki, który pozwoli

uwzgl

ędnić wewnętrzną budowę zdań prostych. Rachunkiem takim jest rachunek predykatów,

zwany te

ż rachunkiem kwantyfikatorów.

Zacznijmy wi

ęc od ustalenia, czym jest zdanie proste. Z grubsza rzecz biorąc:

•

zdanie proste to wyra

żenie przypisujące pewną własność pewnemu przedmiotowi,

wskazywanemu za pomoc

ą odpowiedniej nazwy, np.

Sokrates jest omylny

,

albo

•

zdanie proste to wyra

żenie opisujące pewien związek (relację) zachodzący miedzy dwoma lub

wi

ęcej przedmiotami, wskazywanymi przez odpowiednie nazwy, np.

Ewa kusi Adama

.

5

KRP: preliminaria

Ustalaj

ąc symbole, które mogą reprezentować nazwy przedmiotów oraz symbole, które mogą

reprezentowa

ć wyrażenia odnoszące się do własności przedmiotów lub relacji miedzy

przedmiotami, mo

żemy każdemu zdaniu prostemu przyporządkować pewna formułę

reprezentuj

ącą jego formę logiczną. Zacznijmy od zdania:

Ewa kusi Adama.

„Ewa” i „Adam” to nazwy jednostkowe. S

ą one połączone predykatem „kusi”. Zapiszmy

rozwa

żane zdanie tak, aby najpierw występował predykat, a następnie jego argumenty:

Kusi(Ewa, Adam).

Niech

a zast

ępuje nazwę „Ewa”,

b zast

ępuje nazwę „Adam”,

K zast

ępuje predykat „kusi”.

Wobec tego rozwa

żane zdanie można zapisać jako: K(a, b).

6

KRP: preliminaria

Wprowadzaj

ąc stosowne skróty, można podobnie zapisać inne zdania proste, takie jak:

0 jest liczba naturaln

ą

,

a mianowicie

N(0)

Dygresja.

W zdaniu tym wyra

żenie „jest liczbą naturalną” jest predykatem 1-argumentowym.

Zauwa

żmy, że składa się on z nazwy generalnej „liczba naturalna”, poprzedzonej słowem „jest”.

Ogólnie mo

żemy przyjąć, że każdej nazwie generalnej odpowiada pewien predykat 1-

argumentowy: nazwie „adwokat” – predykat „jest adwokatem”, nazwie „kwadrat” – predykat

„jest kwadratem” itp. W j

ęzyku rachunku predykatów nazwy są nazwami jednostkowymi, czyli

nazwami oznaczaj

ącymi tylko jeden przedmiot. ■

7

KRP: preliminaria

Podane tu przykłady nazw (jednostkowych) były to nazwy proste – jednowyrazowe.

Przypomnijmy, nazwy j

ęzyka naturalnego ze względu na budowę dzieli się na proste i złożone.

Argumentami predykatów mog

ą być również nazwy złożone – wielowyrazowe, np.

naiwny Adam,

prezydent RP,

0 + 1.

Nazwy tego typu składaj

ą się z pewnej liczby nazw i wyrażenia je łączącego, tzw. wyrażenia

funkcyjnego (funktora).

8

KRP: preliminaria

Niech

f zast

ępuje funktor „naiwny”.

Wobec tego nazw

ę

naiwny Adam

mo

żna zapisać jako

f(b),

za

ś zdanie

Ewa kusi naiwnego Adama

mo

żna zapisać jako

K(a, f(b)).

Dygresja.

W j

ęzyku rachunku predykatów dla oznaczenia wszystkich nazw (zarówno prostych,

jak i zło

żonych) stosuje się techniczny termin:

term

. Mówi

ąc dokładniej, term to formuła

nazwowa.

■

9

KRP: preliminaria

We

źmy następujące schematy:

x kusi y

,

log

y

x + 0

.

Wyst

ępujące w tych schematach litery x i y to tzw.

zmienne indywiduowe

(

nazwowe

), czyli

takie litery, za które mo

żna podstawiać jedynie nazwy danego języka. Reprezentują one

przedmioty jednostkowe (indywidua) z pewnego ustalonego zbioru, zwanego

zakresem

zmiennych

, np. zbioru ludzi, zbioru liczb (mówimy te

ż że zmienne przebiegają odpowiedni

zbiór).

Pierwszy z podanych tu schematów jest

formuł

ą zdaniową

– po podstawieniu za zmienne nazw

otrzymamy zdanie, za

ś drugi jest

formuła nazwow

ą

(czyli termem) – po podstawieniu za

zmienne nazw otrzymamy na powrót nazw

ę.

10

KRP: preliminaria

Formuły zdaniowe, takie jak „x kusi y”. a wi

ęc zawierające zmienne, za które można podstawić

pewne nazwy okre

śla się mianem

funkcji zdaniowych

. Funkcje zdaniowe s

ą swego rodzaju

równaniami, które spełniaj

ą odpowiednie przedmioty. Np. funkcję zdaniową:

x > 0

spełnia ka

żda liczba większa od zera, i żadna inna.

Dygresja.

Dodajmy,

że zmiennym nazwowym w języku naturalnym odpowiadają takie

wyra

żenia, jak

co

ś

,

kto

ś

,

jaki

ś

itp. Np.

Je

żeli ktoś pożyczył od kogoś jakiś przedmiot, to jest tego kogoś dłużnikiem.

Mo

żna to zapisać symbolicznie następująco:

P(x, y, z) → D(x, y),

gdzie litera „P” reprezentuje predykat „po

życzył”, a litera „D” predykat „jest dłużnikiem”. ■

11

KRP: preliminaria

Chc

ąc przedstawić formę logiczną zdania, które nie zawiera żadnej nazwy (jednostkowej)

ustalamy jedynie symboliczna reprezentacj

ę predykatów (dbając o to, by różnym predykatom

odpowiadały ró

żne symbole). Potrzebne nam będą jeszcze pewne specjalne symbole:

∀

kwantyfikator generalny

, który czytamy:

dla ka

żdego

,

dla dowolnego

,

wszystkie

.

∃

kwantyfikator egzystencjalny

, który czytamy:

istnieje takie,

że

,

dla pewnego

.

Dygresja.

W literaturze u

żywane są inne jeszcze zapisy kwantyfikatorów. Kwantyfikator

generalny (ogólny, du

ży) zapisywany bywa następująco: Λ, (x), a egzystencjalny (szczegółowy,

mały) za pomoc

ą symboli V, (Ex). ■

Niech

L(x) reprezentuje:

x jest leniwy

.

(Zakładamy,

że zmienna x przebiega po zbiorze ludzi.)

12

KRP: preliminaria

Wszyscy s

ą leniwi

(zdanie ogólnotwierdz

ące)

∀x [L(x)] czytamy:

Dla ka

żdego x, x jest leniwy

zasi

ęg kwantyfikatora

Niektórzy s

ą leniwi

(zdanie szczegółowotwierdz

ące)

∃x [L(x)] czytamy:

Istnieje x takie,

że x jest leniwy

zasi

ęg kwantyfikatora

Nikt nie jest leniwy

(zdanie ogólnoprzecz

ące)

∀x ~L(x) czytamy:

Dla ka

żdego x, x nie jest leniwy

zasi

ęg kwantyfikatora

Niektórzy nie s

ą leniwi

(zdanie szczegółowoprzecz

ące)

∃x ~L(x) czytamy:

Istnieje x takie,

że x nie jest leniwy

zasi

ęg kwantyfikatora

13

KRP: preliminaria

Rola kwantyfikatora polega na wi

ązaniu zmiennych. Zmienna związana przez kwantyfikator jest

„zmienn

ą pozorną”, za którą nie wolno nic podstawiać.

: preliminaria

Formuł

ę występującą w nawiasie (otwartym bezpośrednio po kwantyfikatorze) nazywamy

zasi

ęgiem kwantyfikatora

. Gdy zasi

ęg kwantyfikatora nie budzi wątpliwości nawiasy możemy

pomin

ąć; np. zamiast ∀x[L(x)] można pisać: ∀xL(x).

Niech

F(x) reprezentuje:

x jest filozofem

;

L(x) reprezentuje:

x jest leniwy

.

(Zakładamy ponownie,

że zmienna x przebiega po zbiorze ludzi.)

14

KRP: preliminaria

Ka

żdy filozof jest leniwy.

(zdanie ogólnotwierdz

ące)

Ka

żdy, kto jest filozofem, jest leniwy.

F(x) → L(x)

Je

śli x jest filozofem, to x jest leniwy.

∀x[F(x) → L(x)]

Dla ka

żdego x, jeśli x jest filozofem, to x jest leniwy.

Pewien filozof jest leniwy.

(zdanie szczegółowotwierdz

ące)

Istnieje kto

ś, kto(ś) jest filozofem i jest leniwy.

F(x) ∧ L(x)

x jest filozofem i x jest leniwy.

∃x[F(x) ∧ L(x)]

Istnieje x takie,

że x jest filozofem i x jest leniwy.

15

KRP: preliminaria

Podobnie w przypadku zda

ń:

Żaden filozof nie jest leniwy.

∀x[F(x) → ~L(x)]

(zdanie ogólnoprzecz

ące)

Pewien filozof nie jest leniwy.

∃x[F(x) ∧ ~L(x)]

(zdanie szczegółowoprzecz

ące)

Nie ma leniwych filozofów.

~∃x[F(x) ∧ L(x)]

Tylko filozofowie s

ą leniwi.

∀x[L(x) → F(x)]

W zdaniach mo

że występować więcej zwrotów kwantyfikujących. Mogą one występować nie

tylko na pocz

ątku wypowiedzi, ale także wewnątrz niej lub na końcu. Weźmy zdania:

Wszystko jest przyczyn

ą wszystkiego.

∀x∀y P(x, y)

Istnieje co

ś, co jest przyczyną wszystkiego.

∃x∀y P(x, y)

Wszystko ma swoj

ą przyczynę.

∀y∃x P(x, y)

Nic nie jest przyczyn

ą wszystkiego.

∀x∀y ~P(x, y)

Pewien student nie przeczytał

żadnej książki.

∃x[S(x) ∧ ∀y (K(y) → ~ P(x, y))]

16

KRP: preliminaria

Sposób tworzenia formuł bardziej zło

żonych z formuł prostszych opisuje następująca tabela:

∀x(A)

Dla ka

żdego x, A

∃x(A)

Istnieje x takie,

że A

~(A)

Nieprawda,

że A

(A) ∧ (B)

A i B

(A) ∨ (B)

A lub B

(A) → (B)

Je

żeli A, to B

(A) ≡ (B)

A wtw B

17

KRP: preliminaria

Z semantycznego punktu widzenia, rola kwantyfikatorów polega na stwierdzeniu uniwersalno

ści

lub akcydentalno

ści występowania pewnej cechy lub relacji, wskazywanej przez predykat.

Najprostsze intuicyjne rozumienie kwantyfikatorów uzyskuje si

ę rozważając kwantyfikatory

ograniczone do zbiorów sko

ńczonych n-elementowych takich, że każdy element rozważanego

zbioru, U, posiada swoj

ą nazwę a

i

. Wówczas:

•

formuła postaci ∀xA(x) jest równowa

żna koniunkcji A(x/a

1

) ∧ ... ∧ A(x/a

n

), a

•

formuła postaci ∃xA(x) jest równowa

żna alternatywie A(x/a

1

) ∨ ... ∨ A(x/a

n

).

St

ąd kwantyfikator generalny nazywa się niekiedy uogólnioną koniunkcją, a kwantyfikator

egzystencjalny – uogólnion

ą alternatywą.

Przykład.

∀x Leniwy(x) ≡ Leniwy(Zenek) ∧ Leniwa(Ziuta) ∧ ... .

∃x Leniwy(x) ≡ Leniwy(Zenek) ∨ Leniwa(Ziuta) ∨ ... . ■

18

KRP: preliminaria

Zdanie generalnie skwantyfikowane ∀x A(x)

•

jest prawdziwe, gdy dla ka

żdej nazwy a jest tak, jak głosi zdanie A(x/a);

•

jest fałszywe, gdy dla co najmniej jednej nazwy a nie jest tak, jak głosi zdanie A(x/a).

Z kolei, zdanie egzystencjalnie skwantyfikowane ∃x A(x)

•

jest prawdziwe, gdy dla co najmniej jednej nazwy a jest tak, jak głosi zdanie A(x/a);

•

jest fałszywe, gdy dla ka

żdej nazwy a nie jest tak, jak głosi zdanie A(x/a).

19

KRP: preliminaria

Zagadki.

Pewn

ą wyspę zamieszkują tylko rycerze i łotry. Rycerze zawsze mówią prawdę, a łotry

zawsze kłami

ą. Mamy trzy osoby, X, Y i Z, ale tylko dwie z nich wygłaszają zdania (każda z

nich jest albo rycerzem, albo łotrem).

(1) X mówi:

Wszyscy jeste

śmy rycerzami

.

Y mówi:

Wszyscy jeste

śmy łotrami.

Kim s

ą X, Y i Z?

(2) X mówi:

Jest w

śród nas rycerz.

Y mówi:

Jest w

śród nas łotr.

Kim s

ą X, Y i Z?

20

KRP: preliminaria

Dygresja historyczna.

Kwantyfikatory zostały wprowadzone przez G. Fregego w 1879 r.

Jednak

że jego praca z uwagi na trudną symbolikę została niezauważona. Około 1885 r. C. S.

Peirce wprowadził bardziej czytelne symbole dla kwantyfikatorów i zauwa

żył, że można je

traktowa

ć, odpowiednio, jako koniunkcję i alternatywę. Rachunek kwantyfikatorów

upowszechnili B. Russell i A. N. Whitehead w „Principia Mathematica”.

■