Elementy Matematyki Dyskretnej

Wykład prowadzony jest wspólnie z drem Adamem Sędziwym.

Materiały wykładowe stanowią rozszerzone opracowanie trzech wykładów prof. Antoniego Ligęzy pt. Elementy logiki dla informatyków - wersja 2002 (dostępne dla kursantów).

Dostrzeżone błędy i nieścisłości proszę zgłaszać e-mailem podając nazwę przedmiotu, numer wykładu oraz numer strony/slajdu.

2004
  • Igor Ławrow Łarisa Maksimowa, Zadania z Teori Mnogości, Logiki Matematycznej i Teorii Algorytmów, 2004
  • Witold Lipski, Kombinatoryka dla programistów, 2004
2003
  • Charles R.B. Wright Kenneth A. Ross, Matematyka dyskretna, 2003
2002
  • Janusz Onyszkiewicz Wiktor Marek, Elementy logiki i teorii mnogości w zadaniach, 2002
2001
  • Roman Murawski, Filozofia Matematyki - Zarys Dziejów, 2001
1998
  • Helena Rasiowa, Wstęp do matematyki współczesnej, 1998
1994
  • Marek Skomorowski, Wstęp do projektowania układów cyfrowych, 1994
1991
  • Marek Wójcik, Zasada Rezolucji - Metoda automatycznego

dowodzenia twierdzeń, 1991

1986
  • Norman L. Biggs, Discrete mathematics, 1986

Wykład I: Algebra zbiorów

  • pojęcie zbioru
  • definiowanie zbiorów
  • operacje algebry zbiorów
  • wybrane zbiory liczbowe
  • prawa algebry zbiorów
  • zbiory z powtórzeniami

Wykład II: Relacje

  • relacje dwuargumentowe
  • projekcja i rozszerzenie cylindryczne
  • obcięcie, dopełnienie, domknięcie
  • obraz zbioru i złożenie relacji
  • własności relacji dwuargumentowych
  • relacje równoważności i klasy równoważności
    • twierdzenie o podziale zbioru na klasy abstrakcji

Wykład III: Funkcje

  • funkcja i relacja
  • iniekcja, suriekcja i bijekcja
    • twierdzenie o funkcji równocześnie iniektywnej i bijektywnej
  • funkcja charakterystyczna
  • funkcja odwracalna
    • twierdzenie o funkcji odwracalnej

Wykład IV: Liczność zbiorów

  • moc zbioru, liczby kardynalne
  • zbiory równoliczne, zbiory przeliczalne i conajwyżej przeliczalne
  • zbiory skończone
  • Paradoks Hilberta
  • przykłady zbiorów różnej mocy
  • twierdzenie Cantora_Bernsteina dla liczb kardynalnych
  • twierdzenie „„przekątniowe”” Cantora
  • twierdzenie Cantora „„O mocy zbioru potęgowego””
  • hipoteza continuum

Wykład V: Relacje częściowego porządku

  • element najmniejszy, największy, minimalny, maksymalny
  • diagramy Hassego
  • quasi-porządki
  • porządek liniowy, łańcuch
  • pewne szczególne porządki
    • porządek produktowy
    • porządek leksykograficzny
  • elementy teorii krat

Wykład VI: Wprowadzenie do logiki matematycznej

  • wnioskowanie logiczne
  • spójniki i formuły logiczne
  • semantyka rachunku zdań
  • tabele wartości logicznych
  • ważniejsze prawa logiki rachunku zdań
  • postać koniunktywna i dysjunktywna formuły logicznej
  • związki pomiędzy zdaniami logicznymi
  • „„metoda zerojedynkowa””
  • ważniejsze reguły wnioskowania
  • rodzaje formuł logicznych
  • twierdzenia o dedukcji

Wykład VII: Algebra Boole'a

  • sprowadzanie formuł do postaci normalnych
  • algebra Boole'a
    • aksjomatyka
  • funkcje Booleowskie
  • wyrażenia Booleowskie
  • bramki i układy logiczne
    • analiza układów logicznych
    • synteza układów logicznych
  • minimalizacja wyrażeń logicznych
    • reguły: „„sklejania”” i „„pochłaniania””
    • metody:
      • tablic Karnaugha
      • metoda implikantów (Quine'a - McCluskey'a)

Wykład VIII: Rachunek predykatów pierwszego rzędu

  • alfabet, zbiór termów, zmienne wolne i związane
  • formuła, zbiór formuł, interpretacja formuły, wartość formuły, własności formuł
  • przykład
  • zależności logiczne w rachunku predykatów
  • twierdzenie „„Churcha””