Katedra Podstaw Informatyki
Politechnika Wrocławska

Matematyka w liceum ZSA: 2014/15

Omówione zagadnienia

Po każdym wykładzie umieszczane są na tej stronie najważniejsze fakty, twierdzenia i definicje, które powinniście po nim zapamiętać. Oto lista omówionych zagadnień:

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)$
Prawa te możemy dowodziliśmy za pomocą tabelek zero-jedynkowych.
Materiały pomocnicze:
  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))$
Materiały pomocnicze:
  1. Lista zadań: Zbiory
  2. Rozdział II i III z książki Wykłady ze Wstępu do Matematyki

Alternatywna notacja

W szkole średniej spotkać się możecie z innymi oznaczeniami kwantyfikatorów: $\bigwedge$ oraz $\bigvee$. Oto ich tłumaczenie $$(\forall x)\varphi(x) \equiv \bigwedge_{x} \varphi(x)$$ oraz $$(\exists x)\varphi(x) \equiv \bigvee_{x} \varphi(x)$$ Notacja $\exists$ oraz $\forall$ jest powszechnie stosowana w literaturze naukowej na całym świecie. A oto lista kilku innych ważnych własności kwantyfikatorów:
  1. $(\forall x)(\varphi(x) \land \psi(x)) \equiv \big( (\forall x)(\varphi(x)) \land (\forall x)(\psi(x)) \big)$
  2. $\big((\forall x)(\varphi(x)) \lor (\forall x)( \psi(x))\big) \Rightarrow (\forall x)(\varphi(x) \lor \psi(x))$
  3. $(\exists x)(\varphi(x) \lor \psi(x)) \equiv \left( (\exists x)(\varphi(x)) \lor (\exists x)(\psi(x)) \right)$
  4. $(\exists x)(\varphi(x) \land \psi(x)) \Rightarrow \big( (\exists x)(\varphi(x)) \land (\exists x)(\psi(x)) \big)$
×

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\}$
Materiały pomocnicze:
  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)$.
Materiały pomocnicze:
  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.
Materiały pomocnicze:
  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\}$
Materiały pomocnicze:
  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))$
Materiały pomocnicze:
  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}$.
Materiały pomocnicze:
  1. Lista zadań: Permutacje i podzbiory
  2. Rozdział VII z książki Wykłady ze Wstępu do Matematyki