MIMINF:Podstawy matematyki

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Najważniejsze pojęcia i metody teorii mnogości i logiki. Wykształcenie umiejętności posługiwania się abstrakcyjnym aparatem matematycznym i dowodzenia twierdzeń.

Sylabus

Autorzy

• Sławomir Lasota — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

Wymagania wstępne

• Znajomość matematyki na poziomie szkoły średniej

Zawartość

• Rachunek zdań i jego wlasności. Wprowadzenie do rachunku kwantyfikatorów.
• Operacje na zbiorach, w tym działania nieskończone.
• Relacje i funkcje oraz ich podstawowe własności.
• Relacja równoważności, zasada abstrakcji.
• Zasada indukcji.
• Równoliczność. Zbiory skończone i nieskończone, przeliczalne i nieprzeliczalne.
• Twierdzenie Cantora i twierdzenie Cantora-Bernsteina.
• Porządki częściowe i liniowe. Zastosowania lematu Kuratowskiego-Zorna.
• Kresy i twierdzenia o punktach stałych. Przykład zastosowania w semantyce programów.
• Porządki dobre i dobrze ufundowane. Indukcja strukturalna.
• Pojęcie dowodu formalnego. Systemy dowodzenia dla rachunku zdań, twierdzenie o pełności.
• Struktury relacyjne. Język pierwszego rzędu: semantyka, twierdzenie o pełności.

Literatura

1. K. Kuratowski, A. Mostowski, Teoria mnogości, Państwowe Wydawnictwo Naukowe, Warszawa 1978.
2. W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogosci w zadaniach, Wydawnictwo Naukowe PWN, Warszawa 1996.
3. H. Rasiowa, Wstęp do matematyki, Państwowe Wydawnictwo Naukowe, Warszawa 1971, 1984, 1998.
4. J. Tiuryn, Wstęp do teorii mnogości i logiki, skrypt UW.