2.2. KLASYCZNY RACHUNEK PREDYKATÓW

Podamy definicję dowodu w rachunku predykatów. Dowód w ra-

chunku predykatów różni się od dowodu w rachunku zdań tylko do-
datkowymi możliwościami. Ujmują one większe bogactwo języka ra-
chunku predykatów w stosunku do języka rachunku zdań.

2.2.1. Dowód w rachunku predykatów

(DEF. tautologii języka rachunku predykatów) Tautologią języka ra-
chunku predykatów jest każda formuła tego języka otrzymana z ja-
kiejś tautologii

α

języka rachunku zdań przez podstawienie za każdą

literę zdaniową występującą w

α

, jakiejś formuły języka rachunku pre-

dykatów (jednocześnie w każdym miejscu dla wszystkich wystąpień
danej litery zdaniowej).

Oprócz tautologii będziemy mieli aksjomaty (teorii) identyczno-

ści (

≡

)

Id1.

v ≡ v

Id2.

v

i

≡ v ⇒ F v

1

. . .v

i−1

v

i

v

i+1

. . .v

n

≡ F v

1

. . .v

i−1

vv

i+1

. . .v

n

,

gdzie

F

jest

n

-argumentową literą funkcyjną, a

n > 0

Id3.

(

v

i

≡ v ∧ P v

1

. . .v

i−1

v

i

v

i+1

. . .v

n

)

⇒ P v

1

. . .v

i−1

vv

i+1

. . .v

n

gdzie

P

jest

n

-argumentową literą predykatową, a

n > 0

.

Zauważmy, że aksjomatów Id1 jest tyle, ile jest zmiennych indy-

widuowych, – Id2 jest tyle, ile jest wszystkich kombinacji liter funk-
cyjnych i zmiennych indywiduowych, a aksjomatów Id3 tyle, ile jest
kombinacji liter predykatowych i zmiennych indywiduowych.

Rachunek predykatów można budować dla języka nie zawiera-

jącego predykatu identyczności

56

.

Predykat identyczności jest pre-

dykatem używanym w zasadzie we wszystkich językach (teoriach)

56

Predykat identyczności może być zdefiniowany. Możliwe to jest np. w języku,

w którym występują zmienne predykatowe (

n

-argumentowa zmienna predykatowa

przebiega klasę wszystkich i tylko relacji

n

-członowych, dających się utworzyć w

132

2. KLASYCZNA LOGIKA PREDYKATÓW

mających praktyczne znaczenie. Dlatego też jest celowe budowanie
rachunku logicznego dla języka zawierającego ten predykat.

Zależy nam na syntaktycznym scharakteryzowaniu pojęcia wy-

nikania rzeczywistego (definicja wynikania rzeczywistego jako wyni-
kania semantycznego podana zostanie później). Musimy więc spre-
cyzować pojęcie dowodu. Zbiór reguł dowodowych w rachunku zdań
wzbogacamy o nowe reguły dowodzenia. Oprócz reguły odrywania

REGUŁA ODRYWANIA

MP. z

ϕ

i

ϕ ⇒ φ

wynika

φ

,

mamy jeszcze

REGUŁA PODSTAWIANIA

zbiorze uniwersalnym) oraz możliwa jest kwantyfikacja po tych zmiennych (język
drugiego rzędu). Już u Arystotelesa spotykamy się z myślą, że przedmiotom iden-
tycznym przysługują te same własności. Według określenia św. Tomasza z Akwinu
identyczne są takie przedmioty, że cokolwiek przysługuje jedenemu z nich przy-
sługuje też drugiemu. Autorem pewnej definicji identyczności jest Leibniz. Jest
ona znana jako zasada identyczności przedmiotów nieodróżnialnych (principium
identitatis indiscernibilium). Zasadę tę można by sformułować następująco

x ≡ y

wtedy i tylko wtedy, gdy

dla każdego

P.P x ⇔ P y

,

gdzie

P

jest zmienną predykatową, której zakresem jest zbiór wszystkich relacji

jednoczłonowych.

Gdyby uznać, że sprawa odróżnialności bądź nieodróżnialności jest sprawą

języka, z którego korzystamy przy opisie, to identyczność można by zdefiniować
następująco

x ≡ y

wtedy i tylko wtedy, gdy

dla dowolnej jednoargumentowej litery predykatowej

P.P x ⇔ P y

.

Tym razem ma miejsce kwantyfikacja, której zakresem jest zbiór jednoargumen-
towych liter predykatowych, a nie jak powyżej zbiór relacji jednoczłonowych. Tę
definicję można zapisać jako schemat formuł. Takie sformułowanie jako pierwszy
podał Peirce w 1885 r. Po zamieszczeniu jej w Principia Mathematica Whitehe-
ada i Russella została spopularyzowana i niekiedy nazywa się ją russellowską lub
leibnizowsko-russellowską definicją identyczności. Definicja ta daje podstawy zna-
czącej dla matematyki regule zastępowania równych (reguły tej nie należy mylić
z regułą podstawiania). Więcej na ten temat zob. Tarski [1994], s. 56–65.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

133

Sb. z

ϕ

wynika

ϕ(v/t)

, o ile term

t

jest podstawialny w miejsce

zmiennej

v

REGUŁA OPUSZCZANIA DUŻEGO KWANTYFIKATORA

O

∀

. z

ϕ ⇒ ∀v.φ

wynika

ϕ ⇒ φ

REGUŁA DOŁĄCZANIA DUŻEGO KWANTYFIKATORA

D

∀

. z

ϕ ⇒ φ

wynika

ϕ ⇒ ∀v.φ

, jeżeli

v

nie jest zmienną wolną w

ϕ

REGUŁA OPUSZCZANIA MAŁEGO KWANTYFIKATORA

O

∃

. z

∃v.ϕ ⇒ φ

wynika

ϕ ⇒ φ

REGUŁA DOŁĄCZANIA MAŁEGO KWANTYFIKATORA

D

∃

. z

ϕ ⇒ φ

wynika

∃v.ϕ ⇒ φ

, jeżeli

v

nie jest zmienną wolną w

φ

.

Oczywiście reguły są tak dobrane, żeby zachowywały rzeczywisty

stosunek wynikania. Stosujemy je do formuł, które nie muszą być
zdaniami. Mówienie więc o prawdziwości wyrażeń, do których reguły
są stosowane nie jest zasadne. Zamiast terminu „prawda” możemy tu
użyć ogólniejszego terminu „spełnianie”. Będzie to termin techniczny
logiki, jego ścisłe znaczenie określimy w dalszej części rozważań. Na
tym etapie wystarczy kierować się jego intuicyjnym znaczeniem.

Reguła podstawiania odpowiada sposobowi takiego rozumowa-

nia, gdy np. mając formułę

57

x

2

≥ 0

przyjmujemy

(

y + 1)

2

≥ 0

2

2

≥ 0

.

Obie otrzymane formuły są spełnione w zbiorze liczb rzeczywistych.
Pierwsza dla wszystkich możliwych znaczeń, jakie może przyjmować
zmienna

y

w zbiorze liczb rzeczywistych, zaś druga nie zawierając

zmiennych jest po prostu prawdziwa.

57

Wyrażającą prawdziwą zależność w zbiorze liczb rzeczywistych, tj. praw-

dziwą po związaniu przez duży kwantyfikator wszystkich zmiennych wolnych, czyli
spełnioną dla dowolnego znaczenia, jakie możemy przyporządkować zmiennej

x

w zbiorze liczb rzeczywistych.

134

2. KLASYCZNA LOGIKA PREDYKATÓW

Sposób rozumowania odpowiadający regule opuszczania dużego

kwantyfikatora stosujemy wówczas, gdy na podstawie

a > 0 ⇒ ∀x.(x > 0 ⇒ x + a > 0)

uznajemy

a > 0 ⇒ (x > 0 ⇒ x + a > 0)

.

Regułę dołączania dużego kwantyfikatora stosujemy wówczas,

gdy na podstawie

y > 0 ⇒ (x > 0 ⇒ x + y > 0)

uznajemy

y > 0 ⇒ ∀x.(x > 0 ⇒ x + y > 0)

.

Warunek nałożony na poprzednik (

ϕ

) implikacji, do której na-

stępnika (

φ

) dołączamy duży kwantyfikator jest istotny. Na podsta-

wie

y > 0 ⇒ (x > 0 ⇒ x + y > 0)

nie możemy uznać

y > 0 ⇒ ∀y.(x > 0 ⇒ x + y > 0)

58

.

Regule opuszczania małego kwantyfikatora odpowiada rozumo-

wanie, gdy na podstawie

∃x.(0 < x ∧ x ≤ y) ⇒ 0 < y

uznajemy

0

< x ∧ x ≤ y ⇒ 0 < y

.

Sposób rozumowania odpowiadający regule dołączania małego

kwantyfikatora możemy zastosować do

0

< x ∧ x ≤ y ⇒ 0 < y

.

58

W tym wypadku kolidowałoby to z regułą podstawiania. Mianowicie zgodnie

z tą regułą za zmienną wolną

y

moglibyśmy podstawić dowolną liczbę dodatnią

i stosując regułę odrywania otrzymalibyśmy:

∀y.(x > 0 ⇒ x + y > 0)

. Podsta-

wiając zaś dowolną liczbę za zmienną

x

, lub po prostu wiążąc ją dużym kwan-

tyfikatorem otrzymujemy zdanie fałszywe. Tymczasem formuła:

y > 0 ⇒ (x >

0

⇒ x + y > 0)

jest spełniona.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

135

Warunek nałożony na następnik (

φ

) implikacji, do której po-

przednika (

ϕ

) dołączamy mały kwantyfikator jest istotny. Na pod-

stawie

x ≥ 0 ⇒ (y > x ⇒ y > 0)

nie możemy uznać

∃x.(x ≥ 0) ⇒ (y > x ⇒ y > 0)

.

DEFINICJA DOWODU W RACHUNKU PREDYKATÓW

Formuła

ϕ

ma dowód ze zbioru

Σ

formuł języka rachunku kwan-

tyfikatorów – co zapisujemy:

Σ

ϕ

– wtedy i tylko wtedy, gdy istnieje

skończony ciąg formuł

ϕ

0

, ϕ

1

, . . ., ϕ

n

taki, że

ϕ

n

=

ϕ

,

gdzie „=” jest skrótem dla „ jest równokształtne z”

oraz dla każdego

i (0 ≤ i ≤ n)

spełniony jest jeden z warunków

(I)

ϕ

i

jest elementem

Σ

,

(II)

ϕ

i

jest tautologią (języka rachunku predykatów),

(III)

ϕ

i

jest aksjomatem (teorii) identyczności,

(IV) istnieją

ϕ

j

,

ϕ

k

takie, że

ϕ

k

=

ϕ

j

⇒ ϕ

i

;

j, k < i

,

(V) istnieją

ϕ

k

, k < i

, oraz term

t

i zmienna

v

takie, że

t

jest pod-

stawialne za

v

w formule

ϕ

k

i

ϕ

k

(

v/t) = ϕ

i

,

(VI) istnieje

ϕ

k

, k < i

, takie, że

ϕ

k

=

φ ⇒ ∀v.ψ

oraz

ϕ

i

=

φ ⇒ ψ

,

(VII) istnieje

ϕ

k

, k < i

, takie, że

ϕ

k

=

φ ⇒ ψ

i zmienna

v

nie występuje

jako zmienna wolna w

φ

oraz

ϕ

i

=

φ ⇒ ∀v.ψ

,

(VIII) istnieje

ϕ

k

, k < i

, takie, że

ϕ

k

=

∃v.φ ⇒ ψ

oraz

ϕ

i

=

φ ⇒ ψ

,

(IX) istnieje

ϕ

k

, k < i

, takie, że

ϕ

k

=

φ ⇒ ψ

i zmienna

v

nie występuje

jako zmienna wolna w

ψ

oraz

ϕ

i

=

∃v.φ ⇒ ψ

.

Podana definicja dowodu jest jedną z możliwych definicji. Istnieją

inne jej równoważne w tym sensie, że niezależnie którą z tych definicji

136

2. KLASYCZNA LOGIKA PREDYKATÓW

zastosujemy dowód z danego zbioru formuł będą miały te same zbiory
formuł

58

.

(DEF. tezy rachunku predykatów) Formuły mające dowód z pustego
zbioru formuł to tezy rachunku predykatów.

PRZYKŁADY

Formuła

∀x.P x ⇒ P x

ma dowód z pustego zbioru formuł, czyli

∀x.P x ⇒ P x

.

DOWÓD
1.

∀x.P x ⇒ ∀x.P x

tautologia

2.

∀x.P x ⇒ P x

(O

∀

; 1)

Zauważmy, że dla dowolnej zmiennej

v

i dowolnej formuły

ϕ

ana-

logicznie można dowieść, że

59

T1.

∀v.ϕ ⇒ ϕ.

Zamiast dowodzić poszczególnych formuł będziemy więc poda-

wali schematy dowodów. Z takiego schematu będzie można otrzymać
dowód każdej formuły o schemacie formuły podanej jako teza.

Dowód z pustego zbioru formuł ma formuła

ϕ ⇒ ∃v.ϕ

czyli jest ona tezą rachunku predykatów, a więc zachodzi

T2.

ϕ ⇒ ∃v.ϕ.

DOWÓD
1.

∃v.ϕ ⇒ ∃v.ϕ

tautologia

58

Po raz pierwszy pełny sformalizowany system rachunku predykatów został

przedstawiony przez Fregego w 1878 r., a opublikowany w [1879].

59

Zauważmy, że mówiąc tu o dowolnej zmiennej

v

mamy na uwadze to, że za-

kresem zmiennej metaprzedmiotowej „

v

” jest zbiór wszystkich symboli zmiennych

języka rachunku predykatów. A więc może to być dowolna zmienna:

x

0

, x

1

, . . .

.

Podobnie, gdy mówimy o dowolnej formule:

ϕ

może być dowolną formułą, jaką

daje się skonstruować w tu określonym języku rachunku predykatów.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

137

2.

ϕ ⇒ ∃v.ϕ

(O

∃

; 1)

Zastosowanie reguły podstawiania będziemy wskazywali podając

numer wiersza dowodowego, w którym dokonuje się podstawienia oraz
zmienną i podstawiany za nią term.

T3.

∀v.ϕ ⇒ ϕ(v/t)

, jeżeli term

t

jest podstawialny za

v

w

ϕ

.

DOWÓD
1.

∀v.ϕ ⇒ ∀v.ϕ

tautologia

2.

∀v.ϕ ⇒ ϕ

(O

∀

; 1)

3.

∀v.ϕ ⇒ ϕ(v/t)

(2;

v

/t)

jeżeli term

t

jest podstawialny za

v

w

ϕ

.

T4.

ϕ(v/t) ⇒ ∃v.ϕ

, jeżeli term

t

jest podstawialny za

v

w

ϕ

.

DOWÓD
1.

∃v.ϕ ⇒ ∃v.ϕ

tautologia

2.

ϕ ⇒ ∃v.ϕ

(O

∃

; 1)

3.

ϕ(v/t) ⇒ ∃v.ϕ

(2;

v

/t)

jeżeli term

t

jest podstawialny za

v

w

ϕ

.

Zrezygnujemy z przeprowadzania dowodów ściśle według defini-

cji. Zwykle takie dowody są długie i nieprzejrzyste. Krótsze, a dla
znających podstawowe prawa i reguły logiki prostsze są dowody, w
których korzysta się z tych praw i reguł. Pisząc w wierszu dowodo-
wym nazwę tezy wskazujemy, że dowód formuły znajdującej się w
tym wierszu przebiega według schematu dowodu tezy, na którą się
powołujemy. Korzystać będziemy również z praw logiki zdań – jest
oczywiste, że stosują się one do dowodów w rachunku predykatów –
może to być wskazywane przez podanie nazwy zastosowanego prawa
lub jego treści.

Zauważmy, że w zasadzie od samego początku nasze twierdze-

nia o logice dowodzone z pominięciem opisu zastosowanych środków
logicznych. Zresztą w metateorii stosować musimy środki, które nie
koniecznie były przedmiotem naszych rozważań teoretycznych.

Ten sposób postępowania, że dowód przeprowadzany jest tak, aby

intuicja logiczna tego, do kogo skierowany jest tekst, wystarczała dla
stwierdzenia poprawności dowodu, jest powszechnie praktykowany

138

2. KLASYCZNA LOGIKA PREDYKATÓW

przez matematyków. W dowodzie pojawiają się różnego rodzaju luki,
czasem sygnalizowane zwrotami w rodzaju: „łatwo zauważyć”, „pro-
sto wynika”, „ jest oczywiste”. Wielkość luk zależy od adresata. Gdy
tekst skierowany jest dla osób o mniejszym doświadczeniu matema-
tycznym, np. studentów, luka będzie mniejsza niż gdy skierowany
będzie do środowiska specjalistów w danej dziedzinie. Matematycy
stosują się do swoistego „gentelmen agreement” nakazującego auto-
rowi rzetelne uzupełnienie luki, gdy domaga się tego adresat. Czasem
przy próbie uzupełnienia luki okazuje się, że dowód jest niepoprawny.
Bywa, że znajduje się dowód poprawny. Pierre de Fermat (1601–65)
ograniczył się do stwierdzenia na marginesie książki: „dowód mam,
ale za mało tu miejsca, by go zapisać”. Trudno zgodzić się z tym
na tle dzisiejszej wiedzy na temat słynnego Wielkiego Twierdzenia
Fermata (równanie

x

n

+

y

n

=

z

n

, n > 2

, nie ma rozwiązania w licz-

bach naturalnych). Mimo zaangażowania się wielu bardzo wybitnych
i mniej wybitnych matematyków, mimo wysokich nagród i ewentual-
nej sławy, znaleziony po 350 latach dowód wymaga środków, którymi
nie dysponował Fermat.

T5.

∃v

1

.∀v

2

.ϕ ⇒ ∀v

2

.∃v

1

.ϕ

DOWÓD
1.

∀v

2

.ϕ ⇒ ϕ

T1

2.

ϕ ⇒ ∃v

1

.ϕ

T2

3.

∀v

2

.ϕ ⇒ ∃v

1

.ϕ

(SYLL; 1,2)

4.

∃v

1

.∀v

2

.ϕ ⇒ ∃v

1

.ϕ

(D

∃

; 3)

5.

∃v

1

.∀v

2

.ϕ ⇒ ∀v

2

.∃v

1

.ϕ

(D

∀

; 4)

T6.

∃v.(ϕ ∧ ψ) ⇒ (∃v.ϕ ∧ ∃v.ψ

)

DOWÓD
1.

∃v.ϕ ⇒ ∃v.ϕ

tautologia

2.

ϕ ⇒ ∃v.ϕ

(O

∃

; 1)

3.

∃v.ψ ⇒ ∃v.ψ

tautologia

4.

ψ ⇒ ∃v.ψ

(O

∃

; 3)

5.

(

ϕ ∧ ψ) ⇒ (∃v.ϕ ∧ ∃v.ψ)

(

α ⇒ γ

β ⇒ δ

α ∧ β ⇒ γ ∧ δ

; 2,4)

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

139

6.

∃v.(ϕ ∧ ψ) ⇒ (∃v.ϕ ∧ ∃v.ψ)

(D

∃

; 5)

T7.

t ≡ t

DOWÓD
1.

x ≡ x

aksjomat Id1

2.

t ≡ t

(

1;

x/t

).

Teza T7 głosi, że identyczność jest zwrotna.

T8.

(t ≡ t

1

)

⇒ (t

1

≡ t)

DOWÓD
1.

[(

x ≡ x

1

)

∧ (x ≡ x)] ⇒ (x

1

≡ x)

aksjomat Id3

2.

{[(x ≡ x

1

)

∧ (x ≡ x)] ⇒ (x

1

≡ x)}

⇒ {(x ≡ x) ⇒ [(x ≡ x

1

)

⇒ (x

1

≡ x)]}

tautologia

3.

(

x ≡ x) ⇒ [(x ≡ x

1

)

⇒ (x

1

≡ x)]

(MP; 1,2)

4.

(

x ≡ x)

aksjomat Id1

5.

(

x ≡ x

1

)

⇒ (x

1

≡ x)

(MP; 4,3)

6.

(

t ≡ t

1

)

⇒ (t

1

≡ t)

(

5;

x/t, x

1

/t

1

)

Teza T8 głosi, że identyczność jest symetryczna.

T9.

(t ≡ t

1

)

⇒ [(t

1

≡ t

2

)

⇒ (t ≡ t

2

)]

DOWÓD
1.

[(

x

1

≡ x) ∧ (x

1

≡ x

2

)]

⇒ (x ≡ x

2

)

aksjomat Id3

2.

{[(x

1

≡ x) ∧ (x

1

≡ x

2

)]

⇒ (x ≡ x

2

)

}

⇒ {(x

1

≡ x) ⇒ [(x

1

≡ x

2

)

⇒ (x ≡ x

2

)]

}

tautologia

3.

(

x

1

≡ x) ⇒ [(x

1

≡ x

2

)

⇒ (x ≡ x

2

)]

(MP; 1,2)

4.

(

x ≡ x

1

)

⇒ (x

1

≡ x)

T8

5.

(

x ≡ x

1

)

⇒ [(x

1

≡ x

2

)

⇒ (x ≡ x

2

)]

(SYLL; 3,4)

6.

(

t ≡ t

1

)

⇒ [(t

1

≡ t

2

)

⇒ (t ≡ t

2

)]

(

5;

x/t, x

1

/t

1

, x

2

/t

2

)

Teza T9 głosi, że identyczność jest przechodnia.

A oto niektóre ważniejsze prawa, schematy i reguły klasycznej

logiki predykatów. Rozumiemy je analogicznie do praw, schematów i
reguł rachunku zdań.

ϕ/∀v.ϕ

– reguła generalizacji

140

2. KLASYCZNA LOGIKA PREDYKATÓW

∀v.ϕ ⇒ ϕ(v/t)

60

,

jeśli term

t

jest podstawialny za

v

ϕ(v/t) ⇒ ∃v.ϕ

61

,

jeśli term

t

jest podstawialny za

v

∀v.ϕ ⇒ ∃v.ϕ
∀v

1

.∀v

2

.ϕ ⇔ ∀v

2

.∀v

1

.ϕ

∃v

1

.∃v

2

.ϕ ⇔ ∃v

2

.∃v

1

.ϕ

∃v

1

.∀v

2

.ϕ ⇒ ∀v

2

.∃v

1

.ϕ

62

Kwantyfikatory a spójnik negacji – prawa De Morgana

¬∀v.ϕ ⇔ ∃v.¬ϕ
¬∃v.ϕ ⇔ ∀v.¬ϕ

Kwantyfikatory a spójnik implikacji

∀v.(ϕ ⇒ φ) ⇒ (∀v.ϕ ⇒ ∀v.φ)
∀v.(ϕ ⇒ φ) ⇒ (∃v.ϕ ⇒ ∃v.φ)

Kwantyfikatory a spójnik koniunkcji

∀v.(ϕ ∧ φ) ⇔ (∀v.ϕ ∧ ∀v.φ)
∃v.(ϕ ∧ φ) ⇒ (∃v.ϕ ∧ ∃v.φ)

Kwantyfikatory a spójnik alternatywy

60

Teza ta tradycyjnie określana jest jako dictum de omni.

61

Teza ta tradycyjnie określana jest jako dictum de singulo. Teza ta głosi, że

na to aby dowieść zdania egzystencjalnego stwierdzającego istnienie przedmiotu
spełniającego określony warunek, wystarczy określić przedmiot, który ten waru-
nek spełnia. Takie dowody zdań egzystencjalnych nazywa się dowodami efektyw-
nymi. Zdania egzystencjalnego można również dowieść (korzystając z prawa De
Morgana) przez sprowadzenie do niedorzeczności zdania stwierdzającego, że ża-
den przedmiot nie spełnia danego warunku. Takie dowody nie dają jednak na ogół
sposobu konstrukcji przedmiotu spełniającego warunek, nie są więc efektywne.

62

Warto tu zauważyć, że prawem nie jest

∀v

2

.∃v

1

.φ ⇒ ∃v

1

.∀v

2

.φ

.

Prawdziwe nie jest zdanie

∀x.∃y.(x < y) ⇒ ∃y.∀x.(x < y)

,

czyli prawdziwe nie jest zdanie:

jeżeli dla każdej liczby istnieje liczba od niej większa, to istnieje liczba taka,

która jest większa od każdej liczby.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

141

(

∀v.ϕ ∨ ∀v.φ) ⇒ ∀v.(ϕ ∨ φ)

∃v.(ϕ ∨ φ) ⇔ (∃v.ϕ ∨ ∃v.φ)

Kwantyfikatory a spójnik równoważności – prawa ekstensjonalności

∀v.(ϕ ⇔ φ) ⇒ [∀v.(ϕ ⇒ φ) ∧ ∀v.(φ ⇒ ϕ)]
∀v.(ϕ ⇔ φ) ⇒ (∀v.ϕ ⇔ ∀v.φ)
∀v.(ϕ ⇔ φ) ⇒ (∃v.ϕ ⇔ ∃v.φ).

2.2.2. Niesprzeczność rachunku predykatów

Wiele pojęć i twierdzeń metalogiki predykatów nie bardzo różni

się w swoim sformułowaniu – ale, oczywiście, nie w treści – od pojęć i
twierdzeń, których definicje i dowody podaliśmy dla logiki zdań. Ma
to miejsce np. dla pojęcia sprzeczności.

(DEF. sprzecznego zbioru formuł) Zbiór formuł jest sprzeczny wtedy
i tylko wtedy, gdy z tego zbioru ma dowód dowolna formuła.

(DEF. niesprzecznego zbioru formuł) Zbiór formuł jest niesprzeczny
wtedy i tylko wtedy, gdy nie jest sprzeczny.

W wypadku rachunku zdań nie było możliwe mówienie o sprzecz-

ności zdania prostego. Znaczenia zdań były bowiem całkowicie cha-
rakteryzowane przez przysługujące im wartości logiczne. Inaczej jest
w wypadku rachunku predykatów, w którym analizujemy zdania w
ich wewnętrznej strukturze. Oczywiście, zdanie

ϕ

jest sprzeczne, gdy

sprzeczny jest zbiór

{ϕ}

.

(DEF. formuły wewnętrznie sprzecznej) Formuła

ϕ

jest wewnętrznie

sprzeczna (wewnętrznie kontradyktoryczna) wtedy i tylko wtedy, gdy
sprzeczny jest zbiór

{ϕ}

.

Zdaniami wewnętrznie kontradyktorycznymi są np. wszystkie

zdania postaci

∃x.[P (x) ∧ ¬P (x)]

.

Teoria rozumiana jako zbiór formuł taki, że każda formuła mająca

dowód z tego zbioru jest jego elementem, czyli tezą (zbiór zamknięty

142

2. KLASYCZNA LOGIKA PREDYKATÓW

na operację konsekwencji) powinna być niesprzeczna. Rachunek lo-
giczny, jako zbiór formuł mających dowód z pustego zbioru formuł,
aby wart był rozważania, musi być niesprzeczny

63

.

Chodzi więc o to,

by zbiór jego tez – formuł mających dowód z pustego zbioru (formuł)
– nie był równy zbiorowi wszystkich formuł języka tego rachunku,
czyli żeby dla dowolnego

ϕ

nie było prawdą, że:

ϕ

.

W celu dowiedzenia niesprzeczności rachunku predykatów wy-

starczy:

1. znaleźć takie przyporządkowanie formuł języka rachunku predy-

katów zdaniom języka rachunku zdań (taką interpretację formuł
języka rachunku predykatów w zbiorze zdań języka rachunku
zdań), żeby zachowana była negacja, czyli jeżeli formule

ϕ

przy-

porządkowane jest zdanie

α

, to formule

¬ϕ

przyporządkowane

jest zdanie

¬α

(jeżeli formuła

ϕ

interpretowana jest jako zdanie

α

, to formuła

¬ϕ

interpretowana jest jako

¬α

);

2. pokazać, że niesprzeczny jest zbiór wszystkich zdań przyporząd-

kowanych tezom rachunku predykatów.

Gdyby zbiór tez języka rachunku predykatów był równy zbiorowi

wszystkich jego formuł, to sprzeczny byłby zbiór zdań, które przy-
porządkowane są zgodnie z pkt. 1 i 2 tezom rachunku predykatów.
Jeżeli więc pokażemy niesprzeczność tego zbioru zdań, to tym samym
dowiedziemy niesprzeczności rachunku predykatów.

Opisany sposób dowodzenia niesprzeczności ma szersze zastoso-

wanie. Analogicznie dowodzić można niesprzeczności różnych zbio-
rów. Taki dowód wymaga jednak, by niesprzeczny był zbiór formuł,
w którym interpretujemy (syntaktycznie) zbiór formuł, którego nie-
sprzeczności dowodzimy. Uzyskany wynik jest więc zależny od nie-
sprzeczności innego zbioru formuł. Jest to więc wynik relatywny. Mó-

63

Logicy – z różnych zresztą powodów – zainteresowali się systemami, w któ-

rych tezami mogą być jakieś zdanie i jego zaprzeczenie. Powstały różne systemy
logik parakonsystentnych. Na przykład St. Jaśkowski stworzył tzw. dyskusyjny
rachunek zdań. Zob. Jaśkowski [1948]. Jednak również w wypadku tych „sprzecz-
nych” systemów nie może mieć miejsce przepełnienie, tj. zbiór tez nie może po-
krywać się ze zbiorem wszystkich wyrażeń poprawnie zbudowanych.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

143

wimy wówczas o relatywnej niesprzeczności jednego zbioru formuł ze
względu na niesprzeczność innego zbioru formuł.

Wpierw dowiedziemy niesprzeczności klasycznego rachunku pre-

dykatów dla języka bez predykatu identyczności. Rachunek zdań jest
niesprzeczny, bowiem – jak wiemy – nie każde jego zdanie jest tau-
tologią. Otóż, aby udowodnić niesprzeczność rachunku predykatów
dla języka bez predykatu równości, wystarczy pokazać, że wszyst-
kim tezom tego rachunku przyporządkowane są (musi to być przypo-
rządkowanie powyżej omówionego typu, a więc zachowujące negację)
wyłącznie tautologie języka rachunku zdań.

TWIERDZENIE 1

64

.

Rachunek predykatów dla języka bez predykatu identyczności jest
niesprzeczny.

DOWÓD

Niech

h

będzie odwzorowaniem zbioru formuł języka rachunku

predykatów w zbiór zdań języka rachunku zdań takim, że

(I)

h(ϕ)

=

p

gdy

ϕ

jest formułą atomową

(II)

h(¬ϕ)

=

¬h(ϕ)

(III)

h(∀v.ϕ)

=

h(ϕ)

(IV)

h(∃v.ϕ)

=

h(ϕ)

(V)

h(ϕ ∨ φ)

=

h(ϕ) ∨ h(φ)

(VI)

h(ϕ ∧ φ)

=

h(ϕ) ∧ h(φ)

(VII)

h(ϕ ⇒ φ) = h(ϕ) ⇒ h(φ)

(VIII)

h(ϕ ⇔ φ) = h(ϕ) ⇔ h(φ)

Przez indukcję po długości dowodu w rachunku predykatów (dla

języka bez predykatu równości) pokażemy, że odwzorowanie

h

tezom

rachunku predykatów przyporządkowuje tylko tautologie języka ra-
chunku zdań.

Niech

ϕ

będzie dowolną tezą języka rachunku predykatów. Niech

ciąg

64

Pierwszy dowód niesprzeczności rachunku predykatów został opublikowany

w 1928 r. przez matematyków niemieckich D. Hilberta i W. Ackermanna. Podany
tu dowód w istocie nie odbiega od tamtego dowodu.

144

2. KLASYCZNA LOGIKA PREDYKATÓW

ϕ

0

, ϕ

1

, . . ., ϕ

n

(=

ϕ)

będzie dowodem tej tezy.

Z definicji dowodu,

ϕ

0

jest tautologią języka rachunku predyka-

tów.

Należy więc pokazać, że tautologie języka rachunku predykatów

„tłumaczone” są przez

h

na tautologie języka rachunku zdań.

Tautologie języka rachunku predykatów są – w myśl definicji –

formułami otrzymanymi z tautologii języka rachunku zdań przez pod-
stawienie w miejsce liter zdaniowych formuł języka rachunku predy-
katów.

Dla każdej formuły

ϕ

istnieje zdanie

α

języka rachunku zdań ta-

kie, że formuła

ϕ

może być otrzymana z

α

przez podstawienie w

miejsce liter zdaniowych formuł atomowych i formuł postaci:

∀v.φ

,

∃v.φ

. Oczywiście, podstawienie to odbywa się jednocześnie i zgodnie

z zasadą, że za te same litery podstawia się te same formuły. Otóż,
jeżeli

ϕ

jest tautologią, to

α

też jest tautologią. Tautologie języka

rachunku predykatów przez opisane podstawienie otrzymuje się bo-
wiem tylko z tautologii języka rachunku zdań. Odwzorowanie

h

jest

tego rodzaju, że formule

ϕ

przyporządkowuje zdanie, które można

otrzymać ze zdania

α

przez podstawienie w miejsce liter zdaniowych

zdań zbudowanych wyłącznie za pomocą litery zdaniowej

p

(i, oczywi-

ście, spójników oraz nawiasów). Jeżeli

α

jest tautologią, to i to zdanie

jest tautologią. Bowiem jeżeli w tautologii języka rachunku zdań w
miejsce liter zdaniowych za te same litery jednocześnie podstawimy
te same zdania zbudowane tylko za pomocą litery

p

, to otrzmamy

tautologię języka rahunku zdań.

ZAŁOŻENIE INDUKCYJNE: Niech

h(ϕ

i

)

, dla

i ≤ k

, będzie tautolo-

gią języka rachunku zdań.

Pokażemy, że

h(ϕ

k+1

)

jest tautologią języka rachunku zdań.

Gdy

ϕ

k+1

jest tautologią języka rachunku predykatów, to

h(ϕ

k+1

)

jest tautologią języka rachunku zdań.

Niech więc

ϕ

k+1

będzie otrzymane przez zastosowanie reguły MP

do formuł

ϕ

j

,

ϕ

j

⇒ ϕ

k+1

.

Ponieważ z założenia indukcyjnego

h(ϕ

j

)

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

145

oraz

h(ϕ

j

⇒ ϕ

k+1

)

są tautologiami języka rachunku zdań, więc również

h(ϕ

k+1

)

jest tautologią języka rachunku zdań.

Wypadek zastosowania każdej z pozostałych reguł jest jeszcze

krótszy. Zauważmy bowiem, że gdy któraś z tych reguł jest zastoso-
wana do

ϕ

j

,

to

h(ϕ

j

) =

h(ϕ

k+1

)

.

A więc, ponieważ z założenia induk-

cyjnego

h(ϕ

j

)

jest tautologią języka rachunku zdań, to i

h(ϕ

k+1

)

jest

tautologią tego języka.

TWIERDZENIE 2.

Rachunek predykatów z identycznością jest niesprzeczny.

DOWÓD

Formuły języka rachunku predykatów z predykatem identyczno-

ści odwzorowujemy w zbiór zdań języka rachunku zdań w taki sam
sposób, jak to było w dowodzie twierdzenia 1. Tym razem oprócz
tautologii języka rachunku zdań pojawia się jeszcze litera zdaniowa

p

. Zatem zbiór tez rachunku predykatów z identycznością zostaje od-

wzorowany w zbiór wszystkich i tylko zdań, które mają dowód przy
zastosowaniu jedynie reguły odrywania ze zbioru tautologii języka
rachunku zdań zbudowanych za pomocą litery

p

(oraz nawiasów i

spójników języka rachunku zdań) uzupełnionego o literę

p

(tylko w

tym miejscu jest więc inaczej niż wypadku twierdzenia poprzedniego).
Warunkiem wystarczającym niesprzeczności tez rachunku predyka-
tów z identycznością jest niesprzeczność zbioru

Cn{p}

, gdzie

Cn

jest

operacją konsekwencji dla rachunku zdań. Zbiór

Cn{p}

ma model.

Modelem tym jest mianowicie zbiór

{p}

(i każdy inny podzbiór li-

ter zdaniowych zawierający literę

p

). Z uogólnionego twierdzenia o

niesprzeczności dla rachunku zdań mamy, że zbiór

Cn{p}

jest nie-

sprzeczny.

2.2.3. Twierdzenie o dedukcji

Twierdzenie o dedukcji dla rachunku predykatów w swoim sfor-

mułowaniu różni się od twierdzenia o dedukcji dla rachunku zdań
tylko pewnym zastrzeżeniem spowodowanym tym, że w rachunku pre-
dykatów – inaczej niż w rachunku zdań – oprócz zdań wyrażeniami
poprawnie zbudowanymi są również formuły nie będące zdaniami.

146

2. KLASYCZNA LOGIKA PREDYKATÓW

TWIERDZENIE 3. (O DEDUKCJI).

Niech

ϕ

będzie zdaniem (

φ

nie musi być zdaniem).

Σ

∪ {ϕ} φ

wtedy i tylko wtedy, gdy

Σ

ϕ ⇒ φ

.

DOWÓD

Dowód tego twierdzenia przebiega w analogiczny sposób jak w

wypadku rachunku zdań, jest jednak bardziej złożony. We fragmencie,
w którym dowodzimy, że

jeżeli

Σ

∪ {ϕ} φ

, to

Σ

ϕ ⇒ φ

trzeba rozważyć zastosowanie reguł rachunku predykatów.

Niech

γ

1

, γ

2

, . . ., γ

n

będzie dowodem formuły

φ

ze zbioru

Σ

∪ {ϕ}

.

γ

1

może być elementem zbioru

Σ

∪{ϕ}

, tautologią języka rachunku

kwantyfikatorów lub aksjomatem teorii identyczności. Dowód, że for-
muła

ϕ ⇒ φ

ma dowód ze zbioru

Σ

niczym w istocie nie różni się od

analogicznego wypadku w dowodzie twierdzenia o dedukcji dla logiki
zdań.

ZAŁOŻENIE INDUKCYJNE: Jako założenie indukcyjne przyjmu-
jemy, że ze zbioru

Σ

istnieje dowód formuły

ϕ ⇒ γ

i

, i ≤ k

.

W dowodzie tezy indukcyjnej ograniczymy się do pokazania jak

postępujemy w wypadku reguły podstawiania oraz reguł dołączania
(D

∀

) i opuszczania (O

∀

) dużego kwantyfikatora.

(Reguła podstawiania) Niech

γ

k+1

będzie otrzymane przez podsta-

wienie termu

t

na miejsce zmiennej

v

w

γ

i

, czyli

γ

k+1

=

γ

i

(

v/t)

.

Niech

ψ

1

, ψ

2

, . . ., ψ

m

(=

ϕ ⇒ γ

i

)

będzie dowodem ze zbioru

Σ

formuły

ϕ ⇒ γ

i

. Z założenia twierdzenia o dedukcji

ϕ

jest zdaniem, czyli nie za-

wiera zmiennych wolnych, zatem

(

ϕ ⇒ γ

i

)(

v/t) = ϕ ⇒ γ

i

(

v/t)

. Dowód

ϕ ⇒ γ

k+1

ze zbioru

Σ

uzyskamy dopisując

ϕ ⇒ γ

i

(

v/t)

jako kolejny wy-

raz do ciągu

ψ

1

, ψ

2

, . . ., ψ

m

, czyli dopisując formułę otrzymaną przez

zastosowanie do

ψ

m

reguły podstawiania.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

147

(D

∀

) Pokażemy, że jeżeli

γ

k+1

zostało otrzymane przez zastosowanie

reguły D

∀

do

γ

i

, to ze zbioru

Σ

istnieje dowód dla

ϕ ⇒ γ

k+1

. Niech

γ

i

=

ξ ⇒ λ

i niech

γ

k+1

=

ξ ⇒ ∀v.λ

. Z tego wynika, że

ξ

nie zawiera

zmiennej

v

jako wolnej. Z założenia indukcyjnego dostajemy, że ze

zbioru

Σ

istnieje dowód dla

ϕ ⇒ γ

i

, czyli dla

ϕ ⇒ (ξ ⇒ λ)

. Niech

ψ

1

, ψ

2

, . . ., ψ

m

[=

ϕ ⇒ (ξ ⇒ λ)]

będzie tym dowodem. Aby uzyskać

dowód formuły

ϕ ⇒ γ

k+1

, czyli formuły

ϕ ⇒ (ξ ⇒ ∀v.λ)

, do ciągu

ψ

1

, ψ

2

, . . ., ψ

m

dopisujemy następujące wyrazy

(m+1).

[

ϕ ⇒ (ξ ⇒ λ)] ⇒ (ϕ ∧ ξ ⇒ λ)

tautologia

(m+2).

ϕ ∧ ξ ⇒ λ

(MP; m, m+1)

(m+3).

ϕ ∧ ξ ⇒ ∀v.λ

(D

∀

; m+2)

(m+4).

(

ϕ ∧ ξ ⇒ ∀v.λ) ⇒ [ϕ ⇒ (ξ ⇒ ∀v.λ)]

tautologia

(m+5).

ϕ ⇒ (ξ ⇒ ∀v.λ)

(MP; m+3, m+4)

Zauważmy, że do wiersza (m+2) można było zastosować regułę

dołączania dużego kwantyfikatora ponieważ:

1. z założenia twierdzenia o dedukcji

ϕ

jest zdaniem,

a

2.

ξ

nie zawiera

v

jako zmiennej wolnej.

γ

k+1

(=

ξ ⇒ ∀v.λ

) zostało

uzyskane z

γ

i

(=

ξ ⇒ λ

) przez zastosowanie reguły D

∀

, co było

możliwe tylko w wypadku, gdy

ξ

nie zawiera

v

jako zmiennej

wolnej.

(O

∀

) Niech

γ

k+1

będzie otrzymane przez zastosowanie reguły opusz-

czania dużego kwantyfikatora do

γ

i

(=

ξ ⇒ ∀v.λ)

, czyli

γ

k+1

(=

ξ ⇒ λ)

.

Niech

ψ

1

, ψ

2

, . . ., ψ

m

[=

ϕ ⇒ (ξ ⇒ ∀v.λ)]

będzie dowodem ze zbioru

Σ

formuły

ϕ ⇒ γ

i

. Dowód ze zbioru

Σ

formuły

ϕ ⇒ (ξ ⇒ λ)

uzyskujemy

dopisując do ciągu

ψ

1

, ψ

2

, . . ., ψ

m

następujące wyrazy

(m+1).

[

ϕ ⇒ (ξ ⇒ ∀v.λ)] ⇒ (ϕ ∧ ξ ⇒ ∀v.λ)

tautologia

(m+2).

ϕ ∧ ξ ⇒ ∀v.λ

(MP; m, m+1)

(m+3).

ϕ ∧ ξ ⇒ λ

(O

∀

, m+2)

(m+4).

(

ϕ ∧ ξ ⇒ λ) ⇒ [ϕ ⇒ (ξ ⇒ λ)

tautologia

(m+5).

ϕ ⇒ (ξ ⇒ λ)

(MP;m+3, m+4)

Dowód tezy

jeżeli

Σ

ϕ ⇒ φ

, to

Σ

∪ {ϕ} φ

148

2. KLASYCZNA LOGIKA PREDYKATÓW

przebiega w sposób nieistotnie różniący się od analogicznego frag-
mentu dowodu twierdzenia o dedukcji dla rachunku zdań: do dowodu

ϕ ⇒ φ

ze zbioru

Σ

dopisujemy jako kolejne wyrazy ciągu

ϕ

– jest

to element zbioru

Σ

∪ {ϕ}

– oraz

φ

– co uzyskujemy stosując regułę

odrywania.

Kiedy mamy dowód

φ

ze zbioru

Σ

, a dowodzimy

ϕ

ze zbioru

Σ

i w ciągu dowodowym pojawia się

φ

, to dowód

ϕ

możemy „skrócić”

zastępując fragment ciągu będący dowodem

φ

powołaniem się na to,

że

φ

ma dowód z

Σ

. W szczególnym wypadku może to być powoła-

nie się na już udowodnione tezy (formuły mające dowód z pustego
zbioru formuł). Twierdzenie o dedukcji daje dodatkową możliwość
„skracania” – pozwala na wykorzystywanie dowodu

λ ⇒ ξ

ze zbioru

Σ

dowodem

ξ

ze zbioru

Σ

∪ {λ}

, i na odwrót. Korzystając ze wskaza-

nych „skrótów” w opisie dowodu, w niczym nie naruszamy jego istoty,
czyli nie zmieniamy jego definicji.

PRZYKŁAD

T10.

∀x.(P x ⇒ Qx) ⇒ (∃x.P x ⇒ ∃x.Qx).

DOWÓD
1.

∀x.(P x ⇒ Qx) ⇒ (P x ⇒ Qx)

T3

2.

∀x.(P x ⇒ Qx) P x ⇒ Qx

65

(Tw. o dedukcji; 1)

3.

Qx ⇒ ∃x.Qx

T4

4.

∀x.(P x ⇒ Qx) P x ⇒ ∃x.Qx

(SYLL; 2, 3)

5.

∀x.(P x ⇒ Qx) ∃x.P x ⇒ ∃x.Qx

(D

∃

; 4)

6.

∀x.(P x ⇒ Qx) ⇒ (∃x.P x ⇒ ∃x.Qx)

(tw. o dedukcji; 5)

Założenie, że poprzednik implikacji – do której stosujemy twier-

dzenie o dedukcji – jest zdaniem jest istotne. W wyżej przeprowadzo-
nym dowodzie twierdzenia o dedukcji było ono wykorzystane, gdy
rozważaliśmy zastosowanie reguły podstawiania oraz reguły dołącza-
nia dużego kwantyfikatora. Na przykładzie – będzie to przykład od-
noszący się do reguły podstawiania – pokażemy, że jego zignorowanie

65

Jeżeli nie prowadzi to do nieporozumienia zamiast:

{ϕ

1

, . . . , ϕ

n

} φ

pi-

szemy:

ϕ

1

, . . . , ϕ

n

φ

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

149

prowadzi do niepożądanych konsekwencji; do możliwości otrzymywa-
nia fałszywych wniosków z prawdziwych przesłanek.

PRZYKŁAD

Niech

Σ

będzie teorią nierówności

> (⊆ × )

.

Zatem prawdą jest, że

1.

Σ

x > 2 ⇒ x > 1.

Przejście od (1) do (2)

2.

Σ

∪ {x > 2} x > 1

nie jest uprawnione. Stosując regułę generalizacji otrzymamy bowiem

3.

Σ

∪ {x > 2} ∀x.(x > 1)

.

Ponowne zastosowanie twierdzenia o dedukcji daje

4.

Σ

x > 2 ⇒ ∀x.(x > 1)

.

Teraz podstawiamy za zmienną wolną

x

stałą, powiedzmy

3

. Do-

stajemy

5.

Σ

3 > 2 ⇒ ∀x.(x > 1)

.

Ponieważ

6.

Σ

3 > 2

,

więc stosując

MP

dostajemy

7.

Σ

∀x.(x > 1)

.

(7) nie jest prawdziwe.

Nie otrzymamy fałszywych wniosków z prawdziwych przesłanek,

gdy zmienną „

x

” potraktujemy jako zmienną ustaloną. Tak też postę-

pujemy w wypadku nauk formalnych, jak np. matematyki, kierując
się regułami dowodów założeniowych

65

.

Nie podejmując szerszej dys-

kusji nad tą kwestią dodajmy jedynie, że dopóki jakaś ze zmiennych
ustalonych znajduje się po lewej stronie symbolu „

”, to funkcjonuje

ona w obrębie tego fragmentu dowodu, tak jakby była to stała, czyli

65

W sprawie reguł dowodów założeniowych zob. np. Batóg [1986], s. 128–132.

150

2. KLASYCZNA LOGIKA PREDYKATÓW

wykluczone jest wiązanie takiej zmiennej kwantyfikatorami i podsta-
wianie za nią. W sytuacji, gdy wszystkie wyrażenia z taką zmienną
znajdą się po prawej stronie znaku „

”, zmienna ta traci swój charak-

ter zmiennej ustalonej i staje się zmienną wolną, czyli może być wią-
zana kwantyfikatorami i dopuszczalne jest stosowanie do niej reguły
podstawiania. Trzymając się tych zasad dowieść można schematu tez
postaci T10.

T10’.

∀v.(ϕ ⇒ ψ) ⇒ (∃v.ϕ ⇒ ∃v.ψ)

DOWÓD
1.

∀v.(ϕ ⇒ ψ) ⇒ [ϕ(v/v

1

)

⇒ ψ(v/v

1

)]

T3
gdzie

v

1

nie występuje w

ϕ ⇒ ψ

2.

∀v.(ϕ ⇒ ψ) ϕ(v/v

1

)

⇒ ψ(v/v

1

)

(Tw. o dedukcji; 1)

3.

ψ(v/v

1

)

⇒ ∃v.ψ

T4

4.

∀v.(ϕ ⇒ ψ) ϕ(v/v

1

)

⇒ ∃v.ψ

(SYLL; 2, 3)

5.

∀v.(ϕ ⇒ ψ) [ϕ(v/v

1

)](

v

1

/v) ⇒ ∃v.ψ

(4)

∀v.(ϕ ⇒ ψ) ϕ ⇒ ∃v.ψ

6.

∀v.(ϕ ⇒ ψ) ∃v.ϕ ⇒ ∃v.ψ

(D

∃

; 5)

7.

∀v.(ϕ ⇒ ψ) ⇒ (∃v.ϕ ⇒ ∃v.ψ)

(tw. o dedukcji; 6)

W dowodzie stosowaliśmy twierdzenie o dedukcji nie zakładając,

że formuła

∀v.(ϕ ⇒ ψ)

jest zdaniem. Występujące w niej zmienne

traktowane były jako „zmienne ustalone”.

Pomiędzy logiką zdań a logiką predykatów zachodzą istotne róż-

nice. Dla rachunku zdań – co zostało pokazane – istnieje ogólna me-
toda, która w wypadku dowolnego zdania w z góry dającej się okre-
ślić ograniczonej liczbie kroków pozwala znaleźć odpowiedź «tak» lub
«nie» na pytanie, czy zdanie to jest tautologią. Rachunek zdań – jak
to mówimy – jest rozstrzygalny. Twierdzenie o rozstrzygalności nie
zachodzi dla rachunku predykatów. Church, korzystając z wyników
G¨

odla pokazał, że nierozstrzygalna jest każda teoria wyrażona w ję-

zyku rachunku predykatów, który zawiera przynajmniej jedną literę
funkcyjną o liczbie argumentów nie mniejszej niż 1, bądź przynaj-
mniej jedną literę predykatową o liczbie argumentów nie mniejszej
niż 2 [Church, 1936]. Nie istnieje więc żadna ogólna metoda, która w
wypadku dowolnej formuły pozwalałaby w ograniczonej liczbie kro-

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

151

ków dać odpowiedź „tak” lub „nie” na pytanie, czy ta formuła ma do-
wód (w szczególności, z pustego zbioru formuł). Nie znaczy to jednak,
by jakaś teza rachunku predykatów nie miała (skończonego) dowodu,
byłoby to przecież sprzeczne z definicją tezy rachunku predykatów.
Dla dowolnej tezy w skończonej liczbie kroków, choć w nie dającej
się z góry określić ich liczbie, znajduje się odpowiedź na pytanie, czy
formuła ta jest tezą rachunku predykatów. To, że po

n

krokach nie

znajdujemy odpowiedzi „tak” nie przesądza, że nie znajdziemy jej w
kolejnym,

(

n + 1)

-szym kroku. Zaś gdy liczba kroków nie jest z góry

przesądzona nie możemy dać odpowiedzi „nie”. Mówi się, że rachu-
nek predykatów jest półrozstrzygalny: istnieją ogólne procedury, jak
np. dowód, które w wypadku, gdy formuła jest tezą w skończonej
liczbie kroków pozwalają na znalezienie odpowiedzi „tak”. Rachunek
predykatów nie jest rozstrzygalny. Nie znaczy to, by nie były roz-
strzygalne pytania o to, czy formuła jest tezą w wypadku niektórych
klas formuł, np. rozstrzygalne jest pytanie, czy formuła jest tauto-
logią rachunku kwantyfikatorów (bo rozstrzygalne jest pytanie, czy
zdanie jest tautologią). Podobnie jest w wypadku formuł, w których
występują co najwyżej trzy jednoargumentowe litery predykatowe. W
tym wypadku korzystać można z tzw. diagramów Venna.

2.2.4. Tablice semantyczne

W wypadku rachunku zdań – korzystając z definicji tautologii

– podaliśmy metody dowodzenia tautologiczności zdań, w szczegól-
ności metodę tablic semantycznych. Powstaje pytanie o możliwość
takiej metody dla rachunku predykatów. Chodzi więc o uogólnienie
metody tablic semantycznych na rachunek predykatów. Uczynimy to
dla języka, który nie zawiera liter funkcyjnych.

Wszystkie zasady konstrukcji drzewa oraz reguły przyjęte dla

metody tablic semantycznych dla rachunku zdań (słowo „zdanie” za-
stępujemy słowem „formuła”; zamiast „prawdziwe” piszemy „speł-
nione”, a zamiast „fałszywe” – „niespełnione”) uzupełniamy o nastę-
pujące reguły specyficzne dla rachunku predykatów.

152

2. KLASYCZNA LOGIKA PREDYKATÓW

(

∃L

)

Reguła ta stosuje się do formuły

∃v.ψ

zapisanej po lewej stro-

nie gałęzi. Formuła

∃v.ψ

jest spełniona wtedy i tylko wtedy, gdy dla

pewnej stałej

c

spełniona jest formuła

ψ(v/c)

. Fomułę tą zapisujemy

po lewej stronie na każdej gałęzi, na której znajduje się analizowana
formuła

∃v.ψ

. Stała indywiduowa

c

musi być stałą, która nie wystę-

puje na gałęziach, na których dopisujemy formułę

ψ(v/c)

. Do danej

formuły regułę tę stosujemy tylko raz. Jest to reguła jednokrotna.
Fakt jej zastosowania zaznaczamy za pomocą

√

.

(

∃P

)

Reguła ta stosuje się do formuły

∃v.ψ

zapisanej po prawej stronie

gałęzi. Formuła

∃v.ψ

nie jest spełniona wtedy i tylko wtedy, gdy dla

każdej stałej

c

nie jest spełnione

ψ(v/c)

. Formułę

ψ(v/c)

piszemy po

prawej stronie każdej gałęzi, na której znajduje się

∃v.ψ

. Stała

c

jest

dowolna. Ponieważ bez względu na to, jaką weźmiemy stałą

c

nie jest

spełnione

ψ(v/c)

, więc reguła ta może być stosowana wielokrotnie.

Fakt jej zastosowania oznaczamy

.

(

∀L

)

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

153

Reguła ta stosuje się do formuły

∀v.ψ

zapisanej po lewej stronie

gałęzi. Taka formuła jest spełniona wtedy i tylko wtedy, gdy dla do-
wolnej stałej

c

spełnione jest

ψ(v/c)

. Formułę

ψ(v/c)

zapisujemy po

lewej stronie każdej gałęzi, na której znajduje się

∀v.ψ

. Stała

c

jest

dowolna. Ponieważ bez względu na to, jaką weźmiemy stałą

c

speł-

nione jest

ψ(v/c)

, więc regułę tę możemy stosować wielokrotnie. Fakt

jej zastosowania zaznaczamy pisząc

.

(

∀R

)

Reguła ta stosuje się do formuły

∀v.ψ

zapisanej po prawej stronie

gałęzi. Formuła taka nie jest spełniona wtedy i tylko wtedy, gdy dla
przynajmniej jednej stałej

c

nie jest spełnione

ψ(v/c)

. Formułę

ψ(v/c)

piszemy po prawej stronie każdej gałęzi, na której znajduje się

∀v.ψ

.

Stała

c

nie może wystąpić wcześniej na żadnej gałęzi, na której dopi-

sujemy

ψ(v/c)

. Regułę tę stosujemy tylko raz. Fakt jej zastosowania

zaznaczamy za pomocą

√

.

To, że reguły

∀L

i

∃P

mogą być wielokrotnie stosowane powoduje,

że tam, gdzie z tych reguł korzystamy proces konstrukcji drzewa nie
jest ograniczony. Jest więc inaczej niż w wypadku rachunku zdań,
gdzie dane zdanie tylko raz mogło być przedmiotem analizy.

Struktura zdania w języku rachunku zdań i formuły (w języku ra-

chunku predykatów) jednoznacznie wskazują na to, jaka reguła może
być użyta do ich analizy. W wypadku reguł zdaniowych jednoznacz-
nie określony jest wynik analizy. Tak nie jest w wypadku reguł

∃L

i

∀P

oraz

∀L

i

∃P

. Dla

∃L

i

∀P

formalnie wykluczone jest użycie nie-

których stałych. Zaś dla

∀L

i

∃P

to, której stałej użyjemy nie jest w

ogóle wyznaczone przez formalne reguły konstrukcji drzewa.

154

2. KLASYCZNA LOGIKA PREDYKATÓW

Tablica semantyczna jest zamknięta wtedy i tylko wtedy, gdy

analizowana formuła jest tezą lub z formuł znajdujących się po lewej
stronie wynikają formuły znajdujące się po stronie prawej. Dla każdej
tezy lub wynikania istnieje więc taki skończony zbiór stałych, dla
których tablica jest zamknięta. Jednak z góry nie potrafimy określić
wielkości tego zbioru. Fakt ten jest równoważny półrozstrzygalności
rachunku predykatów.

Fakt, że na danym etapie konstrukcji tablica semantyczna tezy

(wynikania) nie jest zamknięta nie przesądza, że w kolejnym kroku to
nie nastąpi. Nie wiemy bowiem z góry jak wielka ma być konstrukcja.
Ponadto, formalne reguły konstrukcji umożliwiają również tworzenie
dla tez (wynikania) niekończących się niezamkniętych tablic. Na przy-
kład, mając po stronie lewej formułę postaci

∀φ

wystarczy ograniczyć

się do stosowania tylko reguły

∀L

– jest to reguła wielokrotna a sta-

łych mamy nieskończenie wiele.

Powyższe uwagi o regułach dają podstawę następującemu zale-

ceniu w sprawie konstruowania tablicy semantycznej:

mając do wyboru analizę formuły, do której stosuje się jedna z
reguł

∀L

lub

∃P

i analizę formuły, do której stosuje się jedna z

reguł

∀P

lub

∃L

, jako pierwszą analizujemy formułę, do której

stosuje się jedna z reguł

∀P

lub

∃L

.

Wyniki konstrukcji tablicy semantycznej mogą być następujące:

1. tablica jest zamknięta; na każdej gałęzi po lewej i prawej stronie

występuje jakaś jedna i ta sama formuła, czyli – jak to mówimy
– na każdej gałęzi ma miejsce sprzeczność;

2. istnieje co najmniej jedna gałąź, na której nie wystąpiła

sprzeczność, a ewentualne stosowanie reguł

∀L

i

∃P

(powta-

rzalnych) nie może do takiej sprzeczności doprowadzić, jak na
przykład wówczas, gdy na gałęzi pozostało tylko stosowanie do
jakiejś formuły reguły

∀L

(lub

∃P

) i miały miejsce wszystkie

wypadki stosowania tej reguły z użyciem stałych już wykorzy-
stanych na tej gałęzi;

3. istnieje co najmniej jedna gałąź, na której nie wystąpiła

sprzeczność i nie mamy podstaw by twierdzić, że stosowanie re-

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

155

guł

∀L

i

∃P

w jakimś momencie nie doprowadziłoby do sprzecz-

ności.

W wypadku 1 twierdzimy, że pytanie o istnienie dowodu danej

formuły z danego zbioru formuł ma odpowiedź pozytywną. W wy-
padku 2 zaś, że ma odpowiedź negatywną. Wypadek 3 pozostawia to
pytanie nierozstrzygniętym.

Wszystkie pozostałe kwestie budowy tablicy rozwiązujemy, sto-

sując się do zasad konstrukcji tablic semantycznych wskazanych dla
zdań (w zasadach opisanych dla rachunku zdań, słowo „zdanie” za-
stępujemy słowem „formuła”).

PRZYKŁADY

Pytanie

Czy

∀x.(P x ⇒ Qx), ∀x.P x ∀x.Qx?

TABLICA SEMANTYCZNA

∀x.(P x ⇒ Qx)

∀x.P x

∀x.Qx

√

Qa

P a ⇒ Qa

√

P a

P a

Qa

ODPOWIEDŹ

Prawdą jest, że:

∀x.(P x ⇒ Qx), ∀x.P x ∀x.Qx.

PYTANIE

Czy

∀x.(P x ⇒ Qx), ∀x.Qx ∀x.P x?

TABLICA SEMANTYCZNA

∀x.(P x ⇒ Qx)

156

2. KLASYCZNA LOGIKA PREDYKATÓW

∀x.Qx

∀x.P x

√

P a

P a ⇒ Qa

√

Qa

P a

Qa

ODPOWIEDŹ

Nie jest prawdą, że:

∀x.(P x ⇒ Qx), ∀x.Qx ∀x.P x.

Tablica nie

może zostać zamknięta. Zauważmy bowiem, że pozostaje tylko sto-
sowanie reguły

∀L

do zdania

∀x.(P x ⇒ Qx)

lub do zdania

∀x.Qx

.

Kontynuując konstrukcję na kolejnych gałęziach dopisywać będziemy
po lewej stronie tylko

P c ⇒ Qc

i

Qc

, a po lewej stronie tylko

P c

, gdzie

c

jest dowolną stałą.

2.2.5. Dedukcja naturalna

Podobnie jak w wypadku rachunku zdań, mamy różne ujęcia ra-

chunku predykatów, które są bliskie intuicjom, jakimi kierujemy się
stosując logikę w dowodach. Tu przedstawimy system nadbudowany
nad systemem dowodów założeniowych.

W mocy pozostają wszystkie reguły dowodzenia oraz wszystkie

reguły pierwotne, jakie przyjęliśmy dla rachunku zdań z tym, że słowo
„zdanie” zastępujemy słowem „formuła”. Dochodzą tylko reguły spe-
cyficzne dla rachunku predykatów. Są nimi reguły dołączania i opusz-
czania kwantyfikatorów, małego i dużego.

REGUŁY PIERWOTNE RACHUNKU PREDYKATÓW

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

157

(D

∀

) Reguła dołączania dużego kwantyfikatora

Z

. . . .

ψ

∀v.ψ

jeżeli

v

nie jest zmienną wolną w żadnej formule z

Z

, gdzie

Z

jest

zbiorem założeń, z których dowodzone jest

ψ

.

(O

∀

) Reguła opuszczania dużego kwantyfikatora

∀v.ψ

∀v.ψ

∀v.ψ

ψ

ψ(v/v

1

)

ψ(v/c)

(D

∃

) Reguła dołączania małego kwantyfikatora

ψ

ψ

ψ(c)

∃v.ψ

∃v.ψ(v

1

/v)

∃v.ψ(c/v)

(O

∃

) Reguła opuszczania małego kwantyfikatora

∃v.ψ

ψ(v/c

v

1

,...,v

n

)

gdzie

c

v

1

,...,v

n

to stała zależna od

v

1

, . . . v

n

.

v

1

, . . . v

n

są wszystkimi i

tylko zmiennymi wolnymi występującymi w

∃v.ψ

.

A uczynić jasną ideę stałej, o której mowa w regule (O

∃

) roz-

ważmy wpierw przykłady. Zdanie

∃x.x + 3 = 5

jest prawdziwe. Na jego podstawie, zgodnie z regułą (O

∃

), docho-

dzimy do wniosku

2 + 3 = 5

.

Formuła

158

2. KLASYCZNA LOGIKA PREDYKATÓW

∃x.x + y = 5

jest dla dowolnego y spełniona w zbiorze liczb całkowitych, a więc
prawdą jest, że

∀y.∃x.x + y = 5

.

Tym razem w miejsce

x

nie możemy wpisać jakiejkolwiek nazwy liczby

całkowitej. Powiedzmy bowiem, że wpisaliśmy

2

. Mamy więc

2 +

y = 5

.

Ta formuła nie jest jednak spełniona dla dowolnego

y

, a więc nie jest

prawdą, że

∀y.2 + y = 5

.

Stała

c

, która wpisujemy w miejsce

x

zależy teraz od wartości

y

.

Możemy więc przyjąć

c(y) + y = 5

.

Ta formuła jest spełniona dla dowolnego

y

. Prawdą bowiem jest,

że

∀y.(5 − y) + y = 5

.

Mówiąc o stałej zależnej od zmiennych wolnych występujących

w formle mamy na uwadze stałą, której wartość zależy od wartości,
jakie przyjmą te zmienne.

PRZYKŁADY

(I)

∀v.(φ ⇒ ϕ)
∀v.φ ⇒ ∀v.ϕ

Dowód wprost

1.

∀v.(φ ⇒ ϕ)

zał.

2.

∀v.φ

zał.

3.

φ ⇒ ϕ

O

∀

; 1

4.

φ

O

∀

; 2

5.

ϕ

(MP; 3,4)

6.

∀v.ϕ

(D

∀

; 5)

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

159

(II)

¬∃v.φ
¬φ

Dowód niewprost

1.

¬∃v.φ

zał.

2.

¬¬φ

zał. dow. niewprost

3.

φ

zasada podwój. negacji.; 2

4.

∃v.φ

D

∃

; 3

(1

, 4)

–sprzeczność

(III)

¬∃v.φ
∀v.¬φ

Dowód wprost

1.

¬∃v.φ

zał.

2.

¬φ

reg. z przykł. II; 1

3.

∀v.¬φ

D

∀

; 2

2.2.6. Rachunek sekwentów

Rachunek sekwentów dla logiki predykatów jest nadbudowany

nad rachunkiem sekwentów dla logiki zdań. Obowiązują więc wszyst-
kie reguły i zasady, które zostały ustalone dla zdaniowego rachunku
sekwentów z tym, że w sformułowanich tych reguł i zasad słowo „zda-
nie” zastępujemy słowem „formuła” (zamiast

α, β, γ . . .

używamy liter

ψ, φ, ϕ, . . .

). Do tego dochodzą nowe reguły. Tu podamy reguły dla ra-

chunku sekwentów bez predykatu równości.

(DEF. termu wyróżnionego) Niech

φ

będzie formułą a

t

1

,

t

2

,

. . .

,

t

n

–

termami. Jeśli istnieje formuła

ψ

i

n

różnych co do kształtu zmiennych

wolnych

v

1

,

v

2

,

. . .

,

v

n

takich, że

φ

jest to

ψ(v

1

/t

1

, v

2

/t

2

, . . . , v

n

/t

n

)

,

czyli

φ

jest równokszatłtna z formuła otrzymaną z

ψ

przez jednocze-

sne podstawienie w miejsce zmiennych wolnych

v

1

, v

2

, . . . , v

n

termów,

160

2. KLASYCZNA LOGIKA PREDYKATÓW

odpowiednio,

t

1

, t

2

, . . . , t

n

(

φ = ψ(v

1

/t

1

, v

2

/t

2

, . . . , v

n

/t

n

)

), to dla każ-

dego

i

(

1

≤ i ≤ n

) otrzymane w wyniku tego podstawienia wystąpienie

termu

t

i

w formule

ψ(v

1

/t

1

, v

2

/t

2

, . . . , v

n

/t

n

)

nazywa się wyróżnionym

w

φ

lub – jak skrótowo mówimy – term

t

i

jest wyróżniony w

φ

.

(DEF. termu w pełni wyróżnionego) Term

t

jest w pełni wyróżniony

w formule

φ

wtedy i tylko wtedy, gdy każde wystąpienie

t

w

φ

jest

wyróżnione.

Fakt wyróżnionego wystąpienia termów

t

1

, t

2

, . . . , t

n

w formule

φ

może być wypowiedziany (mniej precyzyjnie), zapisem formuły

ψ

jako

ψ(v

1

, v

2

, . . . , v

n

)

a formuły

φ

jako

ψ(t

1

, t

2

, . . . , t

n

)

.

66

W formule

φ

term

t

jest w pełni wyróżniony ze względu na for-

mułę

ψ

i zmienną

v

wtedy i tylko wtedy, gdy w formule

ψ

nie wystę-

puje term

t

i

φ = ψ(v/t)

.

Pytamy się o wyróżnione wystąpienia termów w formule

φ

. Od-

powiedź na to pytanie zależy zarówno od wyboru formuły

ψ

jak i

zmiennych wolnych, przez podstawienie za które z

ψ

może być otrzy-

mana formuła

φ

. Samo pytanie ani nie wskazuje formuły

ψ

, ani nie

wskazuje zmiennych wolnych, za które w tej formule możemy doko-
nywać podstawień.

PRZYKŁADY

1. Formułę

x(y + 1) − 23 = 2(y + 1)

można otrzymać przez podstawienie w formule

xz − 23 = 2(y + 1)

w miejsce zmiennej

z

termu

(

y + 1)

. Zatem term ten jest wyróżniony.

2. Ze wzgędu na formułę

xz − 23 = 2z

i zmienną

z

term

y + 1

jest

w pełni wyróżniony w formule

x(y + 1) − 23 = 2(y + 1)

.

66

Naturalnie, w

φ

mogą też być inne wystąpienia termu

t

i

. Ma to miejsce

wówczas, gdy formuła

ψ

zawiera ten term.

2.2. KLASYCZNY RACHUNEK PREDYKATÓW

161

Formułę tę otrzymamy podstawiając

y + 1

w miejsce zmiennej

z

w formule

xz − 23 = 2z

.

REGUŁY KWANTYFIKATOROWE

φ(t), Γ ∆

L

∀

:

;

∀v.φ(t/v), Γ ∆

Γ

∆, φ

P

∀

:

,

Γ

∆, ∀v.φ

gdzie

t

jest dowolnym termem, a

v

nie pojawia się w

dolnym sekwencie jako zmienna wolna. Formuły

φ(t)

i

φ

to formuły boczne, a

∀v.φ(t/v)

[

∀v.φ

] to formuła główna.

W regule P

∀

zmienna wolna

v

jest zmienną własną tej

reguły.

Zauważmy, że w wypadku reguły L

∀

nie każde wystąpienie termu

t

musi być wyróżnione.

φ, Γ ∆

L

∃

:

;

∃v.φ, Γ ∆

Γ

∆, φ(t)

P

∃

:

,

Γ

∆, ∃v.φ(t/v)

gdzie

v

nie pojawia się w dolnym sekwencie jako zmienna

wolna, a

t

jest dowolnym termem. Formuły

φ(t)

i

φ

to

formuły boczne, a

∃v.φ(t/v)

[

∃v.φ

] to formuła główna. W

regule L

∃

zmienna wolna

v

to zmienna własna tej reguły.

W regule P

∃

nie koniecznie każde wystąpienie

t

jest wyróżnione.

Warunek, że zmienna własna nie powinna występować w dolnym

sekwencie w regułach P

∀

i L

∃

, to ograniczenie na zmienną własną dla

tych dwóch reguł.

162

2. KLASYCZNA LOGIKA PREDYKATÓW

PRZYKŁAD

F x F x

P

∃

F x ∃x.F x

P

¬

∃x.F x, ¬F x

P

∀

∃x.F x, ∀y.¬F y

L

¬

¬∀y.¬F y ∃x.F x

P

⇒

¬∀y.¬F y ⇒ ∃x.F x

2.3. MODEL I PRAWDZIWOŚĆ

Naszym celem, tak jak w wypadku logiki zdań, jest porównanie

wynikania syntaktycznego, a więc wynikania według reguł rachunku
predykatów z wynikaniem rzeczywistym. Tak jak w wypadku logiki
zdań musimy więc określić pojęcie wynikania rzeczywistego, czyli po-
dać definicję wynikania semantycznego dla logiki predykatów.

2.3.1. Pojęcie interpretacji

Logika zdań i logika predykatów różnią się znacznie pojęciami

modelu i prawdziwości w modelu. Istota i sama idea tego, czym są
model i prawdziwość w modelu pozostają jednak te same. W wypadku
języka logiki zdań wyrażenia były zbudowane z symboli zdaniowych
(zdań prostych), których znaczenia były całkowicie charakteryzowane
przez wartości logiczne. Dlatego też pojęcie modelu było stosunkowo
proste. Teraz na język składają się między innymi stałe indywiduowe,
litery funkcyjne oraz litery predykatowe. Dla określenia ich znaczeń
musimy dysponować dziedziną, w której będą przedmioty indywidu-
owe – indywidua – oraz

n

-argumentowe funkcje

(

n = 1, 2, . . .)

określone

w zbiorze indywiduów, czyli w zbiorze uniwersalnym i

n

-członowe re-

lacje

(

n = 1, 2, . . .)

zachodzące pomiędzy elementami zbioru uniwer-

salnego. Przyporządkowanie stałym indywiduowym, literom funkcyj-
nym i literom predykatowym, odpowiednio, indywiduów, funkcji i
relacji nazywamy interpretacją.

2.3. MODEL I PRAWDZIWOŚĆ

163

Interpretacja to – mówiąc po prostu – przyporządkowanie do-

kładnie jednego znaczenia przedmiotom pewnego rodzaju, jakimi są
wyrażenia językowe.

2.3.2. Definicja modelu i spełniania

(DEF. modelu) Modelem jest para

(

U, I)

, gdzie

U

jest zbiorem uni-

wersalnym a

I

funkcją, która

n

-argumentowym literom predykato-

wym przyporządkowuje

n

-członowe relacje,

n

-argumentowym literom

funkcyjnym przyporządkowuje

n

-argumentowe funkcje określone w

U

,

stałym indywiduowym przyporządkowuje zaś elementy zbioru

U

.

(DEF. modelu języka) Jeżeli

L

jest językiem o sygnaturze

{P

0

, P

1

, . . ., P

n

, F

0

, F

1

, . . ., F

m

, a

0

, a

1

, . . ., a

q

}

,

to modelem tego języka będzie

M

M =(U, R

0

, R

1

, . . ., R

n

, G

0

, G

1

, . . ., G

m

, x

0

, x

1

, . . ., x

q

)

,

gdzie

I(P

i

) =

R

i

, 0 ≤ i ≤ n

; I

(

F

i

) =

G

i

, 0 ≤ i ≤ m

;

I(a

i

) =

x

i

, 0 ≤ i ≤ q

.

W wypadku języka rachunku zdań nie było mowy o indywiduach.

Teraz wartość logiczna zdania zależy – mówiąc swobodnie – od tego
o jakim przedmiocie jest to zdanie.

Chcemy podać ścisłą definicję prawdziwości zdania w modelu.

Chcemy więc wiedzieć, co to znaczy, że

zdanie

ϕ

jest prawdziwe w modelu

M

.

Oczywiście, jeżeli zdanie

ϕ

jest zdaniem postaci:

¬φ

, to

ϕ

jest

prawdziwe, gdy

φ

jest fałszywe. Tak samo prawdziwość zdania

ϕ

jest

wyznaczona przez wartości logiczne zdań

φ

i

ψ

, tak jak to było w

wypadku rachunku zdań, gdy

ϕ

jest zdaniem postaci:

φ ∨ ψ

,

φ ∧ ψ

,

φ ⇒ ψ

lub

φ ⇔ ψ

. Zdanie

ϕ

może być jednak zdaniem postaci:

∀v.φ

lub

∃v.φ

, a

φ

nie musi być zdaniem. W takiej sytuacji nie możemy po

prostu mówić o wartości logicznej

φ

. Pytanie o wartość logiczną

φ

jest

bezpodstawne. Pytanie takie bowiem zakładałoby, że

φ

jest zdaniem.

Dla formuły

φ

, w której jedyną zmienną wolną jest zmienna

v

,

ma jednak sens pytanie

Czy formuła

φ

jest prawdziwa w modelu

M

, gdy mówi ona o

a

?

164

2. KLASYCZNA LOGIKA PREDYKATÓW

Jeżeli dla każdego przedmiotu należącego do

U

odpowiedź ta będzie

pozytywna, to możemy powiedzieć, że zdanie

∀v.φ

jest zdaniem praw-

dziwym w modelu

M

. Jeżeli będzie pozytywna chociaż o jednym

przedmiocie, to będziemy mogli powiedzieć, że zdanie

∃v.φ

jest praw-

dziwe w modelu

M

. Jeżeli zaś znajdziemy taki przedmiot, dla któ-

rego odpowiedź będzie negatywna, to powiemy, że zdanie

∀v.φ

jest

fałszywe. A gdy okaże się negatywna dla wszystkich przedmiotów, to
powiemy, że zdanie

∃v.φ

jest fałszywe.

Na pytanie

Czy

φ

jest prawdziwe, gdy mówi o przedmiocie

a

?

będziemy znajdować odpowiedź biorąc pod uwagę budowę formuły

φ

.

I tak np., gdy

φ

będzie postaci

¬ ψ

, to

φ

będzie prawdziwe o przed-

miocie

x

, gdy

ψ

będzie o tym przedmiocie fałszywe. Podobne będzie w

wypadku pozostałych spójników zdaniowych. Może jednak być tak,
że

φ

jest formułą postaci

∀v

1

.ψ

lub

∃v

1

.ψ

a w

ψ

będą występowały

dwie zmienne wolne

v

i

v

1

. W takim wypadku problem, czy

φ

o

x

jest prawdziwe w modelu

M

komplikuje się. Pytanie o prawdziwość

ϕ

zaczyna zależeć od odpowiedzi na pytanie

Czy formuła

ψ

jest prawdziwa w modelu

M

,

jeżeli

ψ

mówi o parze elementów

a

i

b

z

U

?

Proces ten można kontynuować. Okazuje się więc, że w wypadku ję-
zyka rachunku predykatów pojęcie prawdziwości zdania w modelu
zakłada inne pojęcie, a mianowicie pojęcie prawdziwości w modelu
formuły ze zmiennymi wolnymi

v

0

, v

1

, . . ., v

n

, gdy znaczeniami tych

zmiennych są, odpowiednio:

x

0

, x

1

, . . ., x

n

.

Chcemy znajdować odpowiedź na pytanie, czy formuła jest praw-

dziwa, gdy mówi o przedmiotach

x

0

, x

1

, . . ., x

n

ze względu na formuły

składające się na daną formułę, czyli ze względu na jej podformuły.
Zauważmy, że w podformule zmiennymi wolnymi mogą być zmienne,
które nie są zmiennymi wolnymi w formule. Np. jedyną zmienną
wolną w formule:

x > 0 ⇒ ∃y.(0 < y < x)

jest zmienna

x

. Podformułą tej formuły jest

0

< y < x

.

166

2. KLASYCZNA LOGIKA PREDYKATÓW

podamy w trzech krokach.

1. Wartość termu

t(v

0

, v

1

, . . ., v

n

)

dla ciągu:

x

0

, x

1

, . . ., x

n

– wartość

tę będziemy oznaczać:

t[x

0

x

1

. . .x

n

]

– określa się następująco

(I) jeżeli

t = v

i

, to

t[x

0

x

1

. . .x

n

] =

x

i

;

(II) jeżeli

t

jest stałą indywiduową

c

, to jako

t[x

0

x

1

. . .x

n

]

bierzemy

interpretację stałej

c

w modelu

M

;

(III) jeżeli

t = F t

1

t

2

. . .t

m

, gdzie

F

jest

m

-argumentową literą funk-

cyjną, to

t[x

0

x

1

. . .x

n

] =

G(t

1

[

x

0

x

1

. . .x

n

]

. . .t

m

[

x

0

x

1

. . .x

n

])

,

gdzie

G

jest interpretacją litery funkcyjnej

F

w modelu

M

.

2. Niech

φ(v

0

, v

1

, . . ., v

n

)

będzie formułą atomową postaci

P t

1

. . .t

m

,

gdzie

P

jest

m

-argumentową literą predykatową a

t

1

(

v

0

v

1

. . .v

n

)

, . . ., t

m

(

v

0

v

1

. . .v

n

)

są termami.

Formuła

φ

jest spełniona przez

x

0

, x

1

, . . ., x

n

wtedy i tylko wtedy,

gdy

Rt

1

[

x

0

x

1

. . .x

n

]

. . .t

m

[

x

0

x

1

. . .x

n

]

,

gdzie

R

jest interpretacją predykatu

P

w modelu

M

.

Piszemy więc

M |= P t

1

. . .t

m

[

x

0

x

1

. . .x

n

]

jeżeli

Rt

1

[

x

0

x

1

. . .x

n

]

. . .t

m

[

x

0

x

1

. . .x

n

]

.

3. Niech

ϕ

będzie formułą, której wszystkie zmienne wolne i zwią-

zane znajdują się w ciągu:

v

0

, v

1

, . . ., v

n

.

(I) Jeżeli

ϕ

jest postaci:

¬φ

,

φ∨ψ

,

φ∧ψ

,

φ ⇒ ψ

,

φ ⇔ ψ

, to spełnia-

nie

ϕ

w modelu

M

przez ciąg:

x

0

, x

1

, . . ., x

n

określamy zgodnie

ze znaczeniem, jakie nadaliśmy spójnikom zdaniowym:

∨

,

∧

,

⇒

,

⇔

. Np. gdy

ϕ

jest postaci

¬φ

mamy

M |= ϕ[x

0

x

1

. . .x

n

]

2.3. MODEL I PRAWDZIWOŚĆ

167

wtedy i tylko wtedy gdy nieprawda, że

M |= φ[x

0

x

1

. . .x

n

]

.

(II) Jeżeli

ϕ

ma postać

∀v

i

.φ

, gdzie

i ≤ n

, to

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ[x

0

x

1

. . .x

i−1

xx

i+1

. . .x

n

]

dla dowolnego

x(∈ U

, dla dowolnego indywiduum).

(III) jeżeli

ϕ

ma postać

∃v

i

.φ

, gdzie

i ≤ n

, to

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ[x

0

x

1

. . .x

i−1

xx

i+1

. . .x

n

]

dla pewnego

x(∈ U

, dla jakiegoś indywiduum).

TWIERDZENIE 4.

Niech term

t

będzie taki, że wszystkie występujące w nim zmienne

znajdują się w ciągu:

v

0

, v

1

, . . ., v

l

. Jeżeli dla każdego

i

takiego, że

v

i

występuje w termie

t

ciągi

x

0

, x

1

, . . ., x

n

(

l ≤ n)

oraz

y

0

, y

1

, . . ., y

m

(

l ≤ m)

są takie, że

x

i

=

y

i

, to

t[x

0

x

1

. . .x

n

] =

t[y

0

y

1

. . .y

m

]

.

DOWÓD

Dowodzić będziemy przez indukcję po długości termu.

(I) Termy proste (niezłożone) to zmienna i stała.

Jeżeli term jest zmienną, czyli

t = v

i

, to na podstawie definicji do-

stajemy, że

t[x

0

x

1

. . .x

n

] =

x

i

, a

t[y

0

y

1

. . .y

m

] =

y

i

. Zatem na podstawie

założenia, że

x

i

=

y

i

mamy

t[x

0

x

1

. . .x

n

] =

t[y

0

y

1

. . .y

m

]

.

Jeżeli term jest stałą, czyli

t = c

, to zgodnie z definicją wartości

termu jest, że

t[x

0

x

1

. . .x

n

] =

t[y

0

y

1

. . .y

m

]

.

ZAŁOŻENIE INDUKCYJNE: Niech termy

t

1

, t

2

, . . ., t

k

będą takie, że

zachodzi dla nich dowodzone twierdzenie, czyli dla

1

≤ i ≤ k

168

2. KLASYCZNA LOGIKA PREDYKATÓW

t

i

[

x

0

x

1

. . .x

n

] =

t

i

[

y

0

y

1

. . .y

m

]

.

(II) Teraz rozważymy wypadek termu złożonego. Niech

t = F t

1

t

2

. . .t

k

.

Niech

G

będzie interpretacją w modelu

M

litery funkcyjnej

F

.

Zatem zgodnie z definicją wartości termu

t[x

0

x

1

. . .x

n

] =

G(t

1

[

x

0

x

1

. . .x

n

]

. . .t

k

[

x

0

x

1

. . .x

n

])

t[y

0

y

1

. . .y

m

] =

G(t

1

[

y

0

y

1

. . .y

m

]

. . .t

k

[

y

0

y

1

. . .y

m

])

Na podstawie założenia indukcyjnego mamy, że

G(t

1

[

x

0

x

1

. . .x

n

]

. . .t

k

[

x

0

x

1

. . .x

n

]) =

G(t

1

[

y

0

y

1

. . .y

m

]

. . .t

k

[

y

0

y

1

. . .y

m

])

.

A zatem

t[x

0

x

1

. . .x

n

] =

t[y

0

y

1

. . .y

m

]

.

TWIERDZENIE 5.

Niech formuła

ϕ

będzie taka, że wszystkie występujące w niej

zmienne znajdują się w ciągu:

v

0

, v

1

, . . ., v

l

. Jeżeli dla każdego

i

ta-

kiego, że

v

i

jest zmienną wolną w formule

ϕ

ciągi

x

0

, x

1

, . . ., x

n

(

l ≤

n)

oraz

y

0

, y

1

, . . ., y

m

(

l ≤ m)

są takie, że

x

i

=

y

i

, to

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ϕ[y

0

y

1

. . .y

m

]

.

DOWÓD

Dowodzić będziemy przez indukcję po długości formuły. Rozpo-

czynamy od formuł prostych.

(I) Niech

ϕ

będzie formułą postaci

t

1

≡ t

2

. Korzystając z poprzed-

niego twierdzenia mamy, że

t

1

[

x

0

x

1

. . .x

n

] =

t

1

[

y

0

y

1

. . .y

m

]

t

2

[

x

0

x

1

. . .x

n

] =

t

2

[

y

0

y

1

. . .y

m

]

.

Na podstawie tych równości i definicji spełniania następujące ko-

lejne stwierdzenia są równoważne

M |= (t

1

≡ t

2

)[

x

0

x

1

. . .x

n

]

t

1

[

x

0

x

1

. . .x

n

] =

t

2

[

x

0

x

1

. . .x

n

]

t

1

[

y

0

y

1

. . .y

m

] =

t

2

[

y

0

y

1

. . .y

m

]

M |= (t

1

≡ t

2

)[

y

0

y

1

. . .y

m

]

,

2.3. MODEL I PRAWDZIWOŚĆ

169

czyli ostatecznie

M |= (t

1

≡ t

2

)[

x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= (t

1

≡ t

2

)[

y

0

y

1

. . .y

m

]

.

(I’) Niech

ϕ

będzie formułą atomową postaci

P t

1

t

2

. . .t

k

. Niech

R

bę-

dzie interpertacją litery predykatowej

P

w modelu

M

. Korzysta-

jąc z poprzedniego twierdzenia mamy, że dla

1

≤ i ≤ k

t

i

[

x

0

x

1

. . .x

n

] =

t

i

[

y

0

y

1

. . .y

m

]

.

Zatem

Rt

1

[

x

0

x

1

. . .x

n

]

. . .t

k

[

x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

Rt

1

[

y

0

y

1

. . .y

m

]

. . .t

k

[

y

0

y

1

. . .y

m

]

.

Ponieważ

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

Rt

1

[

x

0

x

1

. . .x

n

]

. . .t

k

[

x

0

x

1

. . .x

n

]

a

M |= ϕ[y

0

y

1

. . .y

m

]

,

wtedy i tylko wtedy, gdy

Rt

1

[

y

0

y

1

. . .y

m

]

. . .t

k

[

y

0

y

1

. . .y

m

]

,

więc

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ϕ[y

0

y

1

. . .y

m

]

.

ZAŁOŻENIE INDUKCYJNE: Niech formuły

φ

i

ψ

będą takie, że

zachodzi dla nich dowodzone twierdzenie, czyli

M |= φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ[y

0

y

1

. . .y

m

]

,

M |= ψ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ψ[y

0

y

1

. . .y

m

]

.

(II)

(

¬

) Niech

ϕ

będzie formułą postaci

¬φ

. Zgodnie z definicją spełniania

170

2. KLASYCZNA LOGIKA PREDYKATÓW

M |= ¬φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy nie zachodzi

M |= φ[x

0

x

1

. . .x

n

]

.

Na podstawie założenia indukcyjnego

M |= φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ[y

0

y

1

. . .y

m

]

.

Zatem

M |= ¬φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ¬φ[y

0

y

1

. . .y

m

]

.

Dla spójników dwuargumentowych

⇒

,

∨

,

∧

,

⇔

rozważamy for-

muły zbudowane z

φ

i

ψ

. Dowody pomijamy ponieważ przebiegają,

jak w wypadku negacji (

¬

), zgodnie z definicją prawdziwości zdania

w modelu.

(

∀

) Niech

ϕ

będzie postaci

∀v

i

.φ

. Na podstawie definicji spełniania

M |= ∀v

i

.φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

dla dowolnego

x(∈ U

, dla dowolnego indywiduum ze zbioru uni-

wersalnego)

M |= φ[x

0

x

1

. . .x

i−1

xx

i+1

. . .x

n

]

.

Korzystając z założenia indukcyjnego mamy, że dla dowolnego

x(∈ U)

M |= φ[x

0

x

1

. . .x

i−1

xx

i+1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ[y

0

y

1

. . .y

i−1

xy

i+1

. . .y

m

]

.

Z tego wynika, że

dla dowolnego

x(∈ U) : M |= φ[x

0

x

1

. . .x

i−1

xx

i+1

. . .x

n

]

wtedy i tylko wtedy, gdy

dla dowolnego

y(∈ U) : M |= φ[y

0

y

1

. . .y

i−1

yy

i+1

. . .y

m

]

.

67

67

Zauważmy, że skorzystaliśmy z prawa:

∀v.(ϕ ⇔ φ) ⇒ (∀v.ϕ ⇔ ∀v

1

.φ(v/v

1

))

,

jeżeli

v

1

nie występuje w formule

φ

.

2.3. MODEL I PRAWDZIWOŚĆ

171

Zatem

M |= ∀v

i

.φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ∀v

i

.φ[y

0

y

1

. . .y

m

]

.

67

Analogicznie przebiega dowód w wypadku kwantyfikatora egzy-

stencjalnego (

∃

).

67

Niech

ϕ

będzie formułą, której wszystkie zmienne wolne znajdują się w

ciągu:

v

0

, v

1

, . . ., v

m

zaś wszystkie zmienne wolne i związane znajdują się w ciągu:

v

0

, v

1

, . . ., v

n

. Będziemy mówli, że ciąg przedmiotów:

x

0

, x

1

, . . ., x

m

spełnia

ϕ

w modelu

M

,

M |= ϕ[x

0

x

1

. . .x

m

]

wtedy i tylko wtedy, gdy

dla jakiegoś ciągu:

x

m+1

, . . ., x

n

lub – co zgodnie z twierdzeniem 5 na jedno

wychodzi – dla dowolnego ciągu:

x

m+1

, . . ., x

n

M |= ϕ[x

0

x

1

. . .x

m

x

m+1

. . .x

n

]

.

(DEF. prawdziwości zdania w modelu) Zdanie

ϕ

jest

prawdziwe w modelu

M

,

wtedy i tylko wtedy, gdy

M |= ϕ[x

0

x

1

. . .x

n

]

dla pewnego ciągu:

x

0

, x

1

. . ., x

n

lub – co w świetle twierdzenia 5 na jedno wy-

chodzi – dla dowolnego ciągu:

x

0

, x

1

, . . ., x

n

przedmiotów z

U

(dowolnego ciągu

indywiduów ze zbioru uniwersalnego).

(DEF. modelu zdania)

M

jest

modelem zdania

ϕ

wtedy i tylko wtedy, gdy

zdanie

ϕ

jest prawdziwe w modelu

M

.

Zgodnie z powyższymi ustaleniami terminologicznymi następujące stwier-

dzenia są równoważne

67

Korzystamy z tego, że

∀v

1

.ϕ(v/v

1

)

⇔ ∀v.ϕ(v/v

1

)(

v

1

/v)

.

67

W dowodzie korzystać będziemy z

∀v.(ϕ ⇔ φ) ⇒ (∃v.ϕ ⇔ ∃v

1

.φ(v/v

1

))

,

jeżeli

v

1

nie występuje w formule

φ

,

oraz z

∃v

1

.ϕ(v/v

1

)

⇔ ∃v.ϕ(v/v

1

)(

v

1

/v)

.

172

2. KLASYCZNA LOGIKA PREDYKATÓW

zdanie

ϕ

jest prawdziwe w modelu

M

,

zdanie

ϕ

jest spełnione w modelu

M

,

M

jest modelem zdania

ϕ

.

Przytoczona definicja prawdy pochodzi od A. Tarskiego (po raz pierwszy

była opublikowana w 1933 r.

68

).

W związku z regułą podstawiania w dalszych rozważaniach przy-

datne będą dwa kolejne twierdzenia.

TWIERDZENIE 6.

Dla dowolnego modelu

M

i dowolnych termów

t, t

0

takich, że

wszystkie występujące w nich zmienne znajdują się w ciągu:

v

0

, v

1

, . . ., v

n

jeżeli

t

0

[

x

0

x

1

. . .x

n

] =

x

i

, i ≤ n,

to

t[x

0

x

1

. . .x

n

] =

t(v

i

/t

0

)[

x

0

x

1

. . .x

n

]

.

DOWÓD

Dowodzić będziemy przez indukcję po długości termu

t

.

(I) W wypadku termu

t

będącego stałą indywiduową jego wartość

nie zależy od

x

0

x

1

. . .x

n

, zatem zachodzi teza dowodzonego twier-

dzenia.

Gdy term

t

jest zmienną

v

j

, to

t[x

0

x

1

. . .x

n

] =

x

j

zmienna. Gdy

j = i

, to

t[x

0

x

1

. . .x

n

] =

x

i

, a

t(v

i

/t

0

) =

t

0

. Z załóżenia twierdzenia zaś

t

0

[

x

0

x

1

. . .x

n

] =

x

i

, więc

t(v

i

/t

0

) =

x

i

.

ZAŁOŻENIE INDUKCYJNE: Niech termy

t

1

, t

2

, . . ., t

m

będą takie,

że zachodzi dla nich dowodzone twierdzenie, czyli gdy

t

0

[

x

0

x

1

. . .x

n

] =

x

i

,

to

t

j

[

x

0

x

1

. . .x

n

] =

t

j

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

]

,

1

≤ j ≤ m

.

68

Nieformalne przedstawienie wyników tej pracy oraz uzupełnienie nowymi

wynikami zwłaszcza o charakterze filozoficznym i metodologicznym zawiera roz-
prawa A. Tarski [1944].

2.3. MODEL I PRAWDZIWOŚĆ

173

(II) Niech

t

będzie termem

F t

1

t

2

. . .t

k

.

Niech

G

będzie interpretacją

litery funkcyjnej

F

w modelu

M

. Mamy

F t

1

t

2

. . .t

m

[

x

0

x

1

. . .x

i

. . .x

n

] =

=

F t

1

t

2

. . .t

m

[

x

0

x

1

. . .x

i−1

t

0

[

x

0

x

1

. . .x

n

]

x

i+1

. . .x

n

]

.

Z definicji wartości termu w modelu

F t

1

t

2

. . .t

m

[

x

0

x

1

. . .x

i−1

t

0

[

x

0

x

1

. . .x

n

]

x

i+1

. . .x

n

]

jest równe

G(t

1

[

x

0

x

1

. . .x

i−1

t

0

[

x

0

x

1

. . .x

n

]

x

i+1

. . .x

n

]

. . .

. . .t

m

[

x

0

x

1

. . .x

i−1

t

0

[

x

0

x

1

. . .x

n

]

x

i+1

. . .x

n

])

.

A to z kolei na podstawie założenia indukcyjnego jest równe

G(t

1

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

]

. . .t

m

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

])

.

Zaś

G(t

1

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

]

. . .t

m

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

])

jest równe

F t

1

(

v

i

/t

0

)

. . .t

m

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

]

.

Ponieważ na podstawie definicji podstawiania termów za zmienne

mamy, że

F t

1

t

2

. . .t

m

(

v

i

/t

0

)

jest równe

F t

1

(

v

i

/t

0

)

t

2

(

v

i

/t

0

)

. . .t

m

(

v

i

/t

0

)

.

Zatem ostatecznie

F t

1

t

2

. . .t

m

[

x

0

x

1

. . .x

n

] =

F t

1

t

2

. . .t

m

(

v

i

/t

0

)[

x

0

x

1

. . .x

n

]

.

TWIERDZENIE 7.

Dla dowolnego modelu

M

i dowolnych formuły

ϕ

oraz termu

t

takich, że

(I) wszystkie zmienne występujące w formule

ϕ

i termie

t

znaj-

dują się w ciągu:

v

0

, v

1

, . . ., v

n

oraz

(II) term

t

jest podstawialny w formule

ϕ

w miejsce zmiennej

v

i

,

gdy

174

2. KLASYCZNA LOGIKA PREDYKATÓW

t[x

0

x

1

. . .x

n

] =

x

i

,

to

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ϕ(v

i

/t)[x

0

x

1

. . .x

n

]

.

DOWÓD

Dowodzić będziemy przez indukcję po długości formuły.

(I) Niech

ϕ

będzie formułą atomową postaci

P t

1

t

2

. . .t

m

. Niech

R

bę-

dzie interpretacją litery predykatowej

P

w modelu

M

. Z definicji

spełniania w modelu mamy, że

M |= P t

1

t

2

. . .t

m

[

x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

Rt

1

[

x

0

x

1

. . .x

n

]

t

2

[

x

0

x

1

. . .x

n

]

. . .t

m

[

x

0

x

1

. . .x

n

]

.

Korzystając z twierdzenia 6 dostajemy, że

Rt

1

[

x

0

x

1

. . .x

n

]

t

2

[

x

0

x

1

. . .x

n

]

. . .t

m

[

x

0

x

1

. . .x

n

]

.

wtedy i tylko wtedy, gdy

Rt

1

(

v

i

/t)[x

0

x

1

. . .x

n

]

t

2

(

v

i

/t)[x

0

x

1

. . .x

n

]

. . .t

m

(

v

i

/t)[x

0

x

1

. . .x

n

]

.

Z kolei

Rt

1

(

v

i

/t)[x

0

x

1

. . .x

n

]

t

2

(

v

i

/t)[x

0

x

1

. . .x

n

]

. . .t

m

(

v

i

/t)[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= P t

1

(

v

i

/t)t

2

(

v

i

/t). . .t

m

(

v

i

/t)[x

0

x

1

. . .x

n

]

.

Ponieważ na podstawie definicji podstawiania

P t

1

t

2

. . .t

m

(

v

i

/t)

jest

tym samym, co

P t

1

(

v

i

/t)t

2

(

v

i

/t). . .t

m

(

v

i

/t),

więc

M |= P t

1

t

2

. . .t

m

[

x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= P t

1

t

2

. . .t

m

(

v

i

/t)[x

0

x

1

. . .x

n

]

.

ZAŁOŻENIE INDUKCYJNE: Niech formuły

φ

i

ψ

będą takie, że

zachodzi dla nich dowodzone twierdzenie. Należy pokazać, że twier-
dzenie to zachodzi również dla formuł z nich złożonych zbudowanych
za pomocą spójników zdaniowych i kwantyfikatorów.

2.3. MODEL I PRAWDZIWOŚĆ

175

(II)

(

¬

) Niech

ϕ

będzie formułą postaci

¬φ

. Z definicji spełniania w mo-

delu mamy, że

M |= ¬φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy nie zachodzi

M |= φ[x

0

x

1

. . .x

n

]

.

Z założenia indukcyjnego zaś

M |= φ[x

0

x

1

. . .x

n

]

.

wtedy i tylko wtedy, gdy

M |= φ(v

i

/t)[x

0

x

1

. . .x

n

]

.

Na podstawie powyższego

M |= ¬φ(v

i

/t)[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ¬φ[x

0

x

1

. . .x

n

]

.

Zatem, mając na uwadze, że

¬φ

to

ϕ

mamy

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ϕ(v

i

/t)[x

0

x

1

. . .x

n

]

.

(

∨

) Niech

ϕ

będzie formułą postaci

φ ∨ ψ

. Z definicji spełniania w

modelu mamy, że

M |= φ ∨ ψ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ[x

0

x

1

. . .x

n

]

lub

M |= ψ[x

0

x

1

. . .x

n

]

.

Z założenia indukcyjnego

M |= φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ(v

i

/t)[x

0

x

1

. . .x

n

]

,

a

M |= ψ[x

0

x

1

. . .x

n

]

176

2. KLASYCZNA LOGIKA PREDYKATÓW

wtedy i tylko wtedy, gdy

M |= ψ(v

i

/t)[x

0

x

1

. . .x

n

]

.

Ponieważ z definicji spełniania

M |= φ(v

i

/t)[x

0

x

1

. . .x

n

]

lub

M |= ψ(v

i

/t)[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= (φ ∨ ψ)(v

i

/t)[x

0

x

1

. . .x

n

]

,

więc

M |= (φ ∨ ψ)[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= (φ ∨ ψ)(v

i

/t)[x

0

x

1

. . .x

n

]

.

Ponieważ zaś

φ ∨ ψ

to

ϕ

, więc ostatecznie

M |= ϕ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= ϕ(v

i

/t)[x

0

x

1

. . .x

n

]

.

Analogicznie postępujemy w wypadku pozostałych spójników

zdaniowych, czyli:

∧

,

⇒

,

⇔

.

(

∀

) Niech

ϕ

będzie formułą postaci

∀v

j

.φ

. Z definicji spełniania w

modelu mamy, że

M |= ∀v

j

.φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy dla dowolnego przedmiotu

x

ze zbioru uni-

wersalnego

U

M |= φ[x

0

x

1

. . .x

j−1

xx

j+1

. . .x

n

]

.

Na podstawie tego, że term

t

jest podstawialny w formule

ϕ

(

∀v

j

.φ

) w miejsce zmiennej wolnej

v

i

wnosimy, że ciągi

x

0

, x

1

. . ., x

i

, . . ., x

j−1

, x, x

j+1

, . . ., x

n

oraz

x

0

, x

1

, . . ., t[x

0

x

1

. . .x

j−1

xx

j+1

. . .x

n

]

, . . ., x

j−1

, y, x

j+1

, . . ., x

n

różnić się mogą jedynie na

j

-tej pozycji. Z twierdzenia 5 mamy więc,

że

M |= ∀v

j

.φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

2.3. MODEL I PRAWDZIWOŚĆ

177

M |= ∀v

j

.φ[x

0

x

1

. . .x

i−1

t[x

0

x

1

. . .x

n

]

x

i+1

. . .x

n

]

.

Z założenia indukcyjnego

M |= φ[x

0

x

1

. . .x

i−1

t[x

0

x

1

. . .x

n

]

x

i+1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= φ(v

i

/t)[x

0

x

1

. . .x

n

]

.

Ostatecznie zatem

M |= ∀v

j

.φ[x

0

x

1

. . .x

n

]

wtedy i tylko wtedy, gdy

M |= (∀v

j

.φ)(v

i

/t)[x

0

x

1

. . .x

n

]

.

Analogicznie postępujemy w wypadku

∃

.

WNIOSEK

Niech zmienna

v

j

nie występuje w formule

ϕ

. Niech w ciągu

v

0

, v

1

, . . ., v

n

występują wszystkie zmienne formuły

ϕ

oraz zmienna

v

j

. Dla dowolnych modelu

M

oraz zmiennej

v

i

,

0

≤ i ≤ n

M |= ϕ[x

0

x

1

. . .x

n

]

dla dowolnych

x

0

, x

1

. . ., x

n

wtedy i tylko wtedy, gdy

M |= ϕ(v

i

/v

j

)[

x

0

x

1

. . .x

n

]

dla dowolnych

x

0

, x

1

, . . ., x

n

.

DOWÓD

Niech dla dowolnego ciągu:

x

0

, x

1

. . ., x

n

zachodzi

M |= ϕ[x

0

x

1

. . .x

n

]

i niech dla pewnego ciągu

a

0

, a

1

, . . ., a

n

nie zachodzi

M |= ϕ(v

i

/v

j

)[

a

0

a

1

. . .a

n

]

.

Na podstawie powyższego twierdzenia nie zachodzi

M |= ϕ[b

0

b

1

. . .b

n

]

, gdzie

b

k

=

a

k

dla

k = i, b

i

=

a

j

.

Otrzymujemy więc sprzeczność z założeniem.

Niech teraz dla dowolnego ciągu:

x

0

, x

1

, . . ., x

n

zachodzi

M |= ϕ(v

i

/v

j

)[

x

0

x

1

. . .x

n

]

i niech dla pewnego ciągu:

a

0

, a

1

, . . ., a

n

nie zachodzi

178

2. KLASYCZNA LOGIKA PREDYKATÓW

M |= ϕ[a

0

a

1

. . .a

n

]

.

Na podstawie powyższego twierdzenia nie zachodzi

M |= ϕ(v

i

/v

j

)[

b

0

b

1

. . .b

n

]

,

gdzie

b

k

=

a

k

dla

k = j, b

j

=

a

i

.

(DEF. fałszywości zdania w modelu) Zdanie jest fałszywe w modelu

M

lub,

M

jest modelem zdania

¬ϕ

wtedy i tylko wtedy, gdy

ϕ

nie

jest prawdziwe w modelu

M

.

(DEF. prawdziwości) Zdanie jest (logicznie) prawdziwe wtedy i tylko
wtedy, gdy jest ono spełnione (prawdziwe) w dowolnym modelu. To,
że zdanie

ϕ

jest (logicznie) prawdziwe oznaczamy:

|= ϕ

.

(DEF. modelu zbioru zdań)

M

jest modelem zbioru zdań

Σ

wtedy i

tylko wtedy, gdy

M

jest modelem każdego zdania ze zbioru

Σ

.

Zauważmy, że termin „model języka

L

” znaczy coś innego niż

„model zbioru

Σ

zdań języka

L

”. By

M

było modelem zbioru

Σ

zdań

języka

L

konieczne jest, aby

M

dało się opisać jako model języka

L

.

M

nie musi zaś być modelem jakiegoś zbioru

Σ

zdań języka

L

. Aby

M

nie było modelem

Σ

wystarczy, że przynajmniej jedno ze zdań z

Σ

nie jest prawdziwe w

M

(jest fałszywe w

M

).

(DEF. wynikania semantycznego ze zdania) Zdanie

ϕ

wynika seman-

tycznie ze zdania

φ

(symb.:

φ |= ϕ

) wtedy i tylko wtedy, gdy każdy

model zdania

φ

jest modelem zdania

ϕ

; czyli

φ |= ϕ

wtedy i tylko wtedy, gdy

dla każdego

M

: jeżeli

M |= φ

, to

M |= ϕ

.

(DEF. wynikania semantycznego ze zbioru zdań) Mówimy, że zdanie

ϕ

wynika semantycznie ze zbioru zdań

Σ

(symb.:

Σ

|= ϕ

) wtedy i tylko

wtedy, gdy każdy model zbioru

Σ

zdań jest modelem zdania

ϕ

; czyli

Σ

|= ϕ

wtedy i tylko wtedy, gdy

dla każdego modelu

M

: jeżeli

M |= Σ

, to

M |= ϕ

.

2.3. MODEL I PRAWDZIWOŚĆ

179

Można zauważyć, że

TWIERDZENIE 8.

Dla dowolnego zbioru

Σ

zdań oraz dowolnych zdań

ϕ

i

φ

Σ

∪ {ϕ} |= φ

wtedy i tylko wtedy, gdy

Σ

|= ϕ ⇒ φ

.

DOWÓD

Niech

Σ

∪ {ϕ} |= φ

oraz niech nie zachodzi

Σ

|= ϕ ⇒ φ

. Zatem

istnieje taki model

M

, że

M |= Σ

i nieprawda, że

M |= ϕ ⇒ φ

. Na

to, aby nie zachodziło

M |= ϕ ⇒ φ

konieczne jest, żeby

M |= ϕ

oraz

nieprawda, że

M |= φ

. Z tego wynika, że

M |= Σ∪{ϕ}

oraz nieprawda,

że

M |= φ

. A to przeczy założeniu.

Niech teraz

Σ

|= ϕ ⇒ φ

oraz nieprawda, że

Σ

∪ {ϕ} |= φ

. Istnieje

zatem taki model

M

, że

M |= Σ∪{ϕ}

oraz nieprawda, że

M |= φ

. Jest

to więc model

Σ

oraz spełnione jest w nim

ϕ

, zatem nie jest spełnione

w nim

ϕ ⇒ φ

, a to przeczy założeniu, które jest równoważne temu, że

każdy model zbioru

Σ

zdań jest modelem zdania

ϕ ⇒ φ

.

TWIERDZENIE 9. (SEMANTYCZNA ZASADA WYŁĄCZONEGO

ŚRODKA)

Jeżeli

ϕ

jest zdaniem, to dla dowolnego modelu

M

M |= ϕ

lub

M |= ¬ϕ

.

DOWÓD

Niech

ϕ

będzie zdaniem i niech nie zachodzi

M |= ϕ

. Niech

wszystkie zmienne występujące w

ϕ

znajdują się w ciągu:

v

0

, v

1

, . . ., v

n

.

Zatem dla pewnego ciągu przedmiotów:

x

0

, x

1

. . ., x

n

nie zachodzi

M |= ϕ[x

0

x

1

. . .x

n

]

.

W takim razie dla tego ciągu zachodzi

M |= ¬ϕ[x

0

x

1

. . .x

n

]

,

czyli na podstawie definicji prawdziwości zdania w modelu mamy

M |= ¬ϕ

.

TWIERDZENIE 10. (SEMANTYCZNA ZASADA NIESPRZECZ-

NOŚCI)

Dla dowolnego modelu

M

i dowolnego zdania

ϕ

180

2. KLASYCZNA LOGIKA PREDYKATÓW

bądź nie zachodzi

M |= ϕ

, bądź nie zachodzi

M |= ¬ϕ

.

DOWÓD

Niech zachodzi

M |= ϕ

. Niech wszystkie zmienne występujące w

ϕ

znajdują się w ciągu:

v

0

, v

1

, . . ., v

n

. W takim razie dla dowolnego

ciągu przedmiotów:

x

0

, x

1

. . ., x

n

mamy, że

M |= ϕ[x

0

x

1

. . .x

n

]

.

Wykorzystujemy teraz założenie niepustości zbioru uniwersalnego i
na jego podstawie wnioskujemy, że istnieje ciąg przedmiotów taki, że

ϕ

jest spełnione w modelu

M

. A zatem istnieją

x

0

, x

1

, . . ., x

n

takie, że

nie zachodzi

M |= ¬ϕ[x

0

x

1

. . .x

n

]

.

W takim razie nie zachodzi

M |= ¬ϕ

.

Semantyczna zasada wyłączonego środka głosi, że z dwóch zdań,

z których jedno jest negacją drugiego, co najmniej jedno jest praw-
dziwe. Zaś semantyczna zasada niesprzeczności o takich zdaniach
głosi, że oba zarazem nie są prawdziwe. Sformułowania takie sta-
nowią zwykle komentarz do znanych tautologii, odpowiednio:

α ∨ ¬α

;

¬(α ∧ ¬α)

. Praktyka ta nie jest całkiem poprawna. Aby stwierdzić to

zauważmy choćby różnicę w dowodzeniu: inaczej przebiegało wykazy-
wanie tautologiczności, a inaczej przebiegał dowód naszych twierdzeń.
Istota różnicy polega na tym, że w wypadku tautologii nie korzystamy
z pojęć prawdy i spełniania, zaś w wypadku dowodów zasad seman-
tycznych pojęcia te pełnią istotną rolę.

Na zbiór uniwersalny

U

nie nałożyliśmy żadnego warunku. Zbiór

ten może być skończony i może być nieskończony. Celem lepszego zro-
zumienia definicji spełniania i większej intuicyjności znaczeń kwan-
tyfikatorów załóżmy, że zbiór

U

jest skończony, że ma dokładnie

n

elementów. Niech

a

0

, a

1

, . . ., a

n

będą wszystkimi tymi elementami

69

.

Na podstawie definicji spełniania stwierdzamy, że

1.

(

U, I) |= ∀v.φ

69

Jeśli istnieje taka potrzeba wzbogacamy język o stosowne stałe induwiduowe.

2.3. MODEL I PRAWDZIWOŚĆ

181

wtedy i tylko wtedy, gdy

(

U, I) |= φ(v/a

1

)

∧ φ(v/a

2

)

∧ . . . ∧ φ(v/a

n

)

2.

(

U, I) |= ∃v.φ

wtedy i tylko wtedy, gdy

(

U, I) |= φ(v/a

1

)

∨ φ(v/a

2

)

∨ . . . ∨ φ(v/a

n

)

.

Korzystając z tych dwóch faktów, dla dowolnego zdania

φ

(for-

muły nie zawierającej zmiennych wolnych) możemy skonstruować
zdanie

Φ

nie zawierające kwantyfikatorów takie, że dla dowolnej in-

terpretacji

I

(

U, I) |= φ

wtedy i tylko wtedy, gdy

(

U, I) |= Φ

.

Φ

nie zawiera żadnych zmiennych, ani wolnych ani związanych i

– oczywiście – kwantyfikatorów.

Φ

zbudowane jest ze zdań otrzyma-

nych z formuł atomowych przez wpisanie stałych w miejsce zmien-
nych. Zdania te, zdania atomowe, uznajemy za różne jeżeli zbudo-
wane są z różnych liter predykatowych lub różnych liter funkcyjnych,
bądź w jednym zdaniu na

i

-tym miejscu występuje inna stała niż

w drugim. Możemy przyjąć, że zdaniom atomowym interpretacja

I

przyporządkowuje bądź wartość

t

, bądź wartość

f

. Takich interpreta-

cji różniących się tylko przyporządkowaniem tych wartości zdaniom
atomowym jest nie więcej niż

2

m

, gdzie

m

jest liczbą różnych ta-

kich zdań. Możemy teraz stosować metody opracowane dla rachunku
zdań. W zależności od tego, czy dla wszystkich

2

m

„interpretacji”

nasze zdanie przyjmie wartość

t

, czy też choć raz przyjmie wartość

f

, będziemy mogli twierdzieć, że zdanie to jest, odpowiednio, praw-

dziwe w dowolnej

n

-elementowej dziedzinie lub, że nie jest prawdziwe

(jeżeli nie jest prawdziwe w

n

-elementowej dziedzinie, to tym samym

nie jest prawdziwe).

PRZYKŁADY

1. Zdanie

(

∀x.P x ⇒ ∀x.Qx) ⇒ ∀x.(P x ⇒ Qx)

182

2. KLASYCZNA LOGIKA PREDYKATÓW

nie jest prawdziwe, bo nie jest ono prawdziwe w dziedzinie dwuele-
mentowej. W tym celu wystarczy pokazać, że tautologią nie jest

[(

P a ∧ P b) ⇒ (Qa ∧ Qb)] ⇒ [(P a ⇒ Qa) ∧ (P b ⇒ Qb)]

.

2. Prawdziwe nie jest również zdanie

(

∃x.P x ∧ ∃x.Qx) ⇒ ∃x.(P x ∧ Qx)

.

Nie jest ono prawdziwe w dziedzinie, w której są przynajmniej

dwa elementy. Pokazać bowiem można, że tautologią nie jest

[(

P a ∨ P b) ∧ (Qa ∨ Qb)] ⇒ [(P a ∧ Qa) ∨ (P b ∧ Qb).]

3. Prawdziwe nie jest zdanie

∀x.∃y.P xy ⇒ ∃y.∀x.P xy

.

Nie jest ono prawdziwe w dziedzinie dwuelementowej. Tautologią nie
jest bowiem

[(

P aa ∨ P ab) ∧ (P ba ∨ P bb] ⇒

[(

P aa ∧ P ba) ∨ (P ab ∧ P bb)]

.

Zauważmy, że istnieją zdania, które nie są spełnione tylko w dzie-

dzinie nieskończonej, czyli zdania warunkiem koniecznym fałszywości
których jest nieskończoność dziedziny.

Zdanie

∀x.xRf(x) ∧ ∀x.¬xRx ∧ ∀xyz.(xRy ∧ yRz ⇒ xRz)

nie jest prawdziwe w żadnej dziedzinie skończonej.

Niech

a

będzie elementem dziedziny.

Niech

f

0

(

a) = a

,

f

n

(

a) = ff

n−1

(

a), n ∈ N

.

Pokażemy, że wszystkie wyrazy ciągu

a, f(a), ff(a), . . .

są parami różne.

Przede wszystkim zauważmy, że jeżeli

m < n

, to

f

m

(

a)Rf

n

(

a)

.

Ponieważ

∀x.¬xRx

, więc dla dowolnych

m, n(m = n)

:

f

m

(

a) =

f

n

(

a)

.

2.3. MODEL I PRAWDZIWOŚĆ

183

Oczywiście fakt, że zdanie może być prawdziwe tylko w wypadku,

gdy dziedzina jest nieskończona nie pociąga za sobą prawdziwości
tego zdania w dowolnym modelu z nieskończoną dziedziną. W wy-
padku rozważanego zdania wystarczy dobrać takie rozumienie litery
predykatowej

R

, aby nie był spełniony przynajmniej jeden z członów

koniunkcji. Może tak być, gdy

R

zinterpretujemy jako równość. Nie-

skończoność dziedziny jest warunkiem koniecznym prawdziwości na-
szego zdania. Skończoność dziedziny jest warunkiem wystarczającym
jego fałszywości. W takim razie skończoność dziedziny jest warun-
kiem wystarczającym prawdziwości jego negacji, czyli wystarcza na
to, aby prawdziwe było zdanie

∃x.¬xRf(x) ∨ ∃x.xRx ∨ ∃xyz.(xRy ∧ yRz ∧ ¬xRz)

.

Warunkiem koniecznym fałszywości tego zdania jest nieskończo-

ność dziedziny.