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.