Elementy logiki. Klasyczny rachunek predykatów.

1

Elementy logiki

Klasyczny rachunek predykatów

Wojciech Buszkowski

Zakład Teorii Oblicze´n

Wydział Matematyki i Informatyki

Uniwersytet im. Adama Mickiewicza

Elementy logiki. Klasyczny rachunek predykatów.

2

2. K R P´

2.1. Wprowadzenie

Skrót: KRP
Inne nazwy: logika elementarna, logika pierwszego rz ˛edu (ang.
first-order logic, st ˛ad skrót FOL).
Rozwa˙zmy wnioskowanie:
Ka˙zdy Polak jest Europejczykiem. Jan jest Polakiem. Zatem Jan jest
Europejczykiem.
To wnioskowanie jest dedukcyjne, lecz nie mo˙zna tego stwierdzi´c na
gruncie KRZ. Schemat tego wnioskowania na gruncie KRZ to:

p; q

r

Oczywi´scie ten schemat nie jest logiczn ˛a reguł ˛a wnioskowania KRZ.

Elementy logiki. Klasyczny rachunek predykatów.

3

Na gruncie KRP wnikamy gł ˛ebiej w struktur ˛e zda´n.
Oznaczamy:

P(x) : x jest Polakiem
Q(x) : x jest Europejczykiem

a : Jan
Otrzymujemy schemat:

∀x(P(x) → Q(x)); P(a)

Q(a)

,

który jest logiczn ˛a reguł ˛a wnioskowania KRP.
To znaczy: dla ka˙zdej prawidłowej interpretacji symboli P, Q, a,
je˙zeli przesłanki tego schematu s ˛a prawdziwe, to wniosek jest
prawdziwy.

Elementy logiki. Klasyczny rachunek predykatów.

4

W j ˛ezyku formalnym KRP wyst ˛epuj ˛a nast ˛epuj ˛ace symbole.

Zmienne indywiduowe:

x, y, z (ewentualnie z indeksami).

Zmienne indywiduowe reprezentuj ˛a elementy pewnej dziedziny
obiektów, b ˛ed ˛acej niepustym zbiorem.

Stałe indywiduowe:

a, b, c (ewentualnie z indeksami).

Stałe indywiduowe oznaczaj ˛a wyró˙znione elementy dziedziny.
Innymi słowy, graj ˛a rol ˛e nazw własnych tych elementów. W j ˛ezyku
polskim nazwami własnymi s ˛a np. Warszawa, Lech Wał ˛esa. W
matematyce t ˛e rol ˛e graj ˛a symbole liczb, np. 0,1,2,. . ., π, e, symbole
wyró˙znionych zbiorów, np. N, R i inne.

Stałe logiczne:

spójniki logiczne KRZ i kwantyfikatory ∀ i ∃.

∀ nazywamy kwantyfikatorem ogólnym (generalnym, uniwersalnym,
du˙zym). Inne oznaczenie:

V

.

∃ nazywamy kwantyfikatorem szczegółowym (egzystencjalnym,
istnienia, małym). Inne oznaczenie:

W

.

Elementy logiki. Klasyczny rachunek predykatów.

5

Kwantyfikator zawsze wyst ˛epuje razem ze zmienn ˛a, np. ∀x, ∃x.
∀x czytamy: dla ka˙zdego x.
∃x czytamy: istnieje x takie, ˙ze.

Przykład.

∀x∃y(x < y) czytamy: dla ka˙zdego x istnieje y takie, ˙ze x

jest mniejsze od y.

Symbole relacyjne:

P, Q, R (ewentualnie z indeksami). Inna nazwa:

symbole predykatowe.
Przyjmujemy, ˙ze ka˙zdy symbol relacyjny ma jednoznacznie
okre´slon ˛a liczb ˛e argumentów (argumentowo´s´c, arno´s´c), któr ˛a
podajemy w deklaracji j ˛ezyka jako górny indeks, np. P

1

to

jednoargumentowy (unarny) symbol relacyjny, Q

2

to

dwuargumentowy (binarny) symbol relacyjny itp.
Argumentami symboli relacyjnych mog ˛a by´c zmienne i stałe
indywiduowe (równie˙z termy). Symbol relacyjny razem z
argumentami tworzy

formuł ˛e atomow ˛a

(atom).

Elementy logiki. Klasyczny rachunek predykatów.

6

Przykład.

Przykłady formuł atomowych, zbudowanych z symboli

relacyjnych P

1

, Q

1

, R

2

, zmiennych x, y i stałych indywiduowych a, b:

P(a) - czytamy: P od a. Q(x) - czytamy: Q od x. R(x, y) - czytamy:

R od x, y.
Formuła P(a) wyra˙za stwierdzenie, ˙ze a ma własno´s´c P.
Formuła R(x, y) wyra˙za stwierdzenie, ˙ze x jest w stosunku R do y.

Jednoargumentowe symbole relacyjne reprezentuj ˛a własno´sci
elementów dziedziny.
Dwuargumentowe symbole relacyjne reprezentuj ˛a stosunki
dwuczłonowe mi ˛edzy elementami dziedziny. W matematyce takimi
symbolami s ˛a np. =, <, ≤.
Symbole relacyjne o wi ˛ekszej liczbie argumentów reprezentuj ˛a
stosunki wieloczłonowe, np. R(x, y, z) : x le˙zy mi ˛edzy y i z
(dziedzina to zbiór wszystkich punktów danej prostej).

Elementy logiki. Klasyczny rachunek predykatów.

7

W j ˛ezyku matematyki poza symbolami relacyjnymi stosuje si ˛e
symbole funkcyjne.

Symbole funkcyjne

: f, g, h (z indeksami).

Symbole funkcyjne reprezentuj ˛a operacje (działania) okre´slone na
dziedzinie. W matematyce takimi symbolami s ˛a np. +, ·, sin.
Przyjmujemy, ˙ze ka˙zdy symbol funkcyjny ma jednoznacznie
okre´slon ˛a liczb ˛e argumentów, któr ˛a podajemy w deklaracji j ˛ezyka;
np. f

1

to symbol jednoargumentowy, g

2

to symbol

dwuargumentowy.
U. Dwuargumentowe symbole relacyjne i funkcyjne zwykle
piszemy pomi ˛edzy argumentami, np. piszemy x = y zamiast = (x, y)
i x + y zamiast +(x, y). Jest to tzw. notacja infiksowa. W
rozwa˙zaniach teoretycznych wszelkie symbole relacyjne i funkcyjne
piszemy przed ich argumentami; jest to tzw. notacja prefiksowa.

Elementy logiki. Klasyczny rachunek predykatów.

8

Podstawowymi wyra˙zeniami j ˛ezyka KRP s ˛a termy i formuły.

Termy

to wyra˙zenia poprawnie zbudowane ze zmiennych i stałych

indywiduowych za pomoc ˛a symboli funkcyjnych.
Termy proste: zmienne i stałe indywiduowe.
Termy zło˙zone: f (t

1

, . . . , t

n

), gdzie f jest n−argumentowym

symbolem funkcyjnym, a t

1

, . . . , t

n

s ˛a termami.

Przykład.

Niech f

1

, g

2

b ˛ed ˛a symbolami funkcyjnymi, a a, b stałymi

indywiduowymi j ˛ezyka. Wtedy wyra˙zenia:

x, y, a, b, f (x), f (a), f (b), g(x, y), g(a, b), g(x, f (a)), f (g(x, f (b)))

s ˛a termami.
Termy oznaczaj ˛a elementy dziedziny, je˙zeli stałe indywiduowe s ˛a
interpretowane jako nazwy wyró˙znionych elementów, a zmiennym
indywiduowym przypisano konkretne warto´sci w danej dziedzinie.

Elementy logiki. Klasyczny rachunek predykatów.

9

Formuły atomowe

to wyra˙zenia P(t

1

, . . . , t

n

) takie, ˙ze P jest

n−argumentowym symbolem relacyjnym, a t

1

, . . . , t

n

s ˛a termami.

Przykłady.

Niech P

1

, Q

2

b ˛ed ˛a symbolami relacyjnymi, f

1

, g

2

symbolami funkcyjnymi, a a, b stałymi indywiduowymi.
Przykładowe formuły atomowe to:

P(x), P(a), P(b), Q(x, y), Q( f (x), g(x, y)), P(g(x, f (b)))

Rozwa˙zmy j ˛ezyk arytmetyki z symbolami relacyjnymi =

2

, <

2

,

symbolami funkcyjnymi +

2

, ·

2

i stałymi indywiduowymi 0, 1, 2, . . ..

Termami tego j ˛ezyka w notacji infiksowej s ˛a np.

x, y, 0, x + y, (x · y) + z, x + (2 · z). W notacji prefiksowej te same

termy wygl ˛adaj ˛a tak: x, y, 0, +(x, y), +(·(x, y), z), +(x, ·(2, z)).
Formułami atomowymi tego j ˛ezyka w notacji infiksowej s ˛a np.

x = y, x < 2, 2 + 1 = 3, 2 + 2 = 3; w notacji prefiksowej te formuły

wygl ˛adaj ˛a tak = (x, y), < (x, 2), = (+(2, 1), 3), = (+(2, 2), 3).

Elementy logiki. Klasyczny rachunek predykatów.

10

Formuły

to wyra˙zenia poprawnie zbudowane z formuł atomowych

za pomoc ˛a spójników logicznych KRZ i kwantyfikatorów.
Formuły zło˙zone:
(¬A), (A ∧ B), (A ∨ B), (A → B), (A ↔ B), (∀xA), (∃xA), gdzie A, B
s ˛a formułami.
Zamiast ∀xA, ∃xA piszemy te˙z ∀

x

A, ∃

x

A.

W zapisie formuł pomijamy nawiasy zewn ˛etrzne oraz niektóre
nawiasy wewn ˛etrzne, przyjmuj ˛ac siłe wi ˛azania spójników
logicznych jak w KRZ oraz nadaj ˛ac kwantyfikacjom ∀x, ∃x t ˛e sam ˛a
sił ˛e, co negacji.

Przykład.

Napis ∀xP(x) ∧ ∀xQ(x) ↔ ∀x(P(x) ∧ Q(x)) przedstawia

formuł ˛e:

((∀xP(x)) ∧ (∀xQ(x))) ↔ (∀x(P(x) ∧ Q(x)))

Formuły to wyra˙zenia zdaniowe, a termy to wyra˙zenia nazwowe.

Elementy logiki. Klasyczny rachunek predykatów.

11

2.2. Podformuły. Zmienne wolne i zwi ˛azane. Podstawianie.

A ∗ B oznacza dowoln ˛a formuł ˛e postaci A ∧ B, A ∨ B, A → B,
A ↔ B, je˙zeli nie ma znaczenia, który spójnik dwuargumentowy

wystepuje w formule. Podobnie K xA oznacza dowoln ˛a formuł ˛e
postaci ∀xA, ∃xA.

Zło˙zono´s´c formuły

okre´slamy jako liczb ˛e wszystkich wyst ˛apie´n

stałych logicznych w tej formule.
Wiele definicji i dowodów twierdze´n dotycz ˛acych formuł (ogólnie:
wyra˙ze´n formalnych) przebiega przez indukcj ˛e po zło˙zono´sci.

Definicja 1

(podformuła danej formuły).

(a) Podformuł ˛a formuły atomowej jest tylko ta formuła.
(b) Podformuł ˛a formuły ¬A jest ta formuła i ka˙zda podformuła
formuły A; podobnie dla formuły KxA.
(c) Podformuł ˛a formuły A ∗ B jest ta formuła, ka˙zda podformuła
formuły A i ka˙zda podformuła formuły B.

Elementy logiki. Klasyczny rachunek predykatów.

12

Przykład.

Podformułami formuły ¬∀xP(x) → ∃x¬P(x) s ˛a: ta

formuła, ¬∀xP(x), ∀xP(x), P(x), ∃x¬P(x) i ¬P(x). Zauwa˙zmy, ˙ze ta
formuła zawiera dwa wyst ˛apienia podformuły P(x).
Je˙zeli KxB jest wyst ˛apieniem podformuły w formule A, to dane
wyst ˛apienie B nazywamy

zasi ˛egiem

danego wyst ˛apienia

kwantyfikacji K x w formule A.

Przykład.

W powy˙zszym przykładzie, zasi ˛egiem ∀x jest pierwsze

wyst ˛apienie P(x), a zasi ˛egiem ∃x jest jedyne wyst ˛apienie ¬P(x).

Definicja 2

(zwi ˛azane i wolne wyst ˛apienia zmiennej). Wyst ˛apienie

zmiennej x w formule A nazywamy zwi ˛azanym, je˙zeli wchodzi w
skład pewnej podformuły KxB formuły A. Wyst ˛apienie zmiennej,
które nie jest zwi ˛azane, nazywamy wolnym w danej formule.
Mówimy, ˙ze zmienna jest wolna (odp. zwi ˛azana) w danej formule,
je˙zeli ta formuła zawiera przynajmniej jedno wolne (odp. zwi ˛azane)
wyst ˛apienie tej zmiennej.

Elementy logiki. Klasyczny rachunek predykatów.

13

Przykład.

W formule P(x) → ∃xQ(x, y) pierwsze wyst ˛apienie x i

jedyne wyst ˛apienie y s ˛a wolne, a drugie i trzecie wyst ˛apienie x s ˛a
zwi ˛azane. Zatem zmienne wolne w tej formule to x, y, a jedyn ˛a
zmienn ˛a zwi ˛azan ˛a jest x.
U. W praktyce unikamy formuł, w których ta sama zmienna
jest wolna i zwi ˛azana. Powy˙zsza formuła jest logicznie równowa˙zna
formule P(x) → ∃zQ(z, y), poniewa˙z zmienn ˛a zwi ˛azan ˛a mo˙zna
zamieni´c na inn ˛a (z pewnymi ograniczeniami).
Role zmiennych wolnych i zwi ˛azanych s ˛a inne. Warto´s´c logiczna
formuły zale˙zy od warto´sci zmiennych wolnych, lecz nie zale˙zy od
warto´sci zmiennych zwi ˛azanych.
Rozwa˙zmy formuł ˛e ∃y(y < x) j ˛ezyka arytmetyki liczb naturalnych
0, 1, 2, . . .. Ta formuła jest prawdziwa w dziedzinie liczb
naturalnych, je˙zeli warto´sci ˛a x jest liczba dodatnia, lecz fałszywa,
je˙zeli warto´sci ˛a x jest 0. Warto´s´c logiczna tej formuły nie zale˙zy od
warto´sci zmiennej zwi ˛azanej y.

Elementy logiki. Klasyczny rachunek predykatów.

14

Definicja 3.

Formuły nie zawieraj ˛ace zmiennych wolnych

nazywamy zdaniami (albo: formułami domkni ˛etymi).

Przykład.

Zdania atomowe to formuły atomowe nie zawieraj ˛ace

zmiennych, np. P(a), Q(a, b), Q( f (a), g(a, b)), czy te˙z 1 = 2, 1 < 2,
2 + 1 = 3 w j ˛ezyku arytmetyki.
Zdania zło˙zone to albo kombinacje zda´n atomowych za pomoc ˛a
spójników logicznych KRZ, albo formuły, zawieraj ˛ace zmienne, ale
tylko zmienne zwi ˛azane, np. ¬P(a) ∨ Q(a, b), ∀x¬P(x) → ¬∃xP(x).
UWAGA. W zale˙zno´sci od zastosowa´n przyjmujemy ró˙zne symbole
relacyjne, funkcyjne i stałe indywiduowe; pozostałe symbole s ˛a
zawsze takie same. Wobec tego konkretny j ˛ezyk formalny KRP,
zwany te˙z

j ˛ezykiem elementarnym

mo˙zna całkowicie

scharakteryzowa´c, wymieniaj ˛ac wszystkie symbole relacyjne,
symbole funkcyjne i stałe indywiduowe, np. podaj ˛ac listy
odpowiednich symboli.

Elementy logiki. Klasyczny rachunek predykatów.

15

Istotn ˛a rol ˛e odgrywa podstawianie termów za zmienne.

Definicja 4.

Podstawieniem nazywamy sko´nczon ˛a list ˛e

σ = [x

1

/t

1

, . . . , x

n

/t

n

]

tak ˛a, ˙ze x

1

, . . . , x

n

s ˛a ró˙znymi zmiennymi indywiduowymi, a

t

1

, . . . , t

n

s ˛a termami.

Dopuszczamy podstawienie puste (identyczno´sciowe): ε = [].
Przez tσ (odp. Aσ) oznaczamy wynik podstawienia σ w termie t
(odp. formule A), tj. term otrzymany w wyniku podstawienia termu
t

i

za ka˙zde wyst ˛apienie x

i

w t (odp. formuł ˛e otrzyman ˛a w wyniku

podstawienia t

i

za ka˙zde wolne wyst ˛apienie x

i

w A) dla i = 1, . . . , n.

Przykład.

((x + y) · x)[x/y, y/z + 1] ≡ (y + (z + 1)) · y.

(∃x(x = y))[x/y, y/z + 1] ≡ ∃x(x = z + 1).
Symbolem ≡ oznaczamy równo´s´c wyra˙ze´n.

Elementy logiki. Klasyczny rachunek predykatów.

16

Rekurencyjna definicja tσ i Aσ dla σ = [x

1

/t

1

, . . . , x

n

/t

n

].

x

i

σ ≡ t

i

,

yσ ≡ y dla dowolnej zmiennej y < {x

1

, . . . , x

n

},

aσ ≡ a dla dowolnej stałej indywiduowej a,

f (s

1

, . . . , s

m

)σ ≡ f (s

1

σ, . . . , s

m

σ),

P(s

1

, . . . , s

m

)σ ≡ P(s

1

σ, . . . , s

m

σ),

(¬A)σ ≡ ¬Aσ (przyjmujemy, ˙ze σ wi ˛a˙ze najsilniej),
(A ∗ B)σ ≡ Aσ ∗ Bσ,
(KxA)σ ≡ K xAσ, je˙zeli x < {x

1

, . . . , x

n

},

(Kx

i

A)σ ≡ Kx

i

Aσ

0

, gdzie σ

0

powstaje z σ przez usuni ˛ecie

przypisania x

i

/t

i

.

Fakt 1.

Dla wszelkich formuł A, termów t i zmiennych x: tε ≡ t,

Aε ≡ A, (KxA)[x/t] ≡ K xA.

Elementy logiki. Klasyczny rachunek predykatów.

17

Definicja 5.

Mówimy, ˙ze term t jest podstawialny za zmienn ˛a x w

formule A, je˙zeli ˙zadne wolne wyst ˛apienie x w A nie wyst ˛epuje w
podformule postaci KyB takiej, ˙ze y wyst ˛epuje w t.

Przykład.

Niech A ≡ ∃y(x < y). Wtedy t jest podstawialne za x w A

wtw, gdy y nie wyst ˛epuje w t. Na przykład, z, z + x, 0 s ˛a
podstawialne za x w A, lecz y, y + 1 nie s ˛a podstawialne za x w A.
Zauwa˙zmy, ˙ze formuła A jest prawdziwa w dziedzinie liczb
całkowitych dla wszystkich warto´sci x. Je˙zeli t jest podstawialne za

x w A, to formuła A[x/t] jest te˙z prawdziwa w tej dziedzinie, np.

∃y(z < y), ∃y(z + x < y), ∃y(0 < y). Je˙zeli t nie jest podstawialne za x
w A, to A[x/t] mo˙ze nie by´c formuł ˛a prawdziw ˛a w tej dziedzinie, np.
∃y(y < y), ∃y(y + 1 < y). Je˙zeli t nie jest podstawialne za x w A, to
mówimy, ˙ze nast ˛apiła kolizja zmiennych przy podstawianiu A[x/t].
Ka˙zdy term bez zmiennych jest podstawialny za dowoln ˛a zmienn ˛a w
dowolnej formule. Ka˙zdy term jest podstawialny za dowoln ˛a
zmienn ˛a w dowolnej formule, nie zawieraj ˛acej kwantyfikatorów.

Elementy logiki. Klasyczny rachunek predykatów.

18

2.3. Prawa KRP, logiczna równowa˙zno´s´c i logiczne wynikanie w
KRP

Interpretacja

j ˛ezyka elementarnego polega na ustaleniu niepustego

zbioru, zwanego dziedzin ˛a lub uniwersum interpretacji, oraz nadaniu
znaczenia wszystkim symbolom relacyjnym, symbolom funkcyjnym
i stałym indywiduowym j ˛ezyka.
Symbole relacyjne interpretujemy jako nazwy wyró˙znionych relacji
(stosunków) mi ˛edzy elementami dziedziny.
Symbole funkcyjne interpretujemy jako nazwy wyró˙znionych
operacji (działa´n) okre´slonych na dziedzinie, tzn. przyjmuj ˛acych
zarówno argumenty jak i warto´sci w tej dziedzinie.
Stałe indywiduowe interpretujemy jako nazwy wyró˙znionych
elementów dziedziny.

Elementy logiki. Klasyczny rachunek predykatów.

19

Przykład.

Rozwa˙zmy j ˛ezyk z symbolami relacyjnymi R

2

, =

2

i

symbolami funkcyjnymi f

1

, g

1

.

Niech dziedzin ˛a interpretacji M b ˛edzie zbiór wszystkich ludzi.
Nadajemy znaczenie symbolom.
R

M

(x, y) : x i y s ˛a rodze´nstwem

x =

M

y : x jest równe y (x jest t ˛a sam ˛a osob ˛a, co y)

f

M

(x) : matka osoby x

g

M

(x) : ojciec osoby x

Zdania:
∀x∀y(R(x, y) ↔ f (x) = f (y) ∧ g(x) = g(y))
∀x∃y(y = f (x))
s ˛a prawdziwe w tej interpretacji.
Zdanie ∀x∃y(x = f (y)) jest fałszywe w tej interpretacji.

Elementy logiki. Klasyczny rachunek predykatów.

20

Inn ˛a interpretacj ˛a tego samego j ˛ezyka jest M

0

, która ró˙zni si ˛e od M

tylko znaczeniem symbolu R.
R

M

0

(x, y) : x jest osob ˛a młodsz ˛a od y

Oczywi´scie pierwsze z powy˙zszych zda´n jest fałszywe w M

0

.

Istnieje niesko´nczenie wiele mo˙zliwych interpretacji danego j ˛ezyka
elementarnego, które ró˙zni ˛a si ˛e dziedzinami i znaczeniem symboli.
Na ogół zdanie j ˛ezyka jest prawdziwe w jednych, lecz fałszywe w
innych interpretacjach.
Formuła ze zmiennymi wolnymi, np. x < y, mo˙ze by´c prawdziwa
albo fałszywa w danej interpretacji w zale˙zno´sci od warto´sci
przypisanych zmiennym wolnym. Wprowadzimy poj ˛ecie
warto´sciowania zbioru zmiennych indywiduowych V.

Warto´sciowaniem

zbioru V w danej interpretacji nazywamy

dowoln ˛a funkcj ˛e, która zmiennym ze zbioru V przyporz ˛adkowuje
elementy dziedziny tej interpretacji.

Elementy logiki. Klasyczny rachunek predykatów.

21

Ka˙zde zdanie j ˛ezyka jest prawdziwe albo fałszywe w danej
interpretacji tego j ˛ezyka. Ka˙zda formuła j ˛ezyka jest prawdziwa albo
fałszywa w danej interpretacji tego j ˛ezyka przy ustalonym
warto´sciowaniu zmiennych wolnych tej formuły.
Wygodnie jest przyj ˛a´c, ˙ze

formuła jest prawdziwa w interpretacji M

,

je˙zeli jest prawdziwa w M przy ka˙zdym warto´sciowaniu zmiennych
wolnych tej formuły.

Fakt 2.

Formuła A ze zmiennymi wolnymi x

1

. . . , x

n

jest prawdziwa

w interpretacji M wtw, gdy zdanie ∀x

1

. . . ∀x

n

A jest prawdziwe w

interpretacji M.
To zdanie nazywamy

generalizacj ˛a

formuły A.

U. Poj ˛ecia interpretacji oraz prawdziwo´sci zdania i formuły nie
zostały zdefiniowane precyzyjnie. ´Scisłe definicje mog ˛a by´c
sformułowane na gruncie teorii mnogo´sci. Dla naszych potrzeb
wystarcz ˛a powy˙zsze, nie całkiem ´scisłe definicje.

Elementy logiki. Klasyczny rachunek predykatów.

22

Definicja 6.

Prawem KRP nazywamy formuł ˛e, która jest prawdziwa

we wszystkich interpretacjach danego j ˛ezyka.
Prawa KRP s ˛a te˙z nazywane tautologiami KRP.

Przykład.

Prawami KRP s ˛a prawa podstawiania:

∀xP(x) → P(a); P(a) → ∃xP(x)

Pierwsze prawo podstawiania stwierdza, ˙ze je˙zeli ka˙zdy element
dziedziny interpretacji M ma własno´s´c P

M

, to element a

M

ma

własno´s´c P

M

.

Drugie prawo podstawiania stwierdza, ˙ze je˙zeli element a

M

ma

własno´s´c P

M

, to istnieje element dziedziny interpretacji M, maj ˛acy

własno´s´c P

M

.

Oczywi´scie te zdania s ˛a prawdziwe w ka˙zdej interpretacji. Ich
prawdziwo´s´c jest konsekwencj ˛a znaczenia stałych logicznych
∀, ∃, →, niezale˙znie od własno´sci konkretnej interpretacji.

Elementy logiki. Klasyczny rachunek predykatów.

23

Prawami KRP s ˛a te˙z formuły:

∀xP(x) → P(y); P(y) → ∃xP(x)

gdzie x, y s ˛a dowolnymi zmiennymi (dopuszczamy x ≡ y).
Ogólniej, dla dowolnego termu t prawami KRP s ˛a formuły:

∀xP(x) → P(t); P(t) → ∃xP(x)

Jeszcze ogólniej, dla dowolnych formuł A, zmiennych x i termów t
podstawialnych za x w A prawami KRP s ˛a formuły:

∀xA → A[x/t]; A[x/t] → ∃xA

Jest to najogólniejsza posta´c praw podstawiania.

Elementy logiki. Klasyczny rachunek predykatów.

24

Lista podstawowych praw KRP

(TL0) wszystkie formuły logicznie prawdziwe na gruncie KRZ
prawa podstawiania
(TL1a) ∀xA → A[x/t], (TL1e) A[x/t] → ∃xA (warunek: t jest
podstawialne za x w A)
prawa zb ˛ednego kwantyfikatora
(TL2a) ∀xA ↔ A, (TL2e) ∃xA ↔ A (warunek: x nie jest wolne w A)
prawa dwustronnego doł ˛aczania kwantyfikatorów do implikacji
(TL3a) ∀x(A → B) → (∀xA → ∀xB)
(TL3e) ∀x(A → B) → (∃xA → ∃xB)
prawa jednostronnego doł ˛aczania kwantyfikatora do implikacji
(TL4a) ∀x(A → B) → (A → ∀xB) (warunek: x nie jest wolne w A)
(TL4e) ∀x(A → B) → (∃xA → B) (warunek: x nie jest wolne w B)

Elementy logiki. Klasyczny rachunek predykatów.

25

prawa rozdzielno´sci kwantyfikatorów
(TL5a) ∀x(A ∧ B) ↔ ∀xA ∧ ∀xB
(TL5e) ∃x(A ∨ B) ↔ ∃xA ∨ ∃xB
niepełne prawa rozdzielno´sci kwantyfikatorów
(TL6a) ∀xA ∨ ∀xB → ∀x(A ∨ B)
(TL6e) ∃x(A ∧ B) → ∃xA ∧ ∃xB
prawa przestawiania kwantyfikatorów
(TL7a) ∀x∀yA ↔ ∀y∀xA
(TL7e) ∃x∃yA ↔ ∃y∃xA
niepełne prawo przestawiania kwantyfikatorów
(TL8) ∃x∀yA → ∀y∃xA

Elementy logiki. Klasyczny rachunek predykatów.

26

prawa De Morgana dla kwantyfikatorów
(TL9a) ¬∀xA ↔ ∃x¬A , (TL9e) ¬∃xA ↔ ∀x¬A
prawa zamiany zmiennej zwi ˛azanej
(TL10a) ∀xA ↔ ∀yA[x/y] , (TL10e) ∃xA ↔ ∃yA[x/y],
je´sli spełnione s ˛a warunki: (w1) x . y, (w2) y nie jest wolne w A
(w3) y jest podstawialne za x w A. Te warunki s ˛a spełnione, gdy y
nie wyst ˛epuje w ∀xA (jest tzw. now ˛a zmienn ˛a).
prawa wył ˛aczania kwantyfikatora przed nawias
(TL11a) ∀xA ∗ B ↔ ∀x(A ∗ B) je´sli ∗ ∈ {∧, ∨} i x nie jest wolne w B,
(TL11e) ∃xA ∗ B ↔ ∃x(A ∗ B) przy tych samych zastrze˙zeniach.
prawa ekstensjonalno´sci dla kwantyfikatorów
(TL12a) ∀x(A ↔ B) → (∀xA ↔ ∀xB)
(TL12e) ∀x(A ↔ B) → (∃xA ↔ ∃xB)

Elementy logiki. Klasyczny rachunek predykatów.

27

Definicja 7.

Mówimy, ˙ze formuła A jest logicznie równowa˙zna

formule B w KRP, je˙zeli formuła A ↔ B jest prawem KRP.

Przykłady.

Formuła ¬∀xA jest logicznie równowa˙zna formule

∃x¬A. Formuła ∀x(A ∧ B) jest logicznie równowa˙zna formule
∀xA ∧ ∀xB.

Definicja 8.

Interpretacj ˛e M nazywamy modelem zbioru formuł S

danego j ˛ezyka, je˙zeli ka˙zda formuła z S jest prawdziwa w M.

Przykłady.

Ka˙zda interpretacja danego j ˛ezyka jest modelem

dowolnego zbioru praw KRP, sformułowanych w tym j ˛ezyku. M jest
modelem zbioru:

{∃xP(x), ∀x(P(x) → Q(x))}

wtedy i tylko wtedy, gdy przynajmniej jeden element dziedziny ma
własno´s´c P

M

i ka˙zdy element maj ˛acy własno´s´c P

M

ma własno´s´c Q

M

.

Elementy logiki. Klasyczny rachunek predykatów.

28

Definicja 9.

Mówimy, ˙ze formuła A wynika logicznie ze zbioru

formuł S w KRP, je˙zeli A jest prawdziwe we wszystkich modelach
zbioru S .

Fakt 3.

Niech A

1

, . . . , A

n

b ˛ed ˛a zdaniami. Formuła A wynika

logicznie z formuł A

1

, . . . , A

n

(tzn. ze zbioru {A

1

, . . . , A

n

}) wtw, gdy

formuła A

1

∧ · · · ∧ A

n

→ A jest prawem KRP.

U. Implikacja ⇐ jest prawdziwa dla dowolnych formuł

A

1

, . . . , A

n

. Implikacja ⇒ nie zawsze jest prawdziwa, gdy nie

wszystkie formuły A

1

, . . . , A

n

s ˛a zdaniami.

Przykład (wa˙zny).

Dla dowolnej interpretacji M, je˙zeli P(x) jest

prawdziwe w M, to ∀xP(x) jest prawdziwe w M, a wi ˛ec ∀xP(x)
wynika logicznie z P(x).
Formuła P(x) → ∀xP(x) nie jest prawem KRP. Nie jest prawdziwa w
takiej interpretacji M, której pewien element e ma własno´s´c P

M

, lecz

nie ka˙zdy element ma t ˛e własno´s´c.

Elementy logiki. Klasyczny rachunek predykatów.

29

Jak w KRZ, schemat wnioskowania

(SW)

A

1

; . . . ; A

n

A

nazywamy

logiczn ˛a reguł ˛a wnioskowania

KRP, je˙zeli wniosek A

wynika logicznie z przesłanek A

1

, . . . , A

n

.

Pierwsz ˛a grup ˛e logicznych reguł wnioskowania KRP stanowi ˛a
wszystkie schematy (SW) takie, ˙ze formuła A

1

∧ · · · ∧ A

n

→ A jest

prawem KRP. Do tej grupy nale˙z ˛a wszystkie logiczne reguły
wnioskowania KRZ; dokładniej: reguły powstaj ˛ace z logicznych
reguł wnioskowania KRZ przez podstawienie dowolnych formuł
j ˛ezyka elementarnego za zmienne zdaniowe. Na przykład:

(MP)

A → B; A

B

, (SYL)

A → B; B → C

A → C

,

gdzie A, B, C oznaczaj ˛a dowolne formuły j ˛ezyka elementarnego.

Elementy logiki. Klasyczny rachunek predykatów.

30

Oczywi´scie te reguły odpowiadaj ˛a prawom KRP z grupy (TL0), tzn.
prawom powstaj ˛acym z tautologii KRZ przez podstawianie
dowolnych formuł j ˛ezyka elementarnego za zmienne zdaniowe.
Do pierwszej grupy nale˙z ˛a te˙z reguły odpowiadaj ˛ace prawom KRP
postaci A

1

∧ · · · ∧ A

n

→ A, które nie wchodz ˛a w skład (TL0). Na

przykład, prawom (TL1a), (TL1e) odpowiadaj ˛a reguły:

(RL1a)

∀xA

A[x/t]

, (RL1e)

A[x/t]

∃xA

;

warunek: term t jest podstawialny za x w A.
Druga grupa składa si ˛e z reguł, które nie odpowiadaj ˛a prawom KRP.
Wymienimy dwie wa˙zne reguły: reguł ˛e generalizacji (GEN) i reguł ˛e
podstawiania (POD):

(GEN)

A

∀xA

, (POD)

A

A[x/t]

(warunek: jak dla (RL1)).