Elementy Matematyki Dyskretnej
Informacje
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.
Bibliografia
Publications
2004
- Witold Lipski, Kombinatoryka dla programistów, 2004
- Igor Ławrow Łarisa Maksimowa, Zadania z Teori Mnogości, Logiki Matematycznej i Teorii Algorytmó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
Plan wykładów
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””