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.

Publications

2004

2003

2002

2001

1998

1994

1991

1986

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

• 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

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

• 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

• 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

• 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

• 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)

• 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””