Jacek Cichoń

Katedra Podstaw Informatyki ● WIT ● PWr
Strona główna Moje zajęcia

2024/25 (zima): Logika i Struktury Formalne

Wykład przeznaczony jest dla studentów I roku I stopnia Informatyki Algorytmicznej. Odbywa się we wtorki w godz. - oraz piątki w godz. - w sali 23 w budynku C-3.
Wykład ten prowadzę wspólnie z doktorem Dominikiem Bojko.
Na stronie tej znajdziesz informacje o zasadach zaliczenia, literaturze, realizowanym materiale oraz listę zadań.

Literatura

Zasady zaliczania kursu

Ćwiczenia

Na ćwiczeniach będzie mieli dwa kolokwia (po 20 punktów). Oceniani będziecie również za aktywność na ćwiczeniach: do zdobycia będzie mieli dodatkowe 20 punktów. O reszcie detali zostaniecie poinformowani przez prowadzących ćwiczenia.

Egzamin

Ocena za kurs będzie wystawiana za pomocą wzoru: $$ K = \begin{cases} 2 &: E = 2 \\ \frac{E+C}{2} &: E>2 \end{cases}~, $$ gdzie $E$ = ocena z egzaminu zaś $C$ = ocena z ćwiczeń.

  1. Termin I: 06.02.2025, godz. 13:00-15:00, sala 329/A1
  2. Termin II: 17.02.2025, godz. 13:00-15:00, sala 41/C-4

$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\CC{\mathbb{C}} \def\NN{\mathbb{N}} \def\IFF{\leftrightarrow} \newcommand{\span}[1]{\mathrm{span}(#1)} \newcommand{\IS}[2]{\langle\,#1,#2\rangle} \newcommand{\sgn}[1]{\mathrm{sgn}(#1)} $

Zagadnienia omówione na wykładzie

04.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}$
Zadanie domowe: naucz się całego alfabetu greckiego.

08.10.2024: Rachunek Zdań - II

  1. Przegląd najważniejszych tautologii
  2. Spójniki NAND, NOR, XOR
  3. Synteza formuł
  4. Postać dyzjunkcyjno - normalna (DNF)
  5. Klauzule i postać koniunkcyjno normalna (CNF)

11.10.2024: Rachunek Zdań - III

  1. Pojęcie dowodliwości ($\mathcal{P}\models\phi$)
  2. Podstawowe reguły dowodzenia
  3. Klauzule Horna i zdania Horna
  4. Problem spełnialności.
  5. Spełnialność zdań Horna.

15.10.2023: Metody dowodzenia twierdzeń i Zbiory

  1. Przegląd metod dowodzenia twierdzeń
  2. Aksjomat Ekstensjonalości
  3. Jedyność zbioru pustego
  4. Suma i przekrój zbiorów
  5. Twierdzenie Russel'a: nie istnieje zbiór wszystkich zbiorów.

18.10.2023: Zbiory - I

  1. Podstawowe operacje: $\cup, \cap,\setminus$
  2. Zawieranie zbiorów
  3. Sprowadzenie zagadnień rachunku zbiorów do rachunku zdań
  4. Diagramy Venna

22.10.2023: Zbiory - II

  1. Skladowe rodzin zbiorów
  2. Para uporządkowana: $(x,y) = \{\{x\},\{x,y\}\}$ (definicja Kuratowskiego)
  3. Tw. $(x,y)=(a,b) \IFF (x=a)\land(y=b)$
  4. Iloczyn kartezjański zbiorów.

25.10.2023: Zbiory - III

  1. Tw. $A\times(B\cup C) = (A\times B) \cup $(A\times C)$
  2. Pojęcie funkcji logicznej jednej zmiennej.
  3. Kwantyfikatory $\forall$ i $\exists$
  4. Podstawowe własności kwantyfikatorów.

29.10.2023: Kwantyfikatory

  1. Kwantyfikatory ograniczone
  2. Funkcje zdaniowe wielu zmiennych.
  3. Interpretacja wyrażeń $(\forall x)(\forall y)\phi(x,y)$, $(\forall x)(\exists y)\phi(x,y)$, $(\exists x)(\forall y)\phi(x,y)$ i $(\exists x)(\exists y)\phi(x,y)$
  4. Podstawowe własności.
  5. Determinacja gier skończonych.

05.11.2023: Relacje

  1. Działania uogólnione
  2. Pojęcie relacji, dziedzina, obraz
  3. Tw. $(R\circ S)^{-1} = S^{-1}\circ R^{-1}$
  4. Tw. $(R\circ S)\circ T = R\circ (S\circ T)$.
  5. $R[A] = ...$

08.11.2023: Funkcje

  1. Definicja funkcji.
  2. Tw. Złożnie funkcji jest funkcją.
  3. Definicja injekcji i surjekcji
  4. Tw. Złożenie injekcji jest injekcją.
  5. Tw. Złożenie surjekcji jest surjekcją.
  6. Definicja bijekcji.
  7. Tw. Złożenie bijekcji jest bijekcją.
  8. Tw. Niech $f$ będzie funkcją. Wtedy ($f^{-1}$ jes funkcją) $\IFF$ ($f$ jest injekcją).
  9. Def. $|A|=|B| \IFF ...$
  10. Def. $|A| = n \IFF$
Strona główna Moje zajęcia