M

ETALOGIKA

D

ODATEK

2:

D

OWODY

N

IEKTÓRYCH

T

WIERDZE ´

N

D

OTYCZ ˛

ACYCH

O

PERACJI

K

ONSEKWENCJI

W J

˛

EZYKACH

Z

DANIOWYCH

D

EFINICJA

1. Operacja konsekwencji wyznaczona przez reguły wnioskowania.

Niech S b˛edzie zbiorem wszystkich wyra˙ze´n poprawnych (formuł) j˛ezyka zdanio-

wego J . Niech R b˛edzie dowoln ˛

a rodzin ˛

a reguł wnioskowania w J . Przez operacj˛e

konsekwencji w J wyznaczon ˛

a przez R rozumiemy ka˙zd ˛

a funkcj˛e C : 2

S

→ 2

S

,

zdefiniowan ˛

a indukcyjnie nast˛epuj ˛

acymi warunkami dla dowolnego zbioru formuł X

j˛ezyka J :

• (1) C

0

R

(X) = X

• (2) C

k+1

R

(X) = C

k

R

(X) ∪ {α ∈ S : (∃R ∈ R)(∃P ⊆ C

k

R

(X)) (P, α) ∈ R}

• (3) C

R

(X) =

S{C

k

R

(X) : k ∈ N }.

Wyra˙zenie α ∈ C

R

(X) czytamy: α jest wyprowadzalna z X za pomoc ˛

a reguł

nale˙z ˛

acych do R.

Niech Cld(R, X) oznacza, ˙ze zbiór formuł X j˛ezyka J jest domkni˛ety na wszyst-

kie reguły ze zbioru R: Cld(R, X) wtedy i tylko wtedy, gdy

(∀R ∈ R)(∀P ⊆ S)(∀α ∈ S)(((P, α) ∈ R ∧ P ⊆ X) ⇒ α ∈ X).

U

WAGA

. Prosz˛e odró˙znia´c symbol implikacji → w KRZ od u˙zywanego tu metaj˛ezy-

kowego symbolu ⇒.

Twierdzenie A. Operacja konsekwencji wyznaczona przez reguły R ma nast˛epuj ˛

ace

własno´sci:

• (1) Je´sli n < m, to C

n

R

(X) ⊆ C

m

R

(X).

• (2) α ∈ C

R

(X) wtedy i tylko wtedy, gdy α ∈ Y dla ka˙zdego zbioru Y takiego,

˙ze X ⊆ Y oraz Cld(R, Y ).

1

• (3) ((P, α) ∈ R ∧ R ∈ R) ⇒ α ∈ C

R

(P ).

• (4) ((P, α) ∈ R ∧ R ∈ R ∧ P ⊆ C

R

(X)) ⇒ α ∈ C

R

(X).

• (5) X ⊆ C

R

(X)

(zwrotno´s´c).

• (6) X ⊆ Y ⇒ C

R

(X) ⊆ C

R

(Y )

(monotoniczno´s´c).

• (7) R

1

⊆ R

2

⇒ C

R

1

(X) ⊆ C

R

2

(X)

(monotoniczno´s´c).

• (8) C

R

(C

R

(X)) = C

R

(X)

(idempotencja).

• (9) C

R

(X) =

S{C

R

(Y ) : Y ⊆ X ∧ Y < ℵ

0

}

(finitystyczno´s´c).

• (10) C

R

(X) =

S{C

R

0

(X) : R

0

⊆ R ∧ R

0

< ℵ

0

}

(finitystyczno´s´c).

• (11) Je´sli dla dowolnych elementów X, Y niepustej rodziny X zachodzi alter-

natywa X ⊆ Y ∨ Y ⊆ X, to: C

R

(

S{X : X ∈ X }) = S{C

R

(X) : X ∈ X }.

D

OWÓD

.

(1). Dowód przeprowadzimy przez indukcj˛e. Załó˙zmy, ˙ze n < m.

Je´sli n = m − 1, to C

n

R

(X) ⊆ C

m

R

(X) na mocy punktu (2) definicji 1. Załó˙zmy

teraz, ˙ze teza twierdzenia zachodzi dla n = m − k, gdzie k < m. Poka˙zemy, ˙ze
zachodzi ona tak˙ze dla n = m − (k + 1).

Zakładamy zatem, ˙ze C

m−k

R

(X) ⊆ C

R

(X). Niech α ∈ C

m−(k+1)

R

(X). Oznacza

to, ˙ze α ∈ C

(m−k)−1)

R

(X), a wi˛ec, na mocy punktu (2) definicji 1., α ∈ C

m−k

R

(X). Z

zało˙zenia indukcyjnego otrzymujemy wtedy α ∈ C

m

R

(X).

(2). Trzeba dowie´s´c implikacje: prost ˛

a i odwrotn ˛

a.

Dowód

⇐. Załó˙zmy, ˙ze α ∈ Y dla ka˙zdego zbioru Y takiego, ˙ze X ⊆ Y oraz

Cld(R, Y ). Wprost z definicji 1. wida´c, ˙ze X ⊆ C

R

(X). Poka˙zemy, ˙ze C

R

(X) jest

domkni˛ety na wszystkie reguły ze zbioru R.

Je´sli R ∈ R, (P, α) ∈ R oraz P ⊆ C

R

(X), gdzie P = {β

1

, . . . , β

n

}, to dla

wszystkich i

6 n: β

i

∈ C

k

i

R

(X) . Niech k = max(k

1

, . . . , k

n

). Na mocy udowodnio-

nego przed chwil ˛

a punktu (1) twierdzenia A., P ⊆ C

k

R

(X), a st ˛

ad, zgodnie z punktem

(2) definicji 1., α ∈ C

k+1

R

(X). Poniewa˙z C

k+1

R

(X) ⊆ C

R

(X), wi˛ec α ∈ C

R

(X).

Dowód

⇒. Załó˙zmy, ˙ze α ∈ C

R

(X) oraz niech X ⊆ i Cld(Y ). Otrzymujemy st ˛

ad,

˙ze α ∈ C

R

(Y ). Skoro Cld(R, Y ), to α ∈ Y .

(3). Wynika wprost z definicji 1. oraz z udowodnionego przed chwil ˛

a punktu (1)

twierdzenia A.

(4). Wynika wprost z definicji 1. oraz z udowodnionego przed chwil ˛

a punktu (1)

twierdzenia A.

(5). Wynika wprost z definicji 1.

2

(6). Wynika wprost z definicji 5.1.

(7). Wynika wprost z definicji 1.

(8). Inkluzja C

R

(X) ⊆ C

R

(C

R

(X)) jest konsekwencj ˛

a monotoniczno´sci operatora

C

R

.

Dla dowodu inkluzji C

R

(C

R

(X)) ⊆ C

R

(X) załó˙zmy, ˙ze α ∈ C

R

(C

R

(X)).

Istniej ˛

a wtedy β

1

, . . . , β

n

∈ C

R

(X) takie, ˙ze α ∈ C

h

R

({β

1

, . . . , β

n

}), dla pewnej

liczby h.

Z kolei, dla ka˙zdej formuły β

i

, gdzie 1

6 i 6 n istniej ˛

a formuły γ

i

1

, . . . γ

i

m

i

∈ X

takie, ˙ze:

• β

1

∈ C

k

1

R

({γ

1

1

, . . . γ

1

m

1

})

•

..

.

• β

n

∈ C

k

n

R

({γ

n

1

, . . . γ

n

m

n

}).

Niech k = max(k

1

, . . . , k

n

). Wtedy:

α ∈ C

h+k

R

({γ

1

1

, . . . γ

1

m

1

, . . . , γ

n

1

, . . . γ

n

m

n

}).

A zatem α ∈ C

R

(X). Ostatecznie, mamy: C

R

(C

R

(X)) = C

R

(X).

(9). Wynika z faktu, ˙ze rozwa˙zane zbiory przesłanek s ˛

a sko´nczone.

(10). Wynika z faktu, ˙ze rozwa˙zane zbiory przesłanek s ˛

a sko´nczone.

(11). Inkluzja

S{C

R

(X) : X ∈ X } ⊆ C

R

(

S{X : X ∈ X }) wynika z monotonicz-

no´sci operatora C

R

.

Dla dowodu inkluzji C

R

(

S{X : X ∈ X }) ⊆ S{C

R

(X) : X ∈ X } niech

α ∈ C

R

(

S{X : X ∈ X }). Musimy pokaza´c, ˙ze α ∈ C

R

(X) dla pewnego X ∈ X .

Skoro α ∈ C

R

(

S{X : X ∈ X }), to istniej ˛

a β

1

, . . . , β

n

∈

S{X : X ∈ X }

takie, ˙ze α ∈ C

R

({β

1

, . . . , β

n

}). Z zało˙zenia, rodzina X jest liniowo uporz ˛

adkowana

przez inkluzj˛e. Poniewa˙z zbiór {β

1

, . . . , β

n

} jest sko´nczony, wi˛ec istnieje najmniejszy

(wzgl˛edem inkluzji) zbiór X ∈ X taki, ˙ze {β

1

, . . . , β

n

} ⊆ X. Z monotoniczno´sci

operatora C

R

otrzymujemy: α ∈ C

R

(X).

Ostatecznie, mamy: C

R

(

S{X : X ∈ X }) = S{C

R

(X) : X ∈ X }.

D

EFINICJA

2. Reguły dopuszczalne i reguły wyprowadzalne.

Zbiór P erm(R, X) wszystkich reguł dopuszczalnych ze wzgl˛edu na X i R defi-

niujemy nast˛epuj ˛

aco:

R ∈ P erm(R, X) wtedy i tylko wtedy, gdy dla ka˙zdego P ⊆ S oraz ka˙zdej

α ∈ S: je´sli (P, α) ∈ R i P ⊆ C

R

(X), to α ∈ C

R

(X).

Zbiór Der(R, X) wszystkich reguł wyprowadzalnych ze wzgl˛edu na X i R defi-

niujemy nast˛epuj ˛

aco:

R ∈ Der(R, X) wtedy i tylko wtedy, gdy dla ka˙zdego P ⊆ S oraz ka˙zdej α ∈ S:

je´sli (P, α) ∈ R, to α ∈ C

R

(X ∪ P ).

3

Twierdzenie B.

R ∈ P erm(R, X) wtedy i tylko wtedy, gdy C

R∪{R}

(X) ⊆ C

R

(X).

D

OWÓD

. Trzeba dowie´s´c implikacje: prost ˛

a i odwrotn ˛

a.

Dowód

⇒.

Załó˙zmy, ˙ze R ∈ P erm(R, X). Niech α ∈ C

R∪{R}

(X). Na mocy punktu (2)

twierdzenia A. mamy wtedy: je´sli Cld(R ∪ {R}, X), to α ∈ C

R

(X). St ˛

ad i z zało˙ze-

nia, ˙ze R ∈ P erm(R, X) mamy: α ∈ C

R

(X).

Dowód

⇐.

Niech (P, α) ∈ R oraz P ⊆ C

R

(X). Na mocy monotoniczno´sci (wzgl˛edem reguł)

operatora C

R

mamy: P ⊆ C

R∪{R}

(X). St ˛

ad, na mocy punktu (4) twierdzenia A.

otrzymujemy: α ∈ C

R∪{R}

(X) = C

R

(X).

Twierdzenie C.

• (1) R ∈ Der(R, X) wtedy i tylko wtedy, gdy dla ka˙zdego zbioru Y ⊆ S oraz

ka˙zdej rodziny reguł R

0

: C

R∪R

0

∪{R}

(X ∪ Y ) ⊆ C

R∪R

0

(X ∪ Y ).

• (2) Der(R, X) ⊆ P erm(R, X).

• (3) Istniej ˛

a: R oraz X takie, ˙ze P erm(R, X) − Der(R, X) 6= ∅.

D

OWÓD

.

(1). Dowód implikacji ⇐ otrzymujemy bezpo´srednio z punktu (3) twierdzenia A.

Dla dowodu implikacji ⇒ zauwa˙zmy, ˙ze je´sli R ∈ Der(R, X), to, na mocy punk-

tów (5)–(10), zbiór C

R∪R

0

∪{R}

(X ∪ Y ) jest domkni˛ety na reguł˛e R, dla dowolnego

zbioru Y .

Z powy˙zszego, je´sli α ∈ C

R∪R

0

∪{R}

(X ∪ Y ), to, na mocy punktu (2) twierdzenia

A., α ∈ C

R∪R

0

(X ∪ Y ).

(2). Wynika bezpo´srednio z definicji poj˛e´c reguły dopuszczalnej oraz reguły wypro-
wadzalnej.

(3). Niech R

triv

b˛edzie reguł ˛

a o schemacie

α
α

. Niech R

sub

b˛edzie reguł ˛

a podstawiania

(formuł za zmienne zdaniowe, okre´slon ˛

a w wykładach 5-7). Wtedy:

R

sub

∈ P erm({R

triv

}, {p → p}) − Der({R

triv

}, {p → p}).

Zanotujmy jeszcze, bez dowodów, pewne dalsze fakty dotycz ˛

ace dopuszczalno´sci

oraz wyprowadzalno´sci reguł:

• (4) R ⊆ P erm(R, X).

• (5) P erm(P erm(R, X), X) = P erm(R, X).

4

• (6) Funkcja P erm nie jest finitystyczna wzgl˛edem argumentu X. Nie jest mo-

notoniczna ani wzgl˛edem argumentu R, ani wzgl˛edem argumentu X.

• (7) Der(R, X) =

T{P erm(R

0

, X

0

) : R ⊆ R

0

∧ X ⊆ X

0

}.

• (8) R ⊆ Der(R, X).

• (9) Je´sli R ⊆ R

0

, to Der(R, X) ⊆ Der(R

0

, X).

• (10) Je´sli X ⊆ Y , to Der(R, X) ⊆ Der(R, Y ).

• (11) Der(Der(R, X), X) = Der(R, X).

• (12) Funkcja Der nie jest finitystyczna ani wzgl˛edem argumentu R, ani wzgl˛e-

dem argumentu X.

∗ ∗ ∗

U

WAGA

. Twierdzenia dotycz ˛

ace wielu dalszych własno´sci operatorów i relacji konse-

kwencji w j˛ezykach zdaniowych znale´z´c mo˙zna np. w cytowanych ni˙zej pracach.

W wykładach L

OGIKA

M

ATEMATYCZNA

omówili´smy nast˛epuj ˛

ace tego typu rela-

cje i operacje dla KRZ:

• relacja konsekwencji `

krz

oraz operacja C

krz

, wyznaczone przez aksjomatyk˛e

KRZ i reguł˛e odrywania RO;

• relacja konsekwencji `

B

2

oraz operacja C

B

2

, wyznaczone przez matryc˛e B

2

(tu przez X `

B

2

α rozumiemy, ˙ze α ∈ C

B

2

(X));

• relacja konsekwencji `

jas

oraz operacja C

jas

, wyznaczone przez reguły pier-

wotne systemu zało˙zeniowego KRZ;

• relacja konsekwencji `

rez

oraz operacja C

rez

, wyznaczone przez reguł˛e rezolu-

cji w KRZ;

• relacja konsekwencji `

tab

oraz operacja C

tab

, wyznaczone przez tablice anali-

tyczne dla KRZ.

Pokazali´smy, ˙ze wszystkie te relacje konsekwencji s ˛

a równe:

`

krz

= `

B

2

= `

jas

= `

rez

= `

tab

.

Wszystkie wymienione wy˙zej operacje konsekwencji dla KRZ spełniaj ˛

a warunki

(C1)–(C4) omówione w wykładach 5–7.

∗ ∗ ∗

5

U

WAGA

. Przytoczone wy˙zej szkice dowodów wzorowano na dowodach przedstawio-

nych w cytowanej na wykładzie monografii W.A. Pogorzelskiego: Klasyczny Rachunek
Zda´n. Zarys teorii.

, PWN, Warszawa 1975

3

.

Ogólne własno´sci poj˛ecia konsekwencji przedstawione zostały w pracach Alfreda

Tarskiego:

Tarski, A. 1930. Fundamentale Begriffe der Methodologie der deduktiven Wissen-

schaften. Monatshefte für Mathematik und Physik Bd XXXVII, 361–404.

Tarski, A. 1934. Z bada´n metodologicznych nad definiowalno´sci ˛

a terminów. Prze-

gl ˛

ad Filozoficzny.

37, 438–460. Zob. te˙z: Alfred Tarski: Pisma logiczno-

filozoficzne. Tom 2. Metalogika.

(Redakcja naukowa: Jan Zygmunt), Wydaw-

nictwo Naukowe PWN, Warszawa 2001.

Wymie´nmy kilka dalszych prac o fundamentalnym znaczeniu dla tej problematyki:

Czelakowski, J. 2001. Protoalgebraic logics. Kluwer Academic Publishers, Do-

rdrecht Boston London.

Ło´s, J., Suszko, R. 1956. Remarks on sentential logics. Indagationes Mathematicae

XX, 177–183.

Pogorzelski, W.A., Wojtylak, P. 2008. Elements of the theory of completeness in

propositional logic.

Birkhäuser, Basel Boston Berlin.

Wójcicki, R. 1984. Lectures on propositional calculi. Ossolineum, Wrocław.

∗ ∗ ∗

J

ERZY

P

OGONOWSKI

Zakład Logiki Stosowanej UAM

www.logic.amu.edu.pl

6