Logika dla informatyków: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 79: | Linia 79: | ||
# [[Logika dla informatyków/Język logiki pierwszego rzędu|Język logiki pierwszego rzędu]] ([[Logika dla informatyków/Ćwiczenia 2|Ćwiczenia]]) TR | # [[Logika dla informatyków/Język logiki pierwszego rzędu|Język logiki pierwszego rzędu]] ([[Logika dla informatyków/Ćwiczenia 2|Ćwiczenia]]) TR | ||
# [[Logika dla informatyków/Logika pierwszego rzędu. Sposób użycia|Logika pierwszego rzędu. Sposób użycia]] ([[Logika dla informatyków/Ćwiczenia 3|Ćwiczenia]]) TR | # [[Logika dla informatyków/Logika pierwszego rzędu. Sposób użycia|Logika pierwszego rzędu. Sposób użycia]] ([[Logika dla informatyków/Ćwiczenia 3|Ćwiczenia]]) TR | ||
# [[Logika dla informatyków/Ograniczenia logiki pierwszego rzędu|Ograniczenia logiki pierwszego rzędu]] ([[Logika dla informatyków/Ćwiczenia 4|Ćwiczenia]]) | # [[Logika dla informatyków/Ograniczenia logiki pierwszego rzędu|Ograniczenia logiki pierwszego rzędu]] ([[Logika dla informatyków/Ćwiczenia 4|Ćwiczenia]])AS | ||
# [[Logika dla informatyków/Paradygmaty dowodzenia|Paradygmaty dowodzenia]] ([[Logika dla informatyków/Ćwiczenia 5|Ćwiczenia]]) | # [[Logika dla informatyków/Paradygmaty dowodzenia|Paradygmaty dowodzenia]] ([[Logika dla informatyków/Ćwiczenia 5|Ćwiczenia]]) | ||
# [[Logika dla informatyków/Pełność rachunku zdań|Pełność rachunku zdań]] ([[Logika dla informatyków/Ćwiczenia 6|Ćwiczenia]]) | # [[Logika dla informatyków/Pełność rachunku zdań|Pełność rachunku zdań]] ([[Logika dla informatyków/Ćwiczenia 6|Ćwiczenia]])AS | ||
# [[Logika dla informatyków/Pełność rachunku predykatów|Pełność rachunku predykatów]] ([[Logika dla informatyków/Ćwiczenia 7|Ćwiczenia]]) | # [[Logika dla informatyków/Pełność rachunku predykatów|Pełność rachunku predykatów]] ([[Logika dla informatyków/Ćwiczenia 7|Ćwiczenia]])AS | ||
# [[Logika dla informatyków/Teoria modeli|Teoria modeli]] ([[Logika dla informatyków/Ćwiczenia 8|Ćwiczenia]]) TR | # [[Logika dla informatyków/Teoria modeli|Teoria modeli]] ([[Logika dla informatyków/Ćwiczenia 8|Ćwiczenia]]) TR | ||
# [[Logika dla informatyków/Arytmentyka pierwszego rzędu|Arytmetyka pierwszego rzędu]] ([[Logika dla informatyków/Ćwiczenia 9|Ćwiczenia]]) TR | # [[Logika dla informatyków/Arytmentyka pierwszego rzędu|Arytmetyka pierwszego rzędu]] ([[Logika dla informatyków/Ćwiczenia 9|Ćwiczenia]]) TR | ||
| Linia 88: | Linia 88: | ||
# [[Logika dla informatyków/Logika intuicjonistyczna|Logika intuicjonistyczna]] ([[Logika dla informatyków/Ćwiczenia 11|Ćwiczenia]]) | # [[Logika dla informatyków/Logika intuicjonistyczna|Logika intuicjonistyczna]] ([[Logika dla informatyków/Ćwiczenia 11|Ćwiczenia]]) | ||
# [[Logika dla informatyków/Logika drugiego rzędu|Logika drugiego rzędu]] ([[Logika dla informatyków/Ćwiczenia 12|Ćwiczenia]]) | # [[Logika dla informatyków/Logika drugiego rzędu|Logika drugiego rzędu]] ([[Logika dla informatyków/Ćwiczenia 12|Ćwiczenia]]) | ||
# [[Logika dla informatyków/Logika w informatyce|Logika w informatyce]] ([[Logika dla informatyków/Ćwiczenia 13|Ćwiczenia]]) | # [[Logika dla informatyków/Logika w informatyce|Logika w informatyce]] ([[Logika dla informatyków/Ćwiczenia 13|Ćwiczenia]])AS | ||
Wersja z 12:01, 20 wrz 2006
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Zastosowanie metod i narzędzi logiki matematycznej w informatyce.
Sylabus
Autorzy
- Jerzy Tiuryn
- Jerzy Tyszkiewicz
- Paweł Urzyczyn
Wymagania wstępne
- Logika i teoria mnogości
- Automaty i obliczenia
- Matematyka dyskretna
- Bazy danych
- Programowanie funkcyjne
- Złożoność obliczeniowa
Zawartość
- Rachunek zdań.
- Składnia formuł i semantyka zerojedynkowa.
- Wzajemna wyrażalność spójników, funkcjonalna zupełność.
- Postać normalna formuły tautologii.
- Siła wyrazu logiki zdaniowej.
- Logika pierwszego rzędu - cz.1: definicje
- Formuły, zmienne wolne i związane.
- Spełnianie formul w strukturach relacyjnych, pojecie tautologii wynikania semantycznego.
- Podstawienie i jego sens semantyczny.
- Logika pierwszego rzędu - cz. 2: sposób użycia
- Dyskusja ważnych tautologii logiki pierwszego rzędu.
- Preneksowa postać normalna i jej zastosowania
- Logika formalna a zdania języka naturalnego.
- Logika pierwszego rzędu - cz. 3: ograniczenia
- Nierozstrzygalność logiki pierwszego rzędu.
- Elementarna równoważność struktur.
- Gry Ehrenfeuchta-Fraissego.
- Paradygmaty dowodzenia:
- styl Hilberta
- naturalna dedukcja,
- rachunek sekwentów.
- Twierdzenie o pełności dla rachunku zdań.
- Twierdzenie o pełności dla rachunku predykatów.
- Teoria modeli
- Twierdzenie o zwartości i zastosowania
- Twierdzenie Skolema-Lowenheima, niestandardowy model arytmetyki.
- Arytmetyka i tw. o niezupełności Goedla.
- Logiki programów
- Składnia PDL
- Twierdzenie o małym modelu dla PDL
- Twierdzenie o pełności dla PDL
- Logika intuicjonistyczna
- Konstruktywna interpretacja spójników
- Semantyka w zbiorach otwartych (bez dowodu).
- Formuły-typy, normalizacja dowodów jako proces obliczenia.
- Logika 2 rzędu
- Definicja, podstawowe własności.
- Równoważność monadycznej logiki drugiego rzędu i automatów skończonych na słowach
- Informacja o tw. Fagina i Stockmeyera
- Informacja o tw. Rabina
- Logika w informatyce
- Logiki wielowartościowe
- Tw. Codda
- Rozstrzygalnośc teorii logicznych
Moduły
Wykład z logiki w formacie PDF
- Rachunek zdań (Ćwiczenia)
- Język logiki pierwszego rzędu (Ćwiczenia) TR
- Logika pierwszego rzędu. Sposób użycia (Ćwiczenia) TR
- Ograniczenia logiki pierwszego rzędu (Ćwiczenia)AS
- Paradygmaty dowodzenia (Ćwiczenia)
- Pełność rachunku zdań (Ćwiczenia)AS
- Pełność rachunku predykatów (Ćwiczenia)AS
- Teoria modeli (Ćwiczenia) TR
- Arytmetyka pierwszego rzędu (Ćwiczenia) TR
- Zdaniowa logika dynamiczna (Ćwiczenia)
- Logika intuicjonistyczna (Ćwiczenia)
- Logika drugiego rzędu (Ćwiczenia)
- Logika w informatyce (Ćwiczenia)AS
