Na seminarium czytać będziemy prace dotyczące rozstrzygalności i złożoności problemów spełnialności (czy dana formuła ma model), skończonej spełnialności (czy dana formuła ma model skończony) oraz związanych z nimi problemów odpowiadania na zapytania do baz danych/baz wiedzy (dla danej bazy D, teorii logicznej T i zapytania q, czy prawdą jest, że każdy model/skończony model D i T spełnia q?)
Interesować nas będą fragmenty logiki pierwszego rzędu (two-variable fragment, guarded fragment, unary negation fragment, guarded negation fragment, …) oraz logiki deskrypcyjne.
Materiał będzie się częściowo pokrywał z materiałem przedmiotu Problemy Decyzyjne w Logice, ale będzie też sporo innych rzeczy i osoby, które ten przedmiot zaliczyły mogą śmiało zapisać się na seminarium.
Niewykluczone, że spotkamy się z pewnymi problemami otwartymi, które będzie można próbować rozwiązać.
- Nauczyciel: Emanuel Kieroński