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. Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
2. Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.