Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Logika matematyczna

Informacje ogólne

Kod przedmiotu: 1000-135LOM Kod Erasmus / ISCED: 11.113 / (0541) Matematyka
Nazwa przedmiotu: Logika matematyczna
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty fakultatywne dla studiów 2 stopnia na matematyce
Przedmioty fakultatywne na matematyce
Punkty ECTS i inne: 6.00
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 podziału. (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:

O ocenie decyduje wynik egzaminu.

--------------

Zasady oceniania w semestrze zimowym roku 2020/21:

O dopuszczeniu do egzaminu w I terminie decyduje prowadzący ćwiczenia na podstawie punktów za zadania domowe. Egzamin pisemny odbędzie się albo stacjonarnie, jeśli sytuacja epidemiologiczna na to pozwoli, albo za pomocą moodle'a. Pojedyncze osoby, w których przypadku wystawienie oceny na podstawie samego egzaminu pisemnego będzie trudne, mogą zostać zaproszone na egzamin ustny. Liczba zaproszeń na ustny może istotnie wzrosnąć, jeśli egzamin pisemny będzie zdalny.

Do egzaminu w II terminie dopuszczeni są wszyscy uczestnicy kursu. Poza tym egzamin w II terminie podlega tym samym zasadom co w I terminie.

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 2021 r. Egzamin zerowy będzie wyłącznie ustny i będzie sprawdzał zarówno umiejętność rozwiązywania zadań, jak i znajomość teorii.

Zajęcia w cyklu "Semestr zimowy 2020/21" (w trakcie)

Okres: 2020-10-01 - 2021-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Leszek Kołodziejczyk
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.