Romek ver 3 01 finally

1. Definicja Schematu i Tautologii:

-SCHEMAT-zdanie złożone zbudowane ze zdań,

funktorów i nawiasów.
-Niech α będzie schematem. Powiemy, że α jest prawem lub

TAUTOLOGIĄ rachunku zdań co zapiszemy ├α gdzie α jest

zdaniem prawdziwym bez względu na wartości logiczne zdań,

z których α jest zbudowane.

2. Podstawowe tautologie

p<=>~(~p) prawa podwójnego przeczenia(1.8);
p۷~p (1.9); ~(p۸~p) (1.10);

Prawa de Morgana:{

~(p۸q)<=>~p۷~q (1.11)
~(p۷q)<=>~p۸~q (1.12) }
p<=>q<=>[p=>q)۸(q=>p)](1.13)
~(p=>q) <=>(p۸~q)(1.14)
(p=>q) <=>(~p۷q) (1.15)

3. Tw. 1.3( własności schematów)

Dla dowolnych schematów α,β,γ,σ spełnione są następujące warunki:

α≡β b) jeśli α≡β to β≡α c)jeśli α≡β to ~α≡~β

jeśli α≡β i β≡γ to α≡γ e) jeśli α≡β,γ≡σ to α۸γ≡β۸σ, to

α۸γ≡β۸σ α۷γ≡β۷σ α<=>γ≡β<=>σ α=>γ≡β=>

4. Definicja za pomocą v i ~ funktory: , >, >

(p  q) <=> ~(~p  ~q)

(p => q) <=> (~p  q)

(p <=> q) <=> ~[~(~p  q)  ~(~q  p)]

5. Definicja za pomocą B8 funktorów: v, ~, 

(p  q) <=> ~(p B8 q)

(p  q) <=> (~p B8 ~q)

~p <=> ~[(~p) B8 (~q)]

6. Reguła dowodzenia:

Niech α₁,…α_n i β będą schematami. Jeżeli schemat

(α₁ ۸ ….۸ α_n)=>β jest tautologia to piszemy (α₁,...α_n)/β (1.35) i mówimy, że schemat β jest logiczna konsekwencją schematów α₁,…,α_n Wtedy wyrażenie(α₁,...α_n)/β nazywamy REGUŁĄ DOWODZENIA

α₁,…,α_n przesłanki β-wniosek.
Przy stwierdzaniu czy (α₁,...α_n)/β jest reguła dowodzenia pomocne jest

TW. 1.10

Wyrażenie (α₁,...α_n)/β jest reguła dowodzenia wtedy i tylko wtedy gdy spełniony jest warunek: jeśli tylko α₁,…,α_n przedstawiają zdanie prawdziwe to β również przedstawia zdanie prawdziwe.

7. Funkcja zdaniowa:

Przyporządkowanie φ każdemu elementowi x∈X zdania φ(x), prawdziwego lub fałszywego nazywamy funkcje zdaniową jednej zmiennej x, której zakresem zmienności jest X. Piszemy φ(x), x∈X

Powiemy, że dany element α∈X spełnia funkcje zdaniową φ jeżeli: u(φ(a))=1 ( φ(a) zdanie prawdziwe). Zbiór wszystkich x∈X, które spełniają φ będziemy oznaczać przez { x∈X:φ(x)}

8. Wniosek 2.1

(2.2): {x∈X(φ۸ψ)(x)}={x∈X:φ(x)۸ψ(x)={x∈X: φ(x)}∩{x∈X: ψ(x)}

(2.3): {x∈X:(φ۷ψ)(x)}={x∈X: φ(x)۷ψ(x)}={x∈X:φ(x)}U{x∈X: ψ(x)}

(2.4): {x∈X:(~ φ)(x)}={x∈X: ~(φ(x))}=X-{x∈X: φ(x)}

9. Tw. 2.3

a) {x∈X: φ(x)=>ψ(x)}=(X-{x∈X: φ(x)})U{x∈X:ψ(x)}

b) {x∈X: φ(x) <=> ψ(x)}=[ (X-{x∈X: φ(x)})U{x∈X:ψ(x)}∩

[(X-{x∈X:ψ(x)})U{x∈X: φ(x)}]

Dowód a)

{xєX: φ(x) => Ψ(x)} ={ xєX: ~φ(x) ν Ψ(x)}= {xєX: ~φ(x)} ν{ xєX: Ψ(x)}

W powyższym równaniu pierwszy znak równości wynika z tego że funkcja zdaniowa φ(x) xєX, jest prawdziwa w przestrzeni X, jeżeli

{xєX: φ(x)}=X} Drugi znak równości wynika z tego że φ jest wtedy prawdziwa w X gdy X=R, φ(x): x²+x+1>0.

10. Kwantyfikator ogólny to symbol
φ(x), jest to znak wiążący zmienną x o zakresie ograniczonym do X. Zdanie to jest prawdziwe, jeżeli zdanie φ(x) jest prawdziwe dla każdego x ze zbioru X, w przeciwnym wypadku zdanie to jest fałszywe

Kwantyfikator związany(egzystencjalny?) to symbol
φ(x), jest to znak wiążący zmienną x o zakresie ograniczonym do X. Zdanie to jest prawdziwe, jeżeli zdanie φ(x) jest prawdziwe dla co najmniej jednego x ze zbioru X, zdanie to jest fałszywe jeżeli zdanie φ(x)jest fałszywe dla każdego x ze zbioru X.

Zmienna w wyrażeniach
φ(x) i
φ(x) ma inny charakter niż zmienna x w wyrażeniu φ(x) . Gdy w funkcji zdaniowej φ(x) za zmienną x podstawimy nazwę dowolnego elementu aєX, to otrzymamy wówczas zdanie φ(a) prawdziwe lub fałszywe. Podstawiając w kwantyfikatorze za zmienną x nazwę dowolnego elementu z zakresu zmienności zmiennej x otrzymamy wyrażenie pozbawione sensu. Dlatego zmienną x w kwantyfikatorze nazywamy zmienną związaną odpowiednim kwantyfikatorem. Zmienną x w funkcji zdaniowej φ(x) nazywamy dla odróżnienia zmienna wolną.

11.Tw. 2.6

a)
- kwantyfikator o zakresie ograniczonym funkcją zdaniową Ψ:

b)
Y(x)^φ(x)

Dowód a)
{ xєX: Ψ(x)}с{ xєX: φ(x)}

12. Przykłady tautologii rachunku funkcyjnego

2.19 |-
φ(x)=> φ(y) yєX 2.20 |-
φ(x)=>
φ(x), 2.21 |- φ(y)=>
φ(x) yєX

Pr. de Morgana: (2.22) |- ~
φ(x)<=>
~φ(x)

(2.23) |- ~
φ(x)<=>
~φ(x)

Uogólnienia praw(2.22') |-~
φ(x,y)<=>
~φ(x,y), xєX

(2.23') |-~
φ(x,y)<=>
~φ(x,y), xєX.

13. Prawa dotyczące rozdzielności kwantyfikatorów

2.34 |- ~
(φ(x)=> Ψ(x))=> [
φ(x)=>
Ψ(x)]

2.35|-
(φ(x)=> Ψ(x))=> [
φ(x)=>
Ψ(x)]

14. Prawa przestawiania kwantyfikatorów

2.36 |-

φ(x,y)<=>

φ(x,y)

2.37 |-

φ(x,y)<=>

φ(x,y)

2.38 |-

φ(x,y)<=>

φ(x,y)

15.Prawa włączania i wyłączania kwantyfikatorów

2.48 |-
φ(x)=> Ψ)<=> [(
φ(x)=> Ψ)]

2.49 |-
φ(x)=> Ψ)<=> [(
φ(x)=> Ψ)] gdzie Ψ jest zdaniem lub funkcją zdaniową, w której nie występują zmienne wolne x.

16. Twierdzenie 3.5 Prawo de Morgana dla różnicy zbiorów

a)A-(BυC)<=>(A-B)∩(A-C); b) A-(B∩C)<=>(A-B) υ (A-C)

Dowód:a) A-(BυC) wtedy i tylko wtedy gdy xєA, x
BυC. Lecz x nie należy do sumy BυC wtedy i tylko wtedy, gdy x nie należy do żadnego ze składników, czyli gdy x
B i x
C. Warunek xєA, x
B i x
C jest równoważny warunkowi xєA-B i xєA-C, który z kolei jest równoważny warunkowi xє(A-B) ∩(A-C)Wykazaliśmy że xєA-(BυC) wtedy i tylko wtedy gdy xє(A-B) ∩(A-C) co dowodzi to twierdzenie. Dowód b) xєA-(B∩C)<=> xєA i x
B∩C<=>xєAi~(xєBixєC)<=> xєAi(~(xєB) ν ~ (xєC))<=> (xєAi~(xєB)) ν (xєAi~ (xєC))<=> xє(A-B)ν (A-C).

17. Różnicą symetryczną zbiorów A i B rozumiemy wzór określony następująco A
B= (A-B) υ(B-A) !!OZNACZENIE!!
= -`

18. Tw. 3.8 Dla dowolnych zbiorów A,B,C,D

A-` (A-`B)=B A-`C=A-`D<=> C=D.

Dowód a) A-` (A-`B)=(A-`A) -`B≠ø-`B=B-` ø= B

b) A-`C=A-`D<=> (A-`C) -` (A-`D)= ø<=>C-` (A-`D)= ø<=> C-` ((A-`A) -`D)= ø <=> C-`D= ø<=> C=D

19. Def. Dopełnieniem zbioru A c X nazywamy zbiór: X - A = - A; Niech A c X . Mamy: Λx€X (x € - A x nie € A);

Czyli: -A = { x € X : x nie € A };

20. Tw. 3.12 Dla dowolnych A,B c X: a) - (A lub B) = -A i -B;

b) - (A i B) = -A lub -B; c) A - B = A i - B; d) A - B = - (- A lub B); e) A c B A i -B = Ø; f) A c B -A lub B = x; Dowód c) dla x € X , x € A-B x€A i x€Bx€A i x€-B x€A i -B; Dowód d) A-B = Ai -B = -(-(A i -B)) = -(-A lub -(- B)) = -(-A lub B); Dowód e) A c B A - B = Ø A i -B = Ø; Dowód f) Jeśli: A i -B = Ø to: -(A i -B) = - Ø, -A lub -(-B) = X, -A lub B = Xm; Jeśli: -A lub B = X to -(-A lub B) = -X, -(-A) i -B = Ø, A i - B = Ø, Stąd: A i - B = Ø -A lub B = X;

21. Zbiór potęgowy którego elementami są wszystkie podzbiory przestrzeni X nazywamy ZBIOREM POTĘGOWYM zbioru X i oznaczamy przez 2^x. Jęśli X jest n-elementowy to 2^x jest 2^n elementowy.
Zbiór R którego elementami są zbiory nazywamy RODZINĄ ZBIORÓW. Przykładem takiej rodziny jest 2^x. Rodziną R = 2^x ( X ≠ Ø - ustalona przestrzeń) nazywamy CIAŁEM ZBIORÓW, jeśli: a) R jest niepusta; b) A € R => -A € R; c) (A € R i B € R) => A lub B € R;

22. Tw. 3.14 ZAŁ.: R c 2^x - ciało zbiorów; Teza: a) Ø, X € R;

b) (A € R i B € R ) => ( A i B € R i A - B € R);

Dowód b) A-B = -(-A lub B); A i B = -(-(A i B)) = -(-A lub -B)

23. Niech a, b,a1 … an - dowolne przedmioty;

a) Parą Uporządkowaną nazywamy zbiór <a,b> = { {a}, {a,b}};

b) Uporządkowaną N-KĄ nazywamy zbiór

< a1, … , an> = << … < a1, a2>, a3 > … > an;

(D.3.4) Niech X, Y, X1, … , Xn - zbiory;

a) Produkt (iloczyn) kartezjański zbioru X,Y:

X × Y = {< a, b> : a € X i b € Y};

b) Produkt kartezjański zbiorów X1, … , Xn:

X1 × … × Xn = {< a1,…,an> = a1 € X1 , … , an€ Xn}

24. Dla dowolnych przedmiotów a, b, c i d:

{ {a}, {a,b} } = { {c}, {c,d} } (a=c i b=d);
a) <a,b> = <a', b'> (a=a' i b = b');

b) <a1, … , an > = < a1', … ,an' > (a1= a1' i … i an = an')

25. Niech X i Y - dowolne zbiory;

a) RELACJĄ DWUCZŁONOWĄ w X = Y nazywamy każdy podzbiór ς c X × Y; Zamiast <x,y> c ς będziemy pisać x ς y i czytać „ x pozostaje w relacji ς z y „; b) Jeśli Y = X, to ς c X × X będziemy nazywać relacją dwuczłonową w X; c) Relacja F c X × Y będziemy nazywać ODWZOROWANIEM ( funkcją ) zbioru X w zbiór Y i pisać F: X -> Y, jeżeli Λx€Y Vy€Y x Fy oraz Λx€X Λy1,y2€Y [(xFy1 i x Fy2) => y1 = y2]. Zamiast x Fy będziemy wtedy pisać y = F(x);

26. Niech X będzie dowolnym zbiorem. Relację dwuczłonową ς c X × X nazywamy:

a) Zwrotną, jeśli: Λx€X x ς x; b) Przeciwzwrotną, jeśli: Λx€X ~ (x ς x); c) Symetryczną, jeśli: Λx€X ( x ς y => y ς x);

d) Przeciwsymetryczną, jeśli: Λx€X (x ς y => ~ (y ς x));

e) Antysymetryczną, jeśli: Λxy€X [(x ς y i y ς x) => x=y];

f) Przechodnią, jeśli: Λxyz€X [(x ς x i y ς z) => x ς z];

g) Spójną, jeśli: Λxy€X (x ς y lub y ς x lub x = y);

27. Relacja równoważności: .Relację ς c X × X nazywamy relacją równoważności w zbiorze X, jeżeli ς jest relacją zwrotną, symetryczną i przechodnią, to znaczy jeżeli są spełnione trzy następujące warunki: a) x ς x dla każdego x € X; b) x ς y => y ς x dla każdego x,y €X;

c) ( x ς y i y ς z ) => x ς z dla każdego x,y, z € X; (
- relacja równoważności).
Niech
będzie dowolną relacją równoważności w X ≠ 0. Dla każdego elementu x € X niech ||x|| oznacza zbiór tych wszystkich elementów y € X, które pozostają z x w relacji
, czyli takich, dla których spełniony jest warunek x
y. Tak więc z definicji:

||x|| = { y € X: x
y }, (y € ||x||) ( x
y) dla każdego x, y € X. Zbiory ||x|| dla x € X nazywamy Klasami Równoważności relacji
w X lub Klasami Abstrakcji relacji
w X. Dokładniej, klasę ||x|| nazywamy klasą równoważności ( abstrakcji) relacji
w X wyznaczoną przez x lub o reprezentancie x. Zbiór wszystkich klas równoważności relacji
w X oznaczamy symbolem X

28. Tw. 3.20

Z. ς C XxX - Relacja równoważność, x,y, Z1, Z2 €X

T. a) x € [x], b) Z1,Z2 € [x] => Z1 ς Z2, c) [x]=[y]x ς y,, d) [x] ≠[y] =>[x] ∩ [y] = Ø, e) [x] ∩ [y] = Ø ~(x ς y).

Dowód. Ponieważ Λ[a€X] (a€[x]x ς a) Ponieważ ς jest zwrotna, to xςx. Zatem x€[x]. c) „=>” Niech [x]=[y] Zgodnie z a), y€[y] Stąd y€[x] Zatem(warunek 3.17), xςy. „<=” . Niech xςy stąd yςx Przypuśćmy, że z a€[x] Zatem xςa. Łącząc (3.19) i (3.20) otrzymujemy Yςa czyli a€[y]. Stąd [x] c [y] Podobnie sprawdzamy, że [y] c[x] Zatem [x] = [y] d) Przypuścimy, że [x] ≠[y] Λ [x] ∩ [y] ≠Ø Wtedy, istnieje a€[x] ∩[y] czyli a€[x] Λ a€ [y] xςa Λ yςa zatem xςy czyli [x]=[y].

29. Przykład 3.3 Niech k€N - ustalona liczba n€Z (liczby całkowite) V [l € Z] n=lk

Będziemy zapisywac K|n t.j. ςcZxZ Określamy relacje dwuczłonową ς w X=Z Następująco xςyk|(x-y), x,y € Z niech x,y,z € X =Z mamy x-x=0=0k czyli (l=0€Z) k|(x-x) zatem, na mocy (3.14) xςx Stąd ς jest ZWROTNA. Niech xςy czyli k|(x-y) Zatem x-y=lk dla pewnego l€Z Mamy y-x=(-l)k Ponieważ (-l)€Z, to k|(y-x) Stąd yςx Zatem ς jest SYMETRYCZNA. Niech xςy i yςz Mamy x-y=lk i y-z=l1k, l,l1€Z Zatem (l+l1)k=x-y+y-z=x-z czyli K|(x-z) stąd xςz tak więc ς jest PRZECHODNIA. Przykład 3.7 Niech p€N, p≥2 -ustalona liczba Określamy relacje dwuznaczną ςcZxZ: Xςy p|(x-y).

30. Aksjomat 4.1 1 € N Aksjomat 4.2 1 nie jest następnikiem żadnej liczby n€N

Aksjomat 4.3 Dla każdej liczby n€N istnieje dokładnie jedna Liczba m€N, taka że m jest następnikiem n. Aksjomat 4.4 Λ[m,k,n€N] [((m-następnik n) Λ (m- następnik k))=> n=k]

Aksjomat 4.5 Jeżeli AcN Takim, że 1€A oraz Λ[n€N] [n€A Λ (m-nastepnik n))=> m€A to, A=N

31. Dodawanie liczb naturalnych określamy w następujący sposób: Λ [m€N] m+1=m' Λ[m,n€N] m+n'=(m+n)' gdzie k' oznacza następnik k.

Def. 4.2 Mnożenie liczb naturalnych określamy w następujący sposób: Λ [m€N] m1=m Λ[m,n€N] mn'=(mn)+m

32. Tw. 4.2 Aksjomaty 4.5 i 4.6 określają iloczyn mnożenia dla dowolnych m,n€N.

33. Tw. 4.4 (zasada minimum)

Z.AcN, A≠Ø T. V[m€A] Λ [n€A] (m<n v m=n) (m- LICZBA NAJMNIEJSZA w zbiorze A)

35. Def. 5.2 Powiemy, że zbiory X iY są RÓWNOLICZNE, Co zapiszemy X~Y jeżeli istnieje f:X→Y Tw. 5.2

Dla dowolnych zbiorów A,B i C: a) A~A, b) A~B=>B~A,

c) (A~B Λ B~C) => A~C.

36. Aksjomat 5.1(aksjomat istnienie liczb kardynalnych) Każdemu zbiorowi A przyporządkowuje się pewien przedmiot zwany LICZBĄ KARDYNALNĄ lub MOCĄ, oznaczamy przez A[=], w taki sposób, żeA[=]=B[=] A~B Tak więc zamiast mówić, że A i B SA równoważne, możemy również mówić, że A i B są RÓWNEJ MOCY lub że mają tą samą liczbę kardynalną.

37. Zbiór A nazyw. PRZELICZALNYM, jeżeli A jest skończony lub A~N

Wniosek 5.1 Jeśli A,B-zbiory przeliczalne i nieskończone to A[=]=B[=]=N[=] Oznaczamy N[=]=Xo

38. Tw 5.3 Z. A≠φ T. A jest przeliczalny⇔istnieje g: Nna A (tzn. A jest zbiorem wyrazów pewnego ciągu nieskończonego)

39. Tw. 5.4 Z. A-przeliczalny, B⊂A T. B- przeliczalny

Tw. 5.5 Z. A,B przeliczalne T. A∪B- przeliczalny

Tw. 5.6 Z. A_1,.....,A_k-przeliczalne T. A₁∪_.....A_k_-przeliczalny

Tw. 5.7 Z. A,B-przeliczalne T. AxB - przeliczalny

40. Tw. 5.9 Zbiór Q wszystkich liczb wymiernych jest przeliczalny. Dowód: Zbiór Q można zdefiniować jako przestrzeń ilorazową pewnej relacji równoważności ρ⊂(ZxZ*)x(ZxZ*): Q=(ZxZ*)/ၲ Możemy zatem określić odwzorowanie h: ZxZ*Q, h(<x;y>)=[<x;y>] - klasa abstrakcji relacji ၲ reprezentowana przez <x;y> oczywiście h: ZxZ*na Q z Tw. 5.7 i przykładu 5.3 wynika że ZxZ* - przeliczalny. Stąd na mocy tw. 5.3

istnieje f: Nna ZxZ* Niech g=h°f (g: NZxZ*Q) Wtedy g(N)=h(f(N))=h(ZxZ*)=Q czyli g: NnaQ Zatem na mocy 5.3 Q jest przeliczalny.

41. Przykłady zbiorów przeliczalnych Oznaczenia: IQ (A, Π)- zbiór wszystkich liczb niewymiernych (algebraicznych, przestępnych) p∈Q, W(x)=x-p Q⊂A, IQ∩A≠φ W(x)=x2-2=0 ⇔ x=±pierwiastek z 2 ∈IQ a)A jest przeliczalny b)Zbiór wszystkich wielomianów o współczynnikach wymiernych jest przeliczalny

42. Przykłady zbiorów nieprzeliczalnych: Powiemy że zbiór X jest nieprzeliczalny jeżeli X nie jest przeliczalny [a,b]={x∈R : a≤x≤b} [a,b]={x∈R : a<x≤b}, a,b∈R, a<b - przedział [0,1] jest zbiorem nieprzeliczalnym.

Szkic dowodu: Pokazujemy ∧(a_n)^∞_n=1, a_n∈[0,1] ∨ x∈[0,1] ∧n∈N x≠ a_nZatem na mocy Tw. 5.3 [0,1] nie jest przeliczalny.

- R jest nieprzeliczalny. Dowód: [0,1]⊂R

43. Niech n,m - liczby kardynalne a) istnieja zbiory A i B n=A[=] i m=B[=] Jeśli istnieje C⊂B, t.ż, A~C to piszemy n≤m (liczba kardynalna n jest nie większa od liczby kardynalnej m) b) Jeżeli n≤m i n≠m t.j. A[=]≠ B[=] to piszemy n<m n jest mniejsze od m)

44. Moc zbioru R nazywamy continuum i oznaczamy

przez c: c= R[=] Zatem zgodnie z (5.13) x_o<c.

45. Tw. 5.17 Dla dowolnych liczb kardynalnych m,n i p:

a) n≤n, b) (n≤m ∧ m≤p)⇒ n≤p

Tw 5.18 (Cantora - Berusteina) Dla dowolnych liczb kardynalnych m i n: (n≤m ∧ m≤n) ⇒n=m

Tw. 5.19 ( które wynika z Tw. 5.18) Dla dowolnych zbiorów A,B i C: (A⊂B⊂C ∧ A[=]=C[=]) ⇒ A[=]=B[=]=C[=]

46. Przykłady zbiorów CONTINUUM:

- (-π/2;π/2); - (a,b); - [a,b]; - {0,1}^N

47. Tw 5.21: