Logika zadania

Rachunek zdań: Język KRZ: Język klasycznego rachunku zdań. Dzieli się na symbole zdań atomowych (p,q,r,s,t..), symbole spójników logicznych (^, v,=,,~) oraz znaki interpunkcyjne (nawiasy). Wartościowanie: Zbiór formuł logicznych (F) nazywamy wartościowaniem (V)  V: F α r(α) {0,1}
V(~α)=1-v(α)
V(α^β)=v(α)v(β)
V(αvβ)=v(α)+v(β)-v(α)v(β)
V(α=β)=1-v(α)+v(β)v(α)
V(αβ)=1-v(α)-v(β)+2v(α)v(β) Tautologia: Formuła prawdziwa niezależnie od wartości logicznych zdań składowych. Rachunek predykatów: Term: Napis nad alfabetem A, który powstaje przez zastosowanie skończoną liczbę razy regół:
… są termami
… są termami
Jeżeli są termami oraz F jest n-argumentowym symbolem funkcyjnym, to F( ) jest termem. Formuła atomowa: n-argumentowy symbol predykatywny wyznaczony na n termach (tzn. R( )).
Forma zdaniowa (formuła): napis nad alfabetem A, który powstaje przez zastosowanie skończoną ilość razy reguł:
Formułą atomowa jest formą zdaniową
Jeżeli α, β są formami zdaniowymi, to ~α,α^β, αvβ, α=β, αβ są formami zdaniowymi.
Jeżeli α(x) jest formą zdaniową od zminnej x, to i są formami zdaniowymi. Dziedzina formy zdaniowej α(x): zbiór wszystkich stałych, dla których forma α(x) staje się zdniem logicznym po wstawieniu za x tej stałej. Oznaczamy ją D . Zbiór wartości formy zdaniowej α(x): zbiór wszystkich stałych z D takich, że α(x) jest zdaniem prawdziwym po wstawieniu tej stałej (S ).
S = {a Twierdzenia: 1) 2) 3) 4) 5) Kwantyfikatory o ograniczonym zakresie: Ø Teoria mnogości: Działania na zbiorach i ich własności: Prawa rachunku zbiorów: Zbiór potęgowy (P(x)): Niech X będzie zbiorem. Zbiorem potęgowym zbioru X nazywamy zbiór wszystkich podzbiorów zbioru X.
Iloczyn Kartezjański zbiorów A i B: zbiór Rodzina zbiorów: zbiór K := Suma uogólniona rodziny K : Iloczyn uogólniony rodziny K : Rodzina indeksowana zbioru: K := Relacje: Relacja równoważności: relacja, która jest zwrotna, symetryczna i przechodnia.
Oraz R jest równoważnością  Klasa równoważności: R : Zbiór ilorazowy: Zbiór wszystkich klas abstrakcji relacji R :
Podział zbioru X: rodzina D(x) P(x) taka, że:
Zasada abstrakcji:

(…)

… tranzytywnym  elementy jego elementów są również jego elementami:
Własności zbioru tranzytywnego:
Każdy zbiór tranzytywny i liniowo uporządkowany ze względu na relację jest dobrze uporządkowany.
Przekrój zbioru tranzytywnego jest zbiorem tranzytywnym
Liczba porządkowa: α jest liczbą porządkową  α jest tranzytywny oraz: Twierdzenie o klasie liczb porządkowych: Każda niepusta klasa liczb porządkowych ma element najmniejszy.
Definicje działań na liczbach porządkowych:
Twierdzenia równoważne aksjomatowi wyboru:
Aksjomat wyboru 1: Jeżeli K jest rodziną niepustych zbiorów, to istnieje funkcja (funkcja wyboru) taka, że .
Aksjomat wyboru 2: Dla każdej rodziny K niepustych, parami rozłącznych zbiorów istnieje zbiór (selektor) K taki, że .
Lemat Kuratowskiego - Zorna: Jeżeli w zbiorze częściowo uporządkowanym…
… A, to A~B.
Moc zbioru: Najmniejsza liczba porządkowa równoliczna z A (Piszemy |A|)
Własności relacji równości i nierówności dla mocy zbiorów: Zbiory skończone: Mówimy, że zbiór A jest skończony  |A|=n, n N.
Twierdzenia o mocy: |A|=m, |B|=n
Sumy: Iloczynu kartezjańskiego: Zbioru potęgowego: Zbioru funkcji dla zbiorów skończonych:
Zbiory nieskończone: Zbiory, które nie są skończone. Kryterium zbioru…
… relację taką, że .
Funkcje:
Obcięcie funkcji: Ograniczenie funkcji do podzbioru jej dziedziny. Iloczyn kartezjański funkcji: Niech i . Iloczynem kartezjańskim funkcji i nazywamy funkcję: .
Uwaga: !!!
Zestawienie funkcji: Niech i . Zestawieniem funkcji i nazywamy funkcję: , ( , ): .
Funkcja odwrotna: Relacja odwrotna do funkcji injektywnej.
Injekcja: .
Surjekcja: Zwf=Y  .
Bijekcja: Injekacja + surjekcja.
Obraz zbioru A przez funkcję f: Przeciwobraz zbioru B przez funkcję f: Twierdzenia o obrazach i przeciwobrazach: Twierdzenia o złożeniu funkcji i funkcji odwrotnej:
istnieje dokładnie jedna funkcja odwrotna do f.
Twierdzenia o injekcji, surjekcji i bijekcji: Iloczyn kartezjański injekcji (surjekcji, bijekcji) jest injekcją (surjekcją, bijekcją).
Zestawienie injekcji (surjekcji, bijekcji) jest injekcją…
…. Wtedy dla dowolnej funkcji zdaniowej prawdziwe jest zdanie:
Związek dobrego uporządkowania ze spełnieniem zasady indukcji:
Teoria mocy:
Zbiory równoliczne: Mówimy, że zbiór A jest równoliczny ze zniorem B : : f-bijekcja (Piszemy A~B).
Twierdzenia o równoliczności zbiorów: A~A
A~B => B~A
Twierdzenie Cantora-Bernsteina: Jeżeli A jest równoliczny z podzbiorem zbioru B i B jest równoliczny z podzbiorem zbioru…
... zobacz całą notatkę