73

 

 

Obecnie przechodzimy do 

klasycznego rachunku kwantyfikatorów

 (w skrócie KRK), 

zwanego często po prostu logiką klasyczną. KRK jest logiką wystarczającą dla potrzeb 

matematyki, chociaż nadal zbyt ograniczoną, aby pozwolić na analizę wielu rozumowań  

w języku naturalnym. Mimo to zakres zastosowań KRK znacznie przewyższa możliwości 

rachunku zdań omawianego w poprzednim module. Zademonstrujemy to na prostym przykładzie. 

Rozumowanie:  

Bambi jest słoniem. Wszystkie słonie mają wielkie uszy. Zatem, Bambi ma wielkie uszy. 

jest poprawne. Jednak próba wykazania jego poprawności przy użyciu KRZ jest skazana na 

niepowodzenie, gdyż nie występują tu w ogóle spójniki. Na gruncie KRZ schemat powyższego 

rozumowania wygląda więc następująco:  

p, q / r 

Wystarczy użyć wartościowania V(p)=V(q)=1 i V(r)=0, aby taki schemat poddać falsyfikacji. Gdy 

chcemy wykazać,  że interesujące nas rozumowanie jest poprawne, musimy umieć poddać 

analizie strukturę wewnętrzną jego zdań składowych, a to umożliwia dopiero KRK. 

W sposobie prezentacji KRK będziemy się trzymać jak najbliżej tej formy, którą zastosowaliśmy 

w odniesieniu do KRZ w poprzednim module. Przedstawimy w kolejnych tematach język, 

semantykę i reguły dowodzenia. Krótko mówiąc, logika klasyczna zostanie tutaj przedstawiona 

jako formalny rachunek. W ostatnim temacie skupimy się na identyczności i pewnych 

własnościach relacji dwuargumentowych, które znajdą zastosowanie w metodologii (moduł 6). 

Na problemach zastosowania KRK do analizy rozumowań w języku naturalnym skupimy się  

w następnym module. 

 

74

 

 

Wspomnieliśmy we wstępie, że KRK to logika wystarczająca do zastosowań matematycznych. 

Zanim więc przedstawimy formalnie język, pokażemy na prostym przykładzie, jakie kategorie 

syntaktyczne są w matematyce potrzebne. W wyrażeniu: 

1.

 

y=x+4 wtw istnieje z takie, że z-3<y 

można wyróżnić trzy 

zmienne nazwowe

 (albo indywidualne) ”x”, ”y”, ”z”; jedna z nich (”z”) jest 

związana przez 

kwantyfikator mały

 (istnieje... takie, że) często zwany też egzystencjalnym, 

albo szczegółowym - pozostałe są wolne. ”4” i ”3” to 

stałe nazwowe

, gdyż w przeciwieństwie 

do zmiennych ”x”, ”y” ich znaczenie jest ustalone. ”+ ” i ”-” to 

stałe funkcyjne 

(krótko funkcje, 

albo operacje), obie o kategorii n/n,n, natomiast ”= ” i ”< ” to 

stałe predykatywne 

(predykaty, 

orzeczniki) o kategorii z/n,n.  

Wszystkie te wyrażenia to 

stałe pozalogiczne

, gdyż ich znaczenie jest sprecyzowane na 

gruncie pewnej teorii matematycznej, a nie na gruncie logiki. Jedyne stałe logiczne to spójnik 

wtw i kwantyfikator mały. Całość jest 

funkcją zdaniową

, gdyż zmienne ”x” i ”y” są wolne (nie są 

związane przez żaden kwantyfikator, czy ogólniej – operator), a zatem nie mają ustalonego 

znaczenia. 

Powyższy przykład pokazuje, że język KRK musi być wystarczająco bogaty, aby móc 

reprezentować nazwy, predykaty i operacje o dowolnej liczbie argumentów. Powyżej 

występowały stałe pozalogiczne, jednak logika ma dostarczać schematów reguł ważnych 

niezależnie od treści odpowiednich predykatów czy operacji. Dlatego będziemy używać 

zmiennych predykatywnych i funkcyjnych, nie poddając ich jednak kwantyfikacji. 

Intuicyjnie należy to rozumieć jako utajoną kwantyfikację ogólną, czyli – jeżeli w formule będą 

występować np. jakieś zmienne predykatywne, wtedy oznacza to, że warunek wyrażony w tej 

formule dotyczy dowolnych predykatów podstawionych za te zmienne. Z powodów czysto 

technicznych będziemy jednak rozróżniać zmienne nazwowe wiązane przez kwantyfikator od 

zmiennych tej samej kategorii, ale mających reprezentować pozalogiczne stałe nazwowe.  

Te drugie dalej będziemy skrótowo określać jako 

stałe nazwowe

. 

 

75

 

Jak widać z powyższych rozważań 

słownik 

języka KRK jest znacznie bardziej zróżnicowany  

i oprócz nowych stałych logicznych zawiera kilka grup zmiennych różnych kategorii: 

1) Nieskończony, przeliczalny zbiór 

zmiennych nazwowych

, (kategoria syntaktyczna n) który 

będziemy oznaczać krótko ZN; jego elementy to litery: x, y, z, v, w, ..., x

1

, y

1

,.... Zasadniczo 

będziemy ich używać tylko w powiązaniu z kwantyfikatorami. 

2) Nieskończony, przeliczalny zbiór 

zmiennych funkcyjnych 

(ZF) o różnych ilościach 

argumentów (również zeroargumentowych). W przypadku zerowej ilości argumentów mamy 

do czynienia po prostu ze 

stałymi nazwowymi

 (SN). Funkcją SN jest reprezentowanie 

dowolnych prostych nazw indywidualnych, a dla ich oznaczenia używać będziemy liter: a, b, 

c, ...., a

1

, b

1

, .... Dla zmiennych funkcyjnych o nie zerowej ilości argumentów (czyli kategorii 

n/n, n/n,n, n/n,n,n, ...) będziemy używali liter: f, g, h, ...., f

1

, g

1

, .... Ilość potrzebnych 

argumentów najczęściej będzie określał kontekst, w przeciwnym wypadku będzie ona 

zaznaczana górnym indeksem przy symbolu, np. g

3

 oznaczać  będzie,  że g jest kategorii 

n/n,n,n. 

3) Nieskończony, przeliczalny zbiór 

zmiennych predykatywnych

 (ZP), o różnych ilościach 

argumentów (kategorii z/n, z/n,n, z/n,n,n, ....). Tu również dopuszczamy zeroargumentowe 

zmienne predykatywne – są to po prostu zmienne zdaniowe (ZZ). Generalnie będziemy 

tutaj używać dowolnych dużych liter łacińskich: A, B, C, ...., A

1

, B

1

, ...., a jeśli ilość 

argumentów nie będzie wynikała z kontekstu, to będziemy ją zaznaczać, podobnie jak  

w przypadku zmiennych funkcyjnych, przez użycie indeksu górnego. 

4) 

Stałe logiczne

, to te same spójniki co w języku KRZ, a oprócz tego dwa kwantyfikatory:  

ogólny (dla każdego…) 

∀  

mały (dla pewnego …; istnieją takie…, że…)  

∃ 

Oba kwantyfikatory będą występowały zawsze w połączeniu ze zmiennymi nazwowymi, 

które mają wiązać w danej formule w następujący sposób

: 

“

∀x” 

5) 

Nawiasy

, czyli znaki interpunkcyjne. 

 

76

 

Najpierw podamy definicję 

termu

, czyli wyrażenia nazwowego języka KRK (w skrócie 

Term(KRK)), a następnie formuły. Generalnie, w metajęzyku używać będziemy następujących 

symboli: 

α, β  

– na oznaczenie dowolnych zmiennych nazwowych; 

σ  

– dla stałych nazwowych a 

σ

n

 

dla n-argumentowych zmiennych funkcyjnych; 

τ  

– dla dowolnych wyrażeń nazwowych; 

Π

n

  

– dla n-argumentowych zmiennych predykatywnych; 

ϕ i ψ   –

 

nadal oznaczają formuły, natomiast 

ϕ(α), ψ(α,β) oznaczają takie formuły, w których  

odpowiednie zmienne występują co najmniej w jednym miejscu jako wolne (czyli nie 

związane przez żaden kwantyfikator); 

Γ, ∆, Σ  – będą dalej używane jako symbole dowolnych zbiorów formuł. 

Zbiór Term(KRK) definiujemy następująco: 

a) ZN 

⊆ Term(KRK) oraz SN ⊆ Term(KRK) 

b) jeżeli 

τ

1

, ...., 

τ

n

, są (niekoniecznie różnymi) elementami Term(KRK), to wtedy  

σ(τ

1

, ....,

τ

n

) należy do Term(KRK), pod warunkiem, że 

σ

n

  należy do  ZF 

c) nic 

więcej nie należy do Term(KRK) 

 

Zbiór For(KRK) definiujemy następująco: 

a) ZZ 

⊆ For(KRZ) 

b) jeżeli 

τ

1

, ...., 

τ

n

,

  są (niekoniecznie różnymi) elementami Term(KRK), to wtedy  

Π(τ

1

, ....,

τ

n

) należy do For(KRK), pod warunkiem, że 

Π

n

 należy do ZP 

c) jeżeli 

ϕ i ψ należą do For(KRK), to ¬ϕ, (ϕ∧ψ), (ϕ∨ψ), (ϕ→ψ), (ϕ↔ψ),  ∀αϕ,  ∃αϕ też 

należą do For(KRK) 

d) nic 

więcej nie należy do For(KRK) 

Obie powyższe definicje są indukcyjne, przy czym druga z nich po prostu poszerza analogiczną 

definicję dla języka KRZ. Formuły scharakteryzowane w warunku a) i b) będziemy dalej określać 

jako 

formuły atomowe

. Zwróćmy uwagę,  że chociaż w praktyce matematycznej predykaty  

 

77

i operacje dwuargumentowe zwykło się umieszczać pomiędzy argumentami, to dla odpowiednich 

zmiennych przyjęliśmy jednolitą formę zapisu, w której symbol predykatu (operacji) występuje 

zawsze przed swoimi argumentami. Podany wyżej przykład funkcji zdaniowej z języka arytmetyki 

ma więc następujący schemat w języku KRK: 

2. I(y,f(x,a)) ↔∃z(M(g(z,b),y)) 

Gdzie stałe nazwowe “a” i “b” zastępują (denotują) “4” i “3”, zmienne funkcyjne “f” i “g” zastępują 

“+” i “-“, natomiast zmienne predykatywne “I” i “M” zastępują “=” i “<”. 

 

78

 

 

Zachowujemy dla języka KRK wszystkie konwencje skracające zapis, które wprowadziliśmy  

w module 3, ponadto wprowadzamy dodatkowe. 

K4) będziemy pomijali przecinki między termami i nawiasy zamykające argumenty danego 

predykatu lub operacji wszędzie tam, gdzie nie będzie to prowadziło do nieporozumień.  

Przykładowo – formuła 

2.

 z poprzedniego tematu może być zapisana prościej, w taki sposób: 

1. Iyf(xa) ↔∃zMg(zb)y 

Nie mogliśmy pominąć nawiasów otaczających argumenty obu zmiennych funkcyjnych, gdyż 

nie byłoby jasne, czy np. w wyrażeniu “Iyfxa” nie jest tak, że “f” reprezentuje operację  

1-argumentową z “x” jako swoim jedynym argumentem, a “I” reprezentuje predykat 

 

3-argumentowy o argumentach “y”, “fx” i “a”.  

Podobnie, przy zapisie “Mgzby” możliwa byłaby taka interpretacja, że “M” reprezentuje predykat 

1-argumentowy, a jego jedyny argument to “gzby”, czyli 3-argumentowa operacja reprezentowana 

przez “g” i jej trzy argumenty. To kontekst wyznacza, kiedy możliwe jest pominięcie jakiegoś 

nawiasu, a kiedy nie. Przykładowo w formule: 

2. Ixa→Iyfxa 

nie musieliśmy użyć nawiasu po “f”, gdyż pierwsze (od lewej) wystąpienie “I” pokazuje, że jest 

to zmienna reprezentująca predykat 2-argumentowy, a zatem jedyne możliwe odczytanie “Iyfx” 

to takie, że “y” jest jego pierwszym argumentem, a “fxa” drugim, co oznacza, że “f” reprezentuje 

operację 2-argumentową. 

 

W przykładzie 

1.

 mogliśmy również pominąć nawias zamykający formułę “Mg(zb)y”, gdyż jest to 

formuła atomowa, a zatem w całości znajduje się w zasięgu kwantyfikatora. Oba kwantyfikatory 

zachowują się syntaktycznie tak jak negacja, tzn. jeżeli za zmienną występującą za 

kwantyfikatorem otwiera się nawias, to wtedy cała formuła w nawiasie jest w zasięgu tego 

 

79

kwantyfikatora. W przeciwnym wypadku w jego zasięgu znajduje się formuła, która sąsiaduje  

z nim bezpośrednio od prawej.  

Aby dobrze zrozumieć, co stanowi zasięg danego kwantyfikatora przeanalizujmy poniższy przykład: 

3. ∀x(∃yAxy→∀y∃z¬(∀w¬Bw→Czy)∧Dx) 

Mamy tutaj pięć wystąpień kwantyfikatorów; oto ich zasięgi, po kolei od lewej: 

∃yAxy→∀y∃z¬(∀w¬Bw→Czy)∧Dx to zasięg ∀x  

Axy 

 

 

  to 

zasięg  

∃y 

∃z¬(∀w¬Bw→Czy)    to zasięg  ∀y 

¬(∀w¬Bw→Czy)   

to zasięg  

∃z 

¬Bw     

 

to zasięg  

∀w 

 

Umiejętność identyfikacji zasięgu pozwala stwierdzić, które wystąpienia danej zmiennej 

nazwowej są związane i przez który kwantyfikator, a które są wolne. Powiemy, że:  

wystąpienie zmiennej

 

α w formule ϕ jest  związane wtw występuje w zasięgu kwantyfikatora 

∀α lub ∃α; w przeciwnym wypadku (tzn., gdy nie występuje w zasięgu żadnego kwantyfikatora 

lub takiego, przy którym mamy symbol innej zmiennej) wystąpienie zmiennej 

α jest  wolne. 

Zauważmy,  że dana zmienna, występując kilka razy w obrębie danej formuły, może być  

w pewnych wystąpieniach wolna, a w innych nie, np. w formule: 

4. ∀xAx→∀yBxy 

pierwsze wystąpienie “x” (jako argumentu “A”) jest związane, natomiast drugie (w “Bxy”) jest 

wolne, gdyż tylko “Ax” stanowi zasięg “

∀x”. Drugie wystąpienie “x” jest wprawdzie również  

w zasięgu kwantyfikatora, ale wiążącego inną zmienną (“y”). Jeżeli wszystkie wystąpienia danej 

zmiennej są związane w pewnej formule, to powiemy krótko, że dana zmienna jest w tej formule 

związana.  

Uwaga, licząc wystąpienia danej zmiennej w formule bierzemy pod uwagę tylko te, które są 

argumentami predykatów i operacji, a nie uwzględniamy wystąpień zmiennych przy kwantyfikatorze! 

Warto zwrócić uwagę, że w danej formule może wielokrotnie występować kwantyfikator wiążący 

pewną zmienną, wtedy dla każdego wystąpienia tej zmiennej należy określić, który 

 

80

kwantyfikator je wiąże. Przyjmujemy tu zasadę,  że dane wystąpienie zmiennej jest związane 

przez najbliższy od lewej kwantyfikator z taką samą zmienną, w którego zasięgu to wystąpienie 

się znajduje. Najlepiej pokaże to przykład: 

5. ∀x(∃xAx∨Bx→∀xCx∧Dx) 

mamy cztery wystąpienia “x” i trzy kwantyfikatory wiążące tą samą zmienną. Pierwsze od lewej 

wystąpienie kwantyfikatora ogólnego wiąże tylko drugie i czwarte wystąpienie “x” (“Bx” i “Dx”), 

pierwsze wystąpienie (“Ax”) jest związane przez kwantyfikator mały, a trzecie (“Cx”) przez 

drugie wystąpienie dużego kwantyfikatora. 

Formuły, w których wszystkie zmienne są związane będziemy dalej określać jako 

formuły 

domknięte

, natomiast takie, w których co najmniej jedno wystąpienie jakiejś zmiennej 

nazwowej jest wolne to 

formuły otwarte

. Przykładowo, przedstawione w tym temacie formuły 

3.

 i 

5.

 są domknięte, natomiast formuły 

1.

,

 2. 

i 

4. 

są otwarte. 

 

Zarówno w semantyce, jak i w systemie dedukcji, który dalej zaprezentujemy, istotną rolę 

odgrywać będzie dokonywanie podstawień za zmienne nazwowe w formułach otwartych. Niech 

ϕ(α) oznacza formułę otwartą, w której zmienna α występuje co najmniej raz jako zmienna 

wolna. Przez 

ϕ(α/σ) oznaczać  będziemy formułę, w której dokonano 

podstawienia

 stałej 

nazwowej 

σ za zmienną α.  

W logice klasycznej uwzględnia się ogólniejszą formę tej operacji, w której za wolną zmienną 

można podstawiać dowolne termy, nie tylko stałe nazwowe. Jednak dla naszych potrzeb 

wystarczy uwzględnić najprostszą postać. Warunki poprawności podstawiania 

sprowadzają się w tym wypadku do dwóch: 

a) w 

ϕ muszą ulec podstawieniu wszystkie wolne wystąpienia α, 

b) za 

każde z nich podstawiamy tą samą stałą nazwową 

σ. 

Oto poprawne przykłady podstawień: 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (x/a) = ∀xAxz∨Bay→∃y(Cyz∧Dya) 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (y/a) = ∀xAxz∨Bxa→∃y(Cyz∧Dyx) 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (z/a) = ∀xAxa∨Bxy→∃y(Cya∧Dyx) 

 

81

Oto niepoprawne przykłady podstawień (zastanów się dlaczego): 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (x/a) = ∀xAaz∨Bay→∃y(Cyz∧Dya) 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (x/a) = ∀aAaz∨Bay→∃y(Cyz∧Dya) 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (x/a) = ∀xAxz∨Bay→∃y(Cyz∧Dyx) 

∀xAxz∨Bxy→∃y(Cyz∧Dyx) (x/a) = ∀xAxz∨Bay→∃y(Cyz∧Dyb) 

 

Wprowadzimy jeszcze jedną konwencję upraszczającą zapis formuł: 

K5) W przypadku występowania ciągów kwantyfikatorów jednego rodzaju (bądź same ogólne, 

bądź same małe) będziemy symbol kwantyfikatora pisać tylko raz; czyli zamiast pisać 

∀α

1

, ....,

∀α

n

ϕ (lub ∃α

1

, ....,

∃α

n

ϕ) napiszemy ∀α

1

, ...,

α

n

ϕ (lub ∃α

1

, ...,

α

n

ϕ) 

Przykładowo, zamiast pisać: “

∀x∀y∀z∀w(Axy→Bzw)” napiszemy “∀xyzw(Axy→Bzw)”. 

Oczywiście niedopuszczalne jest takie pomijanie symboli kwantyfikatorów wtedy, gdy występują 

w jednym ciągu przemieszane ze sobą kwantyfikatory duże i małe. 

 

82

 

 

Zaprezentujemy obecnie jedną z prostszych wersji 

semantyki teorio-modelowej

. Ograniczymy 

się do analizy znaczenia języka, w którym nie występują zmienne funkcyjne oraz formuły 

otwarte. Struktury interpretacyjne tutaj rozpatrywane to modele 

M

 = < D, V >, gdzie D to 

dziedzina modelu, którą może być dowolny niepusty zbiór, natomiast V to funkcja interpretacji 

przypisująca w modelu ekstensje poszczególnym elementom języka: 

1) dla każdej stałej nazwowej 

σ, V(σ)∈D; dodatkowo zakładamy, że każdy element dziedziny 

ma nazwę (jest desygnatem jakiejś stałej nazwowej) 

2) dla każdej zmiennej predykatywnej 

Π

n

 

(n

≥1), V(Π

n

) 

⊆ DxDx.....xD (D przemnożone n razy, 

czyli 

iloczyn kartezjański

 n-tego stopnia na D, zaznaczany często jako D

n

). Innymi słowy 

ekstensja dowolnej zmiennej predykatywnej jednoargumentowej to podzbiór D, dowolnej 

zmiennej dwuargumentowej – pewien zbiór par uporządkowanych elementów z D (podzbiór 

DxD), dla zmiennej trójargumentowej – zbiór trójek uporządkowanych, itd.  

Dla zmiennych predykatywnych zeroargumentowych, czyli zmiennych zdaniowych pozostawiamy 

ekstensje jak w KRZ, czyli przypisujemy im jakąś wartość logiczną. 

 

Wartość dowolnej formuły w modelu 

M

  (co będziemy zapisywać 

M

=  ϕ i czytać ‘model 

M

  

spełnia 

ϕ’) określamy według poniższych warunków: 

a)  

M

= Π

n

 (dla n=0) 

 

 

wtw 

V(

Π

n

)=1 

b)  

M

= Π

n

(

σ

1

 , ..., 

σ

n

) (dla n>0)  

wtw 

 <V(

σ

1

), ..., V(

σ

n

)> 

∈V(Π

n

) 

c)  

M

= ¬ϕ 

 

 

 

wtw 

M 

≠ϕ  (co czytamy ‘gdy 

M

 nie spełnia 

ϕ’) 

d)  

M 



= 

ϕ∧ψ    

 

 

wtw 

M

 

= ϕ  i   

M

 

= ψ 

e)  

M 

= ϕ∨ψ    

 

 

wtw 

M

 

= ϕ  lub  

M

 

= ψ  

f)   

M

 

= ϕ→ψ   

 

 

wtw 

M 

≠ϕ  lub  

M 

= ψ 

g)  

M 

= ϕ↔ψ   

 

 

wtw 

M

 

= ϕ  i  

M 

= ψ  lub  

M

 

≠ϕ  i  

M

 

≠ ψ  

h)  

M

 

= ∀αϕ   

 

 

 wtw 

M 

= ϕ(α/σ) dla dowolnej stałej σ 

i)  

M

 

= ∃αϕ 

 

 

 

 wtw 

M

 

= ϕ(α/σ) dla pewnej stałej σ 

 

83

Jeżeli chodzi o warunki c)–g), to mamy tu zapisaną w innej formie zawartość tabelek 

definiujących spójniki w temacie 2. modułu 3. Warunek b) podaje, kiedy w modelu spełniona 

jest formuła atomowa, nie będąca zmienną zdaniową.  

Warunki h) i i) formalnie oddają domyślne znaczenie zwrotów kwantyfikujących. Warunek h) 

pokazuje też, dlaczego przyjęliśmy założenie,  że wszystkie elementy dziedziny muszą być 

nazwane. W przeciwnym wypadku możliwa byłaby sytuacja, gdzie warunek wyrażony przez 

formułę 

ϕ byłby wprawdzie spełniony dla wszystkich obiektów z dziedziny, które mają nazwę, 

ale nie zachodziłby dla jakiegoś nienazwanego obiektu z tej dziedziny. 

 

Podobnie jak w KRZ, dowolną formułę, która spełniona jest w każdym modelu będziemy 

określać jako 

tautologię

, czyli prawdę logiczną i oznaczać:

= ϕ . Formuły, które są prawdziwe 

(spełnione) w co najmniej jednym modelu, będziemy określać jako spełnialne. Są to zarówno 

tautologie, jak i formuły kontyngentne.  

Mod(

ϕ) oznaczać będzie zbiór wszystkich modeli, które spełniają ϕ; analogicznie Mod(Γ) będzie 

oznaczał zbiór wszystkich modeli, które spełniają wszystkie formuły ze zbioru 

Γ.  

Formuła, która w każdym modelu jest fałszywa, to 

kontrtautologia

 albo fałsz logiczny. Dla 

oznaczenia dowolnej kontrtautologii będziemy nadal używać symbolu 

⊥, natomiast, żeby 

zaznaczyć, że jakaś konkretna formuła 

ϕ jest kontrtautologią (lub zbiór formuł Γ jest sprzeczny) 

możemy użyć zarówno zapisu z poprzedniego modułu (czyli 

ϕ=⊥ i Γ=⊥), jak i nowego – 

Mod(

ϕ)=∅ (Mod(Γ)=∅). 

Do ważniejszych tautologii KRK należą prawa dystrybucji kwantyfikatora: 

– ogólnego względem implikacji  

 

∀x(Ax→Bx)→(∀xAx→∀xBx); 

– ogólnego względem koniunkcji 

 

∀x(Ax∧Bx)↔∀xAx∧∀xBx; 

– ogólnego względem alternatywy  

 

∀xAx∨∀xBx→∀x(Ax∨Bx); 

–

 

szczegółowego względem alternatywy  

∃x(Ax∨Bx)↔∃xAx∨∃xBx; 

–

 

szczegółowego względem koniunkcji   

∃x(Ax∧Bx)→∃xAx∧∃xBx; 

– prawa De Morgana:   

 

 

¬∀xAx↔∃x¬Ax   i  ¬∃xAx↔∀x¬Ax; 

– prawa przemienności kwantyfikatorów:  

∀x∀yRxy↔∀y∀xRxy,  ∃x∃yRxy↔∃y∃xRxy 

oraz 

∃x∀yRxy→∀y∃xRxy. 

 

84

Wynikanie 

w KRK możemy zdefiniować następująco: 

Ze zbioru 

Γ wynika ϕ ( Γ= ϕ)  wtw Mod(Γ) ⊆ Mod(ϕ) 

Dla KRK również zachodzi 

własność zwartości

, która gwarantuje istnienie jakiegoś 

skończonego podzbioru, z którego dana formuła wynika. Dzięki temu także tutaj zachodzi bliski 

związek między wynikaniem a tautologicznością, wyrażony poniższą równoważnością: 

ψ

1

,..., 

ψ

n

= ϕ    wtw  = ψ

1

∧...∧ψ

n

→ϕ 

Nie da się natomiast zastosować w KRK metody tabelkowej do sprawdzania tautologiczności  

i wynikania. Nie oznacza to oczywiście, że podanej wyżej semantyki nie da się wykorzystać do 

wykazywania tautologiczności, wynikania bądź ich braku. Zademonstrujemy to obecnie na kilku 

przykładach. 

Sprawdźmy czy formuła 

1. ∀x(∃yRxy∨∃y(Ay∧Ryx)) 

jest spełniona w modelu 

M

 takim, że D zawiera dwa obiekty o nazwie “a” i “b”, V(A)={a},  

a V(R)={<a,a>,<a,b>}. Ponieważ formuła 

1.

 jest kwantyfikacją ogólną, więc aby była spełniona  

w tym modelu, to jej zasięg (alternatywa w nawiasie) musi być spełniony dla obu przypadków 

podstawienia: x/a i x/b.  

Niech “x” denotuje “a”, wtedy pierwszy człon alternatywy jest spełniony, gdyż istnieje taki obiekt 

(a nawet dwa), że “Ray”. Zatem cała formuła (jako alternatywa) jest spełniona.  

Niech “x” denotuje “b”; teraz pierwszy człon alternatywy jest fałszywy, gdyż ani <b,a>, ani <b,b> nie 

należy do V(R). Jednak drugi człon alternatywy jest prawdziwy, gdyż przy podstawieniu y/a zarówno 

“Aa”, jak i “Rab” są spełnione, zatem ich koniunkcja również. Więc i w tym wypadku formuła, 

będąca zasięgiem kwantyfikatora dużego, jest spełniona w rozważanym modelu, a ponieważ jego 

dziedzina nie zawiera więcej obiektów, to formuła 

1.

 

jest spełniona w rozważanym modelu. 

2.≠ ∃xAx∧∃xBx→∃x(Ax∧Bx) 

Aby pokazać,  że powyższa formuła nie jest tautologią, wystarczy rozważyć dowolny model, 

którego dziedzina zawiera tylko dwa obiekty o nazwie “a” i “b” takie, że V(a)

∈V(A), ale 

V(a)

∉V(B) i odwrotnie V(b)∈V(B), ale V(b)∉V(A). Wtedy poprzednik naszej implikacji jest 

 

85

spełniony w tym modelu, bo spełnione są formuły “Aa” i “Bb”, ale następnik jest w tym modelu 

fałszywy, skoro fałszywa jest zarówno formuła “Aa

∧Ba”, jak i “Ab∧Bb” a więcej obiektów  

w dziedzinie modelu nie posiadamy. Zatem rozważana implikacja jest w takim modelu fałszywa.  

Dla czytelnika, który woli konkrety od abstrakcyjnych konstrukcji modelowych, sugeruję 

„ukonkretnienie” powyższego modelu falsyfikującego, np. w taki sposób: niech dziedzina 

zawiera psa o nazwie Azor i kota o nazwie Brutal, “A” niech reprezentuje predykat _jest psem,  

a “B” – _jest kotem. Taka interpretacja doskonale spełnia zadanie. 

3. ∀x(Ax→Bx), ∀x(Bx→Cx)= ∀x(Ax→Cx) 

Załóżmy niewprost, że wynikanie nie zachodzi. Zatem istnieje model, w którym obie przesłanki 

są spełnione, ale wniosek nie. Wtedy musi w dziedzinie być co najmniej jeden obiekt – 

nazwijmy go “a” – taki, że V(a)

∈V(A), ale V(a)∉V(C), co gwarantuje, że “Aa→Ca” jest w tym 

modelu fałszywe, czyli “

∀x(Ax→Cx)” również jest fałszywe. Skoro pierwsza przesłanka jest  

w tym modelu spełniona, to V(a)

∈V(B), ale wtedy również V(a)∈V(C), gdyż druga przesłanka 

też jest w tym modelu spełniona. To daje sprzeczność i pokazuje, że nie może istnieć model 

falsyfikujący dla tego rozumowania. 

 

86

 

Zachowamy system dedukcji naturalnej omówiony w module 3. Wszystkie reguły, pierwotne  

i wtórne, zachowują swoją wartość, potrzebujemy tylko dodać odpowiednie reguły dla nowych 

stałych logicznych, czyli kwantyfikatorów. Odstąpimy jednak od zwykłego w dedukcji naturalnej 

sposobu postępowania, w którym charakteryzuje się każdą stałą poprzez reguły dołączania  

i eliminacji.  

Zamiast tego omówimy zestaw reguł charakterystyczny dla 

systemów tablicowych

  (por. np. 

Smullyann 1968), w którym mamy tylko reguły eliminacji – a zamiast reguł dołączania – 

dodatkowe reguły eliminacji kwantyfikatorów zanegowanych. Wybór taki podyktowany jest 

przede wszystkim względami prostoty opisu reguł, a ponadto pozwoli nam – w module 5 – na 

wykorzystanie systemu do sprawdzania poprawności rozumowań.  

Obecnie skupimy się tylko na dowodach tez i dedukcji wniosków z przesłanek  

w rozumowaniach poprawnych. 

 

Jedyne 

reguły pierwotne

, które dołączamy do systemu S/B to cztery 

reguły inferencji

: 

(EO)  

∀αϕ− ϕ(α/σ) 

(ENO) 

¬∀αϕ− ¬ϕ(α/σ) 

(EM) 

∃αϕ− ϕ(α/σ) 

(ENM) 

¬∃αϕ− ¬ϕ(α/σ) 

gdzie: 

M – małego 

O – ogólnego 

W regułach (EO) i (ENM) na stałą 

σ nie nakłada się  żadnych ograniczeń poza tymi, które 

wynikają z warunków poprawności podstawiania (por. temat 2 w 4 module). Natomiast  

w przypadku reguł (ENO) i (EM) 

σ musi  być nową stałą, tzn. taką, która nie występuje wyżej 

w dowodzie!  

 

87

Sens tego ograniczenia jest następujący: prawdziwość przesłanek tych reguł w dowolnym 

modelu gwarantuje, że w dziedzinie rozważanego modelu musi się znajdować jakiś obiekt, dla 

którego zachodzi warunek wyrażony przez 

ϕ (lub ¬ϕ). My po prostu nadajemy mu nazwę. 

Jednak nie możemy mu dać nazwy, która już jest czemuś przyporządkowana, skoro nie mamy 

po temu wystarczających danych. Nie przestrzeganie tego ograniczenia może prowadzić do 

błędów, np. można by było „udowodnić” formułę z przykładu 

2.

 w poprzednim temacie, o której 

wiemy, że nie jest tautologią. 

  

Zachowujemy wszystkie symbole i konwencje dotyczące zapisu dowodów, zaznaczania tez  

i dedukowalności z poprzedniego modułu. Dla obecnego systemu również zachodzi 

twierdzenie o adekwatności

: 

TA) 

ψ

1

,...., 

ψ

n

− ϕ wtw 

ψ

1

,...., 

ψ

n

= ϕ 

 

 

Oto kilka przykładów dowodów: 

1.− ∀x(Ax∧Bx)↔∀xAx∧∀xBx 

Część a): 

1. 

∀x(Ax∧Bx) 

2. 

¬(∀xAx∧∀xBx) ZN 

3. 

¬∀xAx∨¬∀xBx (2 

NK) 

3.1. 

¬∀xAx  

ZDN 

3.2. 

¬Aa   (3.1 

ENO) 

3.3. Aa

∧Ba  

(1 

EO) 

3.4.  Aa  

 

(3.3, EK) 

3.5. 

⊥ 

  (3.2,3.4 

DS.) 

4. 

∀xAx   (3.1–3.5 

DNW) 

5. 

¬∀xBx  

(3,4 

EA) 

 

88

6. 

¬Bb   (5 

ENO) 

7. Ab

∧Bb  

(1 

EO) 

8. 

Bb 

 

  (7, 

EK) 

9. 

⊥ 

  (6,8 

DS) 

Część b): 

1.

 

∀xAx∧∀xBx 

2

. 

¬∀x(Ax∧Bx) ZN 

3

. 

∀xAx   (1 

EK) 

4

. 

∀xBx   (1 

EK) 

5

. 

¬(Aa∧Ba) 

(2 

ENO) 

6

. 

¬Aa∨¬Ba 

(5 NK) 

7

. 

Aa 

  (3 

EO) 

8

. 

Ba 

  (4 

EO) 

9

. 

¬Ba   (6,7 

EA) 

10. 

⊥ 

  (8,9 

DS) 

2. − ∃x(∃xAx→Ax) 

1. 

¬∃x(∃xAx→Ax) ZN 

2. 

¬(∃xAx→Aa) (1 

ENM) 

3. 

∃xAx∧¬Aa  

(2 NI) 

4. 

∃xAx   (3 

EK) 

5. 

¬Aa   (3 

EK) 

6. 

Ab 

  (4 

EM) 

7. 

¬(∃xAx→Ab) (1 

ENM) 

8. 

∃xAx∧¬Ab  

(7 NI) 

9. 

¬Ab   (8 

EK) 

10. 

⊥ 

  (6,9 

DS) 

Powyższy przykład pokazuje sytuację charakterystyczną dla dowodów przeprowadzanych  

z użyciem powyższych reguł. Często reguły (EO) i (ENM) należy stosować w dowodzie 

wielokrotnie, aby uzyskać zamierzony efekt (np. sprzeczność formuł).  

 

89

W powyższym dowodzie najpierw stosujemy (ENM), gdyż nie mamy innych rozsądnych 

możliwości – “a” jest po prostu pierwszą z brzegu stałą nazwową. Stosując później (EM) 

musimy wprowadzić nową stałą – “b”, co nie daje nam sprzeczności (para formuł “

¬Aa” i “Ab”), 

jednak możemy ponownie zastosować (ENM), tym razem podstawiając stałą “b” i uzyskując 

parę formuł sprzecznych. 

3. ∀xy(Rxa∨Sby)− ∃x(Rxx∨Sbx) 

1. 

∀xy(Rxa∨Sby) 

2. 

¬∃x(Rxx∨Sbx) ZN 

3. 

¬(Raa∨Sba) (2 

ENM) 

4. 

∀y(Raa∨Sby) (1 

EO) 

5. Raa

∨Sba  

(4 

EO) 

6. 

⊥ 

  (3,5 

DS) 

Powyższy, krótki dowód ilustruje kolejny ważny problem związany z  kwantyfikatorami – 

znajdowanie właściwych podstawień. Dlaczego stosując do wiersza 2. regułę (ENM) 

podstawiliśmy “a” za “x”?  

Zarówno podstawienie “b”, jak i nowej stałej “c”, byłoby poprawne, ale nie prowadziłoby nas do 

celu. Musimy podstawić “a”, gdyż występuje ono jako drugi argument “R” w wierszu 1., a nam 

chodzi o uzgodnienie argumentów predykatów. To w dalszym ciągu powoduje, że dwukrotnie 

stosując (EO), podstawiamy najpierw “a” za “x”, a potem “a” za “y”, chociaż inne podstawienia 

też są możliwe (ale bezcelowe!).  

Generalnie należy przyjąć następującą wytyczną co do strategii dowodzenia:  

Najpierw starać się (jeżeli to możliwe) stosować reguły (ENO) i (EM), wprowadzając wszystkie 

niezbędne nowe stałe nazwowe do dowodu.  

Potem stosujemy (EO) i (ENM) (jeżeli trzeba to wielokrotnie), starając się znaleźć odpowiednie 

podstawienia tych stałych, które w dowodzie już są.  

Trzeba pamiętać,  że nawet przy stosunkowo niewielkiej liczbie stałych, jeżeli będziemy 

dokonywać przy (EO) i (ENM) podstawień „na ślepo” – do wszystkich możliwych stałych – to 

łatwo możemy w dowodzie „wyprodukować” znaczną ilość wierszy, które nie tylko nie zbliżą nas 

do celu, ale spowodują, że szybko stracimy orientację, w tym co robimy! 

 

90

 

 

Na bazie KRK można budować specyficzne teorie formalne, które znacznie poszerzają zakres 

zastosowania logiki klasycznej i pozwalają ująć w czysto formalny sposób całą matematykę. 

Najczęściej teorie te buduje się w postaci 

systemów aksjomatycznych

, w których odpowiedni 

zbiór twierdzeń pierwotnych (aksjomatów) pozwala, w oparciu o reguły logiki i ewentualne 

reguły specyficzne dla danej teorii (np. regułę indukcji matematycznej), udowodnić wszystkie 

twierdzenia danej teorii.  

Aksjomaty mają za zadanie podać istotne własności 

terminów pierwotnych

 danej teorii, czyli 

jej stałych pozalogicznych (predykatów lub operacji). Najbardziej podstawową teorią – jeżeli 

chodzi o jej zastosowania – jest teoria identyczności; często traktuje się ją zresztą jako część 

logiki klasycznej. O jej niezbędności może  świadczyć choćby to, że w dotychczasowych 

rozważaniach wielokrotnie używaliśmy już symbolu “=”. Omówimy teraz krótko jej podstawy. 

 

Do języka KRK dołączamy jedną stałą predykatywną oznaczaną symbolem „=”. Jest to predykat 

dwuargumentowy, ale syntaktycznie będziemy go traktować raczej zgodnie z matematyczną 

konwencją (zapis pomiędzy argumentami), a nie z gramatyką KRK, czyli, zamiast pisać “=

τ

1

τ

2 

“, 

będziemy pisać “

τ

1

=

τ

2

”. Będziemy też zazwyczaj pisać “

τ

1

≠τ

2

“ zamiast “

¬τ

1

=

τ

2

“. 

Przyjmujemy następujące aksjomaty i reguły pierwotne:  

(ID) 

− τ=τ 

(RL) 

τ

1

=

τ

2

, 

ϕ(τ

1

)

− ϕ(τ

1

//

τ

2

) 

(ID) charakteryzuje najbardziej podstawową cechę relacji identyczności, mianowicie jej 

zwrotność

. 

Przykładami (ID) w języku KRK są: “x=x”, “a=a”, “fxg(ya)=fxg(ya)”. (RL) (czyli reguła Leibniza) 

pokazuje,  że w dowolnym kontekście można pewną nazwę jakiegoś obiektu 

zastąpić

 jakąś 

inną jego nazwą.  

“

ϕ(τ

1

//

τ

2

)” oznacza, że w obrębie 

ϕ dokonano operacji zastąpienia, a nie podstawienia termów. 

Zastąpić można dowolny term (nie tylko zmienną nazwową) przez dowolny term (a nie tylko 

stałą nazwową) i nie musimy zastępować wszystkich wystąpień tego termu (jak przy podstawianiu). 

 

91

Jedyny warunek dotyczy tego, że zastępowane wystąpienie termu może zawierać tylko 

zmienne wolne, a term, który zastępuje, też nie może zawierać zmiennych, które zostałyby 

związane przez jakiś kwantyfikator. Oto przykłady poprawnego zastosowania (RL): 

a=b, 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axb→Byf(bx))∧Cxf(ya) 

a=b, 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axa→Byf(bx))∧Cxf(yb) 

a=b, 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axb→Byf(bx))∧Cxf(yb) 

a=b, 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axa→Byf(ax))∧Cxf(ya) 

a=f(bx), 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axa→Byf(bx))∧Cxf(yf(bx)) 

ale 

a=f(bx), 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axf(bx)→Byf(bx))∧Cxf(ya) 

jest niepoprawne, gdyż pierwsze wystąpienie “a” zostało zastąpione przez term zawierający 

zmienną “x”, która stała się związana. Również 

a=f(bx), 

∀x(Axa→Byf(bx))∧Cxf(ya) − ∀x(Axa→Bya)∧Cxf(ya) 

jest niepoprawne, gdyż zastąpiliśmy term “f(bx)” zawierający zmienną związaną. 

 

Korzystając z (ID) i (RL) można udowodnić wszystkie twierdzenia teorii identyczności oraz 

poprawne schematy rozumowań wykorzystujące ten predykat; oto dwa przykłady: 

1.− Aa→∃x(Ax∧x=a) 

1. Aa 

2. 

¬∃x(Ax∧x=a) ZN 

3. 

¬(Aa∧a=a)  

(2 ENM) 

4. 

a=a 

  (ID) 

5. Aa

∧a=a  

(1,4 

DK) 

6. 

⊥ 

  (3,5 

DS) 

2. Aa, Ab, ∃x∀y(Ay→x=y) − a=b 

1. Aa 

 

 

92

2. Ab 

 

3. 

∃x∀y(Ay→x=y) 

4. 

∀y(Ay→c=y)  

(3 EM) 

5. Aa

→c=a    

(4 EO) 

6. Ab

→c=b  

(4 

EO) 

7. 

c=a 

  (1,5 

EI) 

8. 

c=b 

  (2,6 

EI) 

9. 

a=b 

  (7,8 

RL) 

 

Łatwo jest udowodnić, że dla identyczności zachodzą dwie ważne tezy: 

(SYM=) 

∀xy(x=y→y=x) 

(TR=)  

∀xyz(x=y∧y=z→x=z)    

Pokazują one, że relacja identyczności jest relacją 

symetryczną

 i 

przechodnią

 (tranzytywną). 

Są to ogólne własności dowolnych relacji dwuargumentowych, podobnie jak relacja 

zwrotności

, wyrażana przez (ID). O każdej relacji dwuargumentowej R powiemy, że jest 

relacją równoważnościową

 wtw gdy zachodzą dla niej łącznie te trzy własności, czyli gdy spełnia 

warunki: 

(ZW) 

∀xRxx 

(SYM) 

∀xy(Rxy→Ryx) 

(TR) 

∀xyz(Rxy∧Ryz→Rxz) 

Do innych ważnych własności relacji dwuargumentowych zaliczyć można: 

przeciwzwrotność 

(PZW), 

serialność

 (SER), 

asymetrię słabą 

(antysymetrię), (ASS) i 

mocną 

(ASM), 

spójność 

słabą

 (SS) i 

mocną 

(SM) oraz 

euklidesowość 

(E) wyrażane wzorami: 

(PZW) 

∀x¬Rxx 

(SER) 

∀x∃yRxy 

(ASS) 

∀xy(Rxy∧Ryx→x=y) 

(ASM) 

∀xy(Rxy→¬Ryx) 

(SS) 

∀xy(Rxy∨Ryx∨x=y) 

(SM) 

∀xy(Rxy∨Ryx) 

 

93

(E) 

∀xyz(Rxy∧Rxz→Ryz) 

Nie wszystkie z wymienionych wyżej własności są niezależne, np. z mocnych wersji asymetrii 

(spójności) można wydedukować  słabe wersje, ze zwrotności – serialność. Niektóre z tych 

własności brane łącznie, pozwalają formalnie scharakteryzować wiele ważnych relacji 

rozważanych w matematyce. Rozpatrzmy dwa przykłady: 

 

3. Relacja “≤” w zbiorze liczb naturalnych spełnia warunki: (ZW), (TR), (ASS)  

i (SM) (zatem również (SER) i (SS)). 

4. Relacja “<” w tym samym zbiorze spełnia warunki: (PZW), (SER), (TR), (ASM) i (SS) 

(zatem również (ASS)). 

Obie relacje dają nam konkretne przykłady pewnych relacji porządkujących. Są to porządki 

dosyć silne. Przykładowo, każdą z nich można osłabić przez wyrzucenie warunków spójności, 

które narzucają liniowe uporządkowanie zbioru. Otrzymamy wtedy najsłabszy rodzaj relacji 

porządkującej, tzn. spełniającej tylko warunki (ZW), (TR) i (ASS) bądź częściowo porządkującej 

(warunki (PZW), (TR) i (ASM)). O pewnych zastosowaniach relacji porządkujących  

(i równoważnościowych) powiemy więcej w module 6.