Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Logika matematyczna

Informacje ogólne

Kod przedmiotu: 1000-135LOM
Kod Erasmus / ISCED: 11.113 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Logika matematyczna
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty fakultatywne dla studiów 2 stopnia na matematyce
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

fakultatywne

Założenia (lista przedmiotów):

Wstęp do matematyki (potok I) 1000-111bWMAa

Skrócony opis:

Wprowadzenie do klasycznych zagadnień logiki matematycznej z elementami teorii modeli.

Jeśli w wykładzie nie będą uczestniczyć słuchacze obcojęzyczni, wykład będzie prowadzony po polsku.

Pełny opis:

Systemy relacyjne. Podsystem, zanurzenie, izomorfizm. Algebry

Boole'a. (4 wykłady)

Język logiczny dla danej klasy systemów. Termy i formuły, zasada

indukcji. (1 wykład)

Prawdziwość formuł w systemach - definicja Tarskiego. Teorie i

modele. (2 wykłady)

Rachunek logiczny. Twierdzenie Goedla o pełności. Twierdzenie o

zwartości. (3 wykłady)

Funkcje Skolema i generowanie podmodeli. Realizacja typów - modele pierwsze i uniwersalne.

Kryterium Tarskiego-Vaughta elementarności podmodelu. (2

wykłady)

Ultraprodukt. Modele przeliczalnie nasycone. Modelowa zupełność dla ciał

uporządkowanych domkniętych (przy założeniu hipotezy

continuum). (2 wykłady)

Twierdzenie Tarskiego o eliminacji kwantyfikatorów dla ciał uporządkowanych

domkniętych (w sensie rzeczywistym). (1 wykład)

Literatura:

Z. Adamowicz, P. Zbierski, Logika matematyczna, PWN, Warszawa 1991.

J. Barwise, ed., Handbook of Mathematical Logic, North-Holland, Amsterdam 1978.

J.L. Bell, A.B. Slomson, Models and Ultraproducts: An Introduction, North-Holland, Amsterdam 1986.

R.C. Lyndon, O logice matematycznej, PWN, Warszawa 1978.

Efekty uczenia się:

Student:

1. zna podstawowe pojęcia związane ze składnią i semantyką logiki zdań. Zna twierdzenie o zwartości dla logiki zdań i potrafi podać przykład jego zastosowania. Potrafi udowodnić, że każda formuła jest logicznie równoważna formule w postaci koniunkcyjno-alternatywnej i alternatywno-koniunkcyjnej, a także znajdować postaci normalne dla zadanych formuł. Zna przynajmniej jeden przykład systemu dowodowego dla rachunku zdań i twierdzenie o pełności dla tego systemu;

2. zna definicję struktury relacyjnej (systemu relacyjnego) i definicje podstawowych operacji na strukturach relacyjnych. Umie zilustrować te definicje przykładami. Zna podstawowe pojęcia i twierdzenia teorii algebr Boole'a, w tym pojęcia filtru i ultrafiltru oraz twierdzenie Stone'a o reprezentacji algebr Boole'a jako ciał zbiorów;

3. zna podstawowe pojęcia związane ze składnią i semantyką logiki pierwszego rzędu, w tym pojęcia spełniania i prawdy. Rozumie, jakie klasy formuł zachowują wartość logiczną przy poszczególnych operacjach na strukturach. Zna typowe przykłady tautologii w logice pierwszego rzędu oraz twierdzenie o preneksowej postaci normalnej. Umie sprowadzać proste formuły do preneksowej postaci normalnej;

4. rozumie pojęcie definiowalnej (skończenie aksjomatyzowalnej) i aksjomatyzowalnej klasy struktur. Potrafi konstruować zdania mające określoną wartość logiczną w danych strukturach oraz zdania bądź zbiory zdań aksjomatyzujące określone klasy struktur. Zna pojęcie zbioru definiowalnego i potrafi konstruować formuły definiujące określone zbiory w danych strukturach. Potrafi dowodzić niedefiniowalności zbiorów za pomocą automorfizmów;

5. zna twierdzenie o zwartości dla logiki pierwszego rzędu;

6. zna pojęcie ultraproduktu, przykłady ultraproduktów i twierdzenie Łosia o spełnianiu w ultraproduktach;

7. Potrafi dowodzić nieaksjomatyzowalności klas struktur za pomocą twierdzenia o zwartości bądź twierdzenia Łosia. Zna twierdzenie Frayne'a, Morela i Scotta charakteryzujące klasy aksjomatyzowalne;

8. zna przykład systemu dowodowego dla logiki pierwszego rzędu i twierdzenie o pełności dla tego systemu;

9. zna pojęcie podstruktury elementarnej i twierdzenia Skolema-Löwenheima. Potrafi używać twierdzeń Skolema-Löwenheima do konstruowania struktur o zadanej z góry mocy i określonych własnościach logicznych.

Metody i kryteria oceniania:

1. Do egzaminu w pierwszym terminie dopuszczone zostaną osoby, które uzyskają co najmniej 50% punktów z zadań domowych.

2. Egzaminy odbywające się w sesji będą się składały z części pisemnej, obejmującej teorię i zadania (dla wszystkich) oraz ustnej (patrz p. 3).

3. W szczególnych wypadkach wykładowca może zaproponować studentowi egzamin ustny, którego wynik może zmienić ocenę wynikającą z egzaminu pisemnego. Na dopuszczenie do egzaminu ustnego wpływ ma liczba punktów z zadań domowych oraz opinia z ćwiczeń. Liczba zaproszeń na egzamin ustny może istotnie wzrosnąć, jeśli egzamin pisemny będzie zdalny.

4. O egzamin w terminie zerowym mogą się ubiegać osoby, które w ocenie prowadzących zajęcia mieszczą się (pod względem punktów za zadania domowe, aktywności na ćwiczeniach, ew. aktywności na wykładzie) wśród czołowych 10% uczestników kursu. O możliwość przystąpienia do egzaminu zerowego można się starać począwszy od 15 stycznia 2024 r. Egzamin zerowy będzie wyłącznie ustny i będzie sprawdzał zarówno umiejętność rozwiązywania zadań, jak i znajomość teorii.

5. Ocena z przedmiotu wystawiana jest wyłącznie na podstawie egzaminu.

6. W związku z zaleceniem Dziekana Wydziału MIiM, dotyczącym częstego wietrzenia sal, wykłady (dwa razy po 45 minut z piętnastominutową przerwą) w miarę możliwości będą się odbywać przy otwartych oknach. Proszę wszystkich, żeby w związku z tym mieli ze sobą ciepłe swetry lub inne okrycia.

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Piotr Zakrzewski
Prowadzący grup: Leszek Kołodziejczyk, Piotr Zakrzewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-80474ed05 (2024-03-12)