Rachunek zdań:
Zdaniem w sensie logiki jest zdanie twierdzące, o którym można obiektywnie stwierdzić czy jest prawdziwe czy fałszywe.
Prawem logicznym (tautologią) nazywamy wyrażenia zbudowane za pomocą zdań, funktorów zdaniotwórczych i nawiasów, które jest zawsze prawdziwe dla dowolnych wartości logicznych zdań w nim występujących.
Podstawowe tautologie:
Prawo tożsamości dla implikacji:
p=>pPrawa przemienności koniunkcji i alternatywy:
(p/\q)(q/\p)
(p\/q)(q\/p)Prawa łączności koniunkcji i alternatywy
(p/\q)/\rp/\(q/\r)
(p\/q)\/rp\/(q\/r)Prawa identpotentności
(p/\p)p
(p\/p)pPrawa pochłaniania
(p/\1)p
(p\/0)pPrawa rozdzielności
(p\/q)/\r(p/\r)\/(q/\r)
(p/\q)\/r(p\/r)/\(q\/r)Prawo wyłączonego środka
p\/(~p)Prawo wyłączonej sprzeczności
~(p/\(~p))Prawo podwójnego przeczenia
~(~p)pPrawa de Morgana
~(p/\q)(~p)\/(~q)
~(p\/q)(~p)/\(~q)Zaprzeczenie implikacji
~(p=>q)p/\(~q)Eliminacja implikacji
(p=>q)[(~p)\/q]Eliminacja równoważności
(pq)[(p=>q)/\(q=>p)]Przechodniość implikacji
[(p=>q)/\(q=>r)](p=>r)Prawo kontrapozycji
(p=>q)[(~p)=>(~q)]Reguła odrywania
((p=>q)/\p)=>p
Zbiory:
Zbiory oznaczamy dużymi literami. Element x należący do zbioru A oznaczamy
. Element x nie należący do zbioru A oznaczamy
. Elementy zbioru oznaczamy
. Zbiór który nie ma elementu nazywamy zbiorem pustym. Elementem zbioru może być inny zbiór, wtedy mówimy o rodzinie zbiorów.
Zasada ekstensjonalności:
Mówimy, że zbiory A i B są równe (identyczne) jeśli posiadają te same elementy i zapisujemy
lub
.
Def. 1. Mówimy, że zbiór A jest zawarty w zbiorze B, jeśli dla dowolnego x spełniony jest warunek:
i oznaczamy
.
Tw.1. Zbiory są równe wtedy i tylko wtedy, gdy A zawiera się w B i B zawiera się w A:
Tw.2. Jeśli
i
to
.
Działania na zbiorach:
Prawa przemienności
Prawa łączności
Prawa rozdzielności
Prawa de Morgana
Prawa identpotentności
Prawa pochłaniania
Tw.3. Dla dowolnych zbiorów A,B,C mamy:
Def.2. Funkcją zdaniową zmiennej x nazywamy wyrażenie, które zawiera niewiadomą x i ma taką wartość, że jeśli w miejsce tej niewiadomej podstawimy konkretny przedmiot należący do ustalonego zbioru X to otrzymamy zdanie na gruncie logiki. Zbiór X nazywamy dziedziną lub zakresem zmienności.
Def.3. Iloczyn kartezjański:
. Własności:
Kwantyfikatory
Def.4. Kwantyfikatory. Wyrażenie „dla każdego” nazywamy kwantyfikatorem ogólnym
. Wyrażenie „istnieje” nazywamy kwantyfikatorem egzystencjalnym
.
Tw.4. Jeśli
jest funkcją zdaniową o zakresie zmienności X to istnieje zbiór tych
, a więc zbiór elementów, które spełniają funkcję zdaniową. Dowód jest konsekwencją aksjomatów.
Tw.5. Typowe prawa kwantyfikatorów. Niech
jest funkcją zdaniową o zakresie zmienności X i niech
:
Tw.6. Prawa de Morgana dla kwantyfikatorów:
Tw.7. Niech
będzie funkcją zdaniową o zakresie zmienności X. Wówczas:
Tw.8. Niech
i
będą funkcjami zdaniowymi o zakresie zmienności X. Wówczas:
Tw.9. Niech
i
będą funkcjami zdaniowymi o zakresie zmienności X. Wówczas mamy własności:
Tw.10. Niech
będzie funkcją zdaniową o zakresie zmienności X oraz p niech będzie zdaniem, wówczas:
Kwantyfikatory o ograniczonym zakresie
Def.5.
.
Wszystkie prawa rachunku kwantyfikatorów sformułowane dotychczas pozostają prawdziwe dla kwantyfikatorów o ograniczonym zakresie.
Iloczyn kartezjański
Tw.11. Dla dowolnych elementów a i b istnieje dokładnie jeden zbiór, który zawiera wyłącznie elementy a i b. Zbiór ten oznaczamy
i nazywamy parÄ… nieuporzÄ…dkowanÄ….
Jeśli
to
Dla dowolnych elementów a i b istnieje dokładnie jedne zbiór, który składa się z elementów
i
. Zbiór ten oznaczamy
i nazywamy parÄ… uporzÄ…dkowanÄ…. Stosujemy dla pary uporzÄ…dkowanej oznaczenie
, gdzie a nazywamy poprzednikiem, zaś b następnikiem.
Tw.12.
.
Def.6. Niech
i
. Wówczas zbiór
nazywamy iloczynem kartezjańskim zbiorów A i B i oznaczamy
. Jeśli któryś ze zbiorów A i B jest pusty to
. Iloczyn kartezjański nie jest przemienny.
Tw.13. Dla dowolnych zbiorów A, B, C, D mamy:
Ponadto jeśli
i
, to
Relacje
Def.7. Niech
. Wówczas dowolny zbiór
nazywamy relacją dwuczłonową. Jeśli
to ØÜ jest relacjÄ… n-czÅ‚onowÄ….
Niech
. Dziedziną lewostronną (prawostronną) nazywamy zbiór:
,
.
Typy relacji
Zwrotność
Symetryczność
Przechodniość
Przeciwsymetryczność:
Słabosymetryczność:
Spójność
Przeciwzwrotność
Def.8. RelacjÄ™
, która jest zwrotna, symetryczna i przechodnia nazywa się relacją równoważności.
Def.9. Niech
będzie relacją równoważności to dla dowolnego
to zbiór
nazywamy klasÄ… abstrakcji wyznaczonÄ… przez element
w relacji ØÜ i oznaczamy:
Własności klas abstrakcji: Dla dowolnego
zachodzą własności:
Def.10. Niech
. Niech
będzie rodziną podzbiorów zbioru
. Mówimy, że rodzina
stanowi podział przestrzeni
jeśli spełnione są następujące warunki:
Tw.14. (Zasada abstrakcji) Jeśli
i
jest relacją równoważności to rodzina wszystkich klas abstrakcji stanowi podział przestrzenie
.
Tw.15. Aksjomat wyboru. Dla dowolnej rodziny
zbiorów niepustych i parami rozłącznych istnieje zbiór, który posiada dokładnie po jednym elemencie wspólnym z każdym ze zbiorów rodziny
.
Tw.16. Niech
będzie rodziną zbiorów niepustych w przestrzeni
parami rozłącznych i
, to istnieje relacja
, która jest relacją równoważności i klasy abstrakcji tej rodziny pokrywają się ze zbiorami rodziny
.
Składanie relacji
Niech
i
. Wówczas relację:
,
nazywamy superpozycją (złożeniem) relacji
i
i oznaczamy
.
Tw.17. Składanie relacji jest łączne, a więc, jeśli
,
,
, to
.
Def.11. Niech
. Wówczas
nazywamy relacjÄ… odwrotnÄ… i oznaczamy
. Zatem jeśli
i
, to
Tw.18. Niech
i
. Wówczas
Def.12. Niech
i niech
. Mówimy, że
jest relacją częściowego porządku, jeśli
jest zwrotna, antysymetryczna (słabo symetryczna) i przechodnia.
Def.13. Niech
i niech
. Mówimy, że
jest relacją liniowego porządku, jeśli
jest relacją częściowego porządku i jest spójna.
Def.14. Zbiorem częściowo uporządkowanym nazywamy parę
, gdzie
jest relacją częściowego porządku w
.
Def.15. Zbiorem liniowo uporzÄ…dkowanym nazywamy parÄ™
, gdzie
jest relacjÄ… liniowego porzÄ…dku w
.
Def.16. Jeśli zbiór X jest częściowo uporządkowana przez relację
, zaÅ›
jest liniowo uporzÄ…dkowany przez relacjÄ™
to Y nazywamy łańcuchem.
Def.17 Niech
będzie zbiorem częściowo uporządkowanym. Wówczas element
jest elementem największym (najmniejszym) ze względu na relację
jeśli jest spełniony warunek:
(lub
). Jeśli istnieje element największy (najmniejszy) to tylko jeden.
Def.18. Niech
będzie zbiorem częściowo uporządkowanym, mówimy że
jest elementem maksymalnym (minimalnym) w zbiorze
, gdy nie istnieje
takie, że
i
(lub
dla elementu minimalnego), a zatem:
Def.19. Niech
będzie zbiorem liniowo uporządkowanym. Jeśli dla każdego niepustego zbioru
istnieje element najmniejszy w zbiorze
względem relacji
to takÄ… relacjÄ™ nazywamy relacjÄ… dobrego porzÄ…dku, a parÄ™
zbiorem dobrze uporzÄ…dkowanym.
Tw.19. (Fermallo) Dla każdego zbioru
istnieje relacja
w zbiorze X, która jest relacją dobrego porządku. Twierdzenie to jest równoważne aksjomatowi wyboru.
Funkcje
Def.20 Niech
będzie relacją. Mówimy, że relacja
jest funkcją, jeśli spełniony jest następujący warunek:
(relacja jest prawostronnie jednoznaczna)
- dziedzina lewostronna funkcji
Jeśli
to mówimy, że funkcja
jest określona na zbiorze
i oznaczamy:
.
- przeciwdziedzina (zbiór wartości) funkcji f, dziedzina prawostronna.
Jeśli
to mówimy, że funkcja f jest typu „na” (jest okreÅ›lona na caÅ‚y
) i oznaczamy:
.
Funkcja jest „na”, gdy:
Def.21 Funkcja
jest różnowartościowa, jeśli spełniony jest warunek:
Z faktu, że
, wynika:
JeÅ›li funkcja jest różnowartoÅ›ciowa i „na” to mówimy, że jest to funkcja wzajemnie jednoznaczna i oznaczamy:
.
Jeśli
jest różnowartoÅ›ciowa (lub „na”) i
jest różnowartoÅ›ciowa („na”) to
też jest różnowartoÅ›ciowa („na”).
Jeśli
jest wzajemnie jednoznaczna to
też jest wzajemnie jednoznaczna.
Tw.20. Istnieje (na mocy aksjomatu) zbiór wszystkich funkcji określonych na zbiorze X o wartościach w zbiorze Y i oznaczamy go
.
Tw.21. Jeśli
jest funkcjÄ…, to relacja
jest funkcjÄ… wtedy i tylko wtedy, gdy funkcja
jest różnowartościowa. Ponadto
, gdzie
jest funkcją różnowartościową.
Tw.22. Niech
i
będą funkcjami. Wówczas relacja
jest funkcją (złożeniem funkcji) i
.
Def.22 Obrazem zbioru
przy pomocy funkcji
nazywamy zbiór
i oznaczamy
.
Def.23 Przeciwobrazem zbioru
przy pomocy funkcji
nazywamy zbiór:
i oznaczamy
.
Działania uogólnione
Def.24 Niech
nazywamy rodziną indeksowaną, jeśli istnieje zbiór
i istnieje funkcja
. Zatem
lub
Jeśli T jest zbiorem skończonym
, to
. Jeśli
, to mamy ciÄ…g zbiorów. JeÅ›li ØÜ jest dowolnÄ… rodzina zbiorów, to:
Niech
będzie rodziną indeksowaną postaci
Jeśli
to zapisy te można zastąpić odpowiednio:
Tw.23. Niech
i
będą rodzinami indeksowanymi zbiorów. Wówczas:
Dla dowolnego
:
Prawa de Morgana:
i
Jeśli dla dowolnego
mamy, że
, to
i
Jeśli dla dowolnego
mamy
, to
i
.
Tw.24 Niech
i
będą rodzinami indeksowanymi. Wówczas:
Tw.25 Element x należący do granicy dolnej ciągu zbiorów
z wyjątkiem skończonej ilości. Element x należący do granicy górnej ciągu zbiorów
wtedy i tylko wtedy, gdy należy do nieskończenie wielu zbiorów
.
.
Tw.26 Niech
,
,
. Wówczas:
Tw.27 Niech
,
,
. Wtedy:
Tw.28 Niech
. Niech
i
. Wówczas zachodzą następujące własności:
Tw.29 Niech
bÄ™dzie funkcjÄ… typu „na”. Wówczas dla dowolnego zbioru
mamy
. Twierdzenie odwrotne jest także prawdziwe.
Tw.30 Niech
będzie funkcją różnowartościową. Wówczas dla każdego dowolnego zbioru
mamy
. Twierdzenie odwrotne jest także prawdziwe.
Równoliczność zbiorów
Def.25 Mówimy, że zbiory
są równoliczne, jeśli istnieje taka funkcja
jest różnowartościowa, taka że
i oznaczamy
.
Tw.31 Dla dowolnych niepustych zbiorów
mamy:
Def.26 Zbiór A jest skończony, jeśli jest pusty lub istnieje liczba naturalna
, taka że A jest równoliczny ze zbiorem
.
Tw.32 Zbiór liczb naturalnych nie jest zbiorem skończonym.
Lemat Dla każdej liczby naturalnej
nie istnieje funkcja różnowartościowa.
Def.27 Zbiór A nazywamy zbiorem przeliczalnym, jeśli A jest skończony lub równoliczny ze zbiorem liczb naturalnych lub istnieje
.
Tw.33 Zbiór A jest przeliczalny wtedy i tylko wtedy, gdy jest zbiorem wartości pewnego ciągu nieskończonego, a więc istnieje funkcja
.
Tw.34 Jeśli zbiór A jest przeliczalny i
, to B też jest przeliczalny.
Tw.35 Jeśli A,B są przeliczalne, to
też jest przeliczalny.
Lemat Zbiory
oraz
są równoliczne.
Tw.36 Jeśli A,B są przeliczalne, to
też jest przeliczalny.
Tw.37 Suma dowolnej rodziny
, gdzie
sÄ… przeliczalne, jest zbiorem przeliczalnym.
Def.28 Każdemu zbiorowi A przyporządkowujemy pewien obiekt, zwany mocą zbiorów, przy czym zbiory A i B mają tę samą moc wtedy i tylko wtedy, gdy A i B są równoliczne (
). Oznacza siÄ™
,
,
. Jeśli A jest skończony, czyli
to
. Przyjmuje siÄ™ oznaczenie:
Moce zbiorów nazywane są liczbami kardynalnymi.
Def.29 Mówimy, że liczba kardynalna
(oznaczamy literami gotyckimi) jest nie większa od liczby kardynalnej
, co zapisujemy
, jeśli istnieją zbiory A i B, takie, że
,
praz zbiór A jest równoliczny z pewnym podzbiorem zbioru B.
Def.30 Mówimy, że liczba kardynalna
, jeśli
i
.
Lemat (przekątniowy Cantora) Niech A będzie dowolnym zbiorem, zaś
dowolnym jego podzbiorem. Nie istnieje funkcja
(lub też
), która jest typu „na”.
Def.31 Przyjmuje siÄ™ oznaczenie
(continuum)
Tw.38 Dla dowolnego zbioru A mamy
, nawet jeśli
.
Hipoteza continuum (CH) Nie istnieje liczba kardynalna
taka, że
. Hipoteza continuum jest niezależna od układu aksjomatów ZF (Zermello Frankla).
Tw.39 (Cantora - Bernsteina) Niech
,
są dowolnymi liczbami kardynalnymi, wówczas:
Tw.40 Zbiór
jest nieprzeliczalny.
Tw.41 Dowodzi się, że jeśli
to
, bo istnieje funkcja
.
Tw.42 Nie istnieje zbiór wszystkich zbiorów.
Wyszukiwarka