02.10.2023: Rachunek Zdań - I

1. Pojęcie zdania rachunku zdań ($\mathcal{L}(\mathcal{P})$)
2. Pojęcie waluacji i rozszerzenie waluacji $\pi$ na dowolne zdania ($val(\pi,\phi)$)
3. Pojęcie tautologii: $\phi \in \mathcal{L}(\mathcal{P})$ jest TAUTOLOGIĄ ($\models \phi$), jeśli dla dowolnej waluacji $\pi:\mathcal{P}\to \{0,1\}$ mamy $val(\pi,\phi) = \mathbb{1}$
4. Przykłady:
   • $\models(p \lor q) \IFF (q \lor p)$
   • $\models (p\land q) \IFF (q \land p)$

Zadanie domowe: naucz się całego alfabetu greckiego.

06.10.2023: Rachunek Zdań - najważniejsze tautologie

1. Oznaczenie: $\phi\equiv \psi$ oznacza $\models (\phi \IFF \psi)$
2. Łączność: $(p\land(q\land r)) \equiv ((p\land q)\land r)$ i jej konsekwencje
3. Prawa de Morgana: $\neg(p\lor q) \equiv ((\neg p) \land (\neg q))$, $\neg(p\land q) \equiv ((\neg p) \lor (\neg q))$
4. Prawo eliminacji implikacji: $(p\to q) \equiv (\neg p \lor q)$
5. Wniosek: Za pomocą spójników $\land$ i $\neg$ można zdefiniować spójniki $\lor$, $\to$,$\IFF$

10.10.2023: Rachunek Zdań: synteza formuł

1. Spójnki XOR
2. Synteza formuł
3. Literał: zmienna lub jej negacja
4. Postać dyzjunkcyjno normalna: $\bigvee_{i=1}^{n} \bigwedge_{j=1}^{k_i} L_i^{(j)}$
5. Postać konjunkcyjno normalna: $\bigwedge_{i=1}^{n} \bigvee_{j=1}^{k_i} L_i^{(j)}$
6. Problem P=NP

13.10.2023: Rachunek Zdań: pojęcie konsekwencji

1. Tautologie i metody dowodzenia twierdzeń.
2. Rozumowanie cykliczne: $$\models \large((p_1\to p_2)\land (p_2\to p_3)\land\ldots (p_{n-1}\to p_n)\land (p_n\to p_1)\large) \to \bigwedge_{i=1}^{n} \bigwedge_{j=}^{n} (p_i \IFF p_j)$$
3. Pojęcie konsekwencji: $\{\phi_1,\ldots,\phi_n\}\models \psi$
4. Podstawowe własności konsekwencji.
5. Metoda Rezolucji: $\{\phi\lor\alpha,\neg\phi\lor\beta\}\models (\alpha\lor\beta)$

20.10.2023: Zbiory - I

1. Aksjomat Ekstensjonalności.
2. Własności sumy, przekroju i różnicy zbiorów
3. Operacja wyróżniania: $\{x\in X: \phi(x)\}$
4. Tw.(Russel) Nie istnieje zbiór wszystkich zbiorów.
5. Dopełnienie zbioru: $A^c = \Omega \setminus A$ (Uwaga: zakładamy, że $A\subseteq \Omega$).
6. Prawa de Morgana: $(A\cup B)^c = A^c \cap B^c$, $(A\cap B)^c = A^c \cup B^c$

24.10.2023: Zbiory - II

1. Składowe rodziny $\{A,B\}$.
2. Tw. Dla dowolnych zbiorów $A$ i $B$ następujące zdania są równoważne:
   • $A \subseteq B$
   • $A \cup B = B$
   • $A \cap B = B$
3. Para uporządkowana (Kuratowski): $(x,y) = \{\{x\},\{x,y\}\}$
4. Tw. $(x,y)=(u,v) \IFF ((x=u) \land (y=v))$
5. Iloczyn kartezjański

27.10.2023: Kwantyfikatory - I

1. Diagramy Venna.
2. Funkcja zdaniowa na uniwersum $\Omega$: dowolne przyporządkowanie $\phi$ elementom uniwersum $\Omega$ wartości logicznej $\phi(x) \in \{\mathbf{0},\mathbf{1}\}$
3. Dziedzina funkcji zdaniowej: $\|\phi\| = \{\omega\in\Omega: \phi(\omega) = \mathbf{1}\}$.
4. Definicja:
   • $(\exists x)\phi(x) \equiv (\|\phi| \neq \emptyset)$
   • $(\forall x)\phi(x) \equiv (\|\phi\| = \Omega)$
5. Prawa de Morgana:
   1. $\neg(\exists x)\phi(x) \IFF (\forall x)(\neg \phi(x))$
   2. $\neg(\forall x)\phi(x) \IFF (\exists x)(\neg \phi(x))$
6. Podstawowe własności
   1. $(\exists x)(\phi(x)\lor\psi(x)) \IFF (((\exists x)\phi(x)) \lor ((\exists x)\psi(x)))$
   2. $(\exists x)(\phi(x)\land\psi(x)) \to (((\exists x)\phi(x)) \land ((\exists x)\psi(x)))$
   3. $(\forall x)(\phi(x)\land\psi(x)) \IFF (((\forall x)\phi(x)) \land ((\forall x)\psi(x)))$
   4. $(((\forall x)\phi(x)) \lor ((\forall x)\psi(x))) \to (\forall x)(\phi(x)\lor\psi(x))$

7.11.2023: Kwantyfikatory - II

10.11.2023: Kwantyfikatory i relacje

1. Determinacja dwu osobowych gier skończonych.
2. Def. $R$ jest relacją wtedy i tylko wtedy, gdy istnieje zbiór $X$ taki, że $R\subseteq X\times X$
3. Def. $dom(R) = \{x:(\exists y)(x,y)\in R\}$; $rng(R) = \{y:(\exists x)(x,y)\in R\}$
4. Wniosek. $R\subseteq dom(R)\times rng(R)$
5. Def. $(y,x) \in R^{-1} \IFF (x,y) \in R$
6. Def. $(x,z)\in R\circ S \IFF (\exists y)((x,y)\in S \land (y,z)\in T)$
7. Tw. $(R\circ S)^{-1} = S^{-1} \circ R^{-1}$
8. Tw. $(R\circ S)\circ S = R \circ (S\circ T)$