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

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