Tautologie

• Data: 17.02.2015
• Wykładowca: prof. dr hab. Jacek Cichoń

Wykład poświęcony był pojęciu tautologii oraz przeglądowi najważniejszych tautologii.

1. Zasada podwójnej negacji: $\neg\neg p \leftrightarrow p$
2. Przemienność alternatywy i koniunkcji: $(p \lor q) \leftrightarrow (q \lor p)$, $(p \land q) \leftrightarrow (q \land p)$
3. Łączność alternatywy i koniunkcji: $\big((p \lor q) \lor r\big) \leftrightarrow \big(p \lor (q \lor r)\big) $, $\big((p \land q) \land r\big) \leftrightarrow \big(p \land (q \land r)\big)$
4. Prawo de'Morgana dla alternatywy: $\neg (p \lor q) \leftrightarrow (\neg p \land \neg q)$
5. Prawa de'Morgana dla koniunkcji: $\neg (p \land q) \leftrightarrow (\neg p \lor \neg q)$
6. Prawo eliminacji implikacji: $ (p \rightarrow q) \leftrightarrow (\neg p \lor q)$

1. Lista zadań: Tautologie
2. Rozdział I z książki Wykłady ze Wstępu do Matematyki

Zbiory i kwantyfikatory

• Data: 24.02.2015
• Wykładowca: prof. dr hab. Jacek Cichoń

1. Zasada ekstensjonalności: dwa zbiory są równe wtedy i tylko wtedy, gdy mają te same elementy.
2. Przemienność sumy i przekroju zbiorów: $A \cup B = B \cup A$, $A \cap B = B \cap C$
3. Łączność sumy i przekroju zbiorów: $(A \cup B) \cup C = A \cup (B \cup C)$, $(A \cap B) \cap C = A \cap (B \cap C)$
4. Nie istnieje zbiór wszystkich zbiorów. Mówiąc o dopełnieniu zbiorów zawsze powinniśmy pamiętać do jakiego zbioru dopełniamy !!!
5. Prawa de'Morgana dla sumy zbiorów: $(A \cup B)^c = A^c \cap B^c$
6. Prawo de'Morgana dla przekroju zbiorów: $(A \cap B)^c = A^c \cup B^c$
7. Dla własności $\varphi(x)$ elementów zbioru $X$:
   1. Wyrażenie $(\forall x)\varphi(x)$ oznacza, że $\{\omega \in \Omega: \varphi(x) \} = X$.
   2. Wyrażenie $(\exists x)\varphi(x)$ oznacza, że $\{\omega \in \Omega: \varphi(x) \} \neq \emptyset$.
8. Prawa de'Morgana dla kwantyfikatora ogólnego: $\neg(\forall x)\varphi(x) \equiv (\exists x)(\neg \varphi(x))$
9. Prawa de'Morgana dla kwantyfikatora egzystencjalnego: $\neg(\exists x)\varphi(x) \equiv (\forall x)(\neg \varphi(x))$

1. Lista zadań: Zbiory
2. Rozdział II i III z książki Wykłady ze Wstępu do Matematyki

Operacje teorio-mnogościowe

• Data: 03.03.2015
• Wykładowca: dr Szymon Żeberski

1. Różnica symetryczna zbiorów: $A \triangle B = (A\setminus B) \cup (B\setminus A)$
2. Własności różnicy symetrycznej:
   1. Przemienność: $A \triangle B = B \triangle A$
   2. Łączność: $(A \triangle B)\triangle C =A \triangle (B\triangle C)$
   3. $A \triangle A = \emptyset$, $A \triangle \emptyset = A$
3. Para nieuporządkowana: $x \in \{a,b\} \leftrightarrow (x=a \lor x=b)$
4. Para uporządkowana: $(a,b) = \{\{a\}, \{a,b\}\}$
5. Podstawowa własność pary uporządkowanej: $(a,b) = (c,d) \leftrightarrow ((a=c) \land (b=d))$
6. Iloczyn kartezjański zbiorów: $A\times B = \{(a,b):a\in A \land b \in B\}$

1. Diagram Venna
2. Lista zadań: Operacje teoriomnogościowe
3. Rozdział II i III z książki Wykłady ze Wstępu do Matematyki

Relacje

• Data: 31.03.2015
• Wykładowca: dr Szymon Żeberski

1. Relacja $R$ jest to podzbiór $X\times X$ dla pewnego zbioru $X$.
2. Diagram relacji.
3. Podstawowe klasy relacji:
   1. $R$ jest zwrotna na $X$, jeśli $(\forall x\in X)(x,x)\in R$;
   2. $R$ jest symetryczna, jeśli $(\forall x,y)((x,y)\in R\rightarrow (y,x)\in R)$;
   3. $R$ jest słabo antysymetryczna, jeśli $(\forall x,y)((x,y)\in R\land (y,x)\in R\rightarrow x=y)$;
   4. $R$ jest przechodnia, jeśli $(\forall x,y,z)((x,y)\in R\land (y,z)\in R\rightarrow (x,z)\in R)$;
4. Relacja odwrotna: $R^{-1}=\{(x,y):\ (y,x)\in R\}$
5. Złożenie relacji: $R\circ S = \{(x,y):\ (\exists z)((x,z)\in S\land (z,y)\in R)\}$
6. Własności operacji na relacjach:
   1. $(R\circ S)^{-1}=S^{-1}\circ R^{-1},$
   2. $(R\circ S)\circ T= R\circ (S\circ T)$.

1. Lista zadań: Relacje
2. Rozdział IV z książki Wykłady ze Wstępu do Matematyki

Częściowe porządki

• Data: 14.04.2015
• Wykładowca: dr Szymon Żeberski

1. Relacja $R$ jest częściowym porządkiem na zbiorze $X$ jeśli
   1. $R$ jest zwrotna na $X$,
   2. $R$ jest przechodnia,
   3. $R$ jest słabo antysymetryczna.
2. Diagram Hassego.
3. Izomorfizm (podobieństwo) częściowych porządków.
4. Dowolny częściowy porządek jest izomorficzny z porządkiem $(\mathcal{A},\subseteq )$ dla pewnej rodziny zbiorów $\mathcal{A}$.
5. Wyróżnione elementy w częściowym porządku $(X,R)$:
   1. $a$ jest elementem najmniejszym, jeśli $(\forall x\in X)(aRx)$;
   2. $a$ jest elementem największym, jeśli $(\forall x\in X)(xRa)$;
   3. $a$ jest elementem minimalnym, jeśli $\neg(\exists x\in X)( x\neq a\land xRa)$;
   4. $a$ jest elementem maksymalnym, jeśli $\neg(\exists x\in X)( x\neq a\land aRx)$;
6. Każdy skończony porządek ma element minimalny i element maksymalny.

1. Lista zadań: Częściowe porządki
2. Rozdział VI z książki Wykłady ze Wstępu do Matematyki

Relacje równoważności

• Data: 12.05.2015
• Wykładowca: dr hab. inż. Marek Klonowski

1. Relacja równoważności na zbiorze $X$ to relacja na zbiorze $X$, która jest zwrotna na $X$, symetryczna i przechodnia.
2. Niech $\rho$ będzie relacją równoważności na zbiorze $X$. Wtedy
   1. Klasa abstrakcji elementu $x\in X$ nazywamy zbiór $[x]_\rho = \{y\in X: x\rho y\}$
   2. Twierdzenie o abstrakcji
      1. $(\forall x\in X)(x \in [x]_\rho)$;
      2. $(\forall x,y \in X)(x\rho y \rightarrow [x]_\rho = [y]_\rho)$;
      3. $(\forall x,y \in X)(\neg (x\rho y) \rightarrow [x]_\rho \cap [y]_\rho = \emptyset)$.
   3. Przestrzeń ilorazowa: $X/\rho = \{[x]_\rho: x \in X\}$

1. Lista zadań: Relacje równoważności
2. Rozdział V z książki Wykłady ze Wstępu do Matematyki

Indukcja matematyczna

• Data: 19.05.2015
• Wykładowca: prof. dr hab. Jacek Cichoń

1. Zasada Indukcji: Jeśli $A\subseteq \mathbb{N}$, $0\in A$ oraz $(\forall n)(n\in A \to n+1 \in A)$, to $A=\mathbb{N}$.
2. Wzmocniona Zasada Indukcji: Jeśli $A\subseteq \mathbb{N}$, $a\in A$ oraz $(\forall n \geq a)(n\in A \to n+1 \in A~)$, to $(\forall n\geq a)(n \in A)$.
3. $1+2+\ldots+n = \frac12 n(n+1)$
4. $1^2+2^2+\ldots+n^2 = \frac16 n(n+1)(2n+2)$
5. $(\forall n\in \mathbb{N})(n < 2^n)$
6. Suma kątów wewnetrznych w n-kącie wypukłym jest równa $(n-2)\pi$.
7. $(\forall n\in \mathbb{N})(3|(n^3+2n))$

1. Lista zadań Indukcja
2. Rozdział VII z książki Wykłady ze Wstępu do Matematyki
3. Rozdział I z książki: Richard Courant, Herbert Robbins, Co to jest matematyka ?

Zasada szufladkowa Dirichletta

• Data: 26.05.2015
• Wykładowca: dr Filip Zagórski

Permutacje i podzbiory

• Data: 02.06.2015
• Wykładowca: dr Szymon Żeberski

Oto lista najważniejszych definicji i faktów, które powinniście zapamiętać po tym wykładzie:

1. Niech $X$ będzie zbiorem. Zbiorem potęgowym $P(X)$ nazywamy zbiór wszystkich podzbiorów zbioru $X$. $P(X)=\{A:\ A\subseteq X\}$.
2. Jeśli $|X|=n$, to $|P(X)=2^n$.
3. Funkcję $\sigma: [n]\to [n]$ nazywamy permutacją jeśli $\sigma $ jest funkcję różnowartościową i na. ($[n]=\{1,2,\ldots,n\}$) Zbiór wszystkich permutacji zbioru $[n]$ oznaczymy $Perm([n])$.
4. Dla dowolnego $n\in\mathbb{N}$, $|Perm([n])|=n!$.
5. Symbol Newtona dla $0\le k\le n$ określony jest wzorem: $\displaystyle{n\choose k}=\frac{n!}{k!(n-k)!}$.
6. Jeśli zbiór $A$ ma $n$ elementówo, $k\le n$ oraz $[A]^k=\{B\subseteq A:\ |B|=k\}$, to $|[A]^k|={n\choose k}$.
7. $2^n=\sum_{k=0}^n{n\choose k}$.
8. $(x+y)^n=\sum_{k=0}^n{n\choose k}x^ky^{n-k}$.
9. Powyższy wzór ma kilka zastosowań:
   1. $\displaystyle 3^n=\sum_{k=0}^n{n\choose k}2^k$,
   2. $\displaystyle 0=\sum_{k=0}^n{n\choose k}(-1)^k$,
   3. $\displaystyle \sum_{k=0}^{\lfloor n/2\rfloor}{n\choose 2k} = \sum_{k=1}^{\lceil n/2\rceil}{n\choose 2k-1}=2^{n-1}$.

1. Lista zadań: Permutacje i podzbiory
2. Rozdział VII z książki Wykłady ze Wstępu do Matematyki