Informacje dla kandydatów

Logika i struktury formalne

Stacks Image 362
Wykład ten służy do precyzyjnego sformułowania podstawowych obiektów matematycznych, którymi posługujemy się w innych działach matematyki oraz w informatyce. Dowiesz się, na przykład, że funkcja jest pewną relacją, że relacja jest zbiorem par uporządkowanych a parę uporządkowaną można zdefiniować przy pomocą pary nieuporządkowanej ( wzór Kuratowskiego). Dowiesz się, że nie istnieje zbiór wszystkich zbiorów, oraz, że istnieje tylko jeden zbiór pusty. Na wykładzie tym zostaną wprowadzone pierwsze elementy matematyki dyskretnej: będziemy zajmowali się liczeniem mocy zbiorów skończonych, pojawi się taki wzór jak \(|A \cup B| = |A| + |B| - |A \cap B|\) oraz jego fajne uogólnienia.

W trakcie tego wykładu zapoznasz się z rachunkiem zdań, rachunkiem zbiorów, kwantyfikatorami, podstawowymi klasami relacji (częściowe porządki, relacje równoważności, kraty), różnymi wariantami indukcji matematycznej (zasada dobrego uporządkowania, zasada Dirichletta), elementami teorii mocy (zbiory przeliczalne, zbiory mocy continuum), systemami przepisującymi, elementami logik nieklasycznych ( LTL).

Duża część tego wykładu poświęcona będzie teorii mnogości. Teoria ta stanowi szkielet współczesnej matematyki. Jej twórcą jest George Cantor, którego podobizna znajduje się na tej stronie. Teoria mnogości powstała w XX wieku, na wykładzie tym spotykać się będziesz więc z elementami współczesnej matematyki.

Po omówieniu elementów teorii mocy będziesz wiedział, że tyle samo jest punktów na płaszczyźnie jak punktów na prostej. Dowiesz się również, że liczb naturalnych jest tyle samo co liczb wymiernych. Po wykładzie tym powinno być dla Ciebie oczywiste, że funkcji obliczalnych (czyli takich, które potrafimy oprogramować w dowolnym rozsądnym języku programowania) jest bardzo mało (dokładniej - przeliczalnie wiele), a więc, że istnieje bardzo dużo funkcji nieobliczalnych.

Wykład ten jest bardzo ważny dla informatyków. Dobre poznanie podstawowych tautologii rachunku zdań ułatwi ci pisanie poprawnych instrukcji warunkowych. Poznanie podstawowych własności kwantyfikatorów pozwoli ci na precyzyjne zapisywanie własności algorytmów. Logiki nieklasyczne służą, między innymi, do automatycznej weryfikacji poprawności algorytmów. Standardowe implementacje bazodanowego języka SQL posługują się pewną prostą nieklasyczną logiką.

Musisz uważać na tym wykładzie - większość materiału będzie dla ciebie nowa; nie było tego w szkole średniej. Spotkasz się na nim z wieloma łatwymi, lecz bardzo abstrakcyjnymi pojęciami. Będziesz potrzebował trochę czasu aby z każdym z nich się oswoić - trzeba więc będzie systematycznie pracować.

Dodatkowe materiały

Katedra Informatyki
Politechnika Wrocławska
Wydział Podstawowych Problemów Techniki