MIMINF:Podstawy matematyki

From Studia Informatyczne

Spis treści

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.