Podstawy logiki i teorii mnogości 3800-AIK-PLTM
Celem kursu jest zapoznanie studentów z podstawowymi narzędziami logicznymi i teoriomnogościowymi wykorzystywanymi w analizie formalnej, modelowaniu i reprezentowaniu wiedzy, wnioskowaniu automatycznym oraz podstawach metod sztucznej inteligencji. Student zdobywa umiejętność analizowania zagadnień za pomocą metod klasycznego rachunku zdań i logiki pierwszego rzędu, a także posługiwania się podstawowymi pojęciami teorii mnogości, które stanowią fundament współczesnej informatyki teoretycznej, baz danych i kognitywistyki.
Kurs łączy część teoretyczną z praktyką stosowania metod dowodzenia i narzędzi wykorzystywanych we współczesnej logice obliczeniowej i systemach AI..
Szczegółowe zagadnienia
Klasyczny rachunek zdań: język; semantyka (tabele prawdziwościowe, tautologie, wynikanie logiczne); normalne postaci formuł (CNF/DNF i ich znaczenie dla algorytmów SAT); metody dowodzenia (dedukcja naturalna, tabele semantyczne), rezolucja i jej rola w algorytmach automatycznego wnioskowania.
Logika pierwszego rzędu: język (zmienne, symbole pozalogiczne, kwantyfikatory); semantyka (modele, relacja spełniania i prawdziwość, spełnialność formuł); metody dowodzenia (tablice semantyczne); elementy teorii modeli; elementy metalogiki (poprawność i pełność, rozstrzygalność, twierdzenia limitacyjne); zastosowania logiki pierwszego rzędu w systemach AI i reprezentacji wiedzy
Podstawy teorii mnogości: pojęcie zbioru i elementu, relacja zawierania; operacje na zbiorach; funkcje i relacje; relacje równoważności i klasy abstrakcji; równoliczność zbiorów i podstawy teorii Cantora; relacje porządkujące; zastosowania teorii zbiorów w informatyce i kognitywistyce.
Koordynatorzy przedmiotu
Efekty kształcenia
Nabyta wiedza:
Student:
- zna podstawowe pojęcia klasycznego rachunku zdań i logiki pierwszego rzędu: składnia, semantyka, dowód;
- zna metody dowodzenia, w tym metody tablic semantycznych, oraz zna ich podstawowe własności i ograniczenia;
- zna podstawowe pojęcia teorii mnogości: zbiór i operacje na zbiorach, relacje, funkcje, równoliczność zbiórów, klasa abstrakcji, porządki;
- rozumie rolę logiki i teorii mnogości w reprezentacji wiedzy, systemach wnioskowania i podstawach AI.
K_W09, K_W02, K_W06, K_W21
Nabyte umiejętności:
Student:
- potrafi reprezentować proste problemy w języku rachunku zdań i logiki pierwszego rzędu;
- umie stosować metody tablic semantycznych do rozstrzygania spełnialności formuł;
- potrafi pracować ze zbiorami, funkcjami i relacjami w zadaniach informatycznych i kognitywistycznych;
- umie wykorzystać narzędzia logiczne do analizy prostych algorytmów i modeli poznawczych.
K_U02, K_U03, K_U07, K_U24, K_U25
Nabyte kompetencje społeczne:
Student:
- rozumie znaczenie precyzji argumentacji i formalnego rozumowania w pracy w AI i kognitywistyce;
- potrafi krytycznie analizować poprawność rozumowań w tekstach naukowych i w języku naturalnym.
K_K01, K_K02, K_K06
Kryteria oceniania
Wykład: egzamin pisemny (w postaci testu) weryfikujący znajomość i rozumienie podstawowych pojęć, twierdzeń i metod omówionych na wykładzie; warunkiem formalnym przystąpienia do egzaminu jest zaliczenie ćwiczeń.
Ćwiczenia: kolokwium z zadaniami.
Dopuszczalna liczba nieobecności podlegających usprawiedliwieniu: 3
Literatura
Ben-Ari M., Logika matematyczna w informatyce, Wydawnictwa Naukowo-Techniczne, 2005
Guzicki W., Zakrzewski P., Wykłady ze wstępu do matematyki. Wprowadzenie do teorii mnogości, PWN Warszawa 2005.
Ławrow I. A., Maksimowa Ł. L., Zadania z teorii mnogości, logiki matematycznej i teorii algorytmów, PWN Warszawa 2004.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: