Logika 1
dr T. Połacik
2007/2008
Spis treści
1 WYKAAD 1 (11.10.2007) 2
2 WYKAAD 2 (18.10.2007) 5
3 WYKAAD 3 (25.10.2007) 8
4 WYKAAD 4 (08.11.2007) 11
5 WYKAAD 5 (15.11.2007) 14
6 WYKAAD 6 (22.11.2007) 16
7 WYKAAD 7 (29.11.2007) 18
8 WYKAAD 8 (06.12.2007) 21
9 WYKAAD 9 (13.12.2007) 24
10 WYKAAD 10 (20.12.2007) 27
11 WYKAAD 11 (03.01.2008) 29
12 WYKAAD 12 (10.01.2008) 32
13 WYKAAD 13 (17.01.2008) 35
14 WYKAAD 14 (24.01.2008) 38
1
1 WYKAAD 1 (11.10.2007)
Definicja 1.1. Niech Ł = {fi: i " I} będzie zbiorem symboli funkcyjnych o arnościach
#(fi) 0. Ł nazywamy sygnaturą. Algebrą nad sygnaturą Ł (Ł-algebrą) nazywamy
układ:
A =< A, {fiA: i " I} >,
gdzie A jest niepustym zbiorem, a fiA jest #(fi)-argumentową operacją na A dla i " I
(fiA: An - A, n = #(fi)).
Ponadto, typem algebry A nazywamy ciąg =< mi: i " I >, gdzie mi = #(fi).
Przykład 1.2. Niech Ł = {f0, f1, f2, f3, f4}, =< 0, 0, 1, 2, 2 >, A = (2N, {", N, \, )", *"}),
B =< Z, {0, 1, -, , +})
A A A A A
f0 = ", f1 = N, f2 = \, f3 = )", f4 = *"
B B B B B
f0 = 0, f1 = 1, f2 = -, f3 = , f4 = +
Definicja 1.3. Algebry nazywamy podobnymi, gdy mają ten sam typ. Klasę algebr
podobnych sygnatury oznaczamy K().
Definicja 1.4. Sygnatura Ł jest wzbogaceniem sygnatury Ł (Ł jest reduktem Ł ), gdy
Ł " Ł .
Przykład 1.5. Ł = {1, }, Ł = {1, 0, , +}
Definicja 1.6. Niech A, B będą algebrami nad Ł = {fi: i " I}. Powiemy, że B jest
podalgebrą algebry A, gdy:
" B ą" A,
" fiB = fiA|B
Oznaczamy B < A.
Przykład 1.7. Ł = {", *", )"}, =< 0, 2, 2 >
A =< 2N, {", *", )"} >, B =< Fn(N), {", *", )"} >, B < A
Definicja 1.8. Niech A będzie algebrą nad Ł i niech " = X " A. Algebrą generowaną
przez X nazywamy najmniejszą podalgebrę algebry A zawierającą X. Oznaczamy ją
symbolem (X). Mówimy, że A jest generowana przez X, gdy A = (X).
Definicja 1.9. Niech A, B będą algebrami nad Ł = {fi: i " I}. Odwzorowanie : A - B
nazywamy homomorfizmem algebr A, B (piszemy : A - B), gdy dla dowolnego
f " Ł, #(f) = n i dowolnych elementów a1, . . . , an " A mamy:
(fA(a1, . . . , an)) = fB((a1), . . . , (an))
Epimorfizm, monomorfizm, izomorfizm definiujemy jak zwykle.
2
Przykład 1.10. Ł = {f, g}, =< 0, 2 >, A =< {0, 1}", , ć% >
gdzie fA = - słowo puste, gA = ć% - konkatenacja słów
B =< N, 0, + >, gdzie fB = 0, gB = +
Rozważmy : {0, 1}" - N, (s) = |s| - długość słowa s. jest homomorfizmem A, B.
Jest epimorfizmem, ale nie jest monomorfizmem.
Przykład 1.11. C =< R+, 1, >, D =< R, 0, + >, (R+ = {x " R: x > 0})
: R+ - R, (r) = log r
jest izomorfizmem algebr C, D.
Fakt 1.12.
1. Jeżeli : A - B, : B - C są homomorfizmami, to ich złożenie ć% : A - C
jest homomorfizmem.
2. Jeżeli : A - B, to obraz , Im jest podalgebrą algebry B.
3. Niech A = (X), B = (Y ). Wówczas jeśli : A - B odwzorowuje X na Y , to
jest epimorfizmem.
Lemat 1.13. Niech A = (A0) oraz B = (B0). Jeżeli odwzorowanie : A0 - B daje się
przedłużyć do homomorfizmu algebr A i B, to przedłużenie to jest jedyne.
Dowód. Wezmy 1, 2: A - B, X = {a " A: 1(a) = 2(a)}
A0 " X, X jest domknięty na operacje algebry A
1(fA(a1, . . . , an)) = fB(1(a1), . . . , 1(an)) = fB(2(a1), . . . , 2(an)) = 2(fB(a1, . . . , an))
(X) = X " (A0) = A
Zatem X = A. Czyli 1(a) = 2(a) dla wszystkich a " A.
Definicja 1.14. Niech K będzie klasą algebr podobnych (nad Ł). Mówimy, że Ł-algebra
A jest algebrą wolną w klasie K ze zbiorem wolnych generatorów X, gdy:
" A = (X),
" Dla dowolnej algebry B " K i dowolnego odwzorowania : X - B, ma prze-
dłużenie do homomorfizmu algebr A i B.
Definicja 1.15. Mówimy, że A jest algebrą absolutnie wolną, gdy A jest wolna w klasie
wszystkich algebr podobnych do A.
Przykład 1.16. Algebra termów (wielomianów formalnych)
Ustalmy sygnaturę Ł = {fi: i " I}. Niech X = ". X nazywamy zbiorem zmiennych.
Zbiór termów (wielomianów formalnych) nad X, T (X) definiujemy następująco:
" X " T (X),
" dla każdego f " Ł, (#(f) = n) t1, . . . , tn " T (X), wówczas f(t1, . . . , tn) " T (X).
Algebry termów nad X definiujemy jako T (X) =< T (X), {fi: i " I} >
3
Fakt 1.17. T (X) jest algebrą absolutnie wolną.
Lemat 1.18. Niech A, B będą algebrami termów w K o zbiorze wolnych generatorów
<"
odpowiednio A0 i B0. Wówczas jeżeli A0 i B0 są równoliczne, to A B (są izomorficzne).
=
Dowód. ćwiczenie
Definicja 1.19. Niech A będzie Ł-algebrą i niech R " A2 będzie relacją równoważności
na A. R nazywamy kongruencją algebry A, gdy dla każdego f " Ł, #(f) = n,
a1, . . . , an, b1, . . . , bn " A zachodzi warunek:
Jeżeli aiR bi dla i = 1, . . . , n, to fA(a1, . . . , an)R fA(b1, . . . , bn).
Definicja 1.20. Niech A będzie Ł-algebrą dla Ł = {fi: i " I} i niech R będzie kongru-
encją algebry A. Algebrą ilorazową algebry A względem R, A/R nazywamy Ł-algebrę:
R
A/R =< A/R, {fiA/ : i " I} >
gdzie A/R - rodzina klas abstrakcji względem R.
R
fA/ ([a1]R, . . . , [an]R) = fA(a1, . . . , an)
R
Definicja 1.21. Niech A = {At: t " T } będzie rodziną Ł-algebr. Produktem algebr
rodziny A nazywamy Ł-algebrę:
t
At =< At, {fi A : i " I} >
t"T t"T
t t
gdzie f A (< a1 >t"T , . . . , < an >t"T ) =< fA (a1, . . . , an) >t"T
t t t t
Definicja 1.22. Niech K bedzie klasą algebr. Niech T " T (X)T (X) (dla pewnego X).
Definiujemy:
" = {A " K: t =A s, dla (t, s) " T }
gdzie t =A s wtw, gdy dla dowolnego : T (X) - A mamy (t) = (s). Mówimy, że
K jest definiowana równościowo, gdy K = " dla pewnego zbioru równości .
Definicja 1.23. Klasę algebr K nazywamy rozmaitością, gdy K jest domknięta na
obrazy homomorficzne, podalgebry, produkty.
Twierdzenie 1.24 (Birkhoff). Klasa algebr K jest rozmaitością wtedy i tylko wtedy,
gdy K jest definiowalna równościowo.
4
2 WYKAAD 2 (18.10.2007)
Definicja 2.1 (Huntington). Rozważmy sygnaturę Ł = {*", )", -, 0, 1} typu < 2, 2, 1, 0, 0 >.
Algebrą Boole a nazywamy Ł-algebrę:
B =< B, *"B, )"B, -B, 0B, 1B >
spełniającą nastepujące równości:
(H1) x *" y = y *" x; x )" y = y )" x,
(H2) x *" (y *" z) = (x *" y) *" z; x )" (y )" z) = (x )" y) )" z,
(H3) x *" (y )" x) = x; x )" (y *" x) = x,
(H4) x *" (y )" z) = (x *" y) )" (x *" z); x )" (y *" z) = (x )" y) *" (x )" z),
(H5) x *" -x = 1; x )" -x = 0.
Operacje algebry B : *"B, )"B, -B, 0B, 1B, nazywamy odpowiednio sumą (boole owską),
iloczynem (boole owskim), dopełnieniem (boole owskim), zerem i jedynką.
Uwaga. Klasa algebr Boole a jest rozmaitością, w szczególności dowolna podalgebra
algebry Boole a jest algebrą Boole a. Obraz homomorficzny algebry Boole a jest algebrą
Boole a i produkt dowolnej rodziny algebr Boole a jest algebrą Boole a.
Uwaga. A = (Z, 0, +). A jest grupą.
B = (N, 0, +) A. Ale B nie jest podgrupą grupy A.
Przykład 2.2 (algebr Boole a).
1. Dwuelementowa algebra Boole a
B2 =< {0, 1}, *", )", -, 0, 1 >
gdzie x *" y = max(x, y), x )" y = min(x, y)
0, x = 1
- x =
1, x = 0
2. Algebra potęgowa.
Niech X = " będzie dowolnym zbiorem.
P(X) =< 2X, *", )", -, ", X >
Operacje mnogościowe: *", )", -.
Uwaga. Każda skończona algebra Boole a jest homomorficzna z pewną algebrą potęgową.
Przykład 2.3 (Przeliczalna algebra Boole a). Niech X będzie zbiorem przeliczalnym
(nie skończonym). Rozważmy rodzinę podzbiorów zbioru X:
AX = {Y " X : Y jest zbiorem skończonym lub Y jest ko-skończony}
Algebra AX =< AX, *", )", -, ", X > jest algebrą Boole a. Ponadto AX jest zbiorem
przeliczalnym.
5
Twierdzenie 2.4 (Stone). Każda algebra Boole a jest izomorficzna z pewną podalgebrą
algebry potęgowej (dowolna algebra Boole a daje się zanurzyć w algebrze potęgowej).
Przykład 2.5.
3. Ciało zbiorów,
4. Algebra zbiorów regularnych otwartych.
Niech X będzie przestrzenią topologiczną, a RO(X) rodziną zbiorów regularnie
otwartych w X (tzn. A " RO(X), gdy A = int cl (A))
RX = (RO(X), *"R, )"R, -R, 0R, 1R)
gdzie A *"R B = int cl (A *" B); A )"R B = A )" B,
-R A = int (X \ A); 0R = "; 1R = X.
RX jest algebrą Boole a.
Lemat 2.6. W dowolnej algebrze Boole a spełnione są następujące równości:
(1) x *" x = x; x )" x = x,
(2) x *" 0 = x; x )" 1 = x.
Dowód. (1) x )" (x *" x) = x, (H3)
(x *" x) )" x = x )" (x *" x), (H1)
x *" ((x *" x) )" x) = x, (H3)
x *" ((x *" x) )" x) = x *" x. Stąd x *" x = x.
H5 H1 H3
(2) x *" 0 = x *" (x )" -x) = x *" (-x )" x) = x
Analogicznie dowodzimy dualnych równości.
Lemat 2.7. W dowolnej algebrze Boole a mamy:
x *" y = y ! x )" y = x
Dowód. Załóżmy, że x *" y = y. Wtedy x )" y = x )" (x *" y) = x.
Podobnie dowodzimy implikacji odwrotnej.
Definicja 2.8. x y ! x *" y = x ( jest relacją binarną)
Uwaga. W algebrze potęgowej pokrywa się z ą".
Lemat 2.9. W dowolnej algebrze Boole a relacja zdefiniowana jak wyżej jest częścio-
wym porządkiem.
Dowód.
Zwrotność: x x, ponieważ x *" x = x
Słaba antysymetryczność: Załóżmy, że x y i y x, czyli x *" y = y i y *" x = x.
Ale x *" y = y *" x, stad x = y
Przechodniość: Załóżmy, że x y, y z, czyli x *" y = y i y *" z = z
x *" z = x *" (y *" z) = (x *" y) *" z = y *" z = z. Zatem x z
6
Lemat 2.10. Niech B będzie algebrą Boole a. Dowolny skończony podzbiór zbioru B ma
kres w sensie porządku wyznaczonego przez .
Dowód. Wystarczy rozważyć dwuelementowe podzbiory algebry B.
Pokażemy, że inf (a, b) = a )" b, dla dowolnych a, b " B. Zauważmy, że a )" b a, b, gdyż:
(a )" b) )" a = (a )" a) )" b = a )" b
(a )" b) )" b = a )" (b )" b) = a )" b
Niech c a, b. Pokażemy, że c a )" b. Mamy c )" a = c = c )" b.
Zatem c )" (a )" b) = (c )" a) )" b = c )" b = c. Czyli a )" b jest kresem dolnym zbioru {a, b}
wyznaczonym przez .
Wniosek 2.11. Niech B będzie algebrą Boole a. Wtedy (B, ) jest kratą.
Definicja 2.12. Kratę K = (K, ) nazywamy komplementarną gdy:
(1) K zawiera element najmniejszy ( ) i największy ( ),
(2) Dla dowolnego x " K istnieje y " K spełniający warunek:
x (" y = , x '" y =
gdzie (" = sup {x, y}, '" = inf {x, y}
Mówimy, że y jest dopełnieniem x.
Wniosek 2.13. Dowolna algebra Boole a z porządkiem wyznaczonym przez jest kratą
komplementarną i dystrybutywną.
= 0, = 1, (" = *", '" = )", -x jest dopełnieniem x
Własność dystrybutywności jest charakteryzowana przez (H4).
Uwaga. W każdej kracie komplementarnej i dystrybutywnej można zdefiniować struk-
turę algebry Boole a.
7
3 WYKAAD 3 (25.10.2007)
Lemat 3.1. Jeżeli K = (K, ) jest kratą dystrybutywną i komplementarną, to dopeł-
nienia w K są wyznaczone jednoznacznie.
Dowód. Niech x " K oraz niech y, y będą dopełnieniami x. Pokażemy, że y = y . Mamy:
x '" y = , x (" y =
x '" y = , x (" y =
Wtedy y = y (" = y (" (x '" y ) = (y (" x) '" (y (" y ) = '"(y (" y ) = y (" y
To oznacza, że y y . Podobnie dowodzimy, że y y. Zatem y = y .
Wniosek 3.2. W kracie dystrybutywnej i komplementarnej możemy określić operację
dopełnienia.
Wniosek 3.3. Niech K = (K, ) będzie kratą dystrybutywną i komplementarną z
elementem największym i elementem najmniejszym . Wówczas:
BK =< K, *", )", -, 0, 1 >
jest algebrą Boole a, przy czym dla dowolnych a, b " K:
a *" b = sup (a, b) (= a (" b), a )" b = inf (a, b) (= a '" b)
- a = dopełnienie elementu a w K (jedyne), 0 = , 1 =
Definicja 3.4. Niech B będzie algebrą Boole a. Zbiór " = F ą" B nazywamy filtrem
algebry B, gdy:
(1) dla dowolnych a, b " F mamy a )" b " F ,
(2) dla dowolnego a " F i dowolnego b " B, jeżeli a b, to b " F .
Przykład 3.5.
1. B - filtr niewłaściwy,
2. {1},
3. Ustalmy a " B. Wtedy {x " B: x a} jest filtrem. Nazywamy go filtrem głównym
generowanym przez a i oznaczamy [a).
Uwaga. W dowolnej skończonej algebrze Boole a każdy filtr jest główny.
Przykład 3.6.
4. Niech : A - B będzie homomorfizmem algebr Boole a. Wtedy -1({1B}) jest
filtrem algebry A.
Uwaga. Filtr F algebry Boole a B jest filtrem właściwym wtedy i tylko wtedy, gdy 0 " F .
Definicja 3.7. Niech B będzie algebrą Boole a i niech " = X ą" B. Mówimy, że X jest
zbiorem scentrowanym, gdy dla dowolnych a1, . . . , an " X:
a1 )" . . . )" an = 0.
8
Twierdzenie 3.8. Każdy scentrowany podzbiór algebry Boole a jest zawarty w pewnym
filtrze właściwym.
Dowód. Niech " = X ą" B będzie zbiorem scentralizowanym. Rozważmy zbiór:
FX = {b " B: b a1 )" . . . )" an}
dla pewnych a1, . . . , an " X.
Oczywiście X ą" FX. Pokażemy, że FX jest filtrem.
Niech b, c " FX oraz załóżmy, że b a1 )" . . . )" an, c a )" . . . )" a , dla pewnych
1 m
a1, . . . , an, a , . . . , a " X. Mamy:
1 m
b a1 )" . . . an a1 )" . . . )" an )" a )" . . . )" a
1 m
c a )" . . . )" a a1 )" . . . )" an )" a )" . . . )" a
1 m 1 m
Stąd b )" c a1 )" . . . )" an )" a )" . . . )" a . Zatem b )" c " FX.
1 m
Jeżeli b " FX, to b a1 )" . . . )" an, dla pewnych a1, . . . , an " X. Wówczas dla dowolnego
c spełniającego warunek c b mamy c a1 )" . . . )" an, czyli c " FX.
FX jest filtrem właściwym, bo w przeciwnym wypadku mielibyśmy, że 0 " FX, czyli
0 a1 )" . . . )" an, dla pewnych a1, . . . , an " X, co przeczy załóżeniu o skoncentrowaniu
zbioru X.
Definicja 3.9. Filtr F algebry Boole a B nazywamy maksymalnym, gdy F jest elemen-
tem maksymalnym w zbiorze częściowo uporządkowanym (F, ą"), gdzie F jest rodziną
filtrów właściwych algebry B.
Twierdzenie 3.10. Każdy filtr właściwy algebry Boole a jest zawarty w pewnym filtrze
maksymalnym.
Dowód (LKZ). Niech F będzie filtrem właściwym algebry Boole a B. Rozważmy rodzi-
nę:
F = {G ą" B: F ą" G '" G jest filtrem właściwym w B}
Rozważmy (F, ą"). Pokażemy, że każdy łańcuch w (F, ą") ma ograniczenie górne.
Niech L będzie łańcuchem w (F, ą"). Pokażemy, że L " F.
(1) L jest filtrem.
Niech a, b " L. Wtedy a " Ga, b " Gb dla pewnych Ga, Gb " L. Ponieważ L jest
łańcuchem, możemy założyć, że Ga ą" Gb. Wtedy a, b " Gb. Stąd a)"b " Gb ą" L.
Niech a " L i niech a b " B. Wtedy a " G, dla pewnego G " L. Zatem
b " G ą" L.
(2) L jest filtrem właściwym, bo w przeciwnym razie mielibyśmy, że 0 " L, czyli
0 " G, dla pewnego G " L, co jest niemożliwe, bo L zawiera wyłącznie filtry
właściwe.
(3) Oczywiście F ą" G dla każdego G " L, zatem F ą" L.
Stąd L " F. Zatem na mocy Lematu Kuratowskiego-Zorna, w (F, ą") istnieje element
maksymalny.
9
Wniosek 3.11.
1. Każdy zbiór scentrowany algebry Boole a można rozszerzyć do filtru maksymalne-
go.
2. Dla każdego a = 0 algebry Boole a istnieje filtr maksymalny F , taki że a " F .
3. Niech a, b " B oraz a = b. Wtedy istnieje filtr maksymalny F , taki że:
(a " F '" b " F ) lub (a " F '" b " F )
10
4 WYKAAD 4 (08.11.2007)
Lemat 4.1. W dowolnej algebrze Boole a mamy:
(1) x *" 0 = x,
(2) x )" 1 = x,
(3) -(x )" y) = -x *" -y.
Dowód. (1),(2) oczywiste, (3) ćwiczenie
Twierdzenie 4.2. Niech F będzie filtrem w algebrze Boole a B. Wówczas relacja <"F
zdefiniowana następująco:
a <"F b ! "x"F a )" x = b )" x
jest kongruencją algebry B.
Dowód. Ustalmy dowolną algebrę Boole a B i jej filtr F . <"F jest relacją równoważności.
Zwrotność i symetria są oczywiste. Przechodniość:
Załóżmy, że a <"F b i b <"F c, czyli a )" x = b )" x oraz b )" y = c )" y dla pewnych x, y " F .
Mamy:
x )" y " F , ponadto a )" (x )" y) = b )" x )" y = b )" y )" x = c )" y )" x = c )" (x )" y) co
dowodzi, że a <"F c.
Załóżmy teraz, że a <"F a i b <"F b , czyli a )" x = a )" x i b )" y = b )" y dla pewnych
x, y " F . Pokażemy, że (a *" b) <"F (a *" b ). Rozważmy x )" y " F . Mamy:
(a *" b) )" (x )" y) = (a )" x )" y) *" (b )" x )" y) = (a )" x )" y) *" (b )" x )" y) = (a *" b ) )" (x )" y).
Podobnie pokazujemy, że (a )" b) <"F (a )" b ).
Pokażemy, że -a <"F -a . Z założenia a )" x = a )" x ! -(a )" x) = -(a )" x). Stąd na
mocy punktu (3) poprzedniego lematu:
-a *" -x = -a *" -x ! (-a *" -x) )" x = (-a *" -x) )" x ! -a )" x = -a )" x.
Twierdzenie 4.3. Niech <" będzie kongruencją algebry Boole a B. Wówczas:
F = {a " B: a <" 1}
jest filtrem algebry B. Ponadto, <"F =<".
Dowód. ćwiczenie
Definicja 4.4. Niech F będzie filtrem algebry Boole a B (kraty). Mówimy, że F jest
filtrem pierwszym, gdy dla dowolnych elementów a, b " B, jeżeli a *" b " F , to a " F lub
b " F .
11
Twierdzenie 4.5. Niech B będzie algebrą Boole a i niech F będzie filtrem właściwym
algebry B. Wówczas następujące warunki są równoważne:
(1) F jest maksymalny,
(2) F jest pierwszy,
(3) Dla dowolnego a " B mamy, że a " F lub -a " F ,
(4) B/F <" B2 (B2 jest dwuelementową algebrą Boole a).
=
Dowód.
(1) ! (2). Załóżmy, że F jest maksymalny i przypuśćmy, że dla pewnych a, b " B
mamy: a *" b " F, a " F, b " F .
Rozważmy zbiór G = {x " B: x a )" f, dla pewnego f " F }. G jest filtrem.
Wezmy x, y " G. Wtedy x a )" f i y a )" g, f, g " F .
Stąd x a )" f )" g, y a )" f )" g ! inf{x, y} a )" f )" g ! x )" y " G.
Jeżeli x " G ! x a )" f ! y x a )" f, f " F . Stąd y " G.
Zauważmy, że F G, gdyż a " G \ F . Pokażemy, że b " G. Przypuśćmy, że b " G,
wtedy dla pewnego f " F mamy b a )" f. Mamy:
b = (a )" f) *" b = (a *" b) )" (f *" b) " F - sprzeczność. Zatem G jest filtrem właściwym
rozszerzającym F . Sprzeczność z maksymalnością filtru F .
(2) ! (3). Załóżmy, że F jest filtrem pierwszym. Niech a będzie dowolnym elementem
algebry B. Oczywiście 1 " F , z drugiej strony 1 = a *" -a. Zatem a *" -a " F . Stąd na
mocy założenia a " F lub -a " F .
(3) ! (4). Rozważmy algebrę ilorazową B/F .
[1]F = {x " B: x )" f = 1 )" f, dla pewnego f " F } = F
[0]F = {x " B: x )" f = 0 )" f, dla pewnego f " F } = {-x: x " F }
Niech teraz a " B. Na mocy (3) mamy, że a " F albo -a " F . Zatem [a]F = [1]F albo
[a]F = [0]F , czyli B/F <" B2.
=
(4) ! (1). Przypuśćmy, że F nie jest maksymalny i niech G będzie filtrem właściwym
rozszerzającym F . Niech ponadto a " G \ F .
[a]F = [1]F , bo a " F . [a]F = [0]F , bo w przeciwnym wypadku mielibyśmy -a " F ą" G
co przeczy założeniu, że G jest filtrem właściwym.
Zatem B/F nie może być izomorficzny z B2.
Uwaga. W przypadku algebry Boole a filtr właściwy F spełniający którykolwiek z wa-
runków poprzedniego twierdzenia nazywamy ultrafiltrem.
12
Twierdzenie 4.6 (Stone a o reprezentacji algebry Boole a). Dowolna algebra Boole a
jest izomorficzna z pewną podalgebrą algebry potęgowej.
Dowód. Rozważmy algebrę Boole a B. Rozważmy zbiór:
Ult (B) = {F ą" B: F jest ultrafiltrem algebry B}
Algebrą Stone a nazywamy algebrę potęgową 2Ult (B).
Rozważmy odwzorowanie s: B - 2Ult (B) zdefiniowane nastepująco:
s(a) = {F " Ult (B): a " F }
Odwzorowanie s jest różnowartościowe:
Niech a = b. Wówczas istnieje F " Ult (B) taki, że a " F i b " F lub na odwrót. Zatem
s(a) = s(b).
Odwzorowanie s jest homomorfizmem algebr Boole a:
s(0) = {F " Ult (B): 0 " F } = "
s(1) = {F " Ult (B): 1 " F } = Ult (B)
s(a *" b) = {F " Ult (B): a *" b " F } = {F " Ult (B): a " F } *" {F " Ult (B): b " F } =
s(a) *" s(b)
s(a )" b) = {F " Ult (B): a )" b " F } = {F " Ult (B): a " F } )" {F " Ult (B): b " F } =
s(a) )" s(b)
s(-a) = {F " Ult (B): -a " F } = {F " Ult (B): a " F } = -s(a).
Zatem s jest monomorfizmem algebr Boole a.
13
5 WYKAAD 5 (15.11.2007)
LOGIKA ZDAC
Język logiki zdań L0 wyznaczony jest przez:
" zbiór zmiennych zdaniowych: p0, p1, p2, . . . (lub p, q, r, . . .), zbiór zmiennych zda-
niowych oznaczać będziemy przez P ,
" spójniki zdaniowe: Ź, '", (", (negacja, koniunkcja, alternatywa, implikacja),
" ( , ) (nawias lewy i prawy).
Definicja 5.1. Zbiorem formuł zdaniowych języka L0 nazywamy zbiór L0 spełniający
następujące warunki:
(1) P ą" L0,
(2) Jeżeli A, B " L0, to ŹA, (A '" B), (A (" B), (A B) " L0.
Uwaga. p0 " L0, (p0 '" p2) " L0, (p0 (p0 '" p2)) " L0, Ź(p0 (p0 '" p2)) " L0
Uwaga. Litery A i B w powyższej definicji nie są formułami języka L0, są nazwami
formuł (zmienne metasystemowe).
Będziemy pisać A(p0, . . . , pn) gdy zmienne zdaniowe występujące w formule A stanowią
podzbiór zbioru {p0, . . . , pn}.
Zbiór formuł L0 języka L0 jest przeliczalny.
Definicja 5.2 (Algebra języka). Rozważmy zbiór formuł L0 języka L0 i operacje okre-
ślone na tym zbiorze w następujący sposób:
Neg: L0 - L0, Neg(A) = ŹA
Alt: L0 L0 - L0, Alt(A, B) = (A (" B)
Kon: L0 L0 - L0, Kon(A, B) = (A '" B)
Imp: L0 L0 - L0, Imp(A, B) = (A B)
Wówczas
A(L0) =< L0, Neg, Alt, Kon, Imp >
nazywamy algebrą języka L0. Dla uproszczenia operacje Neg, Alt, Kon, Imp algebry
A(L0) oznaczać będziemy odpowiednio symbolami Ź, (", '", .
Algebra A(L0) jest algebrą absolutnie wolną ze zbiorem P jako zbiorem jej wolnych
generatorów.
Definicja 5.3. Matrycę logiczną dla języka L0 nazywamy układ:
M = (M, M")
gdzie M jest algebrą podobną do algebry A(L0) oraz " = M" ą" M. Zbiór M" na-
zywamy zbiorem wartości wyróżnionych matrycy. Najczęściej zakłada się, że M" jest
jednoelementowy.
Matrycę M będziemy również przedstawiać w postaci:
M = (M, M", FŹ, F'", F(", F)
14
Definicja 5.4. Ustalmy matrycę M języka L0. Wartościowaniem w matrycy M nazy-
wamy dowolne odwzorowanie : P - M. Ponieważ algebra języka A(L0) jest algebrą
absolutnie wolną ze zbiorem wolnych generatorów M, wartościowanie przedłuża się
(jednoznacznie) na zbiór L0 wszystkich formuł.
Definicja 5.5. Ustalmy matrycę M = (M, M") i wartościowanie : P - M. Mówimy,
że formuła A jest spełniona przez wartościowanie , gdy (A) " M".
Formułę A nazywamy tautologią, gdy formuła A jest spełniona przez każde wartościo-
wanie : P - M (mówimy, że A jest prawdziwa w M ).
Zbiór wszystkich tautologii matrycy M nazywamy zawartością matrycy i oznaczamy
przez E(M).
Uwaga. Algebra Boole a jako algebra podobna do algebry A(L0) (typu < 1, 2, 2, 2 >).
W dowolnej algebrze Boole a
B = (B, -, *", )", 0, 1)
definiujemy dla dowolnych a, b " B: a ! b = -a *" b
! jest operacją algebry B.
Algebrę B możemy uważać za algebrę postaci: (B, -, *", )", !), 0 = a )" -a, 1 = a *" -a.
Przykład 5.6 (Matryce języka L0).
1. M = (B, {1}), gdzie B jest dowolną agebrą Boole a.
2. M2 = (B2, {1}), B2 jest dwuelementową algebrą Boole a. M2 jest izomorficzna z
następującą matrycą:
({0, 1}, {1}, FŹ, F'", F(", F)
FŹ(x) = 1-x, F'"(x, y) = min(x, y), F("(x, y) = max(x, y), F = min(1, 1-x+y).
Operacje tej algebry możemy przedstawić w postaci tabel:
x, y F'"(x, y) F("(x, y) F(x, y)
x FŹ(x) 0, 0 0 0 1
0 1 0, 1 0 1 1
1 0 1, 0 0 1 0
1, 1 1 1 1
M2 będziemy nazywać matrycą dwuelementową lub matrycą klasycznej logiki
zdań.
1
3. M3 = ({0, , 1}, {1}, FŹ, F'", F(", F)
2
gdzie FŹ, F'", F(", F są określone jak w M2 (Aukasiewicz).
4. MT = (O(R), {R}, GŹ, G'", G(", G)
GŹ(X) = int (R \ X), G'"(X, Y ) = X )" Y, G("(X, Y ) = X *" Y,
G(X, Y ) = int ((R \ X) *" Y ),
O(R) - rodzina wszystkich otwartych podzbiorów R.
15
6 WYKAAD 6 (22.11.2007)
Uwaga. Niech A = A(p1, . . . , pn) " L0 i niech M będzie matrycą dla języka logiki
zdań. Wówczas dla dowolnych wartościowań , : P - M takich, że (pi) = (pi) dla
i = 1, . . . , n mamy (A) = (A).
(A B) = F((A), (B)) = F((A), (B)) = (A B)
Fakt 6.1.
(1) p (p (" q) " E(M2) )" E(M3) )" E(MT ),
(2) p (" Źp " E(M2) \ E(M3) \ E(MT ),
(3) (p '" Źp) q " E(M2) )" E(MT ) \ E(M3),
(4) Ź(p '" q) (Źp (" Źq) " E(M2) )" E(M3) \ E(MT ),
(5) p q " E(M2) *" E(M3) *" E(MT ).
E(M) utożsamiamy z klasyczną logiką zdań.
Od tej pory rozważać będziemy klasyczną logikę zdań.
Definicja 6.2. Zbiór formuł Ł nazywamy spełnialnym, gdy istnieje wartościowanie
takie, że (A) = 1 dla wszystkich A " Ł.
Mówimy, że zbiór Ł jest skończenie spełnialny, gdy każdy skończony podzbiór Ł jest
spełnialny.
Lemat 6.3. Niech Ł będzie zbiorem skończenie spełnialnym. Wówczas Ł jest maksy-
malnym zbiorem skończenie spełnialnym wtedy i tylko wtedy, gdy dla dowolnej formuły
A mamy:
A " Ł albo ŹA " Ł
Dowód.
(!) Załóżmy, że Ł jest maksymalnym zbiorem skończenie spełnialnym i przypuśćmy,
że istnieje A, że A " Ł i ŹA " Ł. Rozważmy zbiory Ł *" {A} oraz Ł *" {ŹA}. Ponieważ
Ł jest maksymalnym zbiorem skończenie spełnialnym, zbiory te nie są skończenie speł-
nialne. Niech więc Ł1, Ł2 będą skończonymi podzbiorami zbioru Ł takimi, że Ł1 *" {A}
i Ł2 *" {ŹA} są niespełnialne. Ponieważ Ł jest zbiorem skończenie spełnialnym, więc
Ł1*"Ł2 jest zbiorem spełnialnym. Niech będzie wartościowaniem spełniającym Ł1*"Ł2.
Mamy: (A) = 0 = (ŹA) - sprzeczność.
(!) Korzystamy z faktu, że zbiór {A, ŹA} nie jest spełnialny.
Lemat 6.4. Każdy maksymalny zbiór skończenie spełnialny jest spełnialny.
Dowód. Załóżmy, że Ł jest maksymalnym zbiorem skończenie spełnialnym. Wówczas:
(1) A " Ł ! ŹA " Ł,
(2) A B " Ł ! A " Ł lub B " Ł,
16
(3) A (" B " Ł ! A " Ł lub B " Ł,
(4) A '" B " Ł ! A " Ł oraz B " Ł.
(1) Oczywista z poprzedniego lematu,
(2) Załóżmy, że A B " Ł i przypuśćmy, że A " Ł oraz B " Ł. Wówczas ŹB " Ł.
Mamy zatem Ł0 = {A B, A, ŹB} ą" Ł, ale Ł0 nie jest spełnialny - sprzeczność.
Załóżmy, że A " Ł, B " Ł i przypuśćmy, że A B " Ł.
Wtedy Ł1 = {ŹA, B, Ź(A B)} ą" Ł. Ale Ł1 nie jest spełnialny - sprzeczność.
Podobnie dowodzimy warunki (3),(4).
Definiujemy wartościowanie :
(p) = 1 ! p " Ł
Korzystając z warunków (1)-(4) pokazujemy, że (A) = 1 ! A " Ł, dla dowolnej
formuły A. Zatem spełnia Ł.
Twierdzenie 6.5 (o zwartości). Każdy zbiór skończenie spełnialny jest spełnialny.
Dowód. Niech Ł będzie zbiorem skończenie spełnialnym. Konstruujemy zbiór Ł" taki,
że Ł ą" Ł" oraz Ł" jest maksymalnym zbiorem skończenie spełnialnym. Ustalmy ciąg
wszystkich formuł języka L0: A0, A1, A2, . . .
Definiujemy łańcuch zbiorów Łi, i " N0:
Łi *" {Ai}, jeśli zbiór Ai jest spełnialny,
Ł0 = Ł, Łi+1 =
Łi *" {ŹAi}, jeśli zbiór ŹAi jest spełnialny.
Zauważmy, że Łi jest skończenie spełnialny dla wszystkich i " N0.
Dowód indukcyjny:
Dla i = 0 - oczywiste.
Załóżmy, że Łi jest skończenie spełnialny. Pokażemy, że nie jest możliwe, aby żaden ze
zbiorów Łi *"{Ai}, Łi *"{ŹAi} nie był skończenie spełnialny. Gdyby tak było, to istniały
by zbiory skończone Ł , Ł " Łi takie, że Ł *" {Ai}, Ł *" {ŹAi} byłyby niespełnialne,
i i i i
ale ponieważ Ł *" Ł jest skończonym podzbiorem zbioru Łi, który jest skończenie
i i
spełnialny, przypuszczenie to pociąga, że dla spełniającego Ł *" Ł mielibyśmy, że
i i
(Ai) = 0 = (ŹAi) co jest niemożliwe.
Niech Ł" = Łi.
i"N0
Ł" jest skończenie spełnialny, gdyż Łi są skończenie spełnialne dla każdego i " N0.
Ł" jest maksymalnym zbiorem skończenie spełnialnym, gdyż na mocy jego konstrukcji
dla każdej formuły A, A " Ł" albo ŹA " Ł". Zatem Ł" jest zbiorem spełnialnym.
W szczególności Ł jest spełnialny, bo Ł ą" Ł".
17
7 WYKAAD 7 (29.11.2007)
Definicja 7.1. Ustalmy język L i zbiór formuł L tego języka. Relację " = r ą" 2L L
nazywamy regułą, gdy istnieje taka liczba n " N, że dla dowolnych ą" 2L i A " L,
jeśli < , A >" r, to card = r.
Zbiór nazywamy zbiorem przesłanek, a formułę A wnioskiem reguły r =< , A >.
A1,...,An
Zwyczajowo regułę r =< , A > zapisujemy , gdzie = {A1, . . . , An}.
A
Przykład 7.2.
A,B
(1) < {A, B}, C >" rmn ! C = A '" B, ,
A'"B
B'"C
(2) < {A}, B >" rop ! istnieje formuła C " L taka, że A = B '" C, ,
B
r = {< {B '" C}, B >: B, C " L},
(3) Reguła odrywania
BC,B
< {A, B}, C >" ro ! A = B C ,
C
(4) Reguła podstawiania
Niech : P - L. Odwzorowanie przedłuża się (jednoznacznie) do endomorfi-
zmu algebry języka A(L).
< {A}, B >" r" ! istnieje : P - L takie, że B = (A)
Niech A = A(p1, . . . , pn). Zauważmy, że < {A}, B >" r" ! istnieją formuły
C1, . . . , Cn " L takie, że B = A(p1/C1, . . . , pn/Cn), gdzie A(p1/C1, . . . , pn/Cn) po-
wstaje z A(p1, . . . , pn) w wyniku jednoczesnego podstawienia formuł Ci za zmienną
pi dla i = 1, . . . , n.
Na przykład, niech A = A(p, q, r) = (p (q (p '" r))) oraz niech
B = r Źp, C = q (" Źs, D = s (" q. Wówczas:
A(p/B, q/C, r/D) = ((r Źp) (q (" Źs) ((r Źq) '" (s (" q)))
Definicja 7.3. Systemem aksjomatycznym nazywamy parę S = (Ax, R), gdzie Ax ą" L
są aksjomatami, a R jest zbiorem reguł.
Definicja 7.4. Ustalmy system aksjomatyczny S = (Ax, R). Dowodem (derywacją) w
systemie S formuły A na gruncie zbioru formuł nazywamy skończony ciąg formuł
A1, A2, . . . , An taki, że An = A oraz dla każdego 1 i n:
" Ai " Ax *"
albo
" istnieje ą" {A1, . . . , Ai-1} oraz r " R takie, że < , Ai >" r.
Formułę A nazywamy dowodliwą w S na gruncie , gdy istnieje dowód A w S na gruncie
, fakt ten zapisujemy symbolicznie w następujący sposób:
S A
Ponadto, gdy zbiór = " piszemy S A i mówimy, że A jest tezą systemu S.
18
Lemat 7.5. Niech S będzie systemem aksjomatycznym i niech ", ą" L, A, B " L.
Wtedy:
(1) Jeżeli A " , to S A.
(2) Jeżeli S A oraz ą" , to S A.
(3) Jeżeli " S B dla każdej formuły B " oraz S A, to " S A.
(4) S A wtedy i tylko wtedy, gdy istnieje skończony zbiór ą" taki, że S A.
Definicja 7.6. Zbiór formuł jest niesprzeczny, gdy istnieje formuła A taka, że S A.
W przeciwnym wypadku mówimy, że zbiór jest sprzeczny (czyli wówczas, gdy S B,
dla dowolnej formuły B).
System S jest sprzeczny, gdy każda formuła jest tezą tego systemu.
Definicja 7.7. Odwzorowanie C: 2L - 2L nazywamy operatorem konsekwencji (ope-
ratorem logicznego domknięcia), gdy C spełnia następujące warunki:
(i) ą" C(),
(ii) ą" , to C() ą" C( ),
(iii) C(C()) = C().
Ponadto, gdy spełniony jest warunek:
(iv) C() = {C( ): jest skończonym podzbiorem }.
to C nazywamy finitarnym operatorem konsekwencji.
Uwaga. Ustalmy system aksjomatyczny S. Definiujemy odwzorowanie CS: 2L - 2L w
następujący sposób:
CS() = {A " L: S A}
Wówczas CS jest finitarnym operatorem konsekwencji.
Semantyka Syntaktyka
wartościowanie dowód/derywacja
spełnialność niesprzeczność
niespełnialność sprzeczność
tautologia teza
19
KLASYCZNY RACHUNEK ZDAC (KRZ)
Język, pojęcie formuły pozostają bez zmian. Definiujemy system aksjomatyczny KRZ:
" Jako zbiór aksjomatów AXKRZ przyjmujemy zbiór wszystkich formuł postaci:
(A1) A (B A), prawo symplifikacji,
(A2) (A (B C)) ((A B) (A C)), sylogizm Fregego,
(A3) (A '" B) A,
(A4) (A '" B) B,
(A5) (A B) ((A C) (A (B '" C))),
(A6) A (A (" B),
(A7) B (A (" B),
(A8) (B A) ((C A) ((B (" C) A)),
(A9) ŹA (A B), prawo przepełnienia,
(A10) (A ŹA) ŹA, prawo redukcji do absurdu,
(A11) ŹŹA A, (mocne) prawo podwójnego przeczenia.
A,AB
" Jedyną regułą KRZ jest reguła odrywania . (Będziemy pisać zamiast KRZ).
B
Przyjmijmy definicje: A "! B := (A B) '" (B A).
Uwaga. Każdy aksjomat KRZ jest tautologią matrycy M2.
Zbiór tautologii matrycy M2 jest domkniety na regułę odrywania, to znaczy:
Jeżeli A B, A " E(M2), to również B " E(M2).
Zatem każda teza KRZ jest tautologią.
20
8 WYKAAD 8 (06.12.2007)
Lemat 8.1.
p p
Dowód. Skorzystajmy z aksjomatu (A2):
(A (B C)) ((A B) (A C)) i wykonajmy podstawienie:
A/p, B/p p, C/p
1. p ((p p) p) ((p (p p)) (p p))
2. p ((p p) p)
Podstawmy: A/p, B/p p i skorzystajmy z aksjomatu (A1):
(A (B A))
3. (p (p p)) (p p), RO(1, 2)
4. p (p p), (A1), A/p, B/p
5. p p, RO(3, 4)
Ciąg formuł 1-5 jest derywacją formuły p p. Zatem p p.
Wniosek 8.2. A A, gdzie A jest dowolną formułą.
Twierdzenie 8.3 (o dedukcji). Dla dowolnego zbioru formuł i dowolnych formuł A i
B mamy:
A B wtedy i tylko wtedy, gdy , A B
Dowód.
(!) Załóżmy, że C1, C2, . . . , Cn = A B jest derywacją A B na gruncie . Wtedy
C1, C2, . . . , A B, A, B jest derywcją formuły B na gruncie *" {A}.
Cn
(!) Załóżmy, że , A B i niech C1, C2, . . . , Cn = B będzie derywacją B na gruncie
*" {A}. Pokażemy indukcyjnie, że A Ci dla i = 1, . . . , n.
Baza indukcji: i = 1
Formuła C1 jest albo aksjomatem albo C1 " albo C1 = A. W pierwszych dwóch przy-
padkach mamy C1 (A C1) (A1), a więc C1, skąd A C1.
Gdy C1 = A, mamy A C1 na mocy lematu. Zatem A C1.
Krok indukcyjny: załóżmy, że A Ci, i < k
Pokażemy, że A Ck. Jeśli Ck " Ax *" *" {A}, to postępujemy jak w bazie in-
dukcji. Niech więc dla pewnych j, l < k: Cl = Cj Ck i załóżmy, że Ck znajduje się w
ciągu dowodowym dzięki zastosowaniu reguły odrywania do formuł Cj i Cl. Z założenia
indukcyjnego A Cl, więc A (Cj Ck).
Mamy (A (Cj Ck)) ((A Cj) (A Ck)) jako szczególny przy-
padek aksjomatu (A2). Stąd poprzez dwukrotne zastosowanie RO (reguły odrywania)
A Ck. Zatem A Ci dla wszystkich i = 1, . . . , n. W szczególności, w
przypadku gdy i = n otrzymujemy A B gdyż z założenia Cn = B.
21
Przykład 8.4. Ponieważ A B, B C, A C, na mocy twierdzenia o dedukcji
otrzymujemy:
A B, B C A C
A B (B C) (A C)
(A B) ((B C) (A C)) - prawo sylogizmu hipotetycznego
Przykład 8.5. A (B C), B, A C. Stąd:
(A (B C)) (B (A C)) - prawo wewnętrznego odrywania
Definicja 8.6. Regułę r będziemy nazywać wyprowadzalną w pewnym systemie aksjo-
matycznym S, gdy dla dowolnych , A:
Jeżeli < , A >" r, to S A
Regułę r nazywamy dopuszczalną w S, gdy dla dowolnych , A mamy:
Jeżeli < , A >" r oraz S , to S A
(gdzie S oznacza dowodliwość S B dla wszystkich formuł B " ).
Wniosek 8.7. Następujące reguły są wyprowadzalne w KRZ:
A B, B C A (B C), B
,
A C A C
Lemat 8.8.
A '" B wtedy i tylko wtedy, gdy A oraz B
A,B
Wniosek 8.9. jest regułą wyprowadzalną w KRZ. Wystarczy przyjąć w lema-
A'"B
cie 8.8, = {A, B}.
Lemat 8.10. Zbiór formuł Ł jest sprzeczny wtedy i tylko wtedy, gdy istnieje formuła A
taka, że Ł A '" ŹA (co jest równoważne Ł A oraz Ł ŹA).
Lemat 8.11.
, A '" B C wtedy i tylko wtedy, gdy , A, B C
W szczególności zbiór *" {A '" B} jest zbiorem sprzecznym wtedy i tylko wtedy, gdy
*" {A, B} jest sprzeczny.
Lemat 8.12.
, A (" B C wtedy i tylko wtedy, gdy , A C oraz , B C
W szczególności *"{A("B} jest sprzeczny wtedy i tylko wtedy, gdy *"{A} oraz *"{B}
są sprzeczne.
Lemat 8.13.
ŹA wtedy i tylko wtedy, gdy *" {A} jest sprzeczny
Lemat 8.14.
A wtedy i tylko wtedy, gdy *" {ŹA} jest sprzeczny
22
Uwaga. Twierdzenie o dedukcji wraz z lematami 8.8 8.14 charakteryzuje KRZ.
Dowód lematu 8.8. Załóżmy, że A '" B. Na mocy aksjomatów (A3),(A4) mamy:
(A '" B) A oraz (A '" B) B
Zatem A oraz B.
Załóżmy, że A oraz B. Mamy z (A5) (A A) ((A B) (A (A'"B)))
oraz A A. Stąd (A B) (A (A '" B)). Czyli A, A B A '" B. Z drugiej
strony A oraz B. Zatem A '" B.
Dowód lematu 8.10. Załóżmy, że Ł jest sprzeczny. Wtedy w szczególności Ł A '" ŹA.
Załóżmy teraz, że dla pewnej formuły A mamy Ł A '" ŹA. Zatem Ł A oraz Ł ŹA.
Ponadto ŹA (A B) (A5). Zatem ŹA, A B. Czyli Ł B, gdzie B jest dowolną
formułą, co oznacza sprzeczność zbioru Ł.
Dowód lematu 8.11. Załóżmy, że , A '" B C. Dzięki regule mnożenia mamy w szcze-
gólności A, B A '" B. Stąd , A, B C.
Niech , A, B C. Zauważmy, że (A'"B) A (A3) oraz (A'"B) B (A4). Zatem
A '" B A, A '" B B. Stąd , A '" B C.
Dowód lematu 8.12. (ćwiczenie)
Dowód lematu 8.13. Załóżmy, że ŹA. Ponadto z (A5) ŹA (A B). Zatem
ŹA, A B. Czyli , A B, co oznacza sprzeczność zbioru *" {A} wobec dowolności
formuły B.
Załóżmy, że *" {A} jest zbiorem sprzecznym. W szczególności , A Ź A czyli
A Ź A. Mamy ponadto (A ŹA) ŹA (A10). Stąd ŹA.
Dowód lematu 8.14. (ćwiczenie)
23
9 WYKAAD 9 (13.12.2007)
Lemat 9.1. Tezami KRZ są formuły postaci:
(a) (ŹA '" ŹB) "! Ź(A (" B),
(b) Ź(A '" B) "! (ŹA (" ŹB), prawa de Morgana,
(c) Ź(A '" ŹA), prawo sprzeczności,
(d) A (" ŹA, prawo wyłączonego środka,
(e) (A B) "! (ŹA (" B),
(f) (A '" (B (" C)) "! ((A '" B) (" (A '" C)).
Dowód.
(a) Pokażemy, że (ŹA '" ŹB) Ź(A (" B). Zauważmy, że następujące warunki są
równoważne:
1. (ŹA '" ŹB) Ź(A (" B),
2. ŹA '" ŹB Ź(A (" B), twierdzenie o dedukcji,
3. {ŹA '" ŹB, A (" B} jest sprzeczny, (lemat 8.13),
4. {ŹA '" ŹB, A} oraz {ŹA '" ŹB, B} są sprzeczne, (lemat 8.12),
5. {ŹA, ŹB, A} oraz {ŹA, ŹB, B} są sprzeczne, (lemat 8.11).
Zatem w celu wykazania, że (ŹA '" ŹB) Ź(A (" B) wystarczy pokazać, że zbiory
{ŹA, ŹB, A} oraz {ŹA, ŹB, B} są sprzeczne. Zauważmy jednak, że {ŹA, ŹB, A} A
oraz {ŹA, ŹB, A} ŹA, a także {ŹA, ŹB, B} B oraz {ŹA, ŹB, B} B co na mocy
lematu 8.10 oznacza sprzeczność obu zbiorów.
Pokażemy teraz, że Ź(A (" B) (ŹA '" ŹB). Zauważmy, że na mocy twierdzenia o
dedukcji i lematu 8.8 warunek Ź(A (" B) (ŹA '" ŹB) równoważny jest koniunkcji
warunków:
(1) Ź(A (" B) ŹA, (2) Ź(A (" B) ŹB.
Ponadto (1) równoważny jest na mocy lematu 8.13:
(3) {Ź(A (" B), A} jest sprzeczny,
oraz (2) równoważny jest warunkowi:
(4) {Ź(A (" B), B} jest sprzeczny.
Na mocy lematu 8.14, (3) i (4) równoważne są warunkom:
(5) A A (" B, (6) B A (" B.
Zauważmy jednak, że warunki (5), (6) wynikają dzięki twierdzeniu o dedukcji z faktu,
że formuły A A (" B, B A (" B są aksjomatami KRZ.
Pokazaliśym, że (ŹA '" ŹB) Ź(A (" B) oraz Ź(A (" B) (ŹA '" ŹB), to na mocy
lematu 8.8 otrzymujemy (ŹA '" ŹB) "! Ź(A (" B)
(b) (f) ćwiczenie
24
Rozważmy relację <" na zbiorze formuł KRZ:
A <" B wtedy i tylko wtedy, gdy A "! B
Relacja <" jest relacją równoważności.
Niech L0 będzie zbiorem formuł KRZ. Rozważmy zbiór L0/<" klas abstrakcji względem
relacji <":
L0/<" = {[A]<": A " L0}
Na L0/<" definiujemy relację :
[A]<" [B]<" wtedy i tylko wtedy, gdy A B
Zauważmy, że jeśli [A]<" [B]<" oraz A " [A]<" i B " [B]<", to A B .
Mamy A B oraz A A i B B . Korzystając z prawa sylogizmu hipote-
tycznego dostajemy A B . Dowodzi to poprawności definicji relacji .
Twierdzenie 9.2.
< L0/<", > jest kratą boole owską
Dowód. Pokażemy, że < L0/<", > jest kratą.
Zwrotność : [A]<" [A]<", gdyż A A.
Słaba antysymetryczność: jeżeli [A]<" [B]<" oraz [B]<" [A]<", to A B oraz
B A. Zatem A "! B, czyli [A]<" = [B]<".
Przechodniość: wynika z prawa sylogizmu hipotetycznego.
Pokażemy, że inf {[A]<", [B]<"} = [A '" B]<".
Na mocy aksjomatów (A3), (A4) mamy: A '" B A, A '" B B.
Zatem [A'"B]<" [A]<", [B]<". Czyli [A'"B]<" jest ograniczeniem dolnym zbioru {[A]<", [B]<"}.
Niech [C]<" [A]<", [B]<". Mamy wtedy: C A oraz C B. Ponadto na mocy
(A5) (C A) ((C B) (C (A '" B)). Zatem korzystając z twierdzenia o
dedukcji C A, C B C (A '" B). Stąd wobec założenia C A i C B
otrzymujemy, że C (A '" B) co oznacza [C]<" [A '" B]<". Zatem [A '" B]<" jest
największym ograniczeniem dolnym zbioru {[A]<", [B]<"}.
Analogicznie dowodzimy, że sup {[A]<", [B]<"} = [A (" B]<".
Zatem < L0/<", > jest kratą.
Zauważmy, że < L0/<", > jest kratą dystrybutywną, gdyż:
(A '" (B (" C)) "! ((A '" B) (" (A '" C))
Pokażemy, że < L0/<", > jest kratą komplementarną.
[B]<" [A]<" dla każdego B " L0 wtedy i tylko wtedy, gdy A. Załóżmy, że A i niech
B będzie dowolną formułą. Na mocy (A1) mamy A (B A). Stąd B A.
Czyli [B]<" [A]<".
Załóżmy teraz, że [B]<" [A]<" dla dowolnego B " L0. W szczególności możemy rozważyć
taką formułę B, że B. Mamy więc B A oraz B skąd A.
25
Pokażemy teraz, że [A]<" [B]<" dla dowolnego B " L0 wtedy i tylko wtedy, gdy ŹA.
Załóżmy, że ŹA. Na mocy (A9) ŹA (A B). Zatem A B dla dowolnej
formuły B. Czyli [A]<" [B]<".
Załóżmy, że [A]<" [B]<" dla dowolnego B " L0. Wówczas, w szczególności dla B = ŹA
mamy A ŹA. Na mocy (A10) (A ŹA) ŹA. Zatem ŹA.
Oznaczmy przez 1 element największy, a przez 0 element najmniejszy kraty < L0/<", >.
Pokażemy, że dla dowolnego A " L0 istnieje B " L0, że:
[A]<" *" [B]<" = 1
[A]<" )" [B]<" = 0
Wystarczy przyjąć B = ŹA. Wówczas na mocy poprzedniego lematu (c), (d) mamy:
[A]<" *" [ŹA]<" = [A (" ŹA]<" = 1
[A]<" )" [ŹA]<" = [A '" ŹA]<" = 0
Zatem -[A]<" = [ŹA]<".
Wynika stąd, że < L0/<", > jest kratą boole owską.
Uwaga. Algebrę Boole a wyznaczoną przez kratę < L0/<", > nazywamy algebrą Lin-
denbauma ( Tarskiego) KRZ. Oznaczamy ją przez AKRZ.
[A]<" *" [B]<" = [A (" B]<"
[A]<" )" [B]<" = [A '" B]<"
- [A]<" = [ŹA]<"
1 = [A (" ŹA]<"
0 = [A '" ŹA]<"
[A]<" ! [B]<" = -[A]<" *" [B]<" = [ŹA (" B]<" = [A B]<"
Uwaga. AKRZ jest przeliczalna (nieskończenie).
Uwaga.
0 = [p0]<" > [p0 '" p1]<" > [p0 '" p1 '" p2]<" > . . . > 0
A = A(q0, . . . , qn)
0 = [A]<" > [A '" p0]<" > [A '" p0 '" p1]<" > . . . > 0
AKRZ jest bezatomowa.
26
10 WYKAAD 10 (20.12.2007)
Lemat 10.1. Niech będzie homomorfizmem algebry AKRZ w B2. Niech : P - {0, 1}
będzie odwzorowaniem zadanym poprzez warunek:
(p) = ([p])
dla p " P . Wówczas (A) = ([A]) dla każdej formuły A.
Dowód. Indukcja względem budowy formuły A.
A = p oczywiste z określenia .
A = B (" C
(A) = (B) *" (C) = ([B]) *" ([C]) = ([B (" C]) = ([A]).
Podobnie dowodzimy pozostałe przypadki.
Twierdzenie 10.2 (o pełności KRZ względem M2). Każda tautologia matrycy M2 jest
tezą systemu KRZ.
Dowód. Załóżmy, że A. Zatem w algebrze AKRZ mamy [A] = 1, czyli [ŹA] = 0. Niech
F będzie ultrafiltrem algebry AKRZ takim, że [ŹA] " F . Mamy ponadto AKRZ/F <" B2.
=
Niech będzie homomorfizmem kanonicznym AKRZ w B2. Rozważmy wartościowanie
indykowane przez w sensie lematu. Mamy: (ŹA) = ([ŹA]) = 1. Stąd (A) = 0.
Zatem A nie jest tautologią matrycy M2.
Wniosek 10.3. Formuła A jest tautologią matrycy M2 wtedy i tylko wtedy, gdy A jest
tezą systemu KRZ.
Wniosek 10.4.
1. System KRZ jest niesprzeczny.
2. System KRZ jest rozstrzygalny.
Twierdzenie 10.5. Zbiór formuł Ł jest niesprzeczny wtedy i tylko wtedy, gdy Ł jest
spełnialny.
Dowód.
(!) Załóżmy, że Ł jest niesprzeczny. Wówczas każdy skończony podzbiór zbioru Ł jest
niesprzeczny. Pokażemy, że każdy niesprzeczny skończony podzbiór zbioru formuł Ł jest
spełnialny.
Przypuśćmy, że tak nie jest. Niech Ł0 będzie niespełnialnym skończonym podzbiorem
Ł. Niech Ł0 = {C1, . . . , Cn} oraz niech C = C1 '" . . . '" Cn. Ponieważ Ł0 jest niespeł-
nialny, formuła C jest kontrtautologią. Zatem ŹC jest tautologią i na mocy twierdzenia
o pełności ŹC. Mamy jednak Ł0 C, co oznacza w szczególności sprzeczność zbioru
Ł0, wbrew założeniu.
Zatem każdy skończony podzbiór zbioru Ł jest spełnialny, czyli zbiór Ł jest skończenie
spełnialny, a zatem na mocy twierdzenia o zwartości zbiór Ł jest spełnialny.
27
(!) Przypuśćmy, że Ł jest sprzeczny. Wówczas w szczególności Ł p '" Źp. Zatem
dla pewnego skończonego zbioru Ł0 " Ł mamy Ł0 p '" Źp. Niech C będzie koniunk-
cją wszystkich formuł ze zbioru Ł0 (Ł0 jest skończony). Mamy na mocy twierdzenia o
dedukcji C (p '" Źp), czyli wobec twierdzenia o pełności formuła C (p '" Źp)
jest tautologią. Zauważmy jednak, że formuła p '" Źp jest niespełnialna. Zatem C rów-
nież przyjmuje wartość 0 przy każdym wartościowaniu. Oznacza to, że zbiór Ł0 jest
niespełnialny. Skąd w szczególności zbiór Ł jest niespełnialny.
LOGIKA KWANTYFIKATORÓW
Język logiki kwantyfikatorów składa się z następujących symboli:
" symbole relacyjne Pi, i " I, każdemu symbolowi Pi przyporządkowana jest liczba
naturalna #(Pi) 1,
" symbole funkcyjne fj, j " J, jeżeli fj jest n-argumentowym symbolem funkcyjnym,
to piszemy #(fj) = n 1,
" stałe ck, k " K, stałe traktować możemy jako 0-argumentowe symbole funkcyjne.
Ponadto zakładamy, że dysponujemy nieskończonym (przeliczalnym) zbiorem V zmien-
nych indywiduowych.
Symbole Pi, fj, ck nazywamy symbolami pozalogicznymi. Językiem logiki kwantyfikato-
rów (językiem pierwszego rzędu) nazywamy układ:
L = {(Pi)i"I, (fj)j"J, (ck)k"K}
Możemy dodatkowo zakładać, że dysponujemy pewnym 2-argumentowym symbolem
relacyjnym = . Mówimy wówczas o języku pierwszego rzędu z identycznością.
Ponadto dysponujemy tak zwanymi symbolami logicznymi, czyli:
" spójnikami zdaniowymi, na przykład , Ź, ('", (", . . .),
" kwantyfikatorami ", ("),
" symbolami pomocniczymy, na przykład nawiasy, przecinki...
Moc języka L oznaczamy przez L i określamy jako L = 5!0 + card (L).
28
11 WYKAAD 11 (03.01.2008)
Definicja 11.1. Zbiór termów T (L) języka L jest najmniejszym zbiorem spełniającym
następujące warunki:
(1) V ą" T (L), (V -zbiór zmiennych indywiduowych),
(2) C ą" T (L), (C-zbiór stałych),
(3) Jeżeli t1, . . . , tn są termami, a f jest n-argumentowym symbolem funkcyjnym, to
wyrażenie f(t1, . . . , tn) jest termem, (f(t1, . . . , tn) " T (L)).
Definicja 11.2. Zbiór formuł atomowych języka L jest zbiorem wszystkich wyrażeń
postaci:
P (t1, . . . , tn)
gdzie P jest n-argumentowym symbolem relacyjnym języka L oraz t1, . . . , tn " T (L).
W przypadku języka z identycznością, formułami atomowymi są oczywiście wyrażenia
postaci t1 = t2, gdzie t1, t2 " T (L).
Definicja 11.3. Zbiór formuł F (L) języka L jest najmniejszym zbiorem spełniającym
następujące warunki:
(1) F (L) zawiera wszystkie formuły atomowe,
(2) Jeżeli A, B " F (L), to do F (L) należą również wyrażenia ŹA, (A B), "xA.
Definiujemy pozostałe spójniki zdaniowe i kwantyfikator szczegółowy:
(A (" B) = (ŹA B),
(A '" B) = Ź(A ŹB),
(A "! B) = ((A B) '" (B A)),
"xA = Ź"xŹA.
Dla formuły "xA, A leży w zasięgu kwantyfikatora " wiążącego zmienną x. Formuła A
jest bezpośrednią podformułą formuł postaci:
"xA, ŹA, (A B), (B A)
Definicja 11.4. Zbiór zmiennych wolnych i zbiór zmiennych związanych termu t ozna-
czamy odpowiednio przez vf (t) i vb (t) i definiujemy następująco:
vf (x) = {x}, vf (c) = ", vf (f(t1, . . . , tn)) = vf (t1) *" . . . *" vf (tn),
vb (x) = vb (c) = vb (f(t1, . . . , tn)) = ".
Zbiór zmiennych wolnych i związanych formuły A określamy następująco:
vf (P (t1, . . . , tn)) = vf (t1) *" . . . *" vf (tn),
vb (P (t1, . . . , tn)) = ",
vf (ŹA) = vf (A), vb (ŹA) = vb (A),
vf (A B) = vf (A) *" vf (B), vb (A B) = vb (A) *" vb (B),
vf ("xA) = vf (A) \ {x}, vb ("xA) = vb (A) *" {x}.
Formułę A nazywamy zdaniem (formułą domkniętą), gdy vf (A) = ". Będziemy pisać
t(x1, . . . , xn) oraz A(x1, . . . , xn) gdy vf (t), vf (A) ą" {x1, . . . , xn}.
29
Uwaga.
A := "xP (x, y, z) "yQ(y)
vf (A) = {y, z}, vb (A) = {x, y}
Dokładniej, mówimy o wolnych i związanych wystąpieniach zmiennych.
Definicja 11.5. Operacje podstawienia termu t za zmienną x oznaczać będziemy sym-
bolem (x/t) i definiujemy w następujący sposób:
t, gdy x = y
" y(x/t) =
y, gdy x = y
" c(x/t) = c
" f(t1, . . . , tn)(x/t) = f(t1(x/t), . . . , tn(x/t))
" P (t1, . . . , tn)(x/t) = P (t1(x/t), . . . , tn(x/t))
" (ŹA)(x/t) = Ź(A(x/t))
" (A B)(x/t) = (A(x/t) B(x/t))
"yA, gdy x = y lub y " vf (t)
" ("yA)(x/t) =
"yA(x/t), w przeciwnym wypadku
Uwaga. A = "x(P (y) P (x)) (P (y) "xP (x))
A(y/x) = "x(P (y) P (x)) (P (x) "xP (x))
A(y/x)(y/c) = "x(P (c) P (x)) (P (x) "xP (x))
P (x) = x = 0 , c = 1
"x(1 = 0 x = 0) (x = 0 "xx = 0)
Definicja 11.6. Zbiór zmiennych wolnych Ff (t, A) dla termu t w formule A definiujemy
następująco:
x " Ff (t, A) ! x " vf (A) lub
x " Ff (t, A) ! x " vf (t) oraz
" A jest formułą atomową,
" A = ŹB i x " Ff (t, B),
" A = B C i x " Ff (t, B) )" Ff (t, C),
" A = "yB i y " vf (t) oraz x " Ff (t, B).
Uwaga. Zawsze będziemy zakładać, że rozważane podstawienie A(x/t) jest poprawne,
czyli że x " Ff (t, A).
30
Definicja 11.7. Ustalmy język L = {(Pi)i"I, (fj)j"J, (ck)k"K} i niech M = ". Interpre-
tacją języka L w M nazywamy dowolną funkcję I przyporządkowującą symbolom języka
L odpowiednie relacje, funkcje, elementy:
I(P ) ą" M#(P ), I(f): M#(f) - M, I(c) " M
Modelem dla języka L nazywamy parę:
M = (M, I)
Przy ustalonym modelu M piszemy:
M
P zamiast I(P )
fM zamiast I(f)
cM zamiast I(c).
31
12 WYKAAD 12 (10.01.2008)
N
Definicja 12.1. Model N = (N, {PiN}, {fj }, {cN}) nazywamy podmodelem modelu
k
M
M = (M, {PiM}, {fj }, {cM}) (oznaczamy N ą" M), gdy:
k
" N ą" M,
" dla dowolnych a1, . . . , an " N, PiN(a1, . . . , an) wtedy i tylko wtedy, gdy PiM(a1, . . . , an),
gdzie Pi jest dowolnym n-argumentowym symbolem relacyjnym,
N M
" fj = fj |N, dla dowolnego symbolu funkcyjnego fj,
" cN = cM, dla dowolnej stałej ck.
k k
M
Definicja 12.2. Rozważmy model M = (M, {PiM}, {fj }, {cM}). Niech <" będzie kon-
k
M
gruencją algebry (M, {fj }, {cM}). Modelem ilorazowym modelu M względem kongru-
k
encji <" nazywamy model:
<"
M/<" = (M/<", {Pi<"}, {fj }, {c<"})
k
gdzie
<"
" (M/<", {fj }, {c<"}) jest algebrą ilorazową algebry (M, {fj}, {ck}) względem kon-
k
gruencji <",
" Pi<"([a1]<", . . . , [an]<") wtedy i tylko wtedy, gdy PiM(a , . . . , a ), dla pewnych a " [ai]<".
1 n i
Definicja 12.3. Niech M = (M, I) będzie modelem dla języka L. Wartościowaniem w
modelu M nazywamy dowolną funkcję ą: V - M.
Gdy V = {x1, x2, x3. . . .}, dla wygody przyjmujemy oznaczenie ą(xi) = ai.
Definicja 12.4. Wartość termu t przy wartościowaniu ą w modelu M (tM[ą]) definiu-
jemy następująco:
" xM[ą] = ą(xi) (= ai),
i
" cM[ą] = cM,
" (f(t1, . . . , tn))M[ą] = fM(tM[ą], . . . , tM[ą]).
1 n
Definicja 12.5. Relację spełniania formuły A w modelu M przez wartościowanie ą,
M |= A[ą] definiujemy indukcyjnie względem budowy A:
M
" M |= P (t1, . . . , tn)[ą] ! P (tM[ą], . . . , tM[ą]),
1 n
" M |= ŹA[ą] ! M |= A[ą],
" M |= (A B)[ą] ! jeżeli M |= A[ą], to M |= B[ą],
" M |= "xA(x)[ą] ! dla każdego a " M, M |= A(x)[ą x/a],
ą(y), gdy y = x
gdzie ą x/a(y) =
a, gdy y = x
32
Mówimy, że formuła A jest prawdziwa w modelu M, gdy M |= A[ą] dla każdego warto-
ściowania ą: V - M. Piszemy wówczas M |= A.
Formuła A jest prawdziwa, gdy M |= A dla każdego modelu. Piszemy wówczas |= A.
Niech będzie zbiorem zdań, wówczas piszemy M |= , gdy prawdziwe jest każde zdanie
ze zbioru . Mówimy wtedy, że M jest modelem dla .
Uwaga. Spełnialność formuł A(x1, . . . , xn) przez wartościowanie ą zależy tylko i wyłącz-
nie od wartościowania zmiennych wolnych formuły A.
Będziemy zatem pisać M |= A(x1, . . . , xn)[a1, . . . , an] zamiast M |= A(x1, . . . , xn)[ą].
Lemat 12.6. Niech M będzie dowolnym modelem dla języka L.
(1) Niech A = A(x1, . . . , xn), wtedy M |= A ! M |= "x . . . "x A,
1 n
(2) Niech A bedzie zdaniem.
Wówczas M |= A ! M |= A[ą], dla każdego ą ! M |= A[ą] dla pewnego ą,
(3) Dla żadnej formuły A nie zachodzi M |= A oraz M |= ŹA,
(4) Dla dowolnego zdania A zachodzi M |= A lub M |= ŹA,
(5) Dla dowolnej formuły B zachodzi M |= B (" ŹB.
Uwaga. Założenie w punkcie (4) lematu, że A jest zdaniem jest istotne.
Niech M = (N, <) i wezmy A = x < y. Wtedy:
M |= A, bo M |= (x < y)[x/1, y/0]
M |= ŹA, bo M |= (x < y)[x/0, y/1]
KLASYCZNY RACHUNEK KWANTYFIKATORÓW
Ustalmy język L (przeliczalny). Aksjomaty i reguły Klasycznego Rachunku Kwantyfi-
katorów (KRK).
Aksjomaty:
(Q0) Schematy aksjomatów KRZ w języku {Ź, } sformułowanych dla formuł języka
L (np. P (x) (Q(x) P (x))),
(Q1) "xA A(x/t), gdzie x " Ff (t, A),
(Q2) "x(A B) (A "xB), gdzie x " vf (A).
Reguły:
A,AB
ro = reguła odrywania,
B
A
rG = reguła generalizacji.
"xA
System, którego aksjomatami są (Q0),(Q1),(Q2) z regułami ro, rG oznaczamy KRK.
Pojęcie dowodu, wyprowadzalności pozostaje bez zmian.
Uwaga. Podstawienie dowolnej tezy KRZ formułami języka L jest tezą KRK.
33
Twierdzenie 12.7 (o zgodności). Każda teza jest formułą prawdziwą, czyli
KRZ A ! |= A.
Dowód. Wystarczy sprawdzić, że |= A dla dowolnego aksjomatu, oraz że zbiór formuł
prawdziwych jest domknięty na reguły ro, rG.
Rozważmy (Q2). Przypuśćmy, że |= "x(A B) (A "xB).
Zatem istnieje model M i wartościowanie ą: V - M takie, że
M |= "x(A B) (A "xB)[ą], czyli M |= "x(A B)[ą] oraz M |= (A "xB)[ą].
Zatem M |= A[ą] oraz M |= "xB[ą]. Ponieważ z założenia x " vf (A) i z faktu, że
M |= A[ą] wynika, że w M |= B[ą x/a] dla każdego a. Z drugiej strony M |= "xB[ą],
czyli istnieje a, że M |= B[ą x/a]. Sprzeczność.
34
13 WYKAAD 13 (17.01.2008)
Lemat 13.1. Następujące formuły są tezami KRK:
(1) "xA(x, y) A(x, y),
Ż Ż
(2) A(x, y) "xA(x, y),
Ż Ż
(3) "xA "xA,
gdzie y = y1, . . . , yn.
Ż
Dowód. (1) (Q1), x " Ff (x, A),
(2) "xŹA(x) ŹA(x)
ŹŹA(x) Ź"xŹA(x)
A(x) "xA(x),
(3) Mamy "xA A(x) oraz A(x) "xA.
Stąd "xA "xA (prawdziwa tylko w modelach niepustych).
Lemat 13.2. Niech A i B będą dowolnymi formułami oraz niech C będzie taką formułą,
że x " vf (C). Wtedy następujące reguły są wyprowadzalne:
CB(x)
(1) ,
C"xB(x)
A(x)C
(2) ,
"xA(x)C
A"xB
(3) ,
AB
"xAB
(4) .
AB
Dowód. (1) Mamy C B(x) C B(x). Stąd C B(x) "x(C B(x))
CB(x)
oraz na mocy (Q2), C B(x) C "xB(x). Zatem jest regułą
C"xB(x)
wyprowadzalną.
(3) Mamy A "xB A "xB oraz "xB B, skąd A "xB A B. Czyli
A"xB
jest regułą wyprowadzalną.
AB
(2),(4) Analogicznie jak (1),(3) korzystając z kontrapozycji.
Lemat 13.3. Następujące formuły są tezami KRK:
(1) "x(A '" B) "! ("xA '" "xB),
(2) ("xA (" "xB) "x(A (" B),
(3) "x(A (" B) "! ("xA (" "xB),
(4) "x(A '" B) ("xA '" "xB),
35
(5) "x(A (" B) "! ("xA (" B), gdy x " vf (B),
(6) "x(A '" B) "! ("xA '" B), gdy x " vf (B),
(7) "x"yA "! "y"xA, "x"yA "! "y"xA,
(8) "x"yA "y"xA.
Dowód. (1) (!) Mamy "x(A '" B) (A '" B), (A '" B) A.
Mamy "x(A'"B) A oraz "x(A'"B) B. Stąd, ponieważ x " vf ("x(A'"B))
otrzymujemy "x(A '" B) "xA oraz "x(A '" B) "xB.
Stąd "x(A '" B) ("xA '" "xB).
(!) Mamy ("xA '" "xB) "xA oraz ("xA '" "xB) "xB.
Stąd ("xA '" "xB) A i ("xA '" "xB) B, czyli ("xA '" "xB) (A '" B).
Zatem ponieważ x " vf ("xA '" "xB), ("xA '" "xB) "x(A '" B).
(8) A(x, y) A(x, y)
"yA(x, y) A(x, y)
A(x, y) "xA(x, y)
Stąd "yA(x, y) "xA(x, y). Zatem, ponieważ y " vf ("yA(x, y)) i x " vf ("xA(x, y))
"x"yA(x, y) "y"xA(x, y).
Twierdzenie 13.4 (o dedukcji). Niech A będzie zdaniem, zbiorem zdań, a B dowolną
formułą. Wówczas:
KRK A B wtedy i tylko wtedy, gdy , A KRK B
Dowód. (!) Oczywista.
(!) Dowodzimy podobnie jak w KRZ. Wystarczy rozważyć użycie reguły generalizacji.
Niech B1, . . . , Bn = B bedzie dowodem B na gruncie , A.
Pokazujemy, że A Bj dla każdego j n. Załóżmy, że Bj = "xBi dla pewnego
i < j (użycie reguły generalizacji). Z założenia indukcyjnego mamy: A Bi(x).
Ponieważ x " vf (A) otrzymujemy A "xBi.
Bj
Uwaga.
A(x) "xA(x) ale A(x) "xA(x)
Twierdzenie 13.5 (o eliminacji stałych). Niech Ł będzie zbiorem formuł. Załóżmy, że
stała c nie występuje w żadnej z formuł zbioru Ł. Wtedy:
c
Ł A(c) ! Ł "yA( )
y
c
gdzie A(y ) jest formułą powstałą przez zastąpienie wszystkich wystąpień stałej c zmien-
c
ną y. Ponadto istnieje dowód formuły "yA(y ), w której nie występuje stała c.
36
Dowód. Załóżmy, że B1, . . . , Bn(c) = A(c) jest dowodem formuły A(c) na gruncie Ł.
Wybieramy nową zmienną y nie występującą w żadnej z formuł Bi, 1 i n. Poka-
c c c c
żemy, że B1(y ), . . . , Bn-1(y ), A(y ) jest dowodem formuły A(y ) na gruncie Ł. Niech Bi
będzie aksjomatem.
(Q1) "xA(y) A(x/t(c)), x " Ff (t(c), A),
(Q2) "x(C(y) D(x, y)) (C(y) "xD(x, y)).
Używamy reguły odrywania w oczywisty sposób. Załóżmy, że Bj = "xBi gdzie i < j.
Bi(x, y), . . . , "xBi(x, y)
Bj
Wniosek 13.6. Załóżmy, że stała nie występuje w Ł oraz w A. Wtedy:
Ł A(x/c) ! Ł "xA(x)
Wniosek 13.7. Niech L będzie wzbogaceniem języka L o nowe stałe i niech A będzie
formułą języka L. Wtedy:
Ł A (w L ) ! Ł A (w L)
W szczególności, jeżeli Ł jest niesprzeczny (w L), to Ł jest zbiorem niesprzecznym w
każdym wzbogaceniu języka L o nowe stałe.
37
14 WYKAAD 14 (24.01.2008)
Twierdzenie 14.1 (Lindenbauma). Każdy niesprzeczny zbiór formuł zawarty jest w
maskymalnym niesprzecznym zbiorze formuł.
Dowód. Korzystamy z lematu Kuratowskiego-Zorna. Niech zbiór będzie niesprzeczny.
Definiujemy rodzinę:
R = {": " - niesprzeczny, " " }
Każdy łańcuch (względem ą") ma ograniczenie górne w R. Zatem w R istnieje element
maksymalny.
Lemat 14.2. Niech będzie maksymalnym niesprzecznym zbiorem formuł i niech A
będzie dowolną formułą. Wówczas:
(a) A " wtedy i tylko wtedy, gdy A (domknięcie na konsekwencje),
(b) A albo ŹA (zupełność).
Dowód.
(a) (!) oczywista
(!) Załóżmy, że A " , ponieważ jest maksymalnym zbiorem niesprzecznym,
*" {A} jest zbiorem sprzecznym. Zatem ŹA. Stąd wobec niesprzeczności
dostajemy A.
(b) Przypuśćmy, że dla pewnego A
A oraz ŹA
Rozważmy zbiór *" {A} . Ponadto *" {A} jest niesprzeczny (bo ŹA).
Zatem nie jest maksymalnym zbiorem sprzecznym.
Definicja 14.3. Mówimy, że M jest modelem dla zbioru zdań , gdy M |= A, dla
wszystkich A " .
Zbiór formuł ma model (jest spełnialny), gdy istnieją M oraz ą: V - M takie, że
M |= A[ą] dla wszystkich formuł A " .
Definicja 14.4. Niech C będzie zbiorem stałych. Mówimy, że C jest zbiorem świadków
dla zbioru formuł języka L, gdy dla dowolnej formuły A zbioru istnieje c " C takie,
że:
"xA(x) A(x/c)
Mówimy, że ma własność świadka, gdy istnieje zbiór świadków C dla .
Twierdzenie 14.5 (o istnieniu modelu). Każdy niesprzeczny zbiór formuł języka L ma
model. W szczególności, każdy niesprzeczny zbiór zdań języka L ma model. Ponadto,
moc tego modelu jest nie większa od mocy języka L.
38
Szkic dowodu. Ustalmy język L i niech L = . Niech będzie niesprzecznym zbiorem
formuł języka L. Niech C bedzie zbiorem nowych stałych mocy . Pokazujemy, że:
(1) Zbiór możemy rozszerzyć do niesprzecznego zbioru + w języku L+ = L *" C
takiego, że C jest zbiorem świadków dla +.
(2) + ma model.
Zakładamy, że + jest maksymalnym niesprzecznym zbiorem, dla którego C jest zbiorem
świadków i ą" +.
Definiujemy model dla języka L:
N
N = (T, {PiN}, {fj }, {cN})
k
taki, że:
" T jest zbiorem wszystkich termów (stałych) języka L+,
N
" P (t1, . . . , tn) wtedy i tylko wtedy, gdy + P (t1, . . . , tn),
" fN(t1, . . . , tn) = f(t1, . . . , tn) " T ,
" cN = c.
N nie musi być modelem dla + (na przykład + t = s dla różnych termów t, s).
Definiujemy więc model M. Dla t, s " T , niech t <" s ! + t = s. <" jest kongruencją
zachowującą relacje modelu N. Niech M = N/<".
Definiujemy wartościowanie ą w modelu M: ą(x) = [x]<".
Dowodzimy, że:
(3) M |= +.
Wówczas redukt M do modelu dla języka L jest modelem zbioru . Ponadto, z kon-
strukcji wynika, że moc modelu M jest równa L .
Wniosek 14.6. Niech będzie zbiorem zdań. Wówczas jest niesprzeczny wtedy i
tylko wtedy, gdy ma model.
Twierdzenie 14.7 (o pełności). Dla dowolnego niesprzecznego zbioru zdań i dowol-
nego zdania A mamy:
A wtedy i tylko wtedy, gdy |= A
Dowód. (!) Załóżmy, że A. Wówczas zbiór *" {ŹA} jest niesprzeczny, a zatem
ma model. Mamy więc M taki, że M |= oraz M |= A, czyli |= A.
(!) Załóżmy, że A. Wówczas istnieje skończony zbiór ą" taki, że A.
Niech C będzie koniunkcją wszystkich zdań ze zbioru . Wówczas C A. Zatem
M |= C A, dla dowolnego modelu M. Niech M |= , wówczas oczywiście M |= C, a
zatem M |= A co dowodzi, że |= A.
39
Twierdzenie 14.8 (dolne twierdzenie Lowenheima-Skolema). Każdy niesprzeczny zbiór
zdań języka L ma model mocy nie większej od mocy języka L.
Twierdzenie 14.9 (o zwartości). Zbiór zdań ma model wtedy i tylko wtedy, gdy każdy
jego skończony podzbiór ma model.
Twierdzenie 14.10 (górne twierdzenie Lowenheima-Skolema). Jeżeli zbiór zdań ję-
zyka L ma model nieskończony, to ma modele dowolnej mocy, większej lub równej od
mocy języka L.
40
Wyszukiwarka
Podobne podstrony:
Wykład 1 Logika rozmytawyklad logikaLogika wykładyLOGIKA wykłady dr Marek Jastrzębskilogika wykladLOGIKA WYKŁADYWykład III Logika systemów cyfrowych, funkcje logicznelogika wyklad 06Logika wyklad 1logika wyklad 05Logika wyklad 2LOGIKA wykladlogika wykladLogika wyklad 6logika wykladlogika wyklad 04więcej podobnych podstron