Logika i teoria mnogości II

obowiązkowe

Zaliczenie przedmiotu „Logika i teoria mnogości I”

Przedmiot stanowi kontynuację zajęć „Logika i teoria mnogości I”. Celem zajęć jest zapoznanie studentów z pojęciami i technikami teorii mnogości oraz bardziej zaawansowanymi zagadnieniami z logiki pierwszego rzędu.

1. ZBIORY I PODSTAWOWE OPERACJE NA ZBIORACH

Zagadnienia: Co to jest zbiór?; relacja należenia, równość zbiorów; metody konstrukcji zbiorów (z danych elementów, definiowanie przez wyróżnianie); zbiór pusty, zawieranie zbiorów; zbiór potęgowy, suma i iloczyn zbiorów, suma i iloczyn rodziny zbiorów, różnica zbiorów, dopełnienie zbiorów, iloczyn kartezjański dwóch zbiorów, podstawowe prawa rachunku zbiorów

2. FUNKCJE

Zagadnienia: pojęcie funkcji, dziedzina, przeciwdziedzina, funkcje „na”, funkcje różnowartościowe, funkcje wzajemnie jednoznaczne, funkcja odwrotna, funkcja identycznościowa, obraz, przeciwobraz zbioru; definiowanie funkcji wzorami jawnymi, definiowanie przez indukcję, funkcje wyboru

3. INDEKSOWANE RODZINY ZBIORÓW

Zagadnienia: indeksowane rodziny zbiorów, suma i iloczyn indeksowanych rodzin zbiorów, funkcje wielu zmiennych, podwójnie indeksowane rodziny zbiorów, uogólniony iloczyn kartezjański, uogólnione prawa rozdzielności

4. ZBIORY RÓWNOLICZNE I NIERÓWNOLICZNE

Zagadnienia: zbiory równoliczne, zbiory nierównoliczne, metoda przekątniowa i Twierdzenie Cantora, porównywanie mocy zbiorów, zbiory skończone i nieskończone, zbiory przeliczalne i nieprzeliczalne, zbiory mocy continuum, hipoteza continuum

5. RELACJE: PODSTAWOWE WŁASNOŚCI

Zagadnienia: pojęcie relacji; dziedzina i pole relacji; złożenie relacji; własności relacji dwuargumentowych; relacje równoważności; podziały zbioru; zbiór ilorazowy

6. RELACJE PORZĄDKU

Zagadnienia: częściowe porządki, liniowe porządki, elementy wyróżnione, porządki gęste, ciągłe i dobre, leksykograficzne, izomorfizmy

7. LOGIKA 1-GO RZĘDU: SIŁA WYRAZU I ELEMENTY METALOGIKI

Zagadnienia: twierdzenie o zwartości, twierdzenie Skolema-Lowenheima, twierdzenia Godla o niezupełności, wyrażalność w logice 1-go rzędu, nierozstrzygalność, problem spectrum, gry Ehrenfeuchta

8. ZMIANA LOGIKI

Zagadnienia: logiki wyższych rzędów, rozstrzygalne fragmenty logiki 1-go rzędu, logiki nieklasyczne

Adamowicz Z., Zbierski P., Logika matematyczna, PWN, Warszawa 1991.

Guzicki W., Zakrzewski P., Wykłady ze wstępu do matematyki. Wprowadzenie do teorii mnogości, PWN Warszawa 2005.

Lyndon R. C., O logice matematycznej, PWN, Warszawa 1978.

Ławrow I. A., Maksimowa Ł. L., Zadania z teorii mnogości, logiki matematycznej i teorii algorytmów, PWN Warszawa 2004.

Marek W., Onyszkiewicz J., Elementy logiki i teorii mnogości w zadaniach, PWN Warszawa 2000.

Nabyta wiedza:

Student zna:

- pojęcie uogólnionej sumy i iloczynu zbiorów, iloczynu kartezjańskiego.

- pojęcie indeksowanej rodziny zbiorów i operacji na rodzinach zbiorów.

- pojęcie równoliczności zbiorów, wie, czym jest zbiór przeliczalny, nieprzeliczalny.

- pojęcie funkcji, porządku częściowego oraz zagadnień pokrewnych.

- podstawowe pojęcia związane ze składnią i semantyką logiki 1-go rzędu, w tym pojęcia spełniania i prawdy; zna typowe przykłady tautologii w logice pierwszego rzędu.

- przynajmniej jeden przykład systemu dedukcyjnego dla logiki 1-go rzędu i twierdzenie o pełności dla tego systemu.

- podstawowe twierdzenia metalogiczne dla logiki klasycznej.

K_W04, K_W10, K_W27, K_W36, K_W42

Nabyte umiejętności:

Student potrafi:

- prowadzić analizę dotyczącą uogólnionych operacji teoriomnogościowych.

- wykazać równoliczność zbiorów, przeliczalność bądź nieprzeliczalność zbiorów na wybranych przykładach.

- sprawdzać podstawowe własności funkcji.

- opisać własności zbiorów uporządkowanych.

- sprawdzać spełnialność i prawdziwość formuł logiki 1-go rzędu; potrafi przedstawić dowód formuły 1-go rzędu w wybranym systemie dedukcyjnym.

- definiować proste własności za pomocą formuł logiki 1-go rzędu.

K_U04, K_U09, K_U14, K_U26, K_U35

Nabyte kompetencje społeczne:

- Umie selekcjonować i porządkować informacje uzyskane w procesie komunikacji.

- Potrafi śledzić tok myślenia innych osób.

- Umie uważnie słuchać innych.

K_K01

a) Metody weryfikacji efektów uczenia się: egzamin pisemny (w postaci testu) weryfikujący znajomość i rozumienie podstawowych pojęć i twierdzeń omówionych na wykładzie

b) Składowe oceny końcowej i ich waga:

Wykład: ocena z egzaminu w formie pisemnego testu 100%

ćwiczenia: aktywność i prace domowe 20%, średnia ocen z kolokwiów 80%

c) Warunki przystąpienia do egzaminu: zaliczenie ćwiczeń

d) W wypadku egzaminu – czy przystąpienie do egzaminu w terminie zerowym powoduje utratę prawa do przystąpienia do egzaminy w głównej sesji egzaminacyjnej:

Przystąpienie do egzaminu w terminie zerowym NIE powoduje utraty prawa do przystąpienia do egzaminy w głównej sesji egzaminacyjnej

e) Semestralna liczba dopuszczalnych nieobecności zajęciach oraz w wypadkach, których to dotyczy, sposoby ich zaliczania: 3 (wykład)

f) Skala ocen: Skala ocen z egzaminu pisemnego (wykład): 5! – 85% pkt., 5 (bdb.) – od 80%, 4+ (db. plus) – od 75%, 4 (db.) – od 70%, 3+ (dst. plus) - od 60%, 3 – (dst.) od 45%, 2 – (ndst.) mniej niż 45%)

g) Warunki dopuszczenia do poprawy: Student ma prawo poprawić wynik z egzaminu pisemnego pod warunkiem, że z egzaminu pisemnego uzyskał ocenę co najmniej 3+, a z ćwiczeń ocenę co najmniej 4.