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

  1. Z. Adamowicz, P. Zbierski, Logika matematyczna, PWN, 1991
  2. J. Hopcroft, J. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN,1994
  3. 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:
PunktyOcena
0-152.0
16-193.0
20-23 3.5
24-27 4.0
28-31 4.5
32-35 5.0
36-$\infty$ 5.5

Zrealizowany materiał

  1. Struktura pierwszego rzędu
    1. Życiowe (i nie tylko) przykłady struktur
    2. Język, termy, formuły
    3. Definicja spełniania $\mathbb{M}\models\varphi$
  2. Dowód, czyli $T\vdash \varphi$
    1. Aksjomaty Klasycznego Rachunku Logicznego
    2. Aksjomaty równości
    3. Reguły dowodzenia: Modus Ponens, reguła generalizacji
    4. Twierdzenie o dedukcji: $T\vdash \varphi\rightarrow\psi$ jest równoważne $T\cup\{\varphi\}\vdash \psi$
    5. Dowód twierdzenia o dedukcji
  3. Teorie
    1. Teora sprzeczna i niesprzeczna
    2. Teoria zupełna
    3. Teoria modelu $Th(\mathbb{M})$, model teorii
  4. Twierdzenie Godla
    1. Każda niesprzeczna teoria ma model
    2. Dowód (w przypadku języka przeliczalnego)
  5. Podstruktury
    1. Izomorfizm
    2. Elementarna podstruktura
    3. Elementarna równoważność
    4. Test Tarskiego-Vaughta
    5. Twierdzenie Lowenheima-Skolema (dolne i górne)
    6. przykład "życiowej" teorii zupełnej $DLO_0$
  6. Gry Erenfeuhta-Fraisego
    1. Opis gry
    2. Strategia
    3. Twierdzenie o charakteryzacji elementarnej równoważności modeli (w języku relacyjnym)
    4. Przykład zastosowania
  7. Ultraprodukty
    1. Produkty
    2. Filtry, ultrafiltry

Powrót