Nazwa przedmiotu:
Elementy logiki i teorii mnogości
Koordynator przedmiotu:
Dr hab. Michał Ziembowski, prof. PW
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0003
Semestr nominalny:
1 / rok ak. 2016/2017
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
brak
Limit liczby studentów:
Ćwiczenia – 30 os. /grupa
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z podstawowymi pojęciami z logiki (na poziomie rachunku zdań i kwantyfikatorów) i „naiwnej” teorii mnogości (na poziomie rachunku zbiorów, relacji i funkcji ze szczególnym uwzględnieniem relacji równoważności i relacji porządkujących) oraz nabycie przez nich umiejętności operowania tymi pojęciami. Ponadto studenci otrzymają informację o relacji równoliczności (ze szczególnym uwzględnieniem przeliczalności) i liczbach kardynalnych. Po ukończeniu kursu studenci powinni rozpoznawać tautologie logiczne, równości i inkluzje między zbiorami, podstawowe pojęcia oraz posiadać umiejętność: - przekształcania formuł rachunku zdań i kwantyfikatorów oraz rozpoznawania tautologii logicznej, - zapisywania złożonych pojęć matematycznych przy pomocy pojęć elementarnych i języka logiki, - weryfikowania równości i inkluzji między zbiorami, - budowania relacji równoważności i wyznaczania ich klas abstrakcji, - definiowania różnymi metodami funkcji oraz operowania pojęciem obrazu i przeciwobrazu, - rysowania diagramów relacji ze szczególnym uwzględnieniem relacji porządkujących i rozpoznawania elementów ekstremalnych w zbiorach uporządkowanych, - odróżniania zbiorów przeliczalnych od nieprzeliczalnych.
Treści kształcenia:
Język matematyki. Symbolika logiczna. Zmienne wolne i związane. Rachunek zdań. Pojęcie zdania. Wartość logiczna zdania. Tautologie rachunku zdań. Dowody formalne i aksjomaty rachunku zdań. Rachunek predykatów. Wyrażanie różnych pojęć w ustalonym języku. Tautologie rachunku predykatów. Kwantyfikatory ograniczone. Operator abstrakcji. Antynomia Russela. Indukcja matematyczna. Zbiory. Relacje między zbiorami i działania na zbiorach (suma, przecięcie, różnica, dopełnienie). Prawa rachunku zbiorów. Iloczyn kartezjański. Relacje. Podstawowe kategorie relacji. Dziedzina, przeciwdziedzina. Operacje na relacjach, Diagram relacji Funkcje Operacje na funkcjach. Obraz, przeciwobraz. Indeksowane rodziny zbiorów i operacje na nich. Suma i przecięcie rodziny zbiorów. Własności tych operacji. Relacje równoważności. Przykłady w różnych dziedzinach matematyki. Klasy abstrakcji i ich własności. Podziały. Zbiory uporządkowane. Przykłady zbiorów uporządkowanych. Diagramy Hassego. Maksy- i minimalność, kresy. Kraty i algebry Boole’a. Liniowe porządki. Dobre porządki i twierdzenie o indukcji pozaskończonej. Równoliczność zbiorów. Własności. Zbiory przeliczalne i ich własności. Informacja o zbiorach nieprzeliczalnych Elementy logiki matematycznej. Pojęcie dowodu formalnego i teorii aksjomatycznej. Aksjomatyczny rachunek zdań.
Metody oceny:
Do zdobycia jest 100 pkt: 40 na ćwiczeniach, 60 na egzaminie (30 pkt - zadania, 20 pkt – test z teorii, 10 pkt – egzamin ustny z umiejętności referowania zadanego tematu). Stopień z przedmiotu ustala się wg następującej zasady: 51 - 60 pkt - dst, 61 - 70 pkt - dst plus, 71 - 80 pkt - db, 81 – 90 pkt - db plus, 91-100 pkt – bdb. Warunkiem koniecznym dopuszczenia do egzaminu jest uzyskanie na ćwiczeniach co najmniej 21 pkt. Punkty na ćwiczeniach pochodzą z dwóch kolokwiów i (ewentualnie - wg decyzji prowadzącego ćwiczenia) z oceny aktywności na zajęciach. Otrzymanie co najmniej 30 pkt z ćwiczeń zwalnia z części zadaniowej egzaminu. Dostaje się wówczas premię punktową w ilości x-10 pkt, gdzie x to ilość punktów zdobytych na ćwiczeniach. Z testu egzaminacyjnego można być zwolnionym po zaliczeniu dwóch repetytoriów (również w formie testów), które odbędą się w połowie i na koniec semestru. Punkty z testu na egzaminie są uznawane (i doliczane do innych wyników), je­śli jest ich co najmniej 5. Dopuszczenie do egzaminu jest ważne do końca b.r. ak., zwolnienia z egzaminu lub jego części – do końca lutego b.r.
Egzamin:
tak
Literatura:
1. W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach, PWN. 2. H. Rasiowa, Wstęp do matematyki współczesnej, PWN. 3. K. Kuratowski, Wstęp do teorii mnogości i topologii, PWN. 4. W. Guzicki, P. Zakrzewski, Wykłady ze wstępu do matematyki. 5. Wstęp do matematyki. Zbiór zadań, PWN 2005.
Witryna www przedmiotu:
e.mini.pw.edu.pl
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W01
Ma podstawową wiedzę z logiki obejmującą metody weryfikowania tautologii i budowania formuł złożonych z formuł elementarnych
Weryfikacja: 2 repetytoria i egzamin
Powiązane efekty kierunkowe: K_W01, K_W10
Powiązane efekty obszarowe: T1A_W01, T1A_W07
Efekt W02
Ma wiedzę ogólną w zakresie relacji i funkcji ze szcze­gól­nym uwzględnieniem relacji równoważności
Weryfikacja: 2 repetytoria i egzamin
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01
Efekt W03
Ma wiedzę ogólną w dziedzinie zbiorów uporządkowa­nych
Weryfikacja: 2 repetytoria i egzamin
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01
Efekt W04
Ma podstawową wiedzę o równoliczności i przeliczal­noś­ci zbiorów
Weryfikacja: 2 repetytoria i egzamin
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01

Profil ogólnoakademicki - umiejętności

Efekt U01
Potrafi wykorzystać nabytą wiedzę matematyczną do formułowania definicji i dowodzenia twierdzeń
Weryfikacja: 2 kolokwia
Powiązane efekty kierunkowe: K_U01, K_U03
Powiązane efekty obszarowe: T1A_U09, T1A_U09
Efekt U02
Potrafi pozyskiwać informacje z literatury, baz danych oraz innych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie
Weryfikacja: 2 kolokwia
Powiązane efekty kierunkowe: K_U05
Powiązane efekty obszarowe: T1A_U01