Wykład przeznaczony jest dla studentów I roku I stopnia Informatyki na WPPT.
Odbywa się w środy w godz. - oraz czwartki w godz. - w sali 130/C13.
Na stronie tej znajdziesz informacje o zasadach zaliczenia, literaturze, listę zadań oraz realizowanym materiale.
Zasady zaliczania kursu
Ćwiczenia
Na ćwiczeniach odbędą się trzy 45 minutowe kolokwia. Na każdym z nich dostaniecie do zrobienia 4 zadania. Za każde z nich będziecie mogli otrzymać do 4 punktów. Dodatkowo możecie dostać 12 punktów za aktywność na ćwiczeniach.
Ocena końcowa (C) z ćwiczeń będzie wystawiana za pomocą następującej tabelki:
Pkt
0..29
30..34
35..39
40..44
45..49
50..54
55..60
C
2.0
3.0
3.5
4.0
4.5
5.0
5.5
Egzamin
Termin I: 01.02.2019 (piątek), godz. 15:00-17:00, sala 322/A1
Termin II: 15.02.2019 (piątek), godz. 11:00-13:00, sala 322/A1
Do egzaminu muszą przystąpić wszyscy (włącznie z osobami, które dostały 5.5 za ćwiczenia).
Do egzaminu w terminie II przystąpić mogą tylko te osoby, które z egzaminu w pierwszym terminie otrzymały ocenę ndst (nie będą one miały wpisanej oceny do systemu Edukacja) - ale mam nadzieję, że takich osób nie będzie.
Na egzamin proszę przynieść kilka kartek papieru formatu A4.
Sposób oceniania i ocena końcowa
Na egzaminie dostaniecie do zrobienia 5 zadań. Za każde z nich będziecie mogli otrzymać do 6 punktów. Ocena (E) z egzaminu będzie wystawiana za pomocą następującej tabelki:
Pkt
0..14
15..17
18..19
20..22
23..24
25..27
28-30
E
2.0
3.0
3.5
4.0
4.5
5.0
5.5
Do indeksu zostanie wam wpisana ocena $K$ wyznaczana za pomocą następującego wzoru:
$$
K = \begin{cases} \max\{E,\frac{E+C}{2}\} &: E\geq 3\\ 2.0 &: E=2.0\end{cases}
$$
Wyniki pierwszego egzaminu
Oceny z pierwszego egzaminu skończyłem wprowadzać do systemuu "Edukacja" w dniu 03.02.2019 około godziny 19:30.
Osoby które nie widzą oceny w systemie muszą się, niestety, pojawić na drugim terminie.
Lista zadań z rozwiązaniami: LiSF_JCI_2019_T1.pdf.
Umówmy się, że każdy kto chciałby w najbliższych dniach ze mną się spotkać w celu omówienia któregoś z tych zadań będzie znał WSZYSTKIE rozumowania z powyższej listy.
Literatura
Podstawowa
K. Kuratowski, Wstęp do teorii mnogości i topologii, PWN,
W. Marek, J. Onyszkiewicz, Zbiór zadań z logiki i teorii mnogości, PWN,
K. Kuratowski, A. Mostowski, Teoria Mnogości, PWN, 1978
A. Błaszczyk, S. Turek, Teoria Mnogości, PWN, 2007
Lista zadań: LSF2018.pdf (uwaga: lista ta zostanie rozbudowana - na końcu pojawią się dodatkowe zadania)
Przykładowe zadania i lista zadań sprzed kilku lat: WDLiTM_Example.pdf,
WDLiTM_E1.pdf.
Dowiedzcie się również jakie zadania dał prof. Szymon Żeberski rok temu.
Def. Formuła jest w postaci dyzjunkcyjno normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami literałów
Def. Formuła jest w postaci konjiuncyjno normalnej (CNF) jeśli jest koniunkcją formuł które są klauzulami (czli alternatywami literałów).
Tw. Dla każdej formuły $\phi$ istnieją formuły $\psi$ i $\eta$ takie, że $\phi \equiv \psi \equiv \eta$ oraz $\psi$ jest w postaci DNF zaś $\eta$ jest w postaci CNF.
Formuła $\psi$ jest spełnialna jeśli istnieje waluacje $\pi$ taka, że $\pi(\psi) = 1$
Problem P=NP: czy istnieje algorytm $\mathbb{A}$ oraz wielomian $w(x)$ taki, że
dla dowolnej formuły $\phi$ w postaci CNF mamy
$\mathbb{A}(\phi)=1$ wtedy i tylko wtedy, gdy $\phi$ jest spełnialna
algorytm $\mathbb{A}$ na formula $\phi$ działa w czasie $w(\|\phi\|)$
Def. $\{\phi_1,\ldots,\phi_n\}\models \psi$ jeśli dla dowolnej waluacji $\pi$ takiej, że $\pi(\phi_1)=\ldots=\pi(\phi_n) = 1$ mamy również $\pi(\psi)=1$.
Twierdzenie. Następujące zdania są równoważne:
$\{\phi_1,\ldots,\phi_n\}\models \psi$
$\models (\phi_1\land\ldots\land\phi_n) \to \psi$
Na razie udowodniliśmy, że $(1) \to (2)$.
Notatki:
10.10.2018: Rachunek Zdań i Zbiory
Twierdzenie. Następujące zdania są równoważne:
$\{\phi_1,\ldots,\phi_n\}\models \psi$
zbiór zdań $\{\phi_1,\ldots,\phi_n, \neg\psi\}$ jest sprzeczny
Przykład (Modus Ponens): $\{\phi,\phi\to\psi\}\models \psi$
Przykład (Rezolucja): $\{\phi \lor \alpha, \neg\phi\lor\beta\}\models \alpha \lor \beta$
Składowe rodziny $\{A_1,\ldots, A_n\}$: zbiory postaci $A_1^{\epsilon_1} \cap \ldots A_n^{\epsilon_n}$, gdzie $\epsilon_1, \ldots, \epsilon_n \in \{0,1\}$ oraz $A^0=A$ i $A^1 = A^c$
Zbiór potęgowy $P(X)$ = zbiór wszystkich podzbiorów zbioru $X$.
Fakt. Jeśli $f$ jest funkcją, to $f^{-1}[A] = \{x\in dom(f): f(x) \in A\}$
Wniosek. Jeśli $f$ jest funkcją to $f^{-1}[A\cap B] = f^{-1}[A] \cap f^{-1}[B]$.
Def. Funkcja $f$ jest injekcją, jeśli $(\forall x_1,x_2)(f(x_1)=df(x_2) \to x_1=x_2)$
Def. Funkcja $f:A\to B$ jest surjekcją, jeśli $(\forall b\in B)(\exists a\in A)(f(a)=b)$
Tw. Złożenie injekcji jest injekcją
Wniosek. Jeśli $f$ jest funkcją, to $f^{-1}$ jest funkcją wtedy i tylko wtedy, gdy $f$ jest injekcją.
Tw. Złożenie surjekcji jest surjekcją
Def $f$ jest bijekcją, jeśli $f$ jest jednocześnie injekcją i surjekcją
Wniosek. Złożenie bijekcji jest bijekcją
Def. $|A|=|B| \IFF$ istnieje bijekcja między A i B
Trochę przyglądaliśmy się hotelom Elona Muska na Księżycu.
Def. Niech $R$ będzie relacją na zbiorze $X$.
$R$ jest zwrotna na $X$, jeśli $(\forall x\in X)((x,x)\in R)$
$R$ jest symetryczna, jeśli $(\forall x, y\in X)((x,y)\in R \to (y,x) \in R)$
$R$ jest przechodnia, jeśli $(\forall x,y,z\in X)(((x,y)\in R \land (y,z)\in R)) \to (x,z)\in R$
$R$ jest słabo antysymetryczna, jeśli $(\forall x,y\in X)(((x,y)\in R\land (y,x)\in R)\to x=y)$
Notatki:
29.10.2018: Relacje równoważności
Przykład: $\emptyset^{\emptyset} = \{\emptyset\}$; dla dowolnego zbioru $X$ mamy $X^\emptyset = \{\emptyset\}$; jeśli $X\neq\emptyset$ to $\emptyset^X = \emptyset$
Fakt. Niech $Id_X = \{(x,x):x\in X\}$. Relacja $R\subseteq X\times X$ jest zwrotne na $X$ wtedy i tylko wtedy, gdy $Id_X\subseteq R$.
Def. Relacja $\sim \subseteq X\times X$ jest relacją równoważności na $X$ jeśli jest zwrotna na $X$, symetryczna i przechodnia
Przykład: Na zbiorze liczb całkowitych $\ZZ$ określamy relację
$$
x \sim y \IFF 5|(x-y)
$$
To jest relacja równoważności na $\ZZ$.
Niech $\sim$ będzie relacją równoważności na $X$. Klasą abstrakcji elementu $a\in X$ (względem relacji $\sim$) nazywamy zbiór
$$
[a]_\sim = \{x\in X: a \sim x\}~.
$$
Niech $\sim$ będzie relacją równoważności na $X$. Wtedy
$(\forall a \in X)(a\in[a]_\sim)$
$(\forall a,b \in X)(a\sim b \to [a]_\sim = [b]_\sim)$
Przykład: dla przykładu z podzielnością przez 5 mamy:
$[0]_\sim = \{5k: k\in\ZZ\}$,
$[1]_\sim = \{5k+1: k\in\ZZ\}$,
$[2]_\sim = \{5k+2: k\in\ZZ\}$,
$[3]_\sim = \{5k+3: k\in\ZZ\}$,
$[4]_\sim = \{5k+4: k\in\ZZ\}$.
Def. Partycją (rozbiciem) zbioru $X$ nazywamy taką rodzinę zbiorów $\mathcal{A}$, że
$(\forall A\in\mathcal{A})(\emptyset \neq A \subseteq X)$
$(\forall A,B\in\mathcal{A})(A\neq B \to A\cap B = \emptyset)$
$\bigcup\mathcal{A} = X$
Def. Jeśli $\sim$ jest relacją równoważności na $X$, to
$$
X/_\sim = \{[a]:a\in X\}
$$
Wniosek: Jeśli $\sim$ jest relacją równoważności na $X$, to $X/_\sim$ jest rozbiciem zbioru $X$
Notatki:
7.11.2018: Relacje równoważności
Tw. Niech $\mathcal{P}$ będzie partycją zbioru $X$. Wtedy relacja
$$
x \sim y \IFF (\exists P\in\mathcal{P})(\{x,y\}\subseteq P)
$$
jest relacją równoważności na $X$ oraz $X/\sim = \mathcal{P}$
Tw. $f:X\to Y$. Na zbiorze $X$ definiujemy relację
$$
x\sim_f y \IFF (f(x)=f(y))
$$
Relacja $\sim_f$ jest relacją równoważności na $X$.
Def. Niech $(X,\leq)$ będzie częściowym porządkiem i $a\in X$.
$a$ jest największy w $(X,\leq)$ jeśli $(\forall x\in X)(x\leq a)$
$a$ jest najmniejszy w $(X,\leq)$ jeśli $(\forall x\in X)(a\leq x)$
$a$ jest maksymalny w $(X,\leq)$ jeśli $(\forall x\in X)(a\leq x \to x=a)$
$a$ jest minimalny w $(X,\leq)$ jeśli $(\forall x\in X)(x\leq a \to x=a)$
Tw. Element największy jest maksymalny.
Def. Częściowe porządki $(X,\leq)$, $(Y,\preceq)$ są izomorficzne jeśli istnieje bijekcja $f:X\to Y$ taka, że
$$
(\forall x,y\in X)((x\leq y) \IFF (f(x)\preceq f(y)))~.
$$
Tw. Niech $(X,\leq)$ będzie częściowym porządkiem oraz $\phi(x) = \{y\in X: y \leq x\}$.
Wtedy $\phi$ jest izomorfizmem między $(X,\leq)$ oraz $(rng(\phi),\subseteq)$.
Notatki:
14.11.2018: Aksjomat wyboru
Def: Para $(X,\leq)$ jest liniowym porządkiem na zbiorze $X$ jeśli $(X,\leq)$ jest częściowym porządkiem takim, że
$(\forall x,y \in X)(x\leq y \lor y \leq x)$.
Obserwacja: w linowych porządkach pojęcia elementu najmniejszego i elementu minimalnego pokrywają się
Def. Niech $(X,\leq)$ będzie częściowym porządkiem. Zbiór $A\subseteq X$ jest łańcuchem, jeśli $(\forall x,y \in A)(x\leq y \lor y\leq x)$
LEMAT KURATOWSKIEGO ZORNA (LKZ) W każdym częściowym porządku o następującej własności: każdy łańcuch ma ograniczenie górne
istnieje element maksymalny.
AKSJOMAT WYBORU (AC): Jeśli $\mathcal{A}$ jest taką rodziną zbiorów, że $(\forall A\in\mathcal{A})(A\neq\emptyset)$ oraz $(\forall A,B\in\mathcal{A})(A\neq B\to A\cap B =\emptyset)$ to istnieje zbiór $S\subseteq \bigcup\mathcal{A}$ takie, że $(\forall A\in\mathcal{A})(|A\cap S|=1)$,
czyli: każda rodzina zbiorów niepustych, parami rozłącznych ma selektor.
TW. LKZ $\to$ AC
Określenie: rodzina zbiorów indeksowana zbiorem $T$: dowolna funkcja o dziedzinie $T$, której wartościami są zbiory; stosujemy następujące oznaczenie $(F_t)_{t\in T}$ na $F$.
Fakt. Jeśli $(\forall t\in T)(A_t = A)$ to $\prod_{t\in T} A_t = A^T$.
Przykład: Niech $T=\{1,2,3\}$. Definiujemy funkcję $\phi:A_1\times (A_2 \times A_3) \to \prod_{t\in T}A_t$ wzorem
$\phi((a,b,c)) = \{(1,a), (2,b), (3,c)\}$. To jest bijekcja.
Fakt: jeśli $(X,\leq)$ jest częściowym porządkiem oraz $A\subseteq X$, to $(A,\leq\cap A\times X)$ też jest częściowym porządkiem
Produkt dwóch częściowych porządków.
Def. Liniowy porządek $(X,\leq)$ jest dobrym porządkiem jeśli
$$
(\forall A\subseteq X)(A\neq \emptyset \to (\exists a\in A)(\forall x \in A)(a\leq x))
$$
Zasada Indukcji Matematycznej: zbiór $(\NN,\leq)$ jest dobrym porządkiem
Tw. Z Zasady Indukcji Matematycznej wynika, że
$$
(\forall A\subseteq \NN)((0\in A \land (\forall n)(n\in A\to n+1\in A)) \to A = \NN)~.
$$
Uwaga: to jest standardowe sformułowanie Zasady Indukcji Matematycznej.
Przykład: Niech $A = \{1-\frac{1}{n+1}:n\in\NN\} \cup \{2-\frac{1}{n+1}:n\in\NN\}$. Para $(A\leq)$ jest dobrym porządkiem
Tw. Nie istnieje ciąg liczb naturalnych $(a_n)_{n\in\NN}$ taki, że $(\forall n)(a_n \gt a_{n+1})$
Uwaga: na razie tego nie udowodniliśmy.
nie istnieje nieskończony ostro malejący ciąg liczb naturalnych
Tw (Zasada Dirichletta; zasada gołębnika). Jeśli $n\gt m$ oraz $f:\{1,\ldots,n\} \to \{1,\ldots,m\}$, to $f$ nie jest injekcją
Tw. Załóżmy, że $|X|=|Y| = n$ oraz $f:X\to Y$. Wtedy następujące warunki sa równoważne:
$f$ jest injekcją
$f$ jest surjekcją
Tw. Jeśli $(X,\leq)$ jest częściowym porządkiem i $X$ jest zbiorem skończonym, to istnieje \liniwy porządek $\preceq$ na zbiorze $X$ taki, że $\leq \ \subseteq\ \preceq$
Przykłady definicji rekurencyjnych:
suma(n,0) = n
suma(n,m+1) = suma(n,m)+1
razy(n,0) = 0
razy(n,m+1) = suma(razy(n,m),n)
Notatki:
22.11.2018: Rekursja
Otoczka (domknięcie) Kleene'ego:
$A_0 = \emptyset$
$A_k = A^{\{0,\ldots,k-1\}}$ dla $k\geq 1$
$A^* = \bigcup_k A_k$
Tw (o rekursji). Załóżmy, że $F:A^*\to A$. Istnieje wtedy dokładnie jedna funkcja $f:\NN\to A$ taka, że
$$ (\forall n\in\NN) (f(n) = F(f|n)),$$
gdzie $f|n$ oznacza obcięcie funkcji do zbioru $\{0,\ldots,n-1\}$
Konkatenacja ciągów z $A^*$: $[a_0,\ldots,a_n] :: [b_0,\ldots,b_m] = [a_0,\ldots,a_n,b_0,\ldots,b_m]$
Definicja: Struktura $(M,e,\star)$ jest monoidem jeśli $\star$ jest łącznym działaniem binarnym na $M$ zaś $e$ jest elementem neutralnym tego działania.
Przykład: $(A^*,[],::)$ jest monoidem
Tw. Załóżmy, że $(M,e,\star)$ jest monoidem oraz $f:A \to M$. Istnieje wtedy dokładnie jeden homomorfizm $f^*: (A^*,[],::)\to (M,e,\star)$ takie, że $(\forall a\in A)(f^*([a]) = f(a))$.
Przykład: Jeśli $f(a)=1$ dla każdego $a\in A$ a monoidem jest $(\NN,0,+)$ to $f^*(x) = $ długość ciągu $x$
Notatki:
28.11.2018: Porządek leksykograficzny
Def. Jeśli $(X,\leq)$ i $(Y,\preceq)$ są liniowymi porządkami to ich produktem leksykograficznym jest
porządek na $X\times Y$ okreslony wzorem
$$
((x,y) \lt_{lex} (x',y')) \IFF ( (x \lt x') \lor (x=x' \land (y \prec y')))
$$
Fakt. $\lt_{lex}$ jest liniowym porządkiem
Tw. Jeśli $(X,\leq)$ i $(Y,\preceq)$ są dobrymi porządkami , to ich produkt leksykograficzny jest również dobrym porządkiem
Porządek na $L^{\NN}$ ($L$ jest liniowo uporządkowany przez $\preceq$):
$$
f \leq g \IFF (f=g) \lor (\exists k)(f(k)\prec g(k) \land (\forall l\lt k)(f(l)=g(l)))
$$
Fakt: Tak skonstruowany porządek jest liniowym porządkiem na $L^{\NN}$
Tw. Jeśli $(A_n)_{n\in\NN}$ jest przeliczalną rodziną zbiorów przeliczalnych, to $\bigcup_n A_n$ jest zbiorem przeliczalnym.
Wniosek. Zbiór obliczalnych funkcji z $\NN$ do $\NN$ jest przeliczalny.
Wniosek. Istnieją funkcje które nie są obliczalne.
Metoda przekątniowa: Jeśli $F:\NN\to P(\NN)$ oraz $C= \{n\in\NN: n\notin F(n)\}$, to $C \notin rng(F)$
Metoda przekątniowa: Jeśli $(f_n)_{n\in\NN}$ jest ciągiem funkcji z $\\N^\NN$, oraz funkcja
$$ g(n) = f_n(n)+1~,$$ to $(\forall n\in\NN)(f\neq f_n)$.
Wniosek: Jeśli $(f_n)_{n\in\NN}$ jest ciągiem wszystkich funkcji obliczalnych, to funkcja $g(n)=f_n(n)+1$ nie jest obliczalna
Przykład: Podziel przez dwa lub pomnóż przez trzy i dodaj jeden:
function DM (n) {
var l = 0;
while (n != 1) {
l++;
if (n % 2 == 0) n = n/2
else n = 3 * n + 1
}
return l
}
console.log(DM(5))
O tej funkcji nie wiadomo, czy jest funkcją całkowitą (tzn. określoną dla wszystkich $n$) (jest to tak zwany problem Collatza)
Twierdzenie [Cantor]: Jeśli $(L,\preceq)$ jest gęstym liniowym porządkiem bez końców, to porządek $(L,\preceq)$ jest izomorficzny z porządkiem $(\QQ,\preceq)$.
Przykład: zbiory $\emptyset, P(\emptyset), P(P(\emptyset)), \ldots$ są tranzytywne
Def. [liczba porządkowa] $ord(x) = tran(x) \land (\forall u,v\in x)(u\in v \lor u=v \lor v \in u)$
Przykład: zbiór pusty jest liczbą porządkową
Przykład: liczby naturalne $\emptyset, S(\emptyset), S(S(\emptyset)), \ldots$ są liczbami porządkowymi
Lemat. $(\forall x) (ord(x) \to ord(S(x)))$, gdzie $S(x) = x \cup \{x\}$
Def. Niech $x$ będzie liczbą porządkową. Określamy relację
$$
u \leq v \IFF ((u \in v) \lor (u=v))
$$
Tw. Niech $x$ będzie liczbą porządkową. Wtedy $(x ,\leq)$ jest dobrym porządkiem.
Uwaga: warto zwrócić uwagę na to jak wykorzystaliśmy w dowodzie Aksjomat Regularności.
Lemat. Niech $x$ będzie liczbą porządkową oraz $u,v \in x$. Wtedy
$u \leq v \IFF u \subseteq v$.
Tw. $(\forall x,y)((ord(x)\land ord(y)) \to (x\in y \lor x=y \lor y \in x))$
Notatki:
09.01.2019, 10.01.2019: Liczby porządkowe i kardynalne
Twierdzenie o rekursji: Jeśli $(\forall x)(\exists! y)\phi(x,y)$ to dla dowolnej liczby porzędkowej $\alpha$ istnieje
dokładnie jedna funkcja $f$ taka, że $dom(f) = \alpha$ oraz
$$
(\forall \beta \lt \alpha) \phi(f|\beta,f(\beta))
$$
Def. Liczba porządkowa $\alpha$ jest następnikiem, jeśli itnieje liczba porządkowa $\beta$ taka, że $\alpha = \beta + 1$. Liczbę porządkową nazywamy graniczną jeśli jest większa od zera i nie jest następnikiem.
Dodawanie liczb porządkowych: $\alpha+0 = \alpha$, $\alpha+(\beta+1) = (\alpha+\beta)+1$; jeśli $\lambda$ jest graniczna, to $\alpha +\lambda = \bigcup\{\alpha+\xi:\xi\lt\lambda\}$.
Tw. Dla dowolnego dobrego porządku $(X,\leq)$ istnieje dokładnie jedna liczba porządkowa $\alpha$ taka, że $(X,\leq)$ jest izomorficzna $(\alpha,\leq)$. Co więcej, ten izomorfizm jest jedyny.
Tw. (AC) Każdy zbiór można dobrze uporządkować.
Def (Hartogs) Hartogsam zbioru $X$ ($H(X)$) nazywamy najmniejszą liczbę porządkową $\alpha$ taką, że nie istnieje injekcja z $\alpha$ w $X$.
Tw. Dla każdego zbioru $X$ istnieje $H(X)$
Def. $\aleph_{\alpha+1} = H(\aleph_{\alpha})$; jeśli $\lambda$ jest graniczna, to $\aleph_{\lambda} = \bigcup\{\aleph_{\xi}:\xi\lt\lambda\}$.