Logika formalna – nauka badająca poprawność rozwiązań



Pobieranie 0,96 Mb.
Strona5/9
Data30.05.2018
Rozmiar0,96 Mb.
1   2   3   4   5   6   7   8   9

Zasada ekstensjonalności

Dwa zbiory są równe jeśli mają te same elementy {x1,…,xn}



A=B ↔ dla każdego x, xAxB
Przykład:

{2,3} = {3,2} = {2,3,2} – ten zbiór ma 2 elementy


Definicja:

A ⊆ B ↔ dla każdego x, xAxB


Twierdzenie:

Dla dowolnych zbiorów A,B,C



  1. A ⊆ A

  2. Jeśli A ⊆ B i B ⊆ C, to A ⊆ C ⊆ - słabe zawieranie;

  3. Jeśli A ⊆ B i B ⊆ A, to A=B ⊂ -mocne zawieranie

A ⊂ B ↔ A ⊆ B  A  B
Definicja zbiorów za pomocą funkcji zdaniowej

(x), xX – funkcja zdaniowa

{xX: (x)}



Przykład:

P = {xZ: 2/x} A= {xR: x²=x}

Niech A będzie dowolnym zbiorem. Rozważmy zbiór {xA; xx}. Żaden obiekt nie spełnia warunku xx, więc rozważany zbiór nie ma żadnego elementu. Na mocy zasady ekstensjonalności istnieje tylko jeden zbiór o tej własności. Nazywamy go zbiorem pustym i oznaczamy go ø.

ø ⊆ A dla dowolnego zbioru A


Definicja:

Zbiorem potęgowym zbioru A nazywamy rodzinę wszystkich podzbiorów zbioru A.

(ozn. ℘(A))

potęga zbioru A – zbiór potęgowy



W sposób nie całkiem formalny można zapisać

(A) = {x: x⊆A}

ø(A), A(A)
Przykłady

1. Jeśli X = ø, to (X)={ø}

(zbiór, którego jedynym elementem jest zbiór pusty).

2. Jeśli X = {a}, to (X)={ø,X}

3. Jeśli X = {a, b}, to (X)={ø,{a},{b},X}

4. Jeśli X = {a, b, c}, to (X) = {ø,{a}.{b},{c},{a,b},{b,c},{c,a},X}





Uwaga!

{xX: (x)}to zawsze jest zbiór

(A)={x: xA} – to czasami może nie być zbiór bo nie ma określonej przestrzeni




Przykład:

A={2,3} (A) = {ø,{2},{3},{2,3}}



Ogólnie jeśli A ma n elementów, to (A) ma

Działania na zbiorach

1). Suma zbiorów

xABxAxB (AB={x: xAxB})

2). Iloczyn zbiorów

xABxAxB (AB={x: xAxA})
3). Różnica zbiorów

xA-BxAx∉B (A-B={x: xAx∉B})


A∸B(A-B)(B-A)-odejmowanie symetryczne

Mówi się, że zbiory A i B są rozłączne jeśli AB=ø




Uwaga!

Jeśli A, B ⊆ U (A⊆U  B⊆ U), to

AB, AB, A-B, A∸B⊆U.

(inaczej, jeśli A,B(U) to AB, AB, A-B, A∸B(U))




Definicja:

Jeśli A⊆U, to zbiór U-A nazywamy dopełnieniem zbioru A do przestrzeni U

(ozn. A=U-A)

Twierdzenie:

Dla dowolnych zbiorów A,B⊆U

A-B=AB

Dowód

xA-B xAx∉BxAxBxAB

na mocy ekstensjonalności


Twierdzenie (podstawowe prawa rachunków zbiorów)

Dla dowolnych zbiorów A,B,C,⊆U

1). AB=BA

2). A(BC)=(AB)C; A(BC)=(AB)C

3). A(BC)=(AB)(AC); A(BC)=(AB)(AC)

4). Aø=A; AU=A

5). AU=U; Aø=ø

6). AA=U; AA=ø



Dowód 3).

xA(BC)xAxBCxA(xBxC)(xAxB)(xAxC) xABxACx(AB)(AC);

Dowód 4).

Aø=A

xAxøxAxøxA



Dowód 5).

Aø=ø

xAøxAxøAø=ø



Twierdzenie

Dla dowolnych zbiorów A,B:

1) A⊆A B, B⊆AB

2) AB⊆A, AB⊆B

3)A⊆BAB=BAB=A

Dowód:


  1. xAxAxB jest prawdziwy

  2. xAxBxA jest prawdziwy

  3. „”A⊆B dla dowolnego x, xAxB

xABxAxBxB

xAxB, to A⊆B

xAxBxB

xBxB


AB⊆BAB=B, bo zawsze B⊆AB

„”


AB=B prawdziwe

A⊆AB więc A⊆B


Twierdzenie

Dla dowolnych zbiorów A,B:



  1. A-B⊆A

  2. A⊆BA-B=ø

Dowód:

1) xAxBxA

2) A-B=ø nie istnieje xA to że x∉B dla każdego xA jest xBA⊆B

Twierdzenie

Dla dowolnych A, B, C ⊆ U:

1) A – ø = A A∸A=ø

2) A∸B=B∸A

3) A∸(B∸C)=(A∸B)∸C

Dowód:


  1. A∸ø=(A-ø)(ø-A)=Aø=A

A∸A=(A-A)(A-A)=øø=ø

  1. A∸B=(A-B)(B-A)=(B-A)(A-B)=B∸A


Twierdzenie

Dla dowolnych A,B⊆U:



  1. jeśli A”=B, to A=B”(w szczególności A”=(A’)’=A)

  2. U’=ø ø’=U

Dowód:

1) Niech A’=B wtedy dla dowolnego x xA’xB. Stąd x∉AxB, a więcxAx∉B, czyli xAxB’. Zatem A=B’ stad A’=B, to A’’=(A’)’=B’=A

2)U’=ø, to zd. xU  xU jest fałszywe

ø’=U na mocy 1!



Twierdzenie

Dla dowolnych A,B⊆U



  1. (AB)’=A’B’

  2. (AB)’=A’B’ (prawa de Morgana w rachunku zb.)

Dowód:

  1. x(AB)’x∉AB ~(xAB) ~(xAxB)xAx∉B

xA’xB’xA’B

  1. x(AB)’x∉AB ~(xAB) ~(xAxB)x∉Ax∉B

xA’xB’xA’B’

Twierdzenie

Dla dowolnych zbiorów A i B

A-B=(AB)-(AB)
Ciała zbiorów

Niech R będzie rodziną podzbioru przestrzeni Uø (tzn. R⊆(U))

Rodzinę R nazywamy ciałem zbiorów przestrzeni U, jeśli:


  1. R jest niepuste

  2. AR, to A’R

3)A, BR, to ABR

Przykład:

    1. Uø(U) i {ø,U} są ciałami zbiorów przestrzeni U

    2. Rodzina (R) skończonych podzbiorów zbioru l. Rzeczywistych (R) i ich dopełnień jest ciałem zbiorów.


Twierdzenie:

Jeśli rodzina R podzbioru przestrzeni U  ø jest ciałem zbioru to:

1). ciało UR, øR

2). jeśli A,BR, to AB, A-B, A∸BR


Dowód:

1). Istnieje AR (bo R niepuste). Stąd A’R a więc U=AA’R. Zatem także ø=U’R



2). Niech A,BR. Wtedy A’,B’R. A więc A’B’R. Stąd AB=(A’B’)’R., także A-B=AB’R. Ponieważ A∸B=(A-B)(B-A) i A-B, B-AR. Więc A∸BR.
Niech A1,…,An ⊆ U oraz =Ak, Ak¹=Ak¹ dla k=1,…,n. Każdy zbiór postaci A1…An, gdzie ik=0 lub ik=1 dla k=1,…,n nazywamy składową przestrzeni U wyznaczoną przez zbiory A1,…,An.

A1…An=(…((A1A2)A3)…)A4




1   2   3   4   5   6   7   8   9


©operacji.org 2019
wyślij wiadomość

    Strona główna