DI1204 - Podstawy teorii mnogości i matematyki dyskretnej

Nazwa w drugim języku: 

Foundations of set theory and discrete mathematics.

Przedmiot realizowany w planach wzorcowych:

• Informatyka Semestr: 2 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: 1

Obieralny dla katalogów:

Znalazłem 0 pozycji. (Pokaż szczegóły)

Skrócone treści: 

Podstawy logiki i rachunku funkcyjnego. Algebra zbiorów. Relacje równoważności i ich zastosowania. Wstęp do teorii mocy oraz zbiorów uporządkowanych. Wprowadzenie do matematyki dyskretnej: elementy kombinatoryki, funkcje całkowitoliczbowe, metoda zaburzeń, rachunek różnicowy, elementy teorii grafów.

Szczegółowe treści merytoryczne: 

1. RACHUNEK ZDAŃ.
    Funktory zdaniotwórcze. Tautologie. Reguły dowodzenia.
2. RACHUNEK FUNKCJI ZDANIOWYCH.
    Pojęcie funkcji zdaniowej. Kwantyfikatory. Zmienna wolna oraz zmienna związana
    kwantyfikatorem.Tautologie rachunku funkcyjnego, które nie są uogólnieniem tautologii
    rachunku zdań.
3. ALGEBRA ZBIORÓW.
    Podstawowe twierdzenia algebry zbiorów. Różnica symetryczna zbiorów. Dopełnienie
    zbioru. Ciało zbiorów. Pojęcie pary uporządkowanej. Iloczyn kartezjański zbiorów.
4. SUMY I ILOCZYNY UOGÓLNIONE ZBIORÓW.
5. AKSJOMATYCZNE UJĘCIE LICZB NATURALNYCH.
    Aksjomat indukcji zupełnej. Definicje indukcyjne. Podstawowe własności liczb natural-
     nych wyprowadzane przy pomocy aksjomatu indukcji zupełnej. Przykłady dowodów
     indukcyjnych.
6. RELACJE DWUCZŁONOWE. RELACJA RÓWNOWAŻNOŚCI.
    Funkcja jako relacja dwuczłonowa. Podstawowe typy relacji w X x X : zwrotna, symetrycz-
    na, przechodnia, itd. Relacja równoważności. Przestrzeń ilorazowa.
7. PRZYKŁADY RELACJI RÓWNOWAŻNOŚCI i odpowiadających im przestrzeni
    ilorazowych: ARYTMETYKA MODULARNA, konstrukcja zbioru liczb wymiernych oraz
    konstrukcja zbioru liczb rzeczywistych.
8. MOCE ZBIORÓW.
    Pojęcie i podstawowe własności równoliczności zbiorów. Aksjomat istnienia liczb kardy-
    nalnych. Zbiory przeliczalne. Zbiory mocy continuum. Twierdzenie Cantora-Bernsteina.
    Zbiór potęgowy. Twierdzenie Cantora.
9. ZBIORY UPORZĄDKOWANE.
    Relacje porządkujące. Elementy maksymalne i minimalne. Lemat Kuratowskiego-Zorna.
    Relacje liniowo porządkujące. Relacje dobrze porządkujące. Liczby porządkowe.
10. FUNKCJE CAŁKOWITOLICZBOWE.
    Funkcje sufitu i podłogi. Potęgi kroczące. Rozkład liczb naturalnych na czynniki pierwsze.
    Kongruencje liczbowe.
11. ELEMENTY KOMBINATORYKI.
    Zasada szufladkowa. Permutacje. Wariacje. Kombinacje. Zasada włączania i wyłączania.
    Podziały. Twierdzenie Halla.
12. METODY MATEMATYKI DYSKRETNEJ.
     Metoda zaburzeń. Rachunek różnicowy. Funkcje tworzące. Zastosowania funkcji tworzą-
     cych.
13. ELEMENTY TEORII GRAFÓW.
     Drogi, ścieżki, kontury. Ciągi graficzne. Drzewa. Dendryty. Charakterystyki liczbowe
     grafów prostych. Zliczanie drzew. Grafy dwudzielne. Kolorowalność. Grafy z wagami.
     Planarność.

Bibliografia: 

1. Rasiowa, H. : Wstęp do matematyki współczesnej. Wydawnictwo naukowe PWN,
    Warszawa (2005).
2. Krempa, J., Mażbic-Kulma, B. : Elementy logiki, teorii mnogości i algebry. Wydawnictwa
    Naukowo-Techniczne, Warszawa (1977).
3. Mostowski, A.W., Pawlak, Z. : Logika dla inżynierów ( Seria : Biblioteka Naukowa
    Inżyniera). Wydawnictwo naukowe PWN, Warszawa (1970).
4. Grygiel, J. : Wprowadzenie do matematyki dyskretnej. Akademicka Oficyna
    Wydawnicza EXIT, Warszawa (2007).
5. Wilson, R.J. : Wprowadzenie do teorii grafów. Wydawnictwo naukowe PWN,
    Warszawa (1998).

Kryteria oceny: 

-

Efekty kształcenia: 

Umiejętność posługiwania się poznanymi pojęciami.

Uwagi: 

Standardowe treści kształcenia ujęte w Rozporządzeniu MNiSW:

Informatyka Semestr: 2 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski

Przedmioty na których bazuje dany przedmiot (prerekwizyty):