Powrót
Teoretyczne podstawy informatyki i elementy logiki (2023/2024)
Wykład odbywa się w czwartki w godz. 11:15 - 13:00 w sali A.1.14 C-19.
W dniu 14.03 wykład będzie wyjątkowo w godz. 9:15 - 11:00 w sali A.1.14 C-19.
Wykład przeznaczony jest dla studentów Matematyki WMat PWr.
Materiały
Literatura podstawowa
- Z. Adamowicz, P. Zbierski, Logika matematyczna, PWN, 1991
- J. Hopcroft, J. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN,1994
- Ch. Papadimitriou, Złożoność obliczeniowa WNT, 2002
Zaliczenie kursu
Ćwiczenia
Na ćwiczeniach można zdobyć punkty za aktywność.
Kolokwium zaliczeniowe
Kolokwium zaliczeniowe odbędzie się na ostatnim wykładzie. Będzie można na nim zdobyć 36 punktów.
Na kolokwium trzeba mieć coś do pisania i ewentualnie czystą kartkę na brudnopis. Wszelkie inne pomoce są nielegalne!
Ocena końcowa
Ocena z ćwiczeń zależy od sumy $K+A$, gdzie $K$ to liczba punktów z kolokwium, $A$ - liczba punktów z aktywności.
Ocena będzie wystawiona na podstawie tabelki:
Punkty | Ocena |
0-15 | 2.0 |
16-19 | 3.0 |
20-23 | 3.5 |
24-27 | 4.0 |
28-31 | 4.5 |
32-35 | 5.0 |
36-$\infty$ | 5.5 |
Zrealizowany materiał
- Struktura pierwszego rzędu
- Życiowe (i nie tylko) przykłady struktur
- Język, termy, formuły
- Definicja spełniania $\mathbb{M}\models\varphi$
- Dowód, czyli $T\vdash \varphi$
- Aksjomaty Klasycznego Rachunku Logicznego
- Aksjomaty równości
- Reguły dowodzenia: Modus Ponens, reguła generalizacji
- Twierdzenie o dedukcji: $T\vdash \varphi\rightarrow\psi$ jest równoważne $T\cup\{\varphi\}\vdash \psi$
- Dowód twierdzenia o dedukcji
- Teorie
- Teora sprzeczna i niesprzeczna
- Teoria zupełna
- Teoria modelu $Th(\mathbb{M})$, model teorii
- Twierdzenie Godla
- Każda niesprzeczna teoria ma model
- Dowód (w przypadku języka przeliczalnego)
- Podstruktury
- Izomorfizm
- Elementarna podstruktura
- Elementarna równoważność
- Test Tarskiego-Vaughta
- Twierdzenie Lowenheima-Skolema (dolne i górne)
- przykład "życiowej" teorii zupełnej $DLO_0$
- Gry Erenfeuhta-Fraisego
- Opis gry
- Strategia
- Twierdzenie o charakteryzacji elementarnej równoważności modeli (w języku relacyjnym)
- Przykład zastosowania
- Ultraprodukty
- Produkty
- Filtry, ultrafiltry
Powrót